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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м
Рядок 1: Рядок 1:
 
'''Увипадковлений алгоритм''' ({{lang-en|randomized algorithm}}) — це [[алгоритм]], який використовує елемент [[випадковість|випадковості]] як частину своєї логіки. Алгоритм зазвичай використовує [[Дискретний рівномірний розподіл|рівномірно випадкові]] біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в ''середньому'' серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде [[випадкова величина]] визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
 
'''Увипадковлений алгоритм''' ({{lang-en|randomized algorithm}}) — це [[алгоритм]], який використовує елемент [[випадковість|випадковості]] як частину своєї логіки. Алгоритм зазвичай використовує [[Дискретний рівномірний розподіл|рівномірно випадкові]] біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в ''середньому'' серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде [[випадкова величина]] визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
   
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і '''ймовірнісні алгоритми''' ({{lang-en|probabilistic algorithms}}), які, залежно від випадкового входу, можуть видати некоректний вислід ([[Алгоритм Монте-Карло]]) або зазнати невдачі в його отриманні ([[Алгоритм Лас-Вегасу]]), повідомивши про провал або через неможливість завершення.
+
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і '''ймовірнісні алгоритми''' ({{lang-en|probabilistic algorithms}}), які, залежно від випадкового входу, можуть видати некоректний вислід ([[Алгоритм Монте-Карло]]) або зазнати невдачі в його отриманні ([[Лас-Вегас (алгоритм)|Алгоритм Лас-Вегаса]]), повідомивши про провал або через неможливість завершення.
   
 
У другому випадку, випадкового виконання і випадкового виходу, використання терміну «алгоритм» під питанням. У разі випадкового виходу, формально це вже не алгоритм.<ref>«Ймовірнісні алгоритми не треба плутати з методами (які я відмовляюсь називати алгоритмами), які видають результат, що з високою ймовірністю правильний. Це суттєво, що алгоритм видає правильний результат (зважаючи на помилки людини чи комп'ютера), навіть якщо це стається за великий проміжок часу.» Henri Cohen (2000). ''A Course in Computational Algebraic Number Theory''. Springer-Verlag, p. 2.</ref>
 
У другому випадку, випадкового виконання і випадкового виходу, використання терміну «алгоритм» під питанням. У разі випадкового виходу, формально це вже не алгоритм.<ref>«Ймовірнісні алгоритми не треба плутати з методами (які я відмовляюсь називати алгоритмами), які видають результат, що з високою ймовірністю правильний. Це суттєво, що алгоритм видає правильний результат (зважаючи на помилки людини чи комп'ютера), навіть якщо це стається за великий проміжок часу.» Henri Cohen (2000). ''A Course in Computational Algebraic Number Theory''. Springer-Verlag, p. 2.</ref>

Версія за 06:15, 11 листопада 2014

Увипадковлений алгоритм (англ. 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.