Probabilistisk algoritm

En probabilistisk algoritm är en algoritm som involverar åtkomst till en slumptalsgenerator i vissa skeden av dess arbete för att spara tid i drift genom att ersätta resultatets absoluta tillförlitlighet med tillförlitlighet med en viss sannolikhet.

Historik

Början till den kvalitativa teorin om probabilistiska algoritmer lades 1956, [1] då det först slogs fast att man med hjälp av probabilistiska algoritmer är möjligt att beräkna exakt samma funktioner som med hjälp av konventionella, deterministiska algoritmer.

1974 visades det att det är möjligt att konstruera ett språk och en funktion så att det för alla existerar en probabilistisk Turing-maskin som känner igen med sannolikhet i tid, och om är körtiden för en deterministisk Turing-maskin som känner igen , då gäller för en oändlig mängd [2] . $L$ $t(x)$ $\epsilon > 0$ $L$ $1 - \epsilon$ $t(x)$ $t'(x)$ $L$ $x$ $t'(x) > t(x)$

Se även

Anteckningar

↑ 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-maskiner // Sjätte årliga ACM-symposium om datorteori, Seattle (Wash.), 30 april - 2 maj 1974. - NY: ACM. - S. 91-96.

Länkar

Uspensky V. A. , Semenov A. L. Algoritmerteori: huvudsakliga upptäckter och tillämpningar . — M .: Nauka, 1987. — S. 231-243 .
Babenko M. A. Sannolikhet i algoritmer , videoföreläsning, School of Data Analysis , 16 mars 2013