Probabilistisk algoritme

En probabilistisk algoritme er en algoritme, der involverer adgang til en tilfældig talgenerator på bestemte stadier af dens arbejde for at spare tid i drift ved at erstatte den absolutte pålidelighed af resultatet med pålidelighed med en vis sandsynlighed.

Historie

Begyndelsen til den kvalitative teori om probabilistiske algoritmer blev lagt i 1956, [1] da det første gang blev fastslået, at det ved hjælp af probabilistiske algoritmer er muligt at beregne nøjagtig de samme funktioner som ved hjælp af konventionelle, deterministiske algoritmer.

I 1974 blev det vist, at det er muligt at konstruere et sprog og en funktion, således at der for enhver eksisterer en sandsynlig Turing-maskine , der genkender med sandsynlighed i tid, og hvis er køretiden for en deterministisk Turing-maskine, der genkender , så gælder for et uendeligt sæt [2] . $L$ $t(x)$ $\epsilon > 0$ $L$ $1 - \epsilon$ $t(x)$ $t'(x)$ $L$ $x$ $t'(x) > t(x)$

Se også

Noter

↑ 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 // Sjette årlige ACM-symposium om databehandlingsteori, Seattle (Wash.), 30. april - 2. maj 1974. - NY: ACM. - S. 91-96.

Probabilistisk algoritme

Historie

Se også

Noter

Links