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

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

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

Формальное определение

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

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

Что делает алгоритмы недетерминированными?

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

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

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

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

Недостатки детерминизма

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

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

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

Меркурий

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

Haskell

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

недетерминизм или понятие провала
  • то Может быть , и Либо типы включают понятие успеха в результате.
  • неудачу метод класса Monad, может быть использован для сигнализации неудачи в качестве исключения.
  • монада Maybe и преобразователь монады MaybeT обеспечивают отказ в вычислениях (останавливают последовательность вычислений и возвращают Nothing)
детерминизм / non-det с множественными решениями
вы можете получить все возможные результаты вычисления нескольких результатов, заключив его тип результата в монаду MonadPlus . (его метод mzero делает результат неудачным, а mplus собирает успешные результаты).

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

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

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

Джава

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

Смотрите также

использованная литература

  1. ^ Эдвард А. Ли. «Проблема нитей» (PDF) . Проверено 29 мая 2009 .
  2. ^ Bocchino младший, Роберт L .; Adve, Vikram S .; Adve, Sarita V .; Снир, Марк (2009). Параллельное программирование по умолчанию должно быть детерминированным . Семинар USENIX по актуальным темам параллелизма.
  3. ^ "Intel Parallel Inspector Thread Checker" . Проверено 29 мая 2009 .
  4. ^ Юань Линь. «Обнаружение гонки данных и взаимоблокировок с помощью анализатора потоков Sun Studio» (PDF) . Проверено 29 мая 2009 .
  5. ^ Intel. «Intel Parallel Inspector» . Проверено 29 мая 2009 .
  6. ^ Дэвид Уортингтон. «Intel решает жизненный цикл разработки с помощью Parallel Studio» . Архивировано из оригинала на 2009-05-28 . Проверено 26 мая 2009 .
  7. ^ Макгроу, Гэри ; Вьега, Джон . «Сделайте так, чтобы ваше программное обеспечение работало: игра в числа: как обмануть в азартных играх онлайн» . Архивировано из оригинала на 2008-03-13 . Проверено 2 июля 2007 .
  8. ^ «Категории детерминизма в языке программирования Меркурий» . Архивировано из оригинала на 2012-07-03 . Проверено 23 февраля 2013 .
  9. ^ "Режимы предиката Меркурия" . Архивировано из оригинала на 2012-07-03 . Проверено 25 февраля 2013 .
  10. ^ «Представление неудачи с использованием монады Maybe» .
  11. ^ "Класс MonadPlus" .