Monte-Carlo-Algorithmus

Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer kleinen Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen, aber meist eine geringe Komplexität haben. Es handelt sich hierbei um einen Algorithmus mit einseitigem Fehler, d.h. bei einer der möglichen Antworten (ja/nein) darf der Algorithmus falsch liegen, bei der anderen nicht.

Um dieses Konzept zu veranschaulichen, nehmen wir an, dass der Algorithmus bei der Antwort ja garantiert korrekt ist, bei der Antwort nein dagegen kann ein Fehler vorliegen, d.h. die korrekte Antwort wäre ja. Dann kann man die Ausgabe eines Monte-Carlo-Algorithmus folgendermaßen interpretieren:

• ja: Der Algorithmus hat korrekt gerechnet, keine verbleibenden Unsicherheiten.
• nein: Diese Antwort kann stimmen, aber dies ist nicht sicher. Da das Ergebnis der Berechnung sowohl von der Eingabe (der Instanz des Problems) als auch von der hier verwendeten Zufallszahl abhängt, setzt man den Algorithmus nochmals auf die gleiche Eingabe an, wobei aber eine neue Zufallszahl geraten werden muss. Bekommt man bei jeder Wiederholung die Antwort nein, so ist sie mit großer Wahrscheinlichkeit korrekt. Tritt aber einmal die Antwort ja auf, so weiß man sofort, dass die vorhergehenden neins Fehler waren, da die ja-Antwort nach der oben beschriebenen Spezifikation immer korrekt ist.

Das Prinzip der wiederholten Durchführung des Algorithmus zum Bestimmen des korrekten Ergebnisses wird auch als probability amplification bezeichnet und ist im Artikel "randomisierter Algorithmus" genauer beschrieben.

Ein Beispiel für einen Monte-Carlo-Algorithmus ist der Miller-Rabin-Test, bei dem probabilistisch bestimmt wird, ob eine natürliche Zahl prim ist oder nicht.

Siehe auch: Liste von Algorithmen, Las-Vegas-Algorithmus, Kreiszahl, Monte-Carlo-Simulation