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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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