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

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

редагування