Вероятностный алгоритм
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
Содержание
История
Начало качественной теории вероятностных алгоритмов было положено в 1956 году,[1] когда впервые было установлено, что посредством вероятностных алгоритмов можно вычислить в точности те же функции, что и посредством обычных, детерминированных алгоритмов.
В 1974 году было показано, что можно построить такой язык <math>L</math> и функцию <math>t(x)</math>, что для любого <math>\epsilon > 0</math> существует вероятностная машина Тьюринга, распознающая <math>L</math> с вероятностью <math>1 - \epsilon</math> за время <math>t(x)</math> и если <math>t'(x)</math> — время работы детерминированной машины Тьюринга, распознающей <math>L</math>, то для бесконечного множества <math>x</math> выполняется <math>t'(x) > t(x)</math>[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.
- Бабенко М. А. [tech.yandex.ru/education/m/shad/talks/655/ Вероятность в алгоритмах], видео-лекция, Школа анализа данных, 16 марта 2013
Отрывок, характеризующий Вероятностный алгоритм
На другой день вечером Пьер узнал, что все эти содержащиеся (и, вероятно, он в том же числе) должны были быть судимы за поджигательство. На третий день Пьера водили с другими в какой то дом, где сидели французский генерал с белыми усами, два полковника и другие французы с шарфами на руках. Пьеру, наравне с другими, делали с той, мнимо превышающею человеческие слабости, точностью и определительностью, с которой обыкновенно обращаются с подсудимыми, вопросы о том, кто он? где он был? с какою целью? и т. п.Вопросы эти, оставляя в стороне сущность жизненного дела и исключая возможность раскрытия этой сущности, как и все вопросы, делаемые на судах, имели целью только подставление того желобка, по которому судящие желали, чтобы потекли ответы подсудимого и привели его к желаемой цели, то есть к обвинению. Как только он начинал говорить что нибудь такое, что не удовлетворяло цели обвинения, так принимали желобок, и вода могла течь куда ей угодно. Кроме того, Пьер испытал то же, что во всех судах испытывает подсудимый: недоумение, для чего делали ему все эти вопросы. Ему чувствовалось, что только из снисходительности или как бы из учтивости употреблялась эта уловка подставляемого желобка. Он знал, что находился во власти этих людей, что только власть привела его сюда, что только власть давала им право требовать ответы на вопросы, что единственная цель этого собрания состояла в том, чтоб обвинить его. И поэтому, так как была власть и было желание обвинить, то не нужно было и уловки вопросов и суда. Очевидно было, что все ответы должны были привести к виновности. На вопрос, что он делал, когда его взяли, Пьер отвечал с некоторою трагичностью, что он нес к родителям ребенка, qu'il avait sauve des flammes [которого он спас из пламени]. – Для чего он дрался с мародером? Пьер отвечал, что он защищал женщину, что защита оскорбляемой женщины есть обязанность каждого человека, что… Его остановили: это не шло к делу. Для чего он был на дворе загоревшегося дома, на котором его видели свидетели? Он отвечал, что шел посмотреть, что делалось в Москве. Его опять остановили: у него не спрашивали, куда он шел, а для чего он находился подле пожара? Кто он? повторили ему первый вопрос, на который он сказал, что не хочет отвечать. Опять он отвечал, что не может сказать этого.
