WikiSort.ru - Не сортированное

Лас-Вегас — вид вероятностного алгоритма (см. также Метод Монте-Карло).

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

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

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

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

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

Ссылки

• 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.  (англ.)

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 15 февраля 2019 года.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.