В інформатиці детермінований алгоритм — це алгоритм, який, з урахуванням конкретних вхідних даних, завжди буде видавати ті ж самі вихідні дані, а основна машина завжди проходить через однакову послідовність станів. Детерміновані алгоритми є на сьогоднішній день найвивченішим і найзвичнішим видом алгоритмів, а також одним із найпрактичніших, оскільки вони можуть бути запущені на реальних машинах ефективно.
Формально детермінований алгоритм обчислює математичну функцію; функція має унікальне значення для будь-яких вхідних даних в своїй області, і алгоритм являє собою процес, який дає на виході певне значення.
Формальне визначення
Детерміновані алгоритми можуть бути визначені в терміні кінцевого автомата: стан описує те, що машина робить в конкретний момент часу. Автомати проходять дискретним способом з одного стану в інший. Тільки після того, як ми вносимо вхідні дані, машина знаходиться в первинному або початковому стані. Якщо машина є детермінованою, це означає, що з цього моменту його поточний стан визначає яким буде наступний стан; його курс через безліч станів визначено. Зауважте, що машина може бути детермінованою і може ніколи не зупинитися чи закінчити якусь дію і, відповідно, не спромогтися надати результат обчислень.
Щодо прикладів конкретних абстрактних машин, які є детермінованими, можна віднести детерміновані машини Тьюринга і детермінований скінченний автомат.
Що робить алгоритми недетермінованими?
Різні фактори можуть змінювати поведінку алгоритму, роблячи її недермінованою:
- Якщо він використовує зовнішні стани, окрім вхідних даних, таких як введення даних користувачем, глобальна змінна, апаратний таймер значення, випадкове значення, або дані, збережені на жорсткому диску.
- Якщо він діє таким чином, що, наприклад, якщо він має кілька процесорів, які записують одні й ті ж самі дані у один і той самий час. В даному випадку, точний порядок, в якому кожен процесор записує дані будуть впливати на результат.
- Якщо апаратна помилка приводить до зміни стану.
Хоча реальні програми рідко є повністю детермінованими, тому що це простіше для людей. З цієї причини, більшість мов програмування і особливо мови функціонального програмування доклали зусиль, щоб запобігти вище описаним подіям, за винятком подій, на контрольованих умовах.
Поширеність багатоядерних процесорів привела до сплеску інтересу до детермінізму в паралельному програмуванні та виклики недетермінованости були добре задокументовані. Цілий ряд інструментів, щоб допомогти впоратися з проблемами, були запропоновані для боротьби з тупиками і умовами гонки.
Недоліки детермінізму
Недетермінована поведінка програми є вигідна в деяких випадках. Поведінка програми карти перетасовки, використовуваної в грі в блекджек, наприклад, не повинні бути передбачуваними гравцями — навіть якщо вихідний код програми видно. Використання генератора псевдовипадкових чисел часто буває недостатньо для того, щоб гравці не в змозі передбачити результат перетасовки. Розумний гравець може вгадати точно число, генератор буде вибирати і таким чином визначити весь вміст колоди завчасно, дозволяючи йому обдурити; наприклад, групи безпеки програмного забезпечення в надійних Software Technologies був в змозі зробити це для реалізації Texas Hold 'Em Poker, який поширюється ASF Software, Inc, що дозволяє їм послідовно передбачити результат руки завчасно. Ці проблеми можна уникнути, зокрема, за рахунок використання криптографічного безпечного генератора псевдовипадкових чисел, але він як і раніше необхідний для непередбачування випадкового числа, використованого для ініціалізації генератора. Для цієї цілі необхідне джерело недетермінізма, таке, яке є згенероване за допомогою апаратного генератора випадкових чисел.
Зверніть увагу, що негативна відповідь на проблеми P = NP не означатиме, що програми з недетермініроваим виходом теоретично більш потужні, ніж з детермінованим . Складність класу NP може бути визначена без посилання на недетермінізма, використовуючи визначення верифікатор основі.
Детермінізм категорій у мовах
Mercury
Ця логіко-функціональна мова програмування, створює різні категорії для режими детермінізму, які є пояснені в реф.[1][2]
Haskell забезпечує кілька механізмів:
- недетермінованість або поняття fail
- типи Maybe і Either включають в себе поняття успіху в результаті.
- Метод fail класу монади, може бути використаний для сигналу fail як виняток.
- Монада Maybe і монада MaybeT перетворює безуспішні обчислення (зупиняє послідовность обчислень і нічого не повертає)[3]
- детермінізм з кількома рішеннями
- ви можете отримати всі можливі результати множинного результату обчислення, обернувши його результат у монади типу MonadPlus. (метод mzero обробляє безуспішні результати і mplus збирає успішні результати).[4]
Сім'я ML та похідні від неї мови
Як зазначено в стандартному ML, OCaml i Scala
- Даний тип option включає в себе поняття успішності.
- Значення NULL може представляти невдалий (який не входить в домен) результат.
Примітки
