Algoritmus typu Las Vegas

Algoritmus typu Las Vegas je v teoretické informatice označení pro takový pravděpodobnostní algoritmus, který vždy na konci vrátí správný výsledek, ovšem s malou pravděpodobností může běžet velmi dlouho a nebo i vyžadovat rozsáhlé zdroje, než skončí. Tím se liší od obecných algoritmů typu Monte Carlo, které mohou s malou pravděpodobností vrátit špatný výsledek. Na obecný algoritmus typu Monte Carlo lze obvykle algoritmus typu Las Vegas převést omezením zdrojů (např. času), po jejichž vyčerpání vrátí algoritmus náhodný výsledek.

Koncept algoritům typu Las Vegas pojmenoval v roce 1979 maďarský matematik László Babai při zkoumání grafových izomorfismů.

Reference

Kategorie:Algoritmy