Увипадковлений алгоритм: відмінності між версіями
[перевірена версія] | [перевірена версія] |
Немає опису редагування |
Немає опису редагування |
||
Рядок 1: | Рядок 1: | ||
'''Увипадковлений алгоритм''' ({{lang-en|randomized algorithm}}) — це [[алгоритм]], який використовує елемент [[випадковість|випадковості]] як частину своєї логіки. Алгоритм зазвичай використовує [[Дискретний рівномірний розподіл|рівномірно випадкові]] біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в ''середньому'' серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде [[випадкова величина]] визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами. |
'''Увипадковлений алгоритм''' ({{lang-en|randomized algorithm}}) — це [[алгоритм]], який використовує елемент [[випадковість|випадковості]] як частину своєї логіки. Алгоритм зазвичай використовує [[Дискретний рівномірний розподіл|рівномірно випадкові]] біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в ''середньому'' серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде [[випадкова величина]] визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами. |
||
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і '''ймовірнісні алгоритми''', які, залежно від випадкового входу, можуть видати некоректний вислід ([[Алгоритм Монте-Карло]]) або зазнати невдачі в його отриманні ([[Алгоритм Лас-Вегасу]]), повідомивши про провал або через не завершення. |
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і '''ймовірнісні алгоритми''' ({{lang-en|probabilistic algorithms}}), які, залежно від випадкового входу, можуть видати некоректний вислід ([[Алгоритм Монте-Карло]]) або зазнати невдачі в його отриманні ([[Алгоритм Лас-Вегасу]]), повідомивши про провал або через не завершення. |
||
[[Категорія:Увипадковлені алгоритми| ]] |
[[Категорія:Увипадковлені алгоритми| ]] |
Версія за 16:39, 30 серпня 2012
Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і ймовірнісні алгоритми (англ. probabilistic algorithms), які, залежно від випадкового входу, можуть видати некоректний вислід (Алгоритм Монте-Карло) або зазнати невдачі в його отриманні (Алгоритм Лас-Вегасу), повідомивши про провал або через не завершення.