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

Скасування редагування № 19581662 користувача ZvukZTyshyny (обговорення)
м (ZvukZTyshyny перейменував сторінку з Увипадковлений алгоритм на Ймовірнісний алгоритм поверх перенаправлення)
(Скасування редагування № 19581662 користувача ZvukZTyshyny (обговорення))
'''ІмовірніснийУвипадковлений алгоритм''' ({{lang-en|randomized algorithm}}) — це [[алгоритм]], який використовує елемент [[випадковість|випадковості]] як частину своєї логіки. Алгоритм зазвичай використовує [[Дискретний рівномірний розподіл|рівномірно випадкові]] біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в ''середньому'' серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде [[випадкова величина]] визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
 
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і '''ймовірнісні алгоритми''' ({{lang-en|probabilistic algorithms}}), які, залежно від випадкового входу, можуть видати некоректний вислід ([[Алгоритм Монте-Карло]]) або зазнати невдачі в його отриманні ([[Лас-Вегас (алгоритм)|Алгоритм Лас-Вегаса]]), повідомивши про провал або через неможливість завершення.
Однак, у деяких випадках, ймовірнісні алгоритми є єдиним практичним способом розв'язання проблеми.<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 830

редагувань