Monte-Carlo-Algorithmus: Unterschied zwischen den Versionen

Breaking News
Zufallsbild: Gerd Altmann / Pixabay

Monte-Carlo-Algorithmus: Unterschied zwischen den Versionen

imported>Aka
K (zu großen Zeilenabstand entfernt)
 
imported>Cepheiden
K
 
Zeile 1: Zeile 1:
'''Monte-Carlo-Algorithmen''' sind [[Randomisierter Algorithmus|randomisierte Algorithmen]], die mit einer nichttrivial 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 [[Fehler 1. Art|Fehlerwahrscheinlichkeit]] gesenkt werden (''Probability Amplification'', weitere Einzelheiten im Artikel [[Randomisierter Algorithmus]]). Im Gegensatz zu Monte-Carlo-Algorithmen dürfen [[Las-Vegas-Algorithmus|Las-Vegas-Algorithmen]] nur korrekte Lösungen berechnen.
'''Monte-Carlo-Algorithmen''' sind [[Randomisierter Algorithmus|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 [[Fehler 1. Art|Fehlerwahrscheinlichkeit]] gesenkt werden (''Probability Amplification'', weitere Einzelheiten im Artikel [[Randomisierter Algorithmus]]). Im Gegensatz zu Monte-Carlo-Algorithmen dürfen [[Las-Vegas-Algorithmus|Las-Vegas-Algorithmen]] nur korrekte Lösungen berechnen.
 
Der Name Monte-Carlo hängt laut [[Nicholas Metropolis]] wie folgt mit der Methode zusammen: [[Stanisław Marcin Ulam|Stan Ulam]] hatte einen Onkel, der sich zum Spielen immer Geld von Verwandten geliehen hatte, denn „er musste nach Monte Carlo gehen“.<ref>{{Literatur |Autor=N. Metropolis |Titel=BEGINNING of the MONTE CARLO METHOD |Sammelwerk=Los Alamos Science Special Issue |Datum=1987 |Seiten=125–130 |Online=https://fas.org/sgp/othergov/doe/lanl/pubs/00326866.pdf}}</ref>
 
Monte-Carlo-Algorithmen dienen als Basis für [[Monte-Carlo-Simulation]]en.


== Ein- und zweiseitiger Fehler ==
== Ein- und zweiseitiger Fehler ==
Monte-Carlo-Algorithmen gibt es für [[Suchproblem]]e (Probleme, bei denen eine Lösung zu berechnen ist) und [[Entscheidbar|Entscheidungsprobleme]] (Probleme, bei denen eine Ja/Nein-Frage zu beantworten ist). Bei Monte-Carlo-Algorithmen für Entscheidungsprobleme unterscheidet man zwischen ein- und zweiseitigen Fehlern. Bei einem zweiseitigen Fehler darf ein Monte-Carlo-Algorithmus sowohl ''[[Falsch positiv|false Positives]]'' liefern (also die Ausgabe Ja, obwohl Nein richtig wäre), als auch ''[[Falsch negativ|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 einem einseitigen Fehler zu sprechen und damit false Negatives zu meinen. Diese Konzepte werden im folgenden Abschnitt verdeutlicht, in dem [[Komplexitätsklasse]]n für Probleme mit Monte-Carlo-Algorithmen definiert werden.
Monte-Carlo-Algorithmen gibt es für
* [[Suchproblem]]e<ref>Suchprobleme sind Aufgaben, bei denen eine Lösung zu berechnen ist.</ref>
* [[Entscheidbar|Entscheidungsprobleme]].<ref>Entscheidungsprobleme sind Aufgaben, bei denen eine Ja/Nein-Frage zu beantworten ist.</ref> Hier wird zwischen ein- und zweiseitigen Fehlern unterschieden:
** Bei einem zweiseitigen Fehler darf ein Monte-Carlo-Algorithmus sowohl ''[[Falsch positiv|false Positives]]'' liefern (also die Ausgabe Ja, obwohl Nein richtig wäre), als auch ''[[Falsch negativ|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 einem einseitigen Fehler zu sprechen und damit „false Negatives“ zu meinen.
* die [[Numerische Integration#Monte-Carlo-Integration|Numerische Integration]]
 
Diese Konzepte werden im folgenden Abschnitt verdeutlicht, in dem [[Komplexitätsklasse]]n für Probleme mit Monte-Carlo-Algorithmen definiert werden.


== Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen ==
== Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen ==
* ''[[BPP (Komplexitätsklasse)|BPP]]'' (von {{enS|''bounded error probabilistic polynomial time''}}) 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.
* ''[[BPP (Komplexitätsklasse)|BPP]]'' (von {{enS|bounded error probabilistic polynomial time}}) 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 (Komplexitätsklasse)|RP]]'' (von {{enS|''randomized polynomial time''}}) 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.  
* ''[[RP (Komplexitätsklasse)|RP]]'' (von {{enS|randomized polynomial time}}) 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 [[Komplement (Mengenlehre)|Komplemente]] der Probleme in RP.
* ''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 [[Komplement (Mengenlehre)|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.
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.  
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).
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 ==
== Methoden ==
=== Miller-Rabin-Primzahltest ===
Alle folgenden Algorithmen gehören zu den [[MCMC-Verfahren|Markov-Chain-Monte-Carlo-Verfahren]], d.&nbsp;h. die Erzeugung der Zustände geschieht auf der Basis der Konstruktion einer [[Markow-Kette]].
Ein Beispiel für einen Monte-Carlo-Algorithmus ist der [[Miller-Rabin-Test]], bei dem probabilistisch bestimmt wird, ob eine natürliche Zahl [[Primzahl|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]].
 
[[Datei:MonteCarloIntegrationCircle.png|miniatur|Illustration zur Monte-Carlo-Bestimmung von Pi.]]
=== Probabilistische Bestimmung der Zahl Pi ===
Man wählt hierzu zufällige Punkte <math>\left( x, y | x \in \left[ -1..1 \right] \wedge y \in \left[ -1..1 \right]\right) </math> aus und überprüft, ob diese innerhalb des [[Einheitskreis]]es liegen. Über das Verhältnis der Anzahl der Punkte innerhalb und
außerhalb des Kreises kann dann folgendermaßen <math>\ \pi  </math> bestimmt werden:
 
:<math>\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 Quadrat}} = P \left( \text{Im Kreis} \right) </math>
{{Siehe auch|Kreiszahl#Statistische Bestimmung|titel1=Kreiszahl}}
 
=== Numerische Integration ===
[[Datei:NumInt-MC.png|miniatur|[[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. Soll das Integral


:<math>S(f)=\int_0^1 f(x) \, dx</math>
=== Metropolis-Algorithmus ===
Der von Nicholas Metropolis publizierte [[Metropolisalgorithmus]] zur Untersuchung [[Statistische Mechanik|statistisch-mechanischer]] Systeme mittels Computersimulation leitet sich von der Monte-Carlo-Integration ab.  Ein Spezialfall des Algorithmus ist das [[Gibbs-Sampling]].


einer Funktion <math>f</math> berechnet werden,
=== Sequenzielle Monte-Carlo-Methode (SMC) ===
dann wählt man <math>m</math> unabhängige im Intervall <math>[0,1]</math> gleichverteilte Punkte <math>x_1,\dots, x_m</math> und approximiert <math>S(f)</math> durch
[[Sequenzielle Monte-Carlo-Methode]]n eignen sich zur [[Bayessche Statistik|Bayesschen]] Zustandsschätzung von dynamischen Systemen. Ziel ist es, den Systemzustand als Funktion der Zeit auf Basis einer Reihe von Beobachtungen des Systems und [[A priori|A-priori-Kenntnissen]] der Systemdynamik zu schätzen. Dazu wird die komplizierte Wahrscheinlichkeitsdichte des Zustandes diskret durch eine Menge von Partikeln approximiert. Sequentielle Monte-Carlo-Methoden werden auch Partikelfilter genannt.


:<math>S_m(f)=\frac 1m \sum_{i=1}^m f(x_i).</math>
=== Quanten-Monte-Carlo-Methoden (QMC) ===
[[Quanten-Monte-Carlo-Methode]]n werden zur Berechnung physikalischer Observablen in [[Quantenfeldtheorie|quantenfeldtheoretischen]] Modellen benutzt. Beispiele sind Modelle aus der theoretischen [[Festkörperphysik]] wie das [[Hubbard-Modell]] oder das tJ-Modell.


Im allgemeineren Fall von höherdimensionalen Funktionen ist das Vorgehen ähnlich. Sei <math>K\subset\mathbb{R}^n</math> eine beliebige <math>n</math>-dimensionale Menge und <math>f:K\rightarrow \mathbb{R}</math> eine integrierbare Funktion. Um den Wert
=== Kinetische Monte-Carlo-Methode ===
Die [[kinetische Monte-Carlo-Methode]] erlaubt es den zeitlichen Fortschritt eines Systems zu simulieren.


:<math>S(f)=\int_K f(x)\,dx</math>
=== Cluster-Algorithmen ===
Cluster-Algorithmen sind nicht-lokale Verfahren. Hierzu zählen der [[Swendsen-Wang-Algorithmus]] und der [[Wolff-Algorithmus]].


näherungsweise zu berechnen, wählt man zufällig in der Menge <math>K</math> gleichverteilte  Punkte <math>x_i</math> für <math>i=1,\dots,m</math>. Dann approximiert
=== Hybrid-Monte-Carlo-Algorithmus ===
 
Der [[Hybrid-Monte-Carlo-Algorithmus]] ist ein Monte-Carlo-Algorithmus zur Erzeugung von Systemen im kanonischen Zustand. Das Verfahren ist eine Kombination aus Molekulardynamik und Monte-Carlo Methoden her: neue Konfigurationen werden mithilfe von Molekulardynamik vorgeschlagen, jedoch müssen die vorgeschlagenen Konfigurationen z.{{nnbsp}}B. durch das Akzeptanzkriterium akzeptiert werden.
:<math>S_m(f)=\frac{\mathrm{vol}(K)}{m}\sum_{i=1}^mf(x_i)</math>
 
den Wert <math>S(f)</math> in Abhängigkeit von <math>m</math> beliebig genau. Um wie oben vorgestellt Pi zu berechnen, muss man <math>K:=[-1,1]^2</math> und <math>f:=\chi_{\mathrm{Kreis}}</math> als [[Charakteristische Funktion (Mathematik)|charakteristische Funktion]] des Einheitskreises wählen. Hier ist <math>S(\chi_{\mathrm{Kreis}})=\pi</math> gerade die Fläche des Einheitskreises.
 
=== Supercomputer ===
Heutige [[Supercomputer]] ([[Hochleistungsrechnen|HPC]]) basieren auf massivem [[Mehrprozessorsystem|Multiprocessing]] mit vielen tausend Einzelprozessoren, die parallel arbeiten. Diese Gegebenheiten lassen sich besonders gut mit solchen probabilistischen Lösungsverfahren ausnutzen.<ref>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.''</ref>


== Siehe auch ==
== Siehe auch ==
*[[Monte-Carlo-Simulation]]
* [[Liste von Algorithmen]]
*[[Liste von Algorithmen]]


== Literatur ==
== Literatur ==
* R. Motwani, P. Raghavan: ''Randomized Algorithms''. Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5.
* R. Motwani, P. Raghavan: ''Randomized Algorithms''. Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5.
* Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: ''Monte Carlo-Algorithmen.'' Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6.
* Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: ''Monte Carlo-Algorithmen.'' Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6.
== Weblinks ==
{{Commonscat|Monte Carlo method|Monte-Carlo-Methode}}
* {{YouTube|wdafwUKV5WI|Selbstorganisation in einem Monte-Carlo-basierten zellulären Automat}}
* {{YouTube|LWF-aqWdH6U|Einfache Monte-Carlo-Simulation, die die Selbstorganisation von Cu-Atomen zeigt}}
* [http://pigen.de.pn/ Visualisierung der Monte-Carlo-basierten Annäherung von Pi]


== Einzelnachweise ==
== Einzelnachweise ==
Zeile 69: Zeile 58:


[[Kategorie:Algorithmus]]
[[Kategorie:Algorithmus]]
[[Kategorie:Computerchemie]]
[[Kategorie:Computerphysik]]
[[Kategorie:Computerphysik]]

Aktuelle Version vom 9. Februar 2022, 22:58 Uhr

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.

Der Name Monte-Carlo hängt laut Nicholas Metropolis wie folgt mit der Methode zusammen: Stan Ulam hatte einen Onkel, der sich zum Spielen immer Geld von Verwandten geliehen hatte, denn „er musste nach Monte Carlo gehen“.[1]

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

Ein- und zweiseitiger Fehler

Monte-Carlo-Algorithmen gibt es für

  • Suchprobleme[2]
  • Entscheidungsprobleme.[3] Hier wird zwischen ein- und zweiseitigen Fehlern unterschieden:
    • Bei einem zweiseitigen 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 einem einseitigen Fehler zu sprechen und damit „false Negatives“ zu meinen.
  • die Numerische Integration

Diese Konzepte werden im folgenden Abschnitt verdeutlicht, in dem Komplexitätsklassen für Probleme mit Monte-Carlo-Algorithmen definiert werden.

Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen

  • BPP (von englisch bounded error probabilistic polynomial time) 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 (von englisch randomized polynomial time) 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).

Methoden

Alle folgenden Algorithmen gehören zu den Markov-Chain-Monte-Carlo-Verfahren, d. h. die Erzeugung der Zustände geschieht auf der Basis der Konstruktion einer Markow-Kette.

Metropolis-Algorithmus

Der von Nicholas Metropolis publizierte Metropolisalgorithmus zur Untersuchung statistisch-mechanischer Systeme mittels Computersimulation leitet sich von der Monte-Carlo-Integration ab. Ein Spezialfall des Algorithmus ist das Gibbs-Sampling.

Sequenzielle Monte-Carlo-Methode (SMC)

Sequenzielle Monte-Carlo-Methoden eignen sich zur Bayesschen Zustandsschätzung von dynamischen Systemen. Ziel ist es, den Systemzustand als Funktion der Zeit auf Basis einer Reihe von Beobachtungen des Systems und A-priori-Kenntnissen der Systemdynamik zu schätzen. Dazu wird die komplizierte Wahrscheinlichkeitsdichte des Zustandes diskret durch eine Menge von Partikeln approximiert. Sequentielle Monte-Carlo-Methoden werden auch Partikelfilter genannt.

Quanten-Monte-Carlo-Methoden (QMC)

Quanten-Monte-Carlo-Methoden werden zur Berechnung physikalischer Observablen in quantenfeldtheoretischen Modellen benutzt. Beispiele sind Modelle aus der theoretischen Festkörperphysik wie das Hubbard-Modell oder das tJ-Modell.

Kinetische Monte-Carlo-Methode

Die kinetische Monte-Carlo-Methode erlaubt es den zeitlichen Fortschritt eines Systems zu simulieren.

Cluster-Algorithmen

Cluster-Algorithmen sind nicht-lokale Verfahren. Hierzu zählen der Swendsen-Wang-Algorithmus und der Wolff-Algorithmus.

Hybrid-Monte-Carlo-Algorithmus

Der Hybrid-Monte-Carlo-Algorithmus ist ein Monte-Carlo-Algorithmus zur Erzeugung von Systemen im kanonischen Zustand. Das Verfahren ist eine Kombination aus Molekulardynamik und Monte-Carlo Methoden her: neue Konfigurationen werden mithilfe von Molekulardynamik vorgeschlagen, jedoch müssen die vorgeschlagenen Konfigurationen z.Vorlage:NnbspB. durch das Akzeptanzkriterium akzeptiert werden.

Siehe auch

  • Liste von Algorithmen

Literatur

  • R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5.
  • Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6.

Einzelnachweise

  1. ↑ N. Metropolis: BEGINNING of the MONTE CARLO METHOD. In: Los Alamos Science Special Issue. 1987, S. 125–130 (fas.org [PDF]).
  2. ↑ Suchprobleme sind Aufgaben, bei denen eine Lösung zu berechnen ist.
  3. ↑ Entscheidungsprobleme sind Aufgaben, bei denen eine Ja/Nein-Frage zu beantworten ist.
Abgerufen von „https://www.cosmos-indirekt.de/physik_137/index.php?title=Monte-Carlo-Algorithmus&oldid=15110“