Monte-Carlo-Algorithmus

Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Durch Wiederholen des Algorithmus mit unabhängigen Zufallszahlen kann jedoch die Fehlerwahrscheinlichkeit gesenkt werden (Probability Amplification, weitere Einzelheiten im Artikel Randomisierter Algorithmus). Im Gegensatz zu Monte-Carlo-Algorithmen dürfen Las-Vegas-Algorithmen nur korrekte Lösungen berechnen.

Monte-Carlo-Algorithmen dienen als Basis für Monte-Carlo-Simulationen.