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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний.

Алгоритм Лас-Вегаса представив Ласло Бабай у 1979, у контексті проблеми визначення чи два графи ізоморфні, як сильнішу версію алгоритму Монте-Карло.[1][2][3] Алгоритм Лас-Вегаса можна використати в ситуаціях коли число можливих розв'язків порівняно обмежене і перевірка правильності кандидата в розв'язки порівняно проста тоді коли обчислення розв'язку складне.

Ім'я покликається до міста Лас-Вегас у штаті Невада, яке добре відоме своїм ігорним бізнесом.

Зв'язок з алгоритмом Монте-Карло[ред.ред. код]

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

Примітки[ред.ред. код]

  1. Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
  2. Леонід Левін, The Tale of One-way Functions, Problems of Information Transmission, vol. 39 (2003), 92-103.
  3. Dan Grundy, Concepts and Calculation in Cryptography, University of Kent, Ph.D. thesis, 2008