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


1. Недетермінірованний алгоритм

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

2. Використання

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

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


3. Приклади

3.1. Список покупок

Уявімо список покупок: список товарів для покупки.

Це можна осмислити двома способами:

  • Як вказівку купити всі ці товари в будь-якому порядку. Це недетермінірованний алгоритм.
  • Як вказівку купити всі ці товари в даному порядку. Це детермінований алгоритм.

3.2. Сортування злиттям

Припустимо ми маємо набір сутностей (скажімо, 300 студентських іспитів), які необхідно відсортувати (скажімо, за номерами студентів).

Один з алгоритмів для цього (називається Сортування злиттям):

  • розбити набір на дві приблизно рівні частини
  • відсортувати обидві половини сортуванням злиттям (тобто рекурсивно)
  • злити результати

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


3.3. Тест простоти

Завдання: дано натуральне число більше одиниці, визначити чи є це число простим.

Недетермінірованний алгоритм наступний:

  1. Взяти будь-яке ціле k таке, що 2 ≤ k ≤ √ (n).
  2. Якщо k є дільником n, зупиниться з відповіддю немає; інакше зупиниться з відповіддю не відомо.

Видно, що алгоритм не завжди дає корисний відповідь, але ніколи не дає неправильної відповіді.

Цей алгоритм недетермінірованний, він не завжди видає вірне рішення, але тільки при певній комбінації виборів. Це приклад пошукового типу недетермінірованного алгоритму.