Las-Vegas-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert.[1] Der Begriff wurde 1979 von László Babai im Zusammenhang mit Graphenisomorphie als eine Variante von Monte-Carlo-Algorithmen eingeführt.[2]

Es gibt zwei Definitionen für Las-Vegas-Algorithmen und ihre Zeitkomplexität:

  • Wenn die Zufallsbits nur Einfluss auf die Vorgehensweise des Algorithmus haben, liefert der Las-Vegas-Algorithmus immer ein korrektes Ergebnis, wenn er terminiert.
    Die Zeitkomplexität ist in diesem Fall abhängig von einer Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist.
  • Wenn das Ergebnis der Berechnung eines Algorithmus mit einer Wahrscheinlichkeit korrekt ist und der Algorithmus zugleich mit einer Wahrscheinlichkeit kein Ergebnis liefert, dann ist es ein Las-Vegas-Algorithmus.[3]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Juraj Hromkovič: Randomisierte Algorithmen. Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger. 1. Auflage. Teubner, 2004, ISBN 3-519-00470-4, S. 67.
  2. László Babai: Monte-Carlo algorithms in graph isomorphism testing. Abgerufen am 12. Dezember 2012 (PDF; 232 kB, englisch).
  3. Juraj Hromkovič: Randomisierte Algorithmen. Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger. 1. Auflage. Teubner, 2004, ISBN 3-519-00470-4, S. 67 f.