Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
История Начало качественной теории вероятностных алгоритмов было положено в 1956 году, когда впервые было установлено, что посредством вероятностных алгоритмов можно вычислить в точности те же функции, что и посредством обычных, детерминированных алгоритмов.
В 1974 году было показано, что можно построить такой язык и функцию , что для любого существует вероятностная машина Тьюринга, распознающая с вероятностью за время и если — время работы детерминированной машины Тьюринга, распознающей , то для бесконечного множества выполняется Gill J. T. Computational complexity of probabilistic Turing machines // Sixth annual ACM symposium on theory of computing, Seattle (Wash.), April 30 — May 2, 1974. — N. Y.: ACM. — P. 91-96..
См. также Лас-Вегас (алгоритм) Метод Монте-Карло Фильтр Блума
Примечания
Ссылки
Бабенко М. А. Вероятность в алгоритмах, видео-лекция, Школа анализа данных, 16 марта 2013
Категория:Теория алгоритмов Категория:Анализ алгоритмов Категория:Алгоритмы