Детерминированные алгоритмы в информатике: определение, принцип работы и важность для практических вычислений. Гарантированный результат для одного ввода.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Тип алгоритма в информатике
Type of algorithm in computer science
В информатике детерминированный алгоритм — это алгоритм, который, получив определенный ввод, всегда выдает один и тот же результат, при этом лежащая в основе машина последовательно проходит через одну и ту же последовательность состояний. Детерминированные алгоритмы являются наиболее изученным и распространенным типом алгоритмов, а также одним из самых практичных, поскольку их можно эффективно выполнять на реальных машинах. Формально детерминированный алгоритм вычисляет математическую функцию; функция имеет единственное значение для любого ввода из своей области определения, и алгоритм — это процесс, который производит это конкретное значение в качестве вывода.
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently. Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output.
Формальное определение
Детерминированные алгоритмы можно определить с точки зрения конечного автомата: состояние описывает, что машина делает в конкретный момент времени. Конечные автоматы дискретно переходят из одного состояния в другое. Сразу после ввода данных машина находится в начальном состоянии. Если машина детерминирована, это означает, что с этого момента её текущее состояние однозначно определяет следующее состояние; её путь по множеству состояний предопределён. Следует отметить, что машина может быть детерминированной, но при этом никогда не останавливаться или завершаться, и, следовательно, не выдавать результат. Примеры конкретных абстрактных машин, являющихся детерминированными, включают детерминированную машину Тьюринга и детерминированный конечный автомат.
Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result. Examples of particular abstract machines which are deterministic include the deterministic Turing machine and deterministic finite automaton.
Недостатки детерминизма
В некоторых случаях для программы выгодно проявлять недетерминированное поведение. Например, поведение программы перетасовки карт, используемой в игре в блэкджек, не должно быть предсказуемо игроками, даже если исходный код программы доступен для просмотра. Использование генератора псевдослучайных чисел часто недостаточно для обеспечения невозможности предсказания игроками результата перетасовки. Хитроумный игрок может точно угадать числа, которые выберет генератор, и таким образом заранее определить состав колоды, что позволит ему жульничать; например, группе по безопасности программного обеспечения компании Reliable Software Technologies удалось это сделать для реализации Texas Hold 'em Poker, распространяемой ASF Software, Inc., что позволило им последовательно предсказывать исход раздач заранее. Эти проблемы можно частично решить, используя криптографически стойкий генератор псевдослучайных чисел, но всё равно необходимо использовать непредсказуемое случайное начальное значение для инициализации генератора. Для этого требуется источник недетерминизма, например, тот, который предоставляет аппаратный генератор случайных чисел. Следует отметить, что отрицательный ответ на вопрос о равенстве P и NP не подразумевает, что программы с недетерминированным выводом теоретически более мощны, чем программы с детерминированным выводом. Класс сложности NP (вычислительная сложность) можно определить без какой-либо ссылки на недетерминизм, используя определение, основанное на проверяющем алгоритме.
It is advantageous, in some cases, for a program to exhibit nondeterministic behavior. The behavior of a card shuffling program used in a game of blackjack, for example, should not be predictable by players — even if the source code of the program is visible. The use of a pseudorandom number generator is often not sufficient to ensure that players are unable to predict the outcome of a shuffle. A clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold 'em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time. These problems can be avoided, in part, through the use of a cryptographically secure pseudo random number generator, but it is still necessary for an unpredictable random seed to be used to initialize the generator. For this purpose, a source of nondeterminism is required, such as that provided by a hardware random number generator. Note that a negative answer to the P=NP problem would not imply that programs with nondeterministic output are theoretically more powerful than those with deterministic output. The complexity class NP (complexity) can be defined without any reference to nondeterminism using the verifier based definition.
Ртуть
Функциональный язык программирования Mercury устанавливает различные категории детерминизма для режимов предиката, как описано в справочнике.
The mercury logic functional programming language establishes different determinism categories for predicate modes as explained in the reference.
Ява
В Java значение null может представлять собой неуспешный (недопустимый) результат.
In Java, the null reference value may represent an unsuccessful (out of domain) result.