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

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

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

• 1 Формальное определение
• 2 Что делает алгоритмы недетерминированными?
• 3 Недостатки детерминизма
• 4 Категории детерминизма в языках
  • 4.1 Mercury
  • 4.2 Haskell
  • 4.3 Семейство ML и производные языки
  • 4.4 Java
• 5 Ссылки

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

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

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

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

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

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

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

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

Меркурий

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

Haskell

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

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

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

детерминизм / не-det с несколькими решениями

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

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

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

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

Java

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

Ссылки

1. ^Эдвард А. Ли. «Проблема нитей» (PDF). Проверено 29 мая 2009 г.
2. ^Боккино-младший, Роберт Л.; 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». Архивировано с оригинального 28 мая 2009 г. Проверено 26 мая 2009 г.
7. ^Гэри МакГро и Джон Виега. Заставьте свою программу вести себя: Игра цифрами: Как обмануть в азартных играх онлайн. http://www.ibm.com/developerworks/library/s-playing/#h4
8. ^«Категории детерминизма в языке программирования Mercury». Архивировано с оригинального 03.07.2012. Проверено 23 февраля 2013 г.
9. ^"Режимы предиката Mercury". Архивировано с оригинального 03.07.2012. Проверено 25 февраля 2013 г.
10. ^Представление сбоя с помощью монады Maybe
11. ^Класс MonadPlus