0000000000097658
AUTHOR
Nikita Larka
showing 3 related works from this author
Kvantu algoritmi algoritmiskās ģeometrijas uzdevumiem
2019
Viens no svarīgākajiem uzdevumiem teorētiskajā datorzinātnē ir 3SUM uzdevums. 3SUM uzdevumu var formulēt sekojoši: ir dota kopa S ar n veseliem skaitļiem, ir jānoteic, vai eksistē tādi a, b, c ∈ S, ka a + b + c = 0. Šim uzdevumam algoritms ar sarežģītību O(n^(2-ϵ)) nav zināms. Uzdevums 3SUM ir reducējams uz daudziem ģeometriskajiem uzdevumiem, un tiem algoritms ar sarežģītību O(n^(2-ϵ)) arī nav zināms. Darbā ir apvienotas divas svarīgas datorzinātnes nozares: kvantu skaitļošana un algoritmiskā ģeometrija ar mērķi izveidot kvantu algoritmus 3SUM-HARD klases ģeometriskajiem uzdevumiem. Daudziem no tiem ir atrasts kvantu algoritms ar sarežģītību O(n^(1+o(1))).
Kvantu algoritmu konstruēšana, izmantojot čaulu programmas
2017
Čaulu programma ir lineāri algebrisks skaitļošanas modelis, ar kura palīdzību var konstruēt programmas Būla funkciju rēķināšanai. Ir zināms, kā čaulu programmu var pārtaisīt par kvantu vaicājošo algoritmu. Pie tam, čaulu programmām var definēt sarežģītību tā, ka pārtaisītajam kvantu algoritmam sarežģītība sakristu ar čaulu programmas sarežģītību. Līdz ar to čaulu programmas ir spēcīgs rīks kvantu algoritmu konstruēšanai. Ir zināms veids, kā uztaisīt čaulu programmu, kura rēķinātu Būla formulu F(x_1,...,x_n), kas sastāv no loģiskajiem elementiem (NOT, OR, AND). Šī darba mērķis ir izveidot metodi, ar kuras palīdzību varētu konstruēt pēc iespējas optimālas čaulu programmas, kuras rēķinātu Būla…
Aptuvenu kopīgu dalītāju atrašana ar režģiem
2015
Darbā "Aptuvenu kopīgu dalītāju atrašana ar režģiem" tiek realizēts prototips, kas aprēķina aptuvenu kopīgu dalītāju nejauši uzģenerētam skaitļu komplektam. Prototips ļauj eksperimentālā veidā aprēķināt parametrus, pie kuriem dalītājs ir aprēķināms/neaprēķināms Prototips tiek veidots lietojot matemātisko programmatūru SageMath.