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

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

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

История[править | править вики-текст]

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

В 1974 году было показано, что можно построить такой язык L и функцию t(x), что для любого \epsilon > 0 существует вероятностная машина Тьюринга, распознающая L с вероятностью 1 - \epsilon за время t(x) и если t'(x) — время работы детерминированной машины Тьюринга, распознающей L, то для бесконечного множества x выполняется 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.

Ссылки[править | править вики-текст]