Что такое детерминированность в информатике кратко

Обновлено: 05.07.2024

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


Вот описание чистой функции из википедии:

  1. Функция всегда вычисляет одинаковое результирующее значение для одних и тех же наборов аргументов. Результирующее значение функции не может зависеть от любой скрытой информации или состояния, которое может изменяться по мере выполнения программы, не может зависеть от любых внешних входных данных от устройств ввода/вывода.
  2. Вычисление результата не должно вызывать любые семантически наблюдаемые побочные эффекты, такие как мутацию изменяемых объектов, или вывод в устройства ввода/вывода.

А вот определение детерминированного алгоритма Национальным Институтом стандартов и технологий (США):

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

Детерминированная и чистая:

Детерминированная, но не чистая:

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

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

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

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

Действительно здорово узнать что-то новое, но еще лучше узнать о том, что ваши знания были неверны.

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

Сколько бы раз мы её не вызывали, передавая туда значение 'cat' , она всегда вернет 'tac' (хотя технически можно написать её и по другому, но смысла в этом никакого, а проблем доставит). В свою очередь, функция, возвращающая случайное число, не является детерминированной, так как у одного и того же входа (даже если он пустой, то есть аргументы не принимаются) мы получим всегда разный результат. Насколько он разный - не важно, даже если хотя бы один из миллиона вызовов вернет что-то другое, эта функция автоматически считается недетерминированной.

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

Побочные эффекты

Вы скорее всего уже заметили (может, подсознательно), что print_r() — это тоже функция. Она принимает на вход данные любого типа и выводит их на экран.

Внимание, вопрос: что возвращает функция print_r() ? Ответ: что бы она ни возвращала, это значение никак не используется.

print_r() выводит что-то на экран, но это не возврат значения, это просто какое-то действие, которое выполняет функция. Вывод на экран и возврат значения из функции — разные и независимые операции. Технически вывод на экран равносилен записи в файл (немного особый, но всё-таки файл). Для понимания этой темы необходимо немного разобраться в устройстве операционных систем, что крайне важно для программистов.

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

Вопрос для самопроверки. Можно ли определить наличие побочных эффектов внутри функции, опираясь только на её возврат?

Когда функция детерминированная и не имеет побочных эффектов, мы называем её "чистой" функцией. Чистые функции:

  • проще читать
  • проще отлаживать
  • проще тестировать
  • не зависят от порядка, в котором они вызываются
  • просто запустить параллельно (одновременно)

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

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

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

Содержание

Формальное определение

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

Что делает алгоритмы недетерминированными?

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

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

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

Недостатки детерминизма

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

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

Категории детерминизма в языках

Меркурий

Этот язык логико-функционального программирования устанавливает различные категории детерминизма для режимов предикатов, как описано в справочнике. [8] [9]

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

Сколько бы раз мы не вызывали эту функцию, передавая туда значение 'hexlet' , она всегда вернет 6 . В свою очередь функция, возвращающая случайное число, не является детерминированной, так как у одного и того же входа (даже если он пустой, то есть параметры не принимаются) мы получим всегда разный результат. Насколько он разный - не важно, даже если хотя бы один из миллиона вызовов вернет что-то другое, эта функция автоматически считается недетерминированной.

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

Читайте также: