Las Vegas algoritam

U računarstvu, Las Vegas algoritam je nasumičan algoritam koji uvek daje tačane rezultate, to jest, uvek daje tačan rezultat ili obaveštava o neuspehu. Drugim rečima, Las Vegas algoritam se ne kocka sa korektnošću rezultata, on se kocka samo sa resursima koje koristi za izračunavanje. Jednostavan primer je Квиксорт, gde se pivot bira nasumično, ali je rezultat uvek sortiran. Uobičajena definicija Las Vegas algoritma uključuje ograničenje da će se očekivano vreme izvršavanja uvek završiti, očekivanje se vrši preko prostora slučajnih informacija, ili entropije, korišćenih u algoritmu.

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.

Las Vegas algoritam je osmislio László Babai 1979. godine, u kontekstu graf-izomorfni problem, kao snažniju verziju Monte Karlo algoritma.^[1][2][3] Las Vegas algoritam može se koristiti u situacijama gde je broj mogućih rešenja relativno ograničen, a gde je provera ispravnosti kandidata relativno laka, dok je zapravo izračunavanje rešenja kompleksno.

Ime se odnosi na grad Лас Вегас, koji je dobro poznat u Sjedinjenim Američkim Državama kao ikona kockanja.

Složenost

Složenost problema odlučivanja koji imaju Las Vegas algoritmi sa očekivanim polinomijalnim vremenom izvršenja je ZPP.

Ispostavlja se da

${\displaystyle {\textrm {ZPP}}={\textrm {RP}}\cap \,{\text{co}}\,{\textrm {-RP}},\,\!}$

je blisko povezan sa načinom kako su ponekad Las Vegas algoritmi kreirani. Naime klasa RP sadrži sve probleme odlučivanja za koje slučajno polinomijalno vreme algoritma postoji da uvek odgovori ispravno kad je tačan odgovor blizu sa "ne", ali je dozvoljeno da bude pogrešno sa određenom verovatnoćom ograničenja daleko kad je odgovor "da". Kad takav algoritam postoji za oba problema i njegov komplement(sa odgovorima "da" ili "ne"), dva algoritma se mogu pokrenuti istovremeno više puta: pokrenuti svaki za određen broj koraka, naizmenično, dok jedan od njih ne vraća definitivno tačan odgovor. Ovo je standardni način da se izgradi Las Vegas algoritam koji radi u očekivanom polinomijalnom vremenu. Imajte na umu da u opštem slučaju ne postoji gornja granica za vreme izvršenja Las Vegas Algoritma.

Povezanost sa Monte Karlo algoritmom

Las Vegas algoritmi mogu biti suprotni sa Monte Karlo algoritmima, u kojima su sredstva ograničena, tačan odgovor nije garantovan 100% vremena, ali je vreme izvršavanja ovog algoritma bolje od najboljeg determinističkog algoritma. Po zahtevu za Markovu nejednakost, Las Vegas algoritam može se pretvoriti u Monte Karlo preko prevremenog prekida.