Что такое детерминированная функция

Чистые функции — Введение в программирование

Транскрипт урока

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

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

Это слово пришло из физики и философии. Детерминированная система, это что-то, что даёт одинаковый результат из определённого начального состояния. Некоторые философские теории рассматривают идею предопределения реальности и то, что случается, случается потому что не могло быть иначе. Свободы выбора не существует и вам было суждено посмотреть сегодня это видео.

Отвлеклись, давайте — к делу. В программировании детерминированная функция, это функция, которая всегда производит тот же результат при одинаковых вводных данных:

Вам наверное интересно, как ещё может вести себя функция. Недетерминированная функция непредсказуема, её результат зависит от чего-то ещё.

Например, представим функцию, которая принимает почтовый индекс и возвращает погоду на данный момент. Она, по всей видимости, подключается к метеорологическому серверу через интернет и отдаёт разные результаты в разное время, потому что погода меняется.

Ещё более простой пример — генератор случайных чисел. Обычно в любом языке программирования есть какой-нибудь встроенный способ генерации случайных чисел. В JavaScript он такой:

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

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

Детериминированные функции предсказуемы: они менее хрупкие, о них проще рассуждать и представлять их. Использовать их тоже проще, собирая сложные структуры и программы.

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

Мы должны затронуть ещё одну тему, перед тем как рассматривать самый красивый и замечательный тип функций. Существует понятие — побочные эффекты — то, как функция изменяет внешний мир.

А ваш хороший друг — функция console.log — имеет: она выводит что-то на экран. Эта штука на экране — определённо что-то за рамками функции, это компьютер, мир в котором живёт функция.

Или рассмотрим следующий код:

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

Чем меньше побочных эффектов имеет функция, тем лучше.

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

Всё, что касается чистых функций кажется «проще»: они просты для чтения, для отладки и поиска ошибок, для тестирования. Чистые функции в системе не зависят ни от чего по-определению, поэтому порядок, в котором они вызываются не имеет значения. Это значит, что их легко запустить, например, параллельно — одновременно — на разных процессорах или даже разных компьютерах.

Чистые функции живут вне времени. Само понятие времени, действий, протекающих в какой-то последовательности, не касается чистых функций. Время их не беспокоит. Когда вы смотрите на чистые функции, читаете код, делаете отладку, тестируете или просто используете их — вам не нужно думать о времени, о том, что случилось до и случится после. Это дает некоторую свободу, и все «простые» штуки, касающиеся чистых функций — последствия этого факта.

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

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

Если вы смотрели видео, но не выполняли упражнения и тесты — то обязательно сделайте это. Курс рассчитан именно на это, а видео сами по себе — это только часть процесса. Есть большая разница между «кажется, понял» и «умею».

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

Я надеюсь, что программирование станет важной и интересной частью вашей жизни.

Выводы

Детерминированная функция всегда возвращает одинаковое значение при определённом вводе (аргументы).

surfaceAreaCalculator это детерминированная функция.

Недетерминированная функция не всегда будет возвращать одинаковое значение при определённом вводе.

Функция, которая возвращает погоду на данный момент для какой-нибудь координаты — недетерминированная: погода всегда меняется, поэтому мы не можем быть уверены, какой ответ выдаст функция.

Другой пример — генератор случайных чисел:

Побочные эффекты: то, как функция меняет внешний мир.

surfaceAreaCalculator не имеет никаких побочных эффектов. Она ничего не меняет за пределами своих границ.

Функция console.log имеет побочный эффект: она что-то выводит на экран.

То, что функции возвращают, не имеет ничего общего с тем, как они влияют на внешний мир.

Чем меньше побочных эффектов имеет функция, тем лучше.

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

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

Дополнительные материалы

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Источник

Чистые и детерминированные функции

Перевод статьи Джастина Этеридж (Justin Etheredge), в которой автор объясняет тонкую разницу между детерминированными и чистыми функциями.

Вчера я читал блог Мэтта Подвизоки (Matt Podwysocki) (этот блог, кстати, потрясающий, идите и подпишитесь), и у него есть пост «Recursing into Recursion – Memoization». Отличный пост, если вы хотите познакомиться с мемоизацией. У меня уже был пост об обобщенной функции мемоизации некоторое время назад, поэтому мы будем говорить не о мемоизации. То, что возбудило во мне интерес, было в конце статьи Мэтта:

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

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

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

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

Алгоритм, поведение которого можно полностью предсказать по входным данным.

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

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

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

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

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

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

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

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

Источник

Детерминированные и недетерминированные функции

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

Определяемые пользователями функции имеют несколько свойств, определяющих способность ядра Компонент SQL Server Database Engine индексировать результаты функции как с помощью индексов вычисляемых столбцов, вызывающих функцию, так и с помощью индексированных представлений, которые на нее ссылаются. Детерминизм функции — одно из таких свойств. Например, в представлении нельзя создать кластеризованный индекс, если оно ссылается на какие-либо недетерминированные функции. Дополнительные сведения о свойствах функций, включая детерминизм, см. в разделе Определяемые пользователем функции.

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

Детерминизм встроенных функций

На детерминизм встроенных функций повлиять нельзя. Каждая из них детерминирована или недетерминирована в зависимости от реализации в SQL Server. Например, если вы укажете в запросе предложение ORDER BY, детерминизм функции, используемой в этом запросе, не изменится.

Все встроенные строковые функции являются детерминированными, кроме FORMAT. Список этих функций см. в разделе Строковые функции (Transact-SQL).

Следующие встроенные функции, отличные от строковых функций, всегда детерминированы.

Источник

Детерминированный и недетерминированный алгоритм (формализация)

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

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

Если можете сформулировать лучше, дайте свои определения для детерминированного и недетерминированного алгоритма (стохастический, уже имеет максимально полное и при этом не большое, но понятное определение).

К разветвляющимся алгоритмам можно отнести:

Таким образом, обработка одних и тех же входных данных всегда приводит к одинаковому результату.

Таким образом, обработка одних и тех же входных данных может приводить как к одинаковым, так и к разным результатам.

Иногда, решение задачи сводиться к использованию случайных величин.

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

3 ответа 3

Такие виды алгоритмов были введены в обращение в 1967 году Робертом Флойдом. Если обратиться к первоисточнику, то картина будет следующая:

Определение детерминированного алгоритма вы уже дали в вопросе.

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

Как видите, поведение функции rand() предсказуемо и зависит от исходного внутреннего состояния. Вместе с тем, если вы не знаете исходного состояния, то поведение предсказать будет сложно, если вообще возможно.

Алгоритмы, которые определяются случайными числами, являются подвидом недетерминированных. Их принято называть вероятностными алгоритмами (probabilistic algorithms). Например, к числу таких можно было бы отнести простую нейронную сеть в которой изначальные веса указываются случайными числами. При прочих равных для данного набора данных и данных исходных весов после обучения вы всегда получите те же самые конечные веса. Другим примером алгоритм, который одновременно недетерминированным и вероятностным, может быть сверточная нейронная сеть, которая содержит содержит dropout-cлой. Итоговые веса после обучения в такой сети могут случайно отличаться при тех же входных данных и исходных весах.

Источник

Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс, страница 10

Описание файла

Онлайн просмотр документа «Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс»

Текст 10 страницы из документа «Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс»

удовлетворяющих системе уравнений (суммы по модулю 2):

Теорема 6. Код Хэмминга порядка n содержит 2 n – k наборов, где и исправляет одну ошибку.

Доказательство. Рассмотрим систему уравнений из определения кода Хэмминга

Таким образом, по выходному слову можно определить номер искаженного разряда и восстановить исходное слово.

Замечание. Обычно разряды с номерами 1, 2, 4, 8, …, 2 k –1 называют проверочными (или контрольными), остальные — информационными.

Доказательство. Имеем (теорема 5). Правое неравенство в теореме 7 следует из того, что S₁ (n) = n + 1. Заметим предварительно, что аналогично нельзя получить и левое неравенство, так как

Глава V. Основы теории конечных
автоматов

§35. Понятие ограниченно детерминированных (автоматных) функций, их представление диаграммой Мура.
Единичная задержка

Пусть даны A = <a₁, a₂, …, a_r> — входной алфавит и B = <b₁, b₂, …, b_m> — выходной алфавит. Определим множества A ∞ и B ∞ как множества всевозможных последовательностей в алфавитах A и B соответственно.

Определение 3. Детерминированная функция  : A ∞ B ∞ называется ограниченно детерминированной, если у неё имеется лишь конечное число различных остаточных функций.

Определение 4. Автоматом (инициальным) называется любая шестёрка (A, B, Q, G, F, q₀), где A, B, Q — конечные алфавиты (A называют входным алфавитом, B — выходным алфавитом, Q — множеством состояний), G: A  Q  Q, F: A  Q  B, q₀  Q — начальное состояние.

Входом автомата служит последовательность a(1)a(2)a(3)…a(t)… A * (конечная или бесконечная), выходом автомата служит последовательность z(t), при этом автомат задаётся системой канонических уравнений

Определение 5. Отображение : A ∞  B ∞ называется автоматной функцией, если существует автомат, который реализует это отображение.

Утверждение. Функция является автоматной тогда и только тогда, когда она является ограниченно детерминированной.

Пример. Пусть A = B = Q = <0, 1>и система канонических уравнений выглядит следующим образом:

Такой автомат, очевидно, осуществляет отображение a(1)a(2)…0a(1)a(2)… и называется единичной задержкой.

Определение 6. Диаграммой Мура для автомата называется ориентированный граф с множеством вершин Q, у которого каждой паре (a, q) сопоставляется дуга, идущая из вершины q в вершину, соответствующую G (a, q). Этой дуге приписывается пометка (a, F (a, q)). Особым образом помечена вершина, соответствующая начальному состоянию. Диаграмма Мура однозначно задаёт автомат.

§36. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими
отображений

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

Пусть A = B = <0, 1>, E₂ n — множество всех булевых векторов длины n.

Теорема 1. Схема из функциональных элементов и задержки осуществляет автоматное отображение.

Доказательство. 1) Пусть в схеме имеется r элементов задержки. Пусть i-я задержка R_i приписана вершине v_i, в которую идёт дуга из вершины w_i. Для всех i = 1, …, r удалим из СФЭЗ дуги (w_i, v_i). По определению СФЭЗ в полученном после этого графе не будет ориентированных циклов и он, тем самым будет представлять собой СФЭ. Входами этой СФЭ будут все входы исходной схемы, а также все вершины v_i, i = 1, …, r (заметим, что все они различны и отличны от входов исходной схемы). Выходами полученной СФЭ объявим все выходы исходной схемы и вершины w_i, i = 1, …, r. Пусть в исходной схеме выходам приписаны переменные z₁, …, z_m, входам — переменные x₁, …, x_n. Вершинам v_i припишем переменные q‘₁, …, q‘_r, а вершинам w_i — переменные q₁, …, q_r. В соответствии с определением функционирования СФЭ, для некоторых функций алгебры логики f_i, g_j справедливо:

Естественно считать, что равенства (1) выполняются в каждый момент времени t = 1, 2, 3,…, то есть

Так как, в соответствии с каноническими уравнениями элемента единичной задержки его выход в момент t совпадает с его входом в момент t – 1, то естественно считать, что в исходной схеме q‘_i (t) = q_i (t – 1) при
t = 1, 2, … для всех i = 1, …, r, где q_i (0) = 0. Тогда равенства (2) принимают вид (где i = 1, …, m и j = 1, …, r):

Полученные равенства определяют функционирование СФЭЗ и называются её каноническими уравнениями.

§37. Моделирование автоматной функции схемой из
функциональных элементов и элементов задержки

Теорема 2. Для любой автоматной функции существует моделирующая её СФЭЗ в базисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элемента задержки.

Тогда можно построить схему из функциональных элементов в базисе <,&, > с n + r входами и m + r выходами, реализующую семейство функций

Источник