Лас-Вегас (алгоритм)

Лас-Вегас — вид вероятностного алгоритма.

Идея алгоритма Лас-Вегас состоит в следующем. Если у нас есть некий вероятностный алгоритм ${\displaystyle A}$, который с определённой вероятностью даёт верный результат, и существует возможность алгоритмически проверить результат алгоритма ${\displaystyle A}$ на корректность (скажем, с помощью алгоритма ${\displaystyle K}$), то можно выполнять алгоритм ${\displaystyle A}$ до тех пор, пока проверка не установит, что результат верен:

Выполнить алгоритм ${\displaystyle A}$ с результатом ${\displaystyle r}$ до тех пор, пока ${\displaystyle K(r)}$ не будет истиной. 

Название этому принципу было дано с одной стороны как намек на метод Монте-Карло. С другой стороны это название намекает на «метод выигрыша в казино», которое схоже с процессом работы алгоритма — «если я буду играть ещё и ещё, я когда-нибудь обязательно выиграю».

Следует заметить, что алгоритм Лас-Вегаса гарантирует получение правильного результата. Алгоритм работает за конечное, но не детерминированное время. Можно указать только вероятность Алгоритм результата за заданное время.

Данный псевдокод можно назвать примером алгоритма Лас-Вегас:

function lasvegas() begin     var a := random();          if(verify(a) = true) then         return a; end 

Примером алгоритма, относящегося к классу Лас-Вегас, является алгоритм сортировки Bogosort: данные, которые нужно отсортировать, перемешиваются случайным образом, и затем проверяется, оказались ли они расположенными в нужном порядке. В случае неудачи перемешивание многократно повторяется вплоть до достижения желаемого порядка.

Пусть ${\displaystyle {\mathcal {A}}}$ — алгоритм Лас-Вегаса с ожидаемой временной сложностью ${\displaystyle f(n)}$, где ${\displaystyle n}$ — длина входа. Если остановить ${\displaystyle {\mathcal {A}}}$ после ${\displaystyle \alpha \cdot f(n)}$ шагов (${\displaystyle 0<\alpha <1}$), то мы получим алгоритм Монте-Карло ${\displaystyle {\mathcal {B}}}$ с вероятностью ошибки в ${\displaystyle 1/\alpha }$. Для доказательства теоремы рассмотрим ${\displaystyle x}$ как вход длины ${\displaystyle n}$ и ${\displaystyle T}$ — случайную переменную, описывающую временную сложность ${\displaystyle {\mathcal {A}}}$. Тогда математическое ожидание ${\displaystyle \mathbb {E} [T]\leqslant f(n)}$ и согласно неравенству Маркова: ${\displaystyle \mathbb {P} r[T\geqslant \alpha \cdot f(n)]\leqslant \mathbb {P} r[T\geqslant \alpha \cdot \mathbb {E} [T]]\leqslant 1/\alpha }$.

• Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999
• «Las Vegas algorithm» / Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. NIST. 17 July 2006. (англ.)

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (22 августа 2018)

Это заготовка статьи по математике. Помогите Википедии, дополнив её.