6533b7d8fe1ef96bd1269d21

RESEARCH PRODUCT

Rēķināšanas sarežģītības samazināšana ar nejaušību lietošanu

subject

description

Maģistra darbs „Rēķināšanas sarežģītības samazināšana ar nejaušības lietošanu” iekļauj pētījumu par varbūtisko pieeju rēķināšanas sarežģītības samazināšanai un apskata divus uzdevumus, proti, mulitilneāru polinomu ģenerēšanu un dārza šļūteņu modeļa izveidi, kuriem autore ir veikusi esošo risinājumu izpēti un izstrādājusi savus risinājumu algoritmus. Multilineāru polinomu ģenerēšanas problēmai, kurā tiek ģenerēti polinomi, kura atbilstu Būla funkcijai, ir veikta multilineāro polinomu izpēte, lai noteiktu to īpašības, kuras tiek izmantotas autores izstrādātajā polinomu ģenerēšanas varbūtiskajā algoritmā. Dārza šļūteņu (Garden - Hose) modeļa problēmai, kura ir salīdzinoši jauna (2013. gadā definēta), ir veikta esošo risinājumu un novērtējumu izpēte un apskatītas vairākas funkcijas, proti, ekvivalences (〖EQ〗_z), lielāks vai vienāds (〖GE〗_z), vieninieku skaita sakritības (〖BO〗_z) un pāra reižu sakritības (〖BM〗_z) funkcijas. Ekvivalences funkcijai ir izstrādāts varbūtiskais algoritms ar novērtējumiem, kurš garantēti ir ar mazāku cauruļu sarežģītību no noteiktas vērtības. 〖BO〗_z funkcijai ir izstrādāts uz ekvivalence reducējams risinājums. 〖GE〗_z un 〖BM〗_z ir izstrādāti determinētie algoritmi, bet 〖GE〗_z arī varbūtiskais algoritms un veikti algoritma novērtējumi.