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

теорія алгоритмів

У теорії алгоритмів - під терміном «алгоритм» зазвичай розуміється «детермінований» алгоритм. «Недетермінірованного» - відрізняється від свого більш відомого «двійника» можливістю отримання результату різними шляхами ( «детермінований» - слід єдиним шляхом: від даних - до результату. - тоді як деякі шляхи виконання «недетермінірованного» можуть привести до однакового результату, а деякі - до інших результатів). Ці властивості - описані математично: в «недетермінованої» моделі обчислень. відомої як «недетермінований автомат».

Розробка алгоритмів

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

"Список покупок"

Уявімо «список покупок»: список товарів для покупки - що можна осмислити двома способами: як вказівку купити всі ці товари.

• . в будь-якому порядку ( «недетермінований» алгоритм);
• . в даному порядку ( «детермінований» алгоритм).

«Сортування злиттям»

Припустимо, - є набір «сутностей» (скажімо, - 300 студентів), який необхідно «впорядкувати» (скажімо, - по «номерами» студентів). Один з алгоритмів для цього - «сортування злиттям»:

• Розділити набір на двепріблізітельно равниегруппи;
• Відсортувати обегруппи даної сортуванням (тобто «рекурсивно»);
• Об'єднати результати ( «злити воєдино»; див. Назва методу).

Елементи можуть бути «унікально» відсортовані, якщо критерій сортування завжди визначає «повний» порядок (тобто «номера» студентів «унікальні»: не повторюються між собою). Але інакше (наприклад, - якщо сортувати іспити за прізвищами студентів без урахування однофамільців) - результат сортування не визначений: невідомо, яке саме впорядкування вважати вірним; - тобто алгоритм «недетермінований».

«Тест простоти»

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

Рішення. «Недетермінований» алгоритм - наступний:

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

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

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