Лучшие вопросы
Таймлайн
Чат
Перспективы
Вероятностный алгоритм
Из Википедии, свободной энциклопедии
Remove ads
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
История
Суммиров вкратце
Перспектива
Начало качественной теории вероятностных алгоритмов было положено в 1956 году,[1] когда впервые было установлено, что посредством вероятностных алгоритмов можно вычислить в точности те же функции, что и посредством обычных, детерминированных алгоритмов.
В 1974 году было показано, что можно построить такой язык и функцию , что для любого существует вероятностная машина Тьюринга, распознающая с вероятностью за время и если — время работы детерминированной машины Тьюринга, распознающей , то для бесконечного множества выполняется [2].
Remove ads
См. также
Примечания
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads