imported>SchlurcherBot: Bot: http → https

2026-01-28T05:45:03Z

Bot: http → https

Neue Seite

Ein '''Las-Vegas-Algorithmus''' ist ein [[randomisierter Algorithmus]], der immer ein korrektes Ergebnis liefert, wenn er terminiert.<ref>{{BibISBN|3519004704|Seite=67}}</ref> Der Begriff wurde 1979 von [[László Babai]] im Zusammenhang mit [[Graphenisomorphie]] als eine Variante von [[Monte-Carlo-Algorithmus|Monte-Carlo-Algorithmen]] eingeführt.<ref>{{Internetquelle | url=https://people.cs.uchicago.edu/~laci/lasvegas79.pdf | titel=Monte-Carlo algorithms in graph isomorphism testing | zugriff=2012-12-12 | autor=[[László Babai]] | sprache=en | format=PDF; 232 kB }}</ref>

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.<br/>Die Zeitkomplexität ist in diesem Fall abhängig von einer Zufallsvariable. Ein bekanntes Beispiel ist der [[Quicksort|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.<ref>{{BibISBN|3519004704|Seite=67f}}</ref>

== Beispiel==
Der folgende Algorithmus liefert garantiert den Index, dessen Arrayelement den Wert 1 annimmt, falls es den Wert 1 gibt.
<syntaxhighlight lang="java" line="1">
// Las-Vegas-Algorithmus
repeat:
k = RandInt(n)
if A[k] == 1,
return k;
</syntaxhighlight>

== Siehe auch ==
* [[Komplexitätstheorie#Randomisierte_Komplexit.C3.A4tsklassen|Randomisierte Komplexitätsklassen]]

== Einzelnachweise ==
<references/>

[[Kategorie:Algorithmus]]

Las-Vegas-Algorithmus - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https