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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м (Вилучення 16 інтервікі, відтепер доступних на Вікіданих: d:q583461)
м
Рядок 6: Рядок 6:
 
Однак, у деяких випадках, ймовірнісні алгоритми є єдиним практичним способом розв'язання проблеми.<ref>«В [[Тест простоти|тестах простоти]] для дуже великих чисел обраних навмання, шанс наткнутись на значення, яке обманює [[Тест простоти Ферма|тест Ферма]] менша ніж шанс того, що [[космічні промені|космічна радіація]] спричинить помилку в перебігу коректного алгоритму. Сприймання алгоритму неадекватним через першу причину, але не через другу показує різницю між математикою й інженерією.» Hal Abelson and Gerald J. Sussman (1996). ''Structure and Interpretation of Computer Programs''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>
 
Однак, у деяких випадках, ймовірнісні алгоритми є єдиним практичним способом розв'язання проблеми.<ref>«В [[Тест простоти|тестах простоти]] для дуже великих чисел обраних навмання, шанс наткнутись на значення, яке обманює [[Тест простоти Ферма|тест Ферма]] менша ніж шанс того, що [[космічні промені|космічна радіація]] спричинить помилку в перебігу коректного алгоритму. Сприймання алгоритму неадекватним через першу причину, але не через другу показує різницю між математикою й інженерією.» Hal Abelson and Gerald J. Sussman (1996). ''Structure and Interpretation of Computer Programs''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>
   
Практично, увипадковлений алгоритм моделюють із використанням [[Генератор псевдовипадкових чисел|генератора псевдовипадкових чисел]] натомість дійсно випадкових біт; таке втілення може відхилятись від очікуваної в теорії поведінки.
+
Практично, увипадковлений алгоритм моделюють із використанням [[Генератор псевдовипадкових чисел|генератора псевдовипадкових чисел]] замість дійсно випадкових біт; таке втілення може відхилятись від очікуваної в теорії поведінки.
   
 
== Примітки ==
 
== Примітки ==

Версія за 17:37, 24 листопада 2013

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