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

Тип алгоритма в информатике

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Меркурий

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

Хаскелл

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

• Недетерминизм или понятие неудачи
  • типы «Может быть» и «Либо» включают в себя понятие успеха в результате.
  • метод error класса Monad может использоваться для сигнализации об исключении как об исключении.
  • Монада Maybe и преобразователь монад MaybeT обеспечивают неудачные вычисления (остановка последовательности вычислений и возврат Nothing) ^[10]
• Нетерминизм/неопределенность с несколькими решениями
  • вы можете получить все возможные результаты вычислений с несколькими результатами, обернув тип результата в монаду MonadPlus . (его метод mzero делает результат неудачным, а mplus собирает успешные результаты). ^[11]

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

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

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

Джава

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

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

• Рандомизированный алгоритм

Рекомендации

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