Русская Википедия:Вероятностный алгоритм
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
История
Начало качественной теории вероятностных алгоритмов было положено в 1956 году,[1] когда впервые было установлено, что посредством вероятностных алгоритмов можно вычислить в точности те же функции, что и посредством обычных, детерминированных алгоритмов.
В 1974 году было показано, что можно построить такой язык <math>L</math> и функцию <math>t(x)</math>, что для любого <math>\epsilon > 0</math> существует вероятностная машина Тьюринга, распознающая <math>L</math> с вероятностью <math>1 - \epsilon</math> за время <math>t(x)</math> и если <math>t'(x)</math> — время работы детерминированной машины Тьюринга, распознающей <math>L</math>, то для бесконечного множества <math>x</math> выполняется <math>t'(x) > t(x)</math>[2].
См. также
Примечания
Ссылки
- Шаблон:Книга
- Бабенко М. А. Вероятность в алгоритмах, видео-лекция, Школа анализа данных, 16 марта 2013
- ↑ Шаблон:Книга
- ↑ 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.
