Увипадковлений алгоритм

Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.

Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і ймовірнісні алгоритми (англ. probabilistic algorithms), які, залежно від випадкового входу, можуть видати некоректний вислід (Алгоритм Монте-Карло) або зазнати невдачі в його отриманні (Алгоритм Лас-Вегаса), повідомивши про провал або через неможливість завершення.

У другому випадку, випадкового виконання і випадкового виходу, використання терміну «алгоритм» під питанням. У разі випадкового виходу, формально це вже не алгоритм.^[1] Однак, у деяких випадках, ймовірнісні алгоритми є єдиним практичним способом розв'язання проблеми.^[2]

Практично, увипадковлений алгоритм моделюють із використанням генератора псевдовипадкових чисел замість дійсно випадкових біт; таке втілення може відхилятись від очікуваної в теорії поведінки.

Спонука

Як спонукальний приклад, розглянимо задачу знаходження ‘a’ в масиві з n елементів.

Вхід: Масив n≥2 елементів, в якому половина мають значення ‘a’, а інша половина ‘b’.

Вихід: Знайти ‘a’ в масиві.

Ми наведемо дві версії алгоритму, одну типу Лас-Вегас і одну Монте-Карло.

Алгоритм типу Лас-Вегас:

findingA_LV(array A, n)
початок
    повторювати
        Випадковим чином вибрати один з n елементів.
    допоки 'a' не знайдене
кінець

Цей алгоритм досягає мети з імовірністю 1. Кількість ітерацій мінлива і може довільно великою, але очікувана кількість ітерацій це

${\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

Завдяки тому, що це константа, очікуваний час виконання на великій кількості викликів це ${\displaystyle \Theta (1)}$. (Див. Нотація Ландау)

Алгоритм типу Монте Карло:

findingA_MC(array A, n, k)
початок
    i := 0
    повторювати
        Випадковим чином вибрати один з n елементів.
        i := i + 1
    допоки i < k або 'a' не знайдене
кінець

Якщо ‘a’ знайдене, то алгоритм завершився успіхом, інакше алгоритм зазнав невдачі. Після k ітерацій, імовірність знаходження ‘a’ становить:

${\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}$

Цей алготитм не гарантує успіху, але його час виконання обмежений. Кількість ітерацій завжди менша ніж або рівна k. Якщо k константа, то час виконання (очікуваний і абсолютний) це ${\displaystyle \Theta (1)}$.

Увипадковлені алгоритми особливо корисні коли маємо справу зі зловмисним «супротивником» або нападником, який зумисно намагається згодувати алгоритму погані входові дані (див. найгірший випадок складності і змагальний аналіз) такі як в дилемі в'язня. Саме з цієї причини випадковість повсюдна в криптографія. У криптографічних застосуваннях, не можна використовувати пседвовипадкові числа, бо суперник може їх передбачити, зробивши алгоритм по суті детерміністичним. Отже, потрібне або джерело дійсно випадкових чисел, або криптографічно стійкий генератор псевдовипадкових чисел. Інша царина, якій притаманна випадковість це квантові обчислення.

У горішньому прикладі, лас-вегасівський алгоритм завжди видає правильну відповідь, але його час виконання це випадкова величина. Алгоритм Монте-Карло (пов'язаний з методом Монте-Карло для симуляцій) гарантовано завершиться за час обмежений функцією з параметром k, але дозвовляє маленьку ймовірність помилки. Зауважте, що будь-який алгоритм Лас-Вегаського типу можна переробити на алгоритм типу Монте-Карло (через нерівність Маркова), повернувши довільний, можливо неправильний, результат, якщо він не спромігся повернути результат у визначений час. І навпаки, якщо існує дієва процедура перевіряння чи певна відповідь правильна, тоді монте-карлівський алгоритм можна обернути на лас-вегасівський виконуючи монте-карлівський знов і знов допоки не отримали правильну відповідь.

Див. також

• Схема_наближення_до_поліноміального_часу#Увипадковлені_алгоритми

Примітки

1. «Ймовірнісні алгоритми не треба плутати з методами (які я відмовляюсь називати алгоритмами), які видають результат, що з високою ймовірністю правильний. Це суттєво, що алгоритм видає правильний результат (зважаючи на помилки людини чи комп'ютера), навіть якщо це стається за великий проміжок часу.» Henri Cohen (2000). A Course in Computational Algebraic Number Theory. Springer-Verlag, p. 2.
2. «В тестах простоти для дуже великих чисел обраних навмання, шанс наткнутись на значення, яке обманює тест Ферма менша ніж шанс того, що космічна радіація спричинить помилку в перебігу коректного алгоритму. Сприймання алгоритму неадекватним через першу причину, але не через другу показує різницю між математикою й інженерією.» Hal Abelson and Gerald J. Sussman (1996). Structure and Interpretation of Computer Programs. MIT Press, section 1.2 [Архівовано 3 вересня 2006 у Wayback Machine.].