Algoritm probabilistic

Un algoritm probabilistic este un algoritm care presupune accesarea unui generator de numere aleatoare în anumite etape ale activității sale pentru a economisi timp în funcționare prin înlocuirea fiabilității absolute a rezultatului cu fiabilitatea cu o anumită probabilitate.

Istorie

Începutul teoriei calitative a algoritmilor probabilistici a fost pus în 1956, [1] când s-a stabilit pentru prima dată că prin intermediul algoritmilor probabilistici este posibil să se calculeze exact aceleași funcții ca prin algoritmi convenționali, determiniști.

În 1974, s-a demonstrat că este posibil să se construiască un limbaj și o funcție astfel încât pentru oricare să existe o mașină Turing probabilistică care recunoaște cu probabilitate în timp, iar dacă este timpul de rulare al unei mașini Turing deterministe care recunoaște , atunci este valabil pentru o mulțime infinită [2] . $L$ $t(x)$ $\epsilon > 0$ $L$ $1 - \epsilon$ $t(x)$ $t'(x)$ $L$ $X$ $t'(x) > t(x)$

Vezi și

Note

↑ K. de Leeuw, E. F. Moore, K. E. Shannon, N. Shapiro, Computability on Probabilistic Machines // Automata. — M. : IL. - S. 242-278.
↑ Gill JT Computational complexity of probabilistic Turing machines // Sixth annual ACM symposium on theory of computing, Seattle (Wash.), 30 aprilie - 2 mai 1974. - NY: ACM. - P. 91-96.

Link -uri

Uspensky V. A. , Semenov A. L. Teoria algoritmilor: principalele descoperiri și aplicații . — M .: Nauka, 1987. — S. 231-243 .
Babenko M. A. Probabilitatea în algoritmi , prelegere video, Școala de Analiză a Datelor , 16 martie 2013