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

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

История

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

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

См. также

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

Примечания

1. де Леу К., Мур Э. Ф., Шеннон К. Э., Шапиро Н. Вычислимость на вероятностных машинах // Автоматы. — М.: ИЛ. — С. 242-278.
2. 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.

Ссылки

• Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987. — С. 231-243.
• Бабенко М. А. Вероятность в алгоритмах, видео-лекция, Школа анализа данных, 16 марта 2013