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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Недетерминированный алгоритм[править | править вики-текст]

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

Использование[править | править вики-текст]

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

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

Примеры[править | править вики-текст]

Список покупок[править | править вики-текст]

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

Это можно осмыслить двумя способами:

  • Как указание купить все эти товары в любом порядке. Это недетерминированный алгоритм.
  • Как указание купить все эти товары в данном порядке. Это детерминированный алгоритм.

Сортировка слиянием[править | править вики-текст]

Допустим, мы имеем набор сущностей (скажем, 300 студентов), которых необходимо отсортировать (скажем, по порядку смертей).

Один из алгоритмов для этого (называется Сортировка слиянием):

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

Элементы могут быть уникально отсортированы, если критерий сортировки всегда определяет полный порядок; т.е. номера студентов уникальны, но если сортировать экзамены по фамилиям студентов и два студента имеют одинаковые фамилии, результат сортировки остаётся неопределённым. В таких случаях, сортировка слиянием всегда будет выдавать один из возможных упорядочиваний, но какое именно остаётся неизвестно, т.е. алгоритм недетерминированный .

Тест простоты[править | править вики-текст]

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

Недетерминированный алгоритм следующий:

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

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

Этот алгоритм недетерминированный, он не всегда выдаёт верное решение, но только при определённой комбинации выборов. Это пример поискового типа недетерминированного алгоритма.

См. также[править | править вики-текст]