Search results for "sarežģītība"
showing 10 items of 11 documents
Precīzie kvantu algoritmi, izmantojot 1-kvantu-vaicājuma izsaukumus
2018
Darbā ir analizēti zināmi unikāli precīzie kvantu algoritmi, kuru īpašības ir atšķirīgas no citiem literatūrā atrodamiem algoritmiem, un uzsākts pētīt iespējas vispārināt šajos algoritmos esošos paņēmienus. Darbā ir noformulēts jauns skaitļošanas modelis, kas ir saistīts ar precīzo kvantu vaicājumu modeli. Veikti skaitliski aprēķini, lai palīdzētu saprast jaunā modeļa iespējas un ierobežojumus. Izteiktas hipotēzes un virzieni, kādos turpināt analīzi un pētījumu.
Algoritmu sarežģītības novērtējumi bumbas meklēšanas modelī
2015
Viena no aktuālākajām problēmām kvantu skaitļošanas nozarē ir kvantu datoru priekšrocību noteikšana salīdzinājumā ar klasiskajiem datoriem. Priekšrocības bieži tiek demonstrētas, pierādot kvantu algoritmu sarežģītības novērtējumu no augšas, kurš ir labāks par novērtējumu jebkuram klasiskajam algoritmam tādas pašas problēmas risināšanai. Darba mērķis ir izpētīt vairākas skaitļošanas problēmas nesen izgudrota „bumbas meklēšanas” skaitļošanas modeļa ietvaros, lai iegūtu tiem atbilstošu algoritmu kvantu vaicājumu sarežģītības novērtējumus, kuri ir potenciāli labāki par zināmajiem. Pētīto algoritmu starpā ir vairāki algoritmi uz simbolu virknēm, daži algoritmi uz grafiem, kā arī vairāku bitu bin…
Kvantu algoritmi bumbu meklēšanas modelī
2016
Viens no uzdevumiem, kurā kvantu datoriem ir priekšrocības, salīdzinot ar klasiskiem datoriem, ir vaicāšanas uzdevums. Šajā uzdevumā ir dota zināma funkcija f, nezināma bitu virkne x, un melnā kaste, ar kuras palīdzību var piekļūt x bitiem. Mērķis ir uzbūvēt f(x) rēķināšanas algoritmu, izmantojot mazu skaitu melnās kastes vaicājumu . Viens no modeļiem tādu algoritmu konstruēšanai ir bumbas meklēšanas modelis. Ar šo modeli ir iespējams iegūt kvantu algoritmus ar zemu vaicājumu skaitu dažiem vaicāšanas uzdevumiem. Šajā darbā šīs modelis ir pielietots dažādām funkcijām f ar mērķi izveidot algoritmus ar mazu vaicājumu skaitu. Iegūtie risinājumi tiek salīdzināti ar risinājumiem, kas izmanto cita…
Algoritmi un to vizualizācija
2021
Bakalaura darbā tika pētīts, kādām prasībām vajadzētu atbilst labam algoritmu vizualizācijas rīkam. Papildus tika pētīts kādi algoritmi tiek apskatīti Latvijas Universitātē bakalaura studiju programmā "Datorzinātnes" uz doto brīdi un šie algoritmi tika izstrādāti vizualizācijas rīkā, kura izstrādes laikā tika pielietotas mācību laikā iegūtās praktiskās zināšanas tīmekļa izstrādē. Algoritmu vizualizācijas rīks ir izveidots tiešsaistē tāpēc, lai tas būtu pieejams studentiem un pasniedzējiem visu diennakti bez nepieciešamības aizņemt papildus atmiņu ierīcēs. Šis rīks var būt noderīgs ikvienam, kas interesējas par algoritmiem, jo īpaši datorzinātņu studentiem, kuri vēlas uzlabot savus rezultātu…
Atbalsta bibliotēka Būla funkciju izpētei
2015
Būla funkcijas ir joprojām aktuāls pētījumu objekts. Tās izmanto sarežģītības teorijā, elektrisko slēgumu projektēšanā, kvantu kriptogrāfijā un citur. Šī darba mērķis ir izveidot pro-grammatūru vienkāršāko Būla funkciju raksturotāju noteikšanai: jūtīguma, bloku jūtīguma, pārstāvošo un tuvināto polinomu aprēķināšanai. Tās galvenais pielietojums varētu būt pielie-tošana projektā “Kvantu algoritmi” (angliski: QALGO: Quantum Algorithmics), kas pēta arī Būla funkcijas. Motivācija šādas programmas izstrādei nāk no pētnieku puses, kas ikdienā no-darbojas ar funkciju un algoritmu sarežģītības pētīšanu, kā procesā ir nepieciešams veikt atse-višķu raksturotāju noteikšanu pastarpinātiem algoritmiem va…
Jaunas sakarības starp Būla funkciju jutīgumu un bloku jutīgumu
2015
Darbā tiek pētīta neatrisināta problēma skaitļošanas sarežģītības teorijā – Būla funkciju jutīguma s(f) saistība ar tādiem sarežģītības mēriem kā bloku jutīgums bs(f) un sertifikātu sarežģītība C(f). Populāra hipotēze apgalvo, ka jutīgums ir polinomiāli saistīts ar bloku jutīgumu un bs(f) = O(s(f)^c) kādai konstantei c. Līdz šim labākais zināmais novērtējums no augšas abiem mēriem ir eksponenciāls, bs(f) ≤ C(f) ≤ 2^(s(f)-1) s(f) - s(f) + 1, bet labākie atrastie piemēri sasniedz tikai kvadrātisku atstarpi, bs(f) = Ω(s(f)^2). Šajā darbā tiek pierādīts jauns novērtējums no augšas, bs(f) ≤ C(f) ≤ max(2^(s(f)-1) (s(f) - 1/3), s(f)).
Kvantu vaicājumu sarežģītība dinamiskās programmēšanas problēmām
2022
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…
Kvantu vaicājumu sarežģītība bezkonteksta gramatikām
2019
Bezkonteksta gramatikas un to ģenerētās valodas ir plaši pētīta tēma datorzinātnē. Tām ir dažādi praktiski pielietojumi, piemēram, XML valodā. Savukārt kvantu skaitļošana, it sevišķi kvantu vaicājumu algoritmi, ir datorzinātnes nozare, kas par spīti popularitātei, ir vēl neizpētīta un neskaidra. Šī darba mērķis ir aplūkot vārda piederības problēmu bezkonteksta valodai no kvantu vaicājumu algoritmu puses. Konkrētāk - darbā tika izvirzīti divi uzdevumi. Pirmais uzdevums bija atrast bezkonteksta valodu ar kvantu vaicājumu sarežģītību O(N^c), kur c0 vai pierādīt par tādas neesamību. Otrais uzdevums - uzrādīt intuitīvi saprotamu bezkonteksta valodas konstrukciju, kas ļauj konstruēt valodu ar kva…
Ultrametrisku galīgu automātu iespējas
2015
Maģistra darbā tiek pētīti ultrametriski galīgi automāti un to iespējas. Ultrametriski automāti ir līdzīgi varbūtiskiem automātiem, tikai varbūtību vietā tiek izmantotas amplitūdas, kas ir p-adiski skaitļi. Pēdējos divos gados tika veikti dažādi pētījumi, kuros piedalījās arī darba autors, par ultrametrisku algoritmu izmantošanas iespējām, ieskaitot to izmantošanu galīgajos automātos. Darbā tiek izpētītas dažādu ultrametrisku galīgu automātu tipu iespējas, salīdzinot tos ar citiem automātu tipiem. Maģistra darbā tiek salīdzinātas dažādi definētu ultrametrisku galīgu automātu valodu atpazīšanas iespējas. Ultrametriski galīgi automāti darbā tiek salīdzināti arī ar dažādu sarežģītību determinē…
Ultrametriski algoritmi
2015
Maģistra darbā tiek pētīta ultrametriska galīga automāta un ultrametriska vaicājošā algoritma definīcija, kas paredz p-adisku skaitļu izmantošanu amplitūdu norādīšanā. Lasītājs tiek iepazīstināts ar p-adisku skaitļošanas sistēmu un absolūtās vērtības jēdzienu. Darba ietvaros tiek izstrādātas ultrametrisku automātu realizācijas dažādu valodu atpazīšanai. Ultrametrisku automātu rēķināšanas sarežģītība tiek novērtēta pēc stāvokļu skaita automātā. Tiek apskatīts ultrametrisks vaicājošais algoritms, kas pārbauda Heminga koda pareizību. Darbā tiek pētītas ultrametrisku algoritmu priekšrocības salīdzinot ar klasiskām un kvantu skaitļošanas teorijas pamatkoncepcijām.