Valószínűségi algoritmus

A valószínűségi algoritmus egy olyan algoritmus, amely magában foglalja a véletlenszám-generátor elérését a munka bizonyos szakaszaiban, hogy időt takarítson meg azáltal, hogy az eredmény abszolút megbízhatóságát a megbízhatósággal helyettesíti egy bizonyos valószínűséggel.

Történelem

A valószínűségi algoritmusok kvalitatív elméletének kezdete 1956-ban volt, [1] amikor először állapították meg, hogy a valószínűségi algoritmusok segítségével pontosan ugyanazokat a függvényeket lehet kiszámítani, mint a hagyományos, determinisztikus algoritmusokkal.

1974-ben kimutatták, hogy meg lehet alkotni egy nyelvet és függvényt úgy, hogy bármelyikhez létezik olyan valószínűségi Turing-gép , amely időben valószínőséggel ismer fel, és ha egy determinisztikus Turing-gép futási ideje, amely felismeri , akkor végtelen halmazra érvényes [2] . $L$ $t(x)$ $\epsilon > 0$ $L$ $1 - \epsilon$ $t(x)$ $t'(x)$ $L$ $x$ $t'(x) > t(x)$

Lásd még

Jegyzetek

↑ K. de Leeuw, E. F. Moore, K. E. Shannon, N. Shapiro, Computability on Probabilistic Machines // Automata. — M. : IL. - S. 242-278.
↑ Gill JT Valószínűségi Turing-gépek számítási összetettsége // Hatodik éves ACM szimpózium a számítástudomány elméletéről, Seattle (Wash.), 1974. április 30. - május 2. - NY: ACM. - P. 91-96.

Linkek

Uspensky V. A. , Semenov A. L. Algoritmusok elmélete: fő felfedezések és alkalmazások . — M .: Nauka, 1987. — S. 231-243 .
Babenko M. A. Valószínűség az algoritmusokban , videó előadás, School of Data Analysis , 2013. március 16.