Лас Вегас алгоритам
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
У рачунарству, Лас Вегас алгоритам је насумичан алгоритам који увек даје тачане резултате, то јест, увек даје тачан резултат или обавештава о неуспеху. Другим речима, Лас Вегас алгоритам се не коцка са коректношћу резултата, он се коцка само са ресурсима које користи за израчунавање. Једноставан пример је Квиксорт, где се пивот бира насумично, али је резултат увек сортиран. Уобичајена дефиниција Лас Вегас алгоритма укључује ограничење да ће се очекивано време извршавања увек завршити, очекивање се врши преко простора случајних информација, или ентропије, коришћених у алгоритму.
Лас Вегас алгоритам је осмислио Лáсзлó Бабаи 1979. године, у контексту граф-изоморфни проблем, као снажнију верзију Монте Карло алгоритма.[1][2][3] Лас Вегас алгоритам може се користити у ситуацијама где је број могућих решења релативно ограничен, а где је провера исправности кандидата релативно лака, док је заправо израчунавање решења комплексно.
Име се односи на град Лас Вегас, који је добро познат у Сједињеним Америчким Државама као икона коцкања.
Сложеност уреди
Сложеност проблема одлучивања који имају Лас Вегас алгоритми са очекиваним полиномијалним временом извршења је ЗПП.
Испоставља се да
је блиско повезан са начином како су понекад Лас Вегас алгоритми креирани. Наиме класа РП садржи све проблеме одлучивања за које случајно полиномијално време алгоритма постоји да увек одговори исправно кад је тачан одговор близу са "не", али је дозвољено да буде погрешно са одређеном вероватноћом ограничења далеко кад је одговор "да". Кад такав алгоритам постоји за оба проблема и његов комплемент(са одговорима "да" или "не"), два алгоритма се могу покренути истовремено више пута: покренути сваки за одређен број корака, наизменично, док један од њих не враћа дефинитивно тачан одговор. Ово је стандардни начин да се изгради Лас Вегас алгоритам који ради у очекиваном полиномијалном времену. Имајте на уму да у општем случају не постоји горња граница за време извршења Лас Вегас Алгоритма.
Повезаност са Монте Карло алгоритмом уреди
Лас Вегас алгоритми могу бити супротни са Монте Карло алгоритмима, у којима су средства ограничена, тачан одговор није гарантован 100% времена, али је време извршавања овог алгоритма боље од најбољег детерминистичког алгоритма. По захтеву за Маркову неједнакост, Лас Вегас алгоритам може се претворити у Монте Карло преко превременог прекида.
Референце уреди
- ^ Лáсзлó Бабаи, Монте-Царло алгоритхмс ин грапх исоморпхисм тестинг, Университé де Монтрéал, D.M.С. Но. 79-10.
- ^ Леонид Левин, „Тхе Тале оф Оне-wаy Фунцтионс”. арXив:абс/цс.ЦР/0012023
Проверите вредност параметра |арxив=(помоћ)., Проблемс оф Информатион Трансмиссион,. . 39. 2003 http://arxiv.org/abs/cs.CR/0012023. Недостаје или је празан параметар|title=(помоћ) , 92-103. - ^ Dan Grundy, Concepts and Calculation in Cryptography Архивирано на сајту Wayback Machine (12. април 2016), Университy оф Кент, Пх.D. тхесис, 2008
- Алгоритхмс анд Тхеорy оф Цомпутатион Хандбоок, ЦРЦ Пресс ЛЛЦ, 1999, "Лас Вегас алгоритхм", ин Дицтионарy оф Алгоритхмс анд Дата Струцтурес [онлине], Паул Е. Блацк, ед., У.С. Натионал Институте оф Стандардс анд Тецхнологy. 17 Јулy 2006. (аццессед Маy 09, 2009) Аваилабле фром: [1]