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

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

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

Основная статья: Недетерминированная машина Тьюринга

В информатике, «недетерминированный алгоритм» — это алгоритм, указывающий несколько путей обработки одних и тех же входных данных, — без какого-либо уточнения, какой именно вариант будет выбран.

Использование

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

В теории алгоритмов — под термином «алгоритм» обычно понимается «детерминированный» алгоритм. «Недетерминированный» — отличается от своего более известного «двойника» возможностью получения результата разными путями («детерминированный» — следует единственным путём: от данных — к результату, — тогда как некоторые пути выполнения «недетерминированного» могут привести к одинаковому результату, а некоторые — к другим результатам). Эти свойства — описаны математически: в «недетерминированной» модели вычислений, известной как «недетерминированный автомат».

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

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

Примеры

«Список покупок»

Представим «список покупок»: список товаров для покупки — что можно осмыслить двумя способами: как указание купить все эти товары...

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

«Сортировка слиянием»

Основная статья: Сортировка слиянием

Допустим, — имеется набор «сущностей» (скажем, — 300 студентов), который необходимо «упорядочить» (скажем, — по «номерам» студентов). Один из алгоритмов для этого — «сортировка слиянием»:

• Разделить набор на две приблизительно равные группы;
• Отсортировать обе группы данной сортировкой (т.е. «рекурсивно»);
• Объединить результаты («слить воедино»; см. название метода).

Элементы могут быть «уникально» отсортированы, если критерий сортировки всегда определяет «полный» порядок (т.е. «номера» студентов «уникальны»: не повторяются между собой). Но иначе (например, — если сортировать экзамены по фамилиям студентов без учёта однофамильцев) — результат сортировки не определён: неизвестно, какое именно упорядочение считать верным; — т.е. алгоритм «недетерминированный».

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

Основная статья: Перебор делителей

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

Решение: «недетерминированный» алгоритм — следующий:

1. Взять любое целое «k» — такое, что 2 ≤ k ≤ √(n);
2. Если «k» является делителем «n» — остановиться с ответом «нет»; иначе — остановиться с ответом «неизвестно».

Видно, что алгоритм не всегда даёт «полезный» ответ, но никогда не даёт неправильного ответа.

Этот алгоритм — «недетерминированный»: он не всегда выдаёт «полезное» решение — но может, при определённой комбинации выборов. Это — пример «поискового» типа «недетерминированного» алгоритма.

См. также

• Детерминационный анализ
• Конечный автомат
• Недетерминированная машина Тьюринга
• Алгоритмы класса NP
• Побочный эффект (программирование)
• Неоднозначная грамматика
• Вероятностный алгоритм