Zum Inhalt springen

Las-Vegas-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|3519004704}} | {{bibISBN/{{#invoke:URIutil|plainISBN|3519004704}} 

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|3519004704}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 67
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ =

}}{{#ifeq: 0 | 0 

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} 

     }}

| {{#if:||{{#if:{{#invoke:URIutil|plainISBN|3519004704}}|Der BibISBN-Eintrag [[Vorlage:BibISBN/{{#invoke:URIutil|plainISBN|3519004704}}]] ist nicht vorhanden. Bitte prüfe die ISBN und lege ggf. einen {{#ifeq:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|3519004704}}|Las-Vegas-Algorithmus|{{#switch:{{{LINK}}}|JA=|NEIN=}}}}[[[:Vorlage:Neuer Abschnitt/URL]] neuen Eintrag] an.|Die angegebene ISBN „3519004704“ ist fehlerhaft. Bitte prüfe und korrigiere die ISBN.}}{{#ifeq: 0 | 0 | }}}}}}</ref> Der Begriff wurde 1979 von László Babai im Zusammenhang mit Graphenisomorphie als eine Variante von Monte-Carlo-Algorithmen eingeführt.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:László Babai|László Babai: }}{{#if:|{{#if:Monte-Carlo algorithms in graph isomorphism testing|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Monte-Carlo algorithms in graph isomorphism testing}}]{{#if:PDF; 232 kB| (PDF; 232 kB)}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://people.cs.uchicago.edu/~laci/lasvegas79.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Monte-Carlo algorithms in graph isomorphism testing}}}}|[{{#invoke:URLutil|getNormalized|1=https://people.cs.uchicago.edu/~laci/lasvegas79.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Monte-Carlo algorithms in graph isomorphism testing}}}}]}}{{#if:PDF; 232 kB| (PDF; 232 kB{{#if:{{#if: 2012-12-12 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://people.cs.uchicago.edu/~laci/lasvegas79.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://people.cs.uchicago.edu/~laci/lasvegas79.pdf}}%7C%7C}}}}{{#if:Monte-Carlo algorithms in graph isomorphism testing|{{#if:{{#invoke:WLink|isValidLinktext|1=Monte-Carlo algorithms in graph isomorphism testing|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2012-12-12 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2012-12-12 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2012-12-12 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:64936||(?)}}}}}}{{#if: 2012-12-12|;}}}}{{#if: 2012-12-12| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2012-12-12 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2012-12-12|class=Zitationswartung}} }} {{#invoke:DateTime|format|2012-12-12|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:{{#if: 2012-12-12 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF; 232 kB | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2012-12-12 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://people.cs.uchicago.edu/~laci/lasvegas79.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://people.cs.uchicago.edu/~laci/lasvegas79.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://people.cs.uchicago.edu/~laci/lasvegas79.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://people.cs.uchicago.edu/~laci/lasvegas79.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://people.cs.uchicago.edu/~laci/lasvegas79.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://people.cs.uchicago.edu/~laci/lasvegas79.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://people.cs.uchicago.edu/~laci/lasvegas79.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://people.cs.uchicago.edu/~laci/lasvegas79.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://people.cs.uchicago.edu/~laci/lasvegas79.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://people.cs.uchicago.edu/~laci/lasvegas79.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://people.cs.uchicago.edu/~laci/lasvegas79.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://people.cs.uchicago.edu/~laci/lasvegas79.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://people.cs.uchicago.edu/~laci/lasvegas79.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://people.cs.uchicago.edu/~laci/lasvegas79.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</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.
    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.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|3519004704}}

| {{bibISBN/{{#invoke:URIutil|plainISBN|3519004704}} 

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|3519004704}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 67f
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ =

}}{{#ifeq: 0 | 0 

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} 

     }}

| {{#if:||{{#if:{{#invoke:URIutil|plainISBN|3519004704}}|Der BibISBN-Eintrag [[Vorlage:BibISBN/{{#invoke:URIutil|plainISBN|3519004704}}]] ist nicht vorhanden. Bitte prüfe die ISBN und lege ggf. einen {{#ifeq:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|3519004704}}|Las-Vegas-Algorithmus|{{#switch:{{{LINK}}}|JA=|NEIN=}}}}[[[:Vorlage:Neuer Abschnitt/URL]] neuen Eintrag] an.|Die angegebene ISBN „3519004704“ ist fehlerhaft. Bitte prüfe und korrigiere die ISBN.}}{{#ifeq: 0 | 0 | }}}}}}</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

Einzelnachweise

<references/>

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Las-Vegas-Algorithmus&oldid=64936“