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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

В 1974 году было показано, что можно построить такой язык и функцию , что для любого существует вероятностная машина Тьюринга, распознающая с вероятностью за время и если  — время работы детерминированной машины Тьюринга, распознающей , то для бесконечного множества выполняется [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.