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

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

Формально детерминированный алгоритм вычисляет математическую функцию ; функция имеет уникальное значение для любого ввода в своей области , а алгоритм - это процесс, который производит это конкретное значение в качестве вывода.

Формальное определение [ править ]

Детерминированные алгоритмы можно определить в терминах конечного автомата : состояние описывает, что машина делает в определенный момент времени. Конечные автоматы дискретным образом переходят из одного состояния в другое. Сразу после того, как мы вводим ввод, машина находится в исходном состоянии или состоянии запуска . Если машина детерминирована, это означает, что с этого момента ее текущее состояние определяет, каким будет ее следующее состояние; его ход через множество состояний предопределен. Обратите внимание, что машина может быть детерминированной и при этом никогда не останавливаться или заканчиваться и, следовательно, не давать результата.

Примеры конкретных абстрактных машин, которые являются детерминированными, включают детерминированную машину Тьюринга и детерминированный конечный автомат .

Что делает алгоритмы недетерминированными? [ редактировать ]

Различные факторы могут привести к тому, что алгоритм будет вести себя недетерминированным или недетерминированным образом:

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

Хотя настоящие программы редко бывают чисто детерминированными, людям, как и другим программам, легче рассуждать о программах, которые являются детерминированными. По этой причине большинство языков программирования и особенно функциональные языки программирования прилагают усилия, чтобы предотвратить возникновение вышеуказанных событий, кроме как в контролируемых условиях.

Преобладание многоядерных процессоров привело к всплеску интереса к детерминизму в параллельном программировании, и проблемы недетерминизма были хорошо задокументированы. ^{[1] [2]} Было предложено несколько инструментов, помогающих справиться с проблемами ^{[3] [4] [5] [6],} чтобы справиться с тупиками и состояниями гонки .

Недостатки детерминизма [ править ]

В некоторых случаях программе выгодно демонстрировать недетерминированное поведение. Поведение программы тасования карт, используемой , например, в игре в блэкджек , не должно быть предсказуемо игроками, даже если исходный код программы виден. Использование генератора псевдослучайных чиселчасто бывает недостаточно, чтобы игроки не могли предсказать результат тасования. Умный игрок может точно угадать числа, которые выберет генератор, и таким образом заранее определить все содержимое колоды, позволяя ему обмануть; например, Software Security Group в Reliable Software Technologies смогла сделать это для реализации Texas Hold 'em Poker, распространяемой ASF Software, Inc, что позволяет им заранее предсказывать исход рук. ^[7] Этих проблем можно частично избежать за счет использования криптографически безопасного генератора псевдослучайных чисел , но он по-прежнему необходим для непредсказуемого случайного начального числа.для инициализации генератора. Для этой цели требуется источник недетерминизма, например, обеспечиваемый аппаратным генератором случайных чисел .

Обратите внимание, что отрицательный ответ на проблему P = NP не будет означать, что программы с недетерминированным выходом теоретически более мощны, чем программы с детерминированным выходом. Класс сложности NP (сложность) может быть определен без какой-либо ссылки на недетерминизм с использованием определения на основе верификатора .

Категории детерминизма в языках [ править ]

Меркурий [ править ]

Этот язык логико-функционального программирования устанавливает различные категории детерминизма для режимов предикатов, как описано в справочнике. ^{[8] [9]}

Haskell [ править ]

Haskell предоставляет несколько механизмов:

недетерминизм или понятие провала

• то Может быть , и Либо типы включают понятие успеха в результате.
• неудачу метод класса Monad, может быть использован для сигнализации неудачи в качестве исключения.
• монада Maybe и преобразователь монады MaybeT обеспечивают отказ в вычислениях (останавливают последовательность вычислений и возвращают Nothing) ^[10]

детерминизм / non-det с множественными решениями

вы можете получить все возможные результаты вычисления нескольких результатов, заключив его тип результата в монаду MonadPlus . (его метод mzero делает результат неудачным, а mplus собирает успешные результаты). ^[11]

Семейство ML и производные языки [ править ]

Как видно в Standard ML , OCaml и Scala

• Тип опциона включает понятие успеха.

Java [ править ]

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

Ссылки [ править ]