Monte-Carlo-Algorithmus

Monte-Carlo-Algorithmus

Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil besteht darin, dass das berechnete Ergebnis falsch sein kann. Durch Wiederholen des Algorithmus mit unabhängigen Zufallsbits 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.

Inhaltsverzeichnis

Ein- und zweiseitiger Fehler

Monte-Carlo-Algorithmen gibt es für Suchprobleme (Probleme, bei denen eine Lösung zu berechnen ist) und Entscheidungsprobleme (Probleme, bei denen eine Ja/Nein-Frage zu beantworten ist). Bei Monte-Carlo-Algorithmen für Entscheidungsprobleme unterscheidet man ein- und zweiseitigen Fehler. Bei zweiseitigem Fehler darf ein Monte-Carlo-Algorithmus sowohl false Positives liefern (also die Ausgabe Ja, obwohl Nein richtig wäre), als auch false Negatives (also die Ausgabe Nein, obwohl Ja richtig wäre). Bei einseitigem Fehler ist nur eine der beiden Fehlermöglichkeiten erlaubt. Eine häufige Vereinbarung besteht darin, von einseitigem Fehler zu sprechen und damit false Negatives zu meinen. Diese Konzepte werden im folgenden Abschnitt verdeutlicht, wo Komplexitätsklassen für Probleme mit Monte-Carlo-Algorithmen definiert werden.

Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen

  • BPP (bounded error probabilistic polynomial) ist die Menge der Entscheidungsprobleme, für die es einen polynomiell zeitbeschränkten randomisierten Algorithmus mit den folgenden Eigenschaften gibt: Wenn die korrekte Ausgabe Ja (Nein) lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja (oder Nein) ausgibt, mindestens 2/3.
  • RP (random polynomial) ist die Menge der Entscheidungsprobleme, für die es einen polynomiell zeitbeschränkten randomisierten Algorithmus mit den folgenden Eigenschaften gibt: Wenn die korrekte Ausgabe Ja lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, mindestens 1/2. Wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, 1.
  • co-RP ist die Menge der Entscheidungsprobleme, für die es einen polynomiell zeitbeschränkten randomisierten Algorithmus mit den folgenden Eigenschaften gibt: Wenn die korrekte Ausgabe Ja lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, 1; wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, mindestens 1/2. Damit enthält co-RP die Komplemente der Probleme in RP.

Die angegebenen Schranken für die Wahrscheinlichkeiten müssen jeweils für alle Eingaben gelten; die Wahrscheinlichkeiten beziehen sich jeweils nur auf die vom Algorithmus verwendeten Zufallsbits (und nicht auf die Eingabe, die Eingabe wird also nicht als zufällig aufgefasst). Mit Hilfe von Probability Amplification kann man zeigen, dass die Konstante 2/3 aus der Definition von BPP durch jede andere Konstante aus dem Intervall (1/2,1) ersetzt werden kann, ohne die Menge BPP zu ändern; ebenso kann in den Definitionen von RP und co-RP die Konstante 1/2 durch jede Konstante aus dem Intervall (0,1) ersetzt werden.

Obwohl BPP und RP Mengen von Problemen sind, werden im allgemeinen Sprachgebrauch häufig Begriffe wie BPP-Algorithmen oder RP-Algorithmen benutzt, um Algorithmen mit den oben definierten Eigenschaften zu bezeichnen.

Zur Verdeutlichung der Definition von RP: Wenn ein RP-Algorithmus die Ausgabe Ja liefert, wissen wir mit Sicherheit, dass die Ausgabe Ja korrekt ist (da die Definition sicherstellt, dass bei korrekter Ausgabe Nein dies auf jeden Fall auch ausgegeben wird). Wenn dagegen ein RP-Algorithmus die Ausgabe Nein liefert, wissen wir nichts über die korrekte Ausgabe (da nach der Definition die Ausgabe Nein möglich ist, wenn Ja oder Nein korrekt wäre).

Beispielanwendungen

Miller-Rabin-Primzahltest

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. Die Ausgabe des Tests lautet entweder „sicher zusammengesetzt“ oder „wahrscheinlich prim“. Die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als „wahrscheinlich prim“ klassifiziert wird, liegt pro Durchgang unter 25 % und kann durch mehrfache Ausführung weiter gesenkt werden. Der Miller-Rabin-Test liefert keine Aussage über die Faktoren einer zusammengesetzten Zahl, ist also kein Faktorisierungsverfahren.

Illustration zur Monte-Carlo-Bestimmung von Pi.

Probabilistische Bestimmung der Zahl Pi

Man wählt hierzu zufällige Punkte \left( x, y | x \in \left[ -1..1 \right] \wedge y \in \left[ -1..1 \right]\right) aus und überprüft, ob diese innerhalb des Einheitskreises liegen. Die sich ergebende Wahrscheinlichkeitsverteilung P(Im Kreis) stellt die Fläche eines Viertels des Einheitskreises dar. Pi kann nun mit folgender Formel berechnet werden:

\frac{\text{Kreisflaeche}}{\text{Quadratflaeche}} = \frac{ r^{2} \cdot \pi }{ (2 \cdot r)^{2} } = \frac{  \pi }{ 4 } = \frac{\text{Treffer in Kreisflaeche}}{\text{generierte Punkte im Rechteck}} = P \left( \text{Im Kreis} \right)
Siehe auch: Kreiszahl

Numerische Integration

Numerische Integration mit Monte Carlo: Die Stützstellen werden zufällig gleichverteilt auf dem Integrationsintervall gewählt. Neue Stützstellen sind dunkelblau, die alten hellblau eingezeichnet. Der Wert des Integrals nähert sich 3,32 an.

Das obige Beispiel zur Bestimmung von Pi bildet praktisch das Flächenintegral einer Viertelkreisfläche. Entsprechend kann man das Flächenintegral allgemeiner, auch höherdimensionaler Funktionen nach dieser Methode berechnen. Dazu bildet man zufällige Werte der Funktionsargumente und zufällige Werte im Intervall der möglichen Funktionsergebnisse und zählt, wie viele der direkt berechneten Funktionswerte unterhalb der zufällig gewählten Werte liegen. Das Integral ergibt sich dann als Rechteckfläche (aus Argument- und Funktionswertintervall, und (Hyper)Quadervolumen) multipliziert mit diesem Zählverhältnis.

Supercomputer

Heutige Supercomputer (HPC) basieren auf massivem Multiprocessing mit vielen tausend Einzelprozessoren, die parallel arbeiten. Diese Gegebenheiten lassen sich besonders gut mit solchen probabilistischen Lösungsverfahren ausnutzen.[1]

Siehe auch

Literatur

R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5.

Weblinks

 Commons: Monte-Carlo-Methode – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Prof. A. Bachem in Interview, c't 12/2010, S. 18: So lassen sich probabilistische Lösungsverfahren zumeist weitaus besser parallelisieren als die heute üblichen deterministischen.

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hybrid-Monte-Carlo-Algorithmus — Der Hybrid Monte Carlo Algorithmus ist eine Monte Carlo Methode zur Erzeugung von Systemen im kanonischen Zustand. Das Verfahren stellt eine Kombination aus Molekulardynamik und Zufallsbewegung her. Die Molekulardynamik wird benutzt, um effizient …   Deutsch Wikipedia

  • Monte-Carlo-Integration — Monte Carlo Algorithmen sind randomisierte Algorithmen, die mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil… …   Deutsch Wikipedia

  • Monte Carlo (Begriffsklärung) — Monte Carlo bezeichnet: Monte Carlo, einen Stadtteil von Monaco Monte Carlo (San Marino), einen Berg in San Marino Rallye Monte Carlo, eine Rallye durch Monaco und Frankreich mit Ziel Monte Carlo Monte Carlo Resort, ein Hotel in Las Vegas… …   Deutsch Wikipedia

  • Monte-Carlo — Spielbank von Monte Carlo Monte Carlo ist ein Stadtteil von Monaco, der für sein Casino und seine Prominenz bekannt ist. Es wird manchmal fälschlicherweise als Hauptstadt von Monaco ausgegeben. Monaco hat als Stadtstaat jedoch keine Hauptstadt.… …   Deutsch Wikipedia

  • Monte Carlo — 43.7397777777787.4271944444444 Koordinaten: 43° 44′ N, 7° 26′ O …   Deutsch Wikipedia

  • Monte-Carlo-Methode — Viertelkreis, dessen Fläche durch die Monte Carlo Methode angenähert wird. Damit lässt sich eine Näherung von Pi bestimmen. Monte Carlo Simulation oder Monte Carlo Studie, auch: MC Simulation, ist ein Verfahren aus der Stochastik, bei dem sehr… …   Deutsch Wikipedia

  • Monte-Carlo-Statistik — Viertelkreis, dessen Fläche durch die Monte Carlo Methode angenähert wird. Damit lässt sich eine Näherung von Pi bestimmen. Monte Carlo Simulation oder Monte Carlo Studie, auch: MC Simulation, ist ein Verfahren aus der Stochastik, bei dem sehr… …   Deutsch Wikipedia

  • Monte-Carlo-Studie — Viertelkreis, dessen Fläche durch die Monte Carlo Methode angenähert wird. Damit lässt sich eine Näherung von Pi bestimmen. Monte Carlo Simulation oder Monte Carlo Studie, auch: MC Simulation, ist ein Verfahren aus der Stochastik, bei dem sehr… …   Deutsch Wikipedia

  • Monte-Carlo-Verfahren — Viertelkreis, dessen Fläche durch die Monte Carlo Methode angenähert wird. Damit lässt sich eine Näherung von Pi bestimmen. Monte Carlo Simulation oder Monte Carlo Studie, auch: MC Simulation, ist ein Verfahren aus der Stochastik, bei dem sehr… …   Deutsch Wikipedia

  • Monte Carlo Simulation — Viertelkreis, dessen Fläche durch die Monte Carlo Methode angenähert wird. Damit lässt sich eine Näherung von Pi bestimmen. Monte Carlo Simulation oder Monte Carlo Studie, auch: MC Simulation, ist ein Verfahren aus der Stochastik, bei dem sehr… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”