Las-Vegas-Algorithmen

Wiki-Quelltext dieser Seite.

von Gruppe 1

Las-Vegas-Algorithmen sind Algorithmen, die sich niemals irren. Allerdings kann es passieren, dass sie kein Ergebnis finden. Dabei gibt es prinzipiell zwei Sorten von Las-Vegas-Algorithmen bezüglich ihrer 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 eine Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist.

todo: Random-Quicksort

* Soll die Zeitkomplexität des Algorithmus beschränkt werden, liegt die Wahrscheinlichkeit, dass der Algorithmus ein korrektes Ergebnis liefert. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.



Dame n*n


Die Wahrscheinlichkeit, dass ein Las-Vegas-Algorithmus terminiert, lässt sich durch eine Erhöhung der Rechenzeit erkaufen. Es kann jedoch auch sinnvoll sein, eine größere Wahrscheinlichkeit für das Scheitern in Kauf zu nehmen, wenn dadurch die Zeit abnimmt, einen Misserfolg zu erkennen.