Детерминированный алгоритм
В информатике — детерминированный алгоритм это алгоритм , который при определенных входных данных всегда будет выдавать один и тот же результат, при этом базовая машина всегда проходит через одну и ту же последовательность состояний. Детерминированные алгоритмы на сегодняшний день являются наиболее изученным и знакомым типом алгоритмов, а также одним из наиболее практичных, поскольку их можно эффективно запускать на реальных машинах.
Формально детерминированный алгоритм вычисляет математическую функцию ; функция имеет уникальное значение для любого входного значения в своей области определения , а алгоритм представляет собой процесс, который создает это конкретное значение в качестве выходного.
Формальное определение [ править ]
Детерминированные алгоритмы можно определить в терминах конечного автомата : состояние описывает, что машина делает в конкретный момент времени. Конечные автоматы дискретно переходят из одного состояния в другое. Сразу после того, как мы вводим ввод, машина находится в исходном или стартовом состоянии . Если машина детерминирована, это означает, что с этого момента ее текущее состояние определяет, каким будет ее следующее состояние; ее ход через множество состояний предопределен. Обратите внимание, что машина может быть детерминированной и при этом никогда не останавливаться и не заканчивать работу и, следовательно, не обеспечивать результат.
Примеры конкретных абстрактных машин , которые являются детерминированными, включают детерминированную машину Тьюринга и детерминированный конечный автомат .
Недетерминированные алгоритмы [ править ]
Множество факторов могут привести к тому, что алгоритм будет вести себя недетерминированным или недетерминированным образом:
- Если он использует внешнее состояние, отличное от входных данных, например пользовательский ввод, глобальную переменную , значение аппаратного таймера, случайное значение или сохраненные данные на диске.
- Если он работает способом, чувствительным к времени, например, если он имеет несколько процессоров, записывающих одни и те же данные одновременно. В этом случае на результат будет влиять точный порядок, в котором каждый процессор записывает свои данные.
- Если аппаратная ошибка приводит к неожиданному изменению его состояния.
Хотя реальные программы редко являются чисто детерминированными, людям, как и другим программам, легче рассуждать о программах, которые таковыми являются. По этой причине большинство языков программирования , и особенно языки функционального программирования , стараются предотвратить возникновение вышеупомянутых событий, за исключением контролируемых условий.
Распространенность многоядерных процессоров привела к всплеску интереса к детерминизму в параллельном программировании, а проблемы недетерминизма хорошо документированы. [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» .