Ла-Парра-де-лас-Вегас
- 1 year ago
- 0
- 0
Лас-Вегас — вид вероятностного алгоритма (см. также Алгоритмы Монте-Карло ).
Идея алгоритма Лас-Вегаса состоит в следующем. Если у нас есть некий вероятностный алгоритм , который с определенной вероятностью дает верный результат, и существует возможность алгоритмически проверить результат алгоритма на корректность (скажем, с помощью алгоритма ), то можно выполнять алгоритм до тех пор, пока проверка не установит, что результат верен.
Выполнить алгоритм с результатом до тех пор, пока не будет истиной.
Название этому принципу было дано с одной стороны как намек на метод Монте-Карло . С другой стороны это название намекает на «метод выигрыша в казино», которое схоже с процессом работы алгоритма — «если я буду играть ещё и ещё, я когда-нибудь обязательно выиграю».
Следует заметить, что алгоритм Лас-Вегаса гарантирует получение правильного результата. Алгоритм работает за конечное, но не детерминированное время. Можно указать только вероятность получения результата за заданное время.
Примером алгоритма, относящегося к классу Лас-Вегас, является алгоритм сортировки Bogosort : данные, которые нужно отсортировать, перемешиваются случайным образом, и затем проверяется, оказались ли они расположенными в нужном порядке. В случае неудачи перемешивание многократно повторяется вплоть до достижения желаемого порядка.
Пусть - алгоритм Лас-Вегаса с ожидаемой временной сложностью , где - длина входа. Если остановить после шагов ( ), то мы получим алгоритм Монте-Карло с вероятностью ошибки в . Для доказательства теоремы рассмотрим как вход длины и - случайную переменную, описывающую временную сложность . Тогда математическое ожидание и согласно неравенству Маркова : .
|
Это
заготовка статьи
по
математике
. Помогите Википедии, дополнив её.
|