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

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

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

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

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

Примітки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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..