Лучшие вопросы
Таймлайн
Чат
Перспективы

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

Из Википедии, свободной энциклопедии

Remove ads

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

История

Суммиров вкратце
Перспектива

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

В 1974 году было показано, что можно построить такой язык и функцию , что для любого существует вероятностная машина Тьюринга, распознающая с вероятностью за время и если  — время работы детерминированной машины Тьюринга, распознающей , то для бесконечного множества выполняется [2].

Remove ads

См. также

Примечания

Ссылки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads