Search results for "Algoritmi"
showing 10 items of 204 documents
Kvanttitietokone voi laskea minuutissa laskun, jota tavallinen tietokone laskee vuosisadan
2023
Kvantu algoritmi simbolu virkņu uzdevumiem
2021
Darbā tiek apskatīti trīs simbolu virkņu uzdevumi. Pirmais no tiem ir nosaukts ”vārda meklēšana tekstā”: dotajam tekstam 𝑠 garuma 𝑛 un vārdam 𝑡 garumā 𝑚, pateikt, vai vārds atro das tekstā. Klasiski šo var atrisināt laikā 𝑂(𝑛 + 𝑚) ar KnutaMorisaPrata algoritmu, kvantiski ̃ √𝑛 + √𝑚) = 𝑂( ̃ √𝑛) laika algoritms. Kaut gan zināms, ka vispārīgajā gadījumā ne eksistē 𝑂( √ pieciešami Ω( 𝑛) vaicājumi virknes simboliem, nav skaidrs, vai šī apakšējā robeža izpildās pie √ jebkuras m vērtības. Šajā darbā mēs pierādām, ka arī tad nepieciešami Ω( 𝑛) vaicājumi. Otrais uzdevums ir nosaukts ”visbiežāk sastopamas virknes meklēšana”: dotiem 𝑛 virknēm garumā 𝑘 √ ̃ pateikt, kāda virknē sastop…
Parametrizētu algoritmu paātrinājumi kvantu datoram
2021
Darbā tiek aplūkots, kā uz kvantu datora iespējams paātrināt zināmus parametrizētus algoritmus problēmām “Closest string”, “Cluster vertex deletion”, “Cluster editing”, “Vertex cover” un “Longest path” problēmu risinājumiem, ka arī to uzlabošana kvantu datoram, izmantojot kvantu algoritmus meklēšanas koka apstaigāšanai un dinamiskai programmēšanai. Ir parādīts, kā izveidot kvantu algoritmus “Cluster vertex deletion” problēmas risinājumam ar laika sarežģītību 𝑂(1.7321^𝑘 * √𝑘 * 𝑛^3) un “Vertex cover” problēmai ar laiku 𝑂(1.175^𝑘 * 𝑘^𝑂(1) + 𝑛√𝑚), kas ir labāk, nekā labākajiem zināmajiem algoritmiem ar laiku 𝑂(1.9102^𝑘 * (𝑛 + 𝑚)) un 𝑂(1.2738^𝑘 + 𝑘𝑛), attiecīgi. Ka arī ir parād…
Kvantu algoritmi grafa koka platumam
2021
Grafu teorijā koka platums ir ar neorientētu grafu asociēts skaitlis. Vairākas NP-pilnas problēmas grafiem var būt atrisinātas polinomiālajā laikā pie nosacījuma, ka grafa koka platums ir ierobežots. Koka platuma rēķināšana ir pats par sevi NP-pilns uzdevums, un labākajam zināmajam klasiskajam algoritmam, kas to risina, ir sarežģītība $O^*(1.7347^n)$. Šajā darbā ir iegūts kvantu algoritms koka platumam ar sarežģītību $O^*(1.6683^n)$.
Kvantu algoritmi Hopkrofta problēmai
2022
Darba nolūks ir izpētīt kvantu algoritmus un apakšējos novērtējumus Hopkrofta problēmai. Šajā uzdevumā doti punkti un taisnes, un vajag noteikt, vai kāds no punktiem atrodas uz kādas taisnes. Šis ir klasisks uzdevums, kas parādās vairākos ģeometriskos pielietojumos, un šajā darbā tiks pētīta tā sarežģītība kvantu skaitļošanas modelī. Lai iegūtu apakšējos novērtējumus, paredzēts kādas pazīstamas problēmas reducēt uz Hopkrofta problēmu. Lai iegūtu kvantu algoritmus, plānots pārveidot klasiskus algoritmus uz kvantu versijām, izmantojot zināmus kvantu skaitļošanas rīkus.
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…
Assessment of nonnegative matrix factorization algorithms for electroencephalography spectral analysis.
2020
AbstractBackgroundNonnegative matrix factorization (NMF) has been successfully used for electroencephalography (EEG) spectral analysis. Since NMF was proposed in the 1990s, many adaptive algorithms have been developed. However, the performance of their use in EEG data analysis has not been fully compared. Here, we provide a comparison of four NMF algorithms in terms of accuracy of estimation, stability (repeatability of the results) and time complexity of algorithms with simulated data. In the practical application of NMF algorithms, stability plays an important role, which was an emphasis in the comparison. A Hierarchical clustering algorithm was implemented to evaluate the stability of NM…
Lidaparātu trajektoriju konstruēšana balstoties uz Bezjē līknēm
2015
Pēdējos gados ļoti strauji attīstās tāda robotikas nozare, kā visu veidu lidojošie droni: kvadro- kopteri, oktakoperi u.t.t. Tehnoloģiju attīstības dēļ palika reāla autonomo dronu realizācija un sāka parādīties daži veidi, kā izmantot dronus. Darbā tiek izstrādāts autonomā kvadrokoptera trajektorijas konstruēšanas algoritms, balstoties uz Bezjē līknēm. Tiek apskatīts iepriekš izman- totais algoritms, tā trūkumi un priekšrocības. Izstrādātais algoritms tika implementēts Latvijas izstrādātajā dronā ”AirDog” un salīdzināti vecā un jaunā algoritma darbības rezultāti dažādos apstākļos.
Vertaileva analyysi live coding -sävellysympäristöihin
2010
Tässä tutkielmassa selvitetään mitä live coding on ja tutustutaan nel- jään live coding -sävellysympäristöön aloittelijan näkökulmasta. Ohjelmia vertail- laan neljän piirteen avulla ensisijaisesti käytettävyyden ja helpon omaksuttavuuden kannalta.
Efficient contour-based annotation by iterative deep learning for organ segmentation from volumetric medical images
2022
Abstract Purpose Training deep neural networks usually require a large number of human-annotated data. For organ segmentation from volumetric medical images, human annotation is tedious and inefficient. To save human labour and to accelerate the training process, the strategy of annotation by iterative deep learning recently becomes popular in the research community. However, due to the lack of domain knowledge or efficient human-interaction tools, the current AID methods still suffer from long training time and high annotation burden. Methods We develop a contour-based annotation by iterative deep learning (AID) algorithm which uses boundary representation instead of voxel labels to incorp…