Увипадковлений алгоритм
З Вікіпедії, вільної енциклопедії
З Вікіпедії, вільної енциклопедії
Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і ймовірнісні алгоритми (англ. probabilistic algorithms), які, залежно від випадкового входу, можуть видати некоректний вислід (Алгоритм Монте-Карло) або зазнати невдачі в його отриманні (Алгоритм Лас-Вегаса), повідомивши про провал або через неможливість завершення.
У другому випадку, випадкового виконання і випадкового виходу, використання терміну «алгоритм» під питанням. У разі випадкового виходу, формально це вже не алгоритм.[1] Однак, у деяких випадках, ймовірнісні алгоритми є єдиним практичним способом розв'язання проблеми.[2]
Практично, увипадковлений алгоритм моделюють із використанням генератора псевдовипадкових чисел замість дійсно випадкових біт; таке втілення може відхилятись від очікуваної в теорії поведінки.
Як спонукальний приклад, розглянимо задачу знаходження ‘a’ в масиві з n елементів.
Вхід: Масив n≥2 елементів, в якому половина мають значення ‘a’, а інша половина ‘b’.
Вихід: Знайти ‘a’ в масиві.
Ми наведемо дві версії алгоритму, одну типу Лас-Вегас і одну Монте-Карло.
Алгоритм типу Лас-Вегас:
findingA_LV(array A, n)
початок
повторювати
Випадковим чином вибрати один з n елементів.
допоки 'a' не знайдене
кінець
Цей алгоритм досягає мети з імовірністю 1. Кількість ітерацій мінлива і може довільно великою, але очікувана кількість ітерацій це
Завдяки тому, що це константа, очікуваний час виконання на великій кількості викликів це . (Див. Нотація Ландау)
Алгоритм типу Монте Карло:
findingA_MC(array A, n, k)
початок
i := 0
повторювати
Випадковим чином вибрати один з n елементів.
i := i + 1
допоки i < k або 'a' не знайдене
кінець
Якщо ‘a’ знайдене, то алгоритм завершився успіхом, інакше алгоритм зазнав невдачі. Після k ітерацій, імовірність знаходження ‘a’ становить:
Цей алготитм не гарантує успіху, але його час виконання обмежений. Кількість ітерацій завжди менша ніж або рівна k. Якщо k константа, то час виконання (очікуваний і абсолютний) це .
Увипадковлені алгоритми особливо корисні коли маємо справу зі зловмисним «супротивником» або нападником, який зумисно намагається згодувати алгоритму погані входові дані (див. найгірший випадок складності і змагальний аналіз) такі як в дилемі в'язня. Саме з цієї причини випадковість повсюдна в криптографія. У криптографічних застосуваннях, не можна використовувати пседвовипадкові числа, бо суперник може їх передбачити, зробивши алгоритм по суті детерміністичним. Отже, потрібне або джерело дійсно випадкових чисел, або криптографічно стійкий генератор псевдовипадкових чисел. Інша царина, якій притаманна випадковість це квантові обчислення.
У горішньому прикладі, лас-вегасівський алгоритм завжди видає правильну відповідь, але його час виконання це випадкова величина. Алгоритм Монте-Карло (пов'язаний з методом Монте-Карло для симуляцій) гарантовано завершиться за час обмежений функцією з параметром k, але дозвовляє маленьку ймовірність помилки. Зауважте, що будь-який алгоритм Лас-Вегаського типу можна переробити на алгоритм типу Монте-Карло (через нерівність Маркова), повернувши довільний, можливо неправильний, результат, якщо він не спромігся повернути результат у визначений час. І навпаки, якщо існує дієва процедура перевіряння чи певна відповідь правильна, тоді монте-карлівський алгоритм можна обернути на лас-вегасівський виконуючи монте-карлівський знов і знов допоки не отримали правильну відповідь.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.