Pravděpodobnostní algoritmus

Pravděpodobnostní algoritmus je algoritmus, který zahrnuje přístup ke generátoru náhodných čísel v určitých fázích své práce , aby se ušetřil čas při provozu nahrazením absolutní spolehlivosti výsledku spolehlivostí s určitou pravděpodobností.

Historie

Počátek kvalitativní teorie pravděpodobnostních algoritmů byl položen v roce 1956, [1] kdy bylo poprvé zjištěno, že pomocí pravděpodobnostních algoritmů je možné vypočítat úplně stejné funkce jako pomocí konvenčních, deterministických algoritmů.

V roce 1974 se ukázalo, že je možné zkonstruovat jazyk a funkci tak, že pro všechny existuje pravděpodobnostní Turingův stroj , který rozpoznává s pravděpodobností v čase, a pokud je doba běhu deterministického Turingova stroje, který rozpoznává , pak platí pro nekonečnou množinu [2] . $L$ $t(x)$ $\epsilon > 0$ $L$ $1 - \epsilon$ $t(x)$ $t'(x)$ $L$ $X$ $t'(x) > t(x)$

Viz také

Poznámky

↑ K. de Leeuw, E. F. Moore, K. E. Shannon, N. Shapiro, Computable on Probabilistic Machines // Automata. — M. : IL. - S. 242-278.
↑ Gill JT Computational complexity of probabilistic Turing machines // Šesté výroční symposium ACM o teorii výpočetní techniky, Seattle (Wash.), 30. dubna - 2. května 1974. - NY: ACM. - S. 91-96.

Odkazy

Uspensky V. A. , Semenov A. L. Teorie algoritmů: hlavní objevy a aplikace . — M .: Nauka, 1987. — S. 231-243 .
Babenko M. A. Probability in algorithms , video přednáška, School of Data Analysis , 16. března 2013