Відмінності між версіями «Увипадковлений алгоритм»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
(пр)
м (r2.7.1) (робот додав: fa:الگوریتم‌های تصادفی)
Рядок 20: Рядок 20:
 
[[eo:Hazardigita algoritmo]]
 
[[eo:Hazardigita algoritmo]]
 
[[es:Algoritmo probabilista]]
 
[[es:Algoritmo probabilista]]
  +
[[fa:الگوریتم‌های تصادفی]]
 
[[fr:Algorithme probabiliste]]
 
[[fr:Algorithme probabiliste]]
 
[[he:אלגוריתם אקראי]]
 
[[he:אלגוריתם אקראי]]

Версія за 12:30, 24 листопада 2012

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

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

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

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

Примітки

  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.