Вероятностный алгоритм

Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.

История

Начало качественной теории вероятностных алгоритмов было положено в 1956 году, когда впервые было установлено, что посредством вероятностных алгоритмов можно вычислить в точности те же функции, что и посредством обычных, детерминированных алгоритмов.

В 1974 году было показано, что можно построить такой язык $L$ и функцию $t(x)$, что для любого $ϵ>0$ существует вероятностная машина Тьюринга, распознающая $L$ с вероятностью $1-ϵ$ за время $t(x)$ и если $t^{\prime }(x)$ — время работы детерминированной машины Тьюринга, распознающей $L$, то для бесконечного множества $x$ выполняется $t^{\prime }(x)>t(x)$.

См. также

• Лас-Вегас (алгоритм)
• Метод Монте-Карло
• Фильтр Блума

Ссылки

• Шаблон:Книга
• Бабенко М. А. Вероятность в алгоритмах, видео-лекция, Школа анализа данных, 16 марта 2013