Вероятностный алгоритм
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
История
[править | править код]Начало качественной теории вероятностных алгоритмов было положено в 1956 году,[1] когда впервые было установлено, что посредством вероятностных алгоритмов можно вычислить в точности те же функции, что и посредством обычных, детерминированных алгоритмов.
В 1974 году было показано, что можно построить такой язык и функцию , что для любого существует вероятностная машина Тьюринга, распознающая с вероятностью за время и если — время работы детерминированной машины Тьюринга, распознающей , то для бесконечного множества выполняется [2].
См. также
[править | править код]Примечания
[править | править код]- ↑ де Леу К., Мур Э. Ф., Шеннон К. Э., Шапиро Н. Вычислимость на вероятностных машинах // Автоматы. — М.: ИЛ. — С. 242-278.
- ↑ 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