В информатике детерминированный алгоритм — это алгоритм , который при заданном вводе всегда будет выдавать один и тот же вывод, при этом базовая машина всегда будет проходить через одну и ту же последовательность состояний. Детерминированные алгоритмы — это, безусловно, наиболее изученный и знакомый тип алгоритма, а также один из самых практичных, поскольку их можно эффективно запускать на реальных машинах.
Формально детерминированный алгоритм вычисляет математическую функцию ; функция имеет уникальное значение для любого входного значения в своей области определения , а алгоритм представляет собой процесс, который выдает это конкретное значение в качестве выходного значения.
Детерминированные алгоритмы можно определить в терминах конечного автомата : состояние описывает, что делает автомат в определенный момент времени. Конечные автоматы дискретно переходят из одного состояния в другое. Сразу после ввода входных данных автомат находится в своем начальном состоянии или начальном состоянии . Если автомат детерминирован, это означает, что с этого момента его текущее состояние определяет, каким будет его следующее состояние; его путь через набор состояний предопределен. Обратите внимание, что автомат может быть детерминированным и при этом никогда не останавливаться и не заканчивать работу, и, следовательно, не выдавать результат.
Примерами конкретных абстрактных машин , которые являются детерминированными, являются детерминированная машина Тьюринга и детерминированный конечный автомат .
Различные факторы могут привести к тому, что алгоритм будет вести себя недетерминированным или недетерминированным образом:
Хотя реальные программы редко бывают чисто детерминированными, людям и другим программам проще рассуждать о программах, которые таковыми являются. По этой причине большинство языков программирования и особенно языки функционального программирования прилагают усилия для предотвращения возникновения вышеуказанных событий, за исключением контролируемых условий.
Распространенность многоядерных процессоров привела к всплеску интереса к детерминизму в параллельном программировании, а проблемы недетерминизма были хорошо документированы. [1] [2] Было предложено несколько инструментов, помогающих справиться с проблемами [3] [4] [5] [6] для борьбы с взаимоблокировками и состояниями гонки .
В некоторых случаях для программы выгодно демонстрировать недетерминированное поведение. Например, поведение программы тасования карт, используемой в игре в блэкджек , не должно быть предсказуемым игроками — даже если исходный код программы виден. Использование генератора псевдослучайных чисел часто недостаточно для того, чтобы гарантировать, что игроки не смогут предсказать результат тасования. Умный игрок может точно угадать числа, которые выберет генератор, и таким образом определить все содержимое колоды заранее, что позволит ему обмануть; например, группа безопасности программного обеспечения в Reliable Software Technologies смогла сделать это для реализации Texas Hold 'em Poker, распространяемой ASF Software, Inc, что позволило им последовательно предсказывать результат рук заранее. [7] Этих проблем можно избежать, отчасти, за счет использования криптографически безопасного генератора псевдослучайных чисел , но все равно необходимо использовать непредсказуемое случайное начальное число для инициализации генератора. Для этой цели необходим источник недетерминизма, например, такой, который обеспечивается аппаратным генератором случайных чисел .
Обратите внимание, что отрицательный ответ на проблему P=NP не будет означать, что программы с недетерминированным выводом теоретически более мощные, чем программы с детерминированным выводом. Класс сложности NP (complexity) может быть определен без какой-либо ссылки на недетерминизм с использованием определения на основе верификатора .
Логико-функциональный язык программирования Mercury устанавливает различные категории детерминизма для предикатных режимов , как поясняется в ссылке. [8] [9]
Haskell предоставляет несколько механизмов:
Как видно из Standard ML , OCaml и Scala
В Java значение ссылки null может представлять собой неудачный (внедомен) результат.