Datorikas fakultāte / Faculty of Computing

Permanent URI for this community

https://dspace-dev.lu.lv/handle/7/70

Browse

Browsing Datorikas fakultāte / Faculty of Computing by Subject "1-dimensiju dinamiskā programmēšana"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Kvantu vaicājumu sarežģītība dinamiskās programmēšanas problēmām
    (Latvijas Universitāte, 2022) Zvirbulis, Ansis; Ambainis, Andris; Latvijas Universitāte. Datorikas fakultāte
    Dinamiskā programmēšana (DP) ir plaši pētīta no klasiskās skaitļošanas puses, un jauni rezultāti tiek atrasti katru gadu. Taču no kvantu skaitļošanas puses tā ir pētīta daudz mazāk. Tāpēc tika izvēlētas un pētītas vairākas plaši pazīstamas 1-dimensiju DP problēmas, izmantojot kvantu vaicājumu modeli. Darbā tika aplūkotas mazākā svara apakš-sekvences (LWS) problēmas, kā, piemēram, kastu komplektēšanas (NestedBoxes) problēma, kā arī dažas saistītās problēmas. Darba mērķis bija atrast aplūkotajām LWS problēmām augšējo novērtējumu, kas labāks par triviālo O ̃(n^1.5 ) vai labu apakšējo novērtējumu. Izdevās atrast vairākus mazākus rezultātus NestedBoxes problēmai – kvantu apakšējo novērtējumu Ω(n√d), klasisku O ̃(n) algoritmu pie konstanta dimensiju skaita, kvantu O ̃(n^1.34 ) algoritmu 4-ķēdes meklēšanai. Kā arī dažus rezultātus saistīto problēmu speciālgadījumiem.
  • Thumbnail Image
    Item
    Kvantu vaicājumu sarežģītība dinamiskās programmēšanas problēmām
    (Latvijas Universitāte, 2022) Zvirbulis, Ansis; Ambainis, Andris; Latvijas Universitāte. Datorikas fakultāte
    Dinamiskā programmēšana (DP) ir plaši pētīta no klasiskās skaitļošanas puses, un jauni rezultāti tiek atrasti katru gadu. Taču no kvantu skaitļošanas puses tā ir pētīta daudz mazāk. Tāpēc tika izvēlētas un pētītas vairākas plaši pazīstamas 1-dimensiju DP problēmas, izmantojot kvantu vaicājumu modeli. Darbā tika aplūkotas mazākā svara apakš-sekvences (LWS) problēmas, kā, piemēram, kastu komplektēšanas (NestedBoxes) problēma, kā arī dažas saistītās problēmas. Darba mērķis bija atrast aplūkotajām LWS problēmām augšējo novērtējumu, kas labāks par triviālo O ̃(n^1.5 ) vai labu apakšējo novērtējumu. Izdevās atrast vairākus mazākus rezultātus NestedBoxes problēmai – kvantu apakšējo novērtējumu Ω(n√d), klasisku O ̃(n) algoritmu pie konstanta dimensiju skaita, kvantu O ̃(n^1.34 ) algoritmu 4-ķēdes meklēšanai. Kā arī dažus rezultātus saistīto problēmu speciālgadījumiem.