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

Алгоритм, поведение и вывод которого могут зависеть от выполнения

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

Различные модели вычислений приводят к различным причинам, по которым алгоритм может быть недетерминированным, и к различным способам оценки его производительности или правильности:

• Параллельный алгоритм может работать по-разному в разных запусках из-за состояния гонки . Это может произойти даже с однопоточным алгоритмом, когда он взаимодействует с внешними по отношению к нему ресурсами. В общем случае считается, что такой алгоритм работает правильно только тогда, когда все возможные запуски дают желаемые результаты.
• Поведение вероятностного алгоритма зависит от генератора случайных чисел, вызываемого алгоритмом. Они подразделяются на алгоритмы Лас-Вегаса , для которых (как и для параллельных алгоритмов) все запуски должны давать правильный вывод, и алгоритмы Монте-Карло , которым разрешено давать сбой или давать неверные результаты с низкой вероятностью. Производительность такого алгоритма часто измеряется вероятностно, например, с помощью анализа его ожидаемого времени .
• В теории вычислительной сложности недетерминизм часто моделируется с использованием явного механизма для принятия недетерминированного выбора, например, в недетерминированной машине Тьюринга . Для этих моделей недетерминированный алгоритм считается работающим правильно, когда для каждого входа существует запуск, который производит желаемый результат, даже когда другие запуски производят неверные результаты. Эта экзистенциальная сила делает недетерминированные алгоритмы такого рода более эффективными, чем известные детерминированные алгоритмы для многих задач. Проблема P против NP инкапсулирует эту предполагаемую большую эффективность, доступную недетерминированным алгоритмам. Алгоритмы такого рода используются для определения классов сложности на основе недетерминированной временной и недетерминированной пространственной сложности. Их можно моделировать с помощью недетерминированного программирования , метода указания недетерминированных алгоритмов и поиска вариантов, которые приводят к правильному запуску, часто с использованием поиска с возвратом .

Понятие недетерминизма было введено Робертом У. Флойдом в 1967 году. ^[1]

Ссылки

1. Роберт В. Флойд (октябрь 1967 г.). «Недетерминированные алгоритмы». Журнал ACM . 14 (4): 636–644. doi : 10.1145/321420.321422 . S2CID  1990464.

Дальнейшее чтение

• Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). MIT Press. ISBN 978-0-262-03384-8.
• "Недетерминированный алгоритм". Национальный институт стандартов и технологий . Получено 7 июля 2013 г.
• «Недетерминированные алгоритмы». New York University Computer Science . Получено 7 июля 2013 г.