Детерминированный алгоритм
В информатике — детерминированный алгоритм это алгоритм , который при определенных входных данных всегда будет выдавать один и тот же результат, при этом базовая машина всегда проходит через одну и ту же последовательность состояний. Детерминированные алгоритмы на сегодняшний день являются наиболее изученным и знакомым типом алгоритмов, а также одним из наиболее практичных, поскольку их можно эффективно запускать на реальных машинах.
Формально детерминированный алгоритм вычисляет математическую функцию ; функция имеет уникальное значение для любого входного значения в своей области определения , а алгоритм представляет собой процесс, который выдает это конкретное значение в качестве выходного значения.
Формальное определение [ править ]
Детерминированные алгоритмы можно определить в терминах конечного автомата : состояние описывает, что машина делает в конкретный момент времени. Конечные автоматы дискретным образом переходят из одного состояния в другое. Сразу после того, как мы вводим ввод, машина находится в исходном или стартовом состоянии . Если машина детерминирована, это означает, что с этого момента ее текущее состояние определяет, каким будет ее следующее состояние; ее ход через множество состояний предопределен. Обратите внимание, что машина может быть детерминированной и при этом никогда не останавливаться и не заканчивать работу и, следовательно, не обеспечивать результат.
Примеры конкретных абстрактных машин , которые являются детерминированными, включают детерминированную машину Тьюринга и детерминированный конечный автомат .
Недетерминированные алгоритмы [ править ]
Множество факторов могут привести к тому, что алгоритм будет вести себя недетерминированным или недетерминированным образом:
- Если он использует внешнее состояние, отличное от входных данных, например, пользовательский ввод, глобальную переменную , значение аппаратного таймера, случайное значение или сохраненные данные на диске.
- Если он работает способом, чувствительным к времени, например, если он имеет несколько процессоров, записывающих одни и те же данные одновременно. В этом случае на результат будет влиять точный порядок, в котором каждый процессор записывает свои данные.
- Если аппаратная ошибка приводит к неожиданному изменению его состояния.
Хотя реальные программы редко являются чисто детерминированными, людям, как и другим программам, легче рассуждать о программах, которые таковыми являются. По этой причине большинство языков программирования , и особенно языки функционального программирования, стараются предотвратить возникновение вышеупомянутых событий, за исключением контролируемых условий.
Распространенность многоядерных процессоров привела к всплеску интереса к детерминизму в параллельном программировании, а проблемы недетерминизма хорошо документированы. [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]
- Нетерминизм/неопределенность с несколькими решениями
Семейство ML и производные языки [ править ]
Как видно из Standard ML , OCaml и Scala.
- Тип опциона включает в себя понятие успеха.
Ява [ править ]
В Java значение нулевой ссылки может представлять неудачный результат (вне домена).
См. также [ править ]
Ссылки [ править ]
- ^ Эдвард А. Ли. «Проблема с потоками» (PDF) . Проверено 29 мая 2009 г.
- ^ Боккино-младший, Роберт Л.; Адве, Викрам С.; Адве, Сарита В.; Снир, Марк (2009). Параллельное программирование должно быть детерминированным по умолчанию . Семинар USENIX по актуальным темам параллелизма.
- ^ «Проверка потоков Intel Parallel Inspector» . Проверено 29 мая 2009 г.
- ^ Юань Линь. «Конкуренция данных и обнаружение тупиковых ситуаций с помощью анализатора потоков Sun Studio» (PDF) . Проверено 29 мая 2009 г.
- ^ Интел. «Intel Parallel Inspector» . Проверено 29 мая 2009 г.
- ^ Дэвид Уортингтон. «Intel решает жизненный цикл разработки с помощью Parallel Studio» . Архивировано из оригинала 28 мая 2009 г. Проверено 26 мая 2009 г.
- ^ Макгроу, Гэри ; Виега, Джон . «Заставьте свое программное обеспечение вести себя: Игра в числа: Как обмануть в азартных играх онлайн» . ИБМ . Архивировано из оригинала 13 марта 2008 г. Проверено 2 июля 2007 г.
- ^ «Категории детерминизма в языке программирования Mercury» . Архивировано из оригинала 3 июля 2012 г. Проверено 23 февраля 2013 г.
- ^ «Режимы предикатов Меркурия» . Архивировано из оригинала 3 июля 2012 г. Проверено 25 февраля 2013 г.
- ^ «Представление неудачи с помощью монады Maybe» .
- ^ «Класс MonadPlus» .