Детермінований алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В інформатиці детермінований алгоритм - це алгоритм , який, з урахуванням конкретних вхідних даних, завжди буде видавати на виході ті ж самі вихідні дані, з основною машиною завжди проходить через ту ж послідовність станів. Детерміновані алгоритми є на сьогоднішній день найбільш вивченим і звичним видом алгоритм, а також одним із найбільш практичних, так як вони можуть бути запущені на реальних машинах ефективно.

Формально детермінований алгоритм обчислює математичну функцію; функція має унікальне значення для будь-яких вхідних даних в своїй області, і алгоритм являє собою процес, який дає на виході певне значення.

Формальне визначення[ред.ред. код]

Детерміновані алгоритми можуть бути визначені в терміні кінцевого автомата: стан описує те, що машина робить в конкретний момент часу. Автомати проходять дискретним способом з одного стану в інший. Тільки після того, як ми вносимо вхідні дані, машина знаходиться в первинному або початковому стані. Якщо машина є детермінованою, це означає, що з цього моменту його поточний стан визначає яким буде наступний стан; його курс через безліч станів визначено. Зауважте, що машина може бути детермінованою і може ніколи не зупинитися чи закінчити якусь дію і, відповідно, не спромогтися надати результат обчислень.

Щодо прикладів конкретних абстрактних машин, які є детермінованими, можна віднести детерміновані машини Тьюринга і детермінований скінченний автомат.

Що робить алгоритми недетермінованими?[ред.ред. код]

Різні фактори можуть змінювати поведінку алгоритму, роблячи її недермінованою:

  • Якщо він використовує зовнішні стани, окрім вхідних даних, таких як введення даних користувачем, глобальна змінна, апаратний таймер значення, випадкове значення, або дані, збережені на жорсткому диску.
  • Якщо він діє таким чином, що, наприклад, якщо він має кілька процесорів, які записують одні й ті ж самі дані у один і той самий час. В даному випадку, точний порядок, в якому кожен процесор записує дані будуть впливати на результат.
  • Якщо апаратна помилка приводить приводить до зміни стану.

Хоча реальні програми рідко є повністю детермінованими, тому що це простіше для людей. З цієї причини, більшість мов програмування і особливо мови функціонального програмування доклали зусиль, щоб запобігти вище описаним подіям, за винятком подій, на контрольованих умовах.

Поширеність багатоядерних процесорів привела до сплеску інтересу до детермінізму в паралельному програмуванні та виклики недетермінованости були добре задокументовані. Цілий ряд інструментів, щоб допомогти впоратися з проблемами, були запропоновані для боротьби з тупиками і умовами гонки.

Недоліки детермінізму[ред.ред. код]

Недетермінована поведінка програми є вигідна в деяких випадках. Поведінка програми карти перетасовки, використовуваної в грі в блекджек, наприклад, не повинні бути передбачуваними гравцями - навіть якщо вихідний код програми видно. Використання генератора псевдовипадкових чисел часто буває недостатньо для того, щоб гравці не в змозі передбачити результат перетасовки. Розумний гравець може вгадати точно число, генератор буде вибирати і таким чином визначити весь вміст колоди завчасно, дозволяючи йому обдурити; наприклад, групи безпеки програмного забезпечення в надійних Software Technologies був в змозі зробити це для реалізації Texas Hold 'Em Poker, який поширюється ASF Software, Inc, що дозволяє їм послідовно передбачити результат руки завчасно. Ці проблеми можна уникнути, зокрема, за рахунок використання криптографічного безпечного генератора псевдовипадкових чисел, але він як і раніше необхідний для непередбачування випадкового числа, використованого для ініціалізації генератора. Для цієї цілі необхідне джерело недетермінізма, таке, яке є згенероване за допомогою апаратного генератора випадкових чисел.

Зверніть увагу, що негативна відповідь на проблеми P = NP не означатиме, що програми з недетермініроваим виходом теоретично більш потужні, ніж з детермінованим . Складність класу NP  може бути визначена без посилання на недетермінізма, використовуючи визначення верифікатор основі.

Детермінізм категорій у мовах[ред.ред. код]

Mercury[ред.ред. код]

Ця логіко-функціональна мова програмування, створює різні категорії для режими детермінізму, які є пояснені в реф.[1][2]

Haskell[ред.ред. код]

Haskell забезпечує кілька механізмів:

недетермінованість або поняття fail
  • типи Maybe і Either включають в себе поняття успіху в результаті.
  • Метод fail класу монади, може бути використаний для сигналу fail як виняток.
  • Монада Maybe і монада MaybeT  перетворює безуспішні обчислення (зупиняє послідовность обчислень і нічого не повертає)[3]
детермінізм з кількома рішеннями
ви можете отримати всі можливі результати множинного результату обчислення, обернувши його результат у монади типу MonadPlus. (метод mzero обробляє безуспішні результати і mplus збирає успішні результати).[4]

Сім`я ML та похідні від неї мови[ред.ред. код]

Як зазначено в стандартному ML, OCaml i Scala

  • Даний тип option  включає в себе поняття успішності.

Java[ред.ред. код]

  • Значення NULL  може представляти невдалий (який не входить в домен) результат.

Посилання[ред.ред. код]

  1. Determinism categories in the Mercury programming language
  2. Mercury predicate modes
  3. Representing failure using the Maybe monad
  4. The class MonadPlus