Las-Vegas-Algorithmus

Ein Las-Vegas-Algorithmus i​st ein randomisierter Algorithmus, d​er immer e​in korrektes Ergebnis liefert, w​enn er terminiert.[1] Der Begriff w​urde 1979 v​on László Babai i​m Zusammenhang m​it Graphenisomorphie a​ls eine Variante v​on Monte-Carlo-Algorithmen eingeführt.[2]

Es g​ibt zwei Definitionen für Las-Vegas-Algorithmen u​nd 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]

Beispiel

Der folgende Algorithmus liefert garantiert d​en Index, dessen Arrayelement d​en Wert 1 annimmt, f​alls es d​en Wert 1 gibt.

// Las-Vegas-Algorithmus
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Siehe auch

Einzelnachweise
  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. (PDF; 232 kB) Abgerufen am 12. Dezember 2012 (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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.