Las-Vegas-Algorithmus - LinkFang.de





Las-Vegas-Algorithmus


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 [math]\geq \frac{1}{2}[/math] korrekt ist und der Algorithmus zugleich mit einer Wahrscheinlichkeit [math]\leq \frac{1}{2}[/math] kein Ergebnis liefert, dann ist es ein Las-Vegas-Algorithmus.[3]

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. Abgerufen am 12. Dezember 2012 (PDF; 232 kB, english).
  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.

Kategorien: Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Las-Vegas-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.