Todennäköisyyspohjainen algoritmi

Todennäköisyyspohjainen algoritmi on algoritmi, joka sisältää pääsyn satunnaislukugeneraattoriin sen työskentelyn tietyissä vaiheissa ajan säästämiseksi toiminnan aikana korvaamalla tuloksen absoluuttisen luotettavuuden luotettavuudella tietyllä todennäköisyydellä.

Historia

Todennäköisyysalgoritmien kvalitatiivisen teorian alku sijoittui vuonna 1956, [1] jolloin ensimmäisen kerran todettiin, että todennäköisyysalgoritmien avulla voidaan laskea täsmälleen samat funktiot kuin tavanomaisten, determinististen algoritmien avulla.

Vuonna 1974 osoitettiin, että on mahdollista rakentaa kieli ja funktio siten, että jokaiselle on olemassa todennäköisyyspohjainen Turingin kone , joka tunnistaa todennäköisyydellä ajassa, ja jos on deterministisen Turingin koneen käyntiaika, joka tunnistaa , niin se pätee äärettömälle joukolle [2] . $L$ $t(x)$ $\epsilon > 0$ $L$ $1 - \epsilon$ $t(x)$ $t'(x)$ $L$ $x$ $t'(x) > t(x)$

Katso myös

Muistiinpanot

↑ K. de Leeuw, E. F. Moore, K. E. Shannon, N. Shapiro, Computability on Probabilistic Machines // Automata. — M .: IL. - S. 242-278.
↑ Gill JT Probabilististen Turing-koneiden laskennallinen monimutkaisuus // Kuudes vuotuinen ACM-symposium laskennan teoriasta, Seattle (Wash.), 30. huhtikuuta - 2. toukokuuta 1974. - NY: ACM. - s. 91-96.

Linkit

Uspensky V. A. , Semenov A. L. Algoritmien teoria: tärkeimmät löydöt ja sovellukset . — M .: Nauka, 1987. — S. 231-243 .
Babenko M. A. Probability in algoritms , videoluento, School of Data Analysis , 16. maaliskuuta 2013