Идемпотентность

Для понятий алгебры см. Идемпотент (теория колец) и Идемпотентная матрица .

Кнопки включения / выключения поезда панели управления знаками назначения . Нажатие кнопки «Вкл» (зеленой) является идемпотентной операцией, поскольку она имеет одинаковый эффект независимо от того, выполняется ли она один или несколько раз. Аналогично, нажатие кнопки Off является идемпотентным.

Идемпотентность ( Великобритания : / ˌ ɪ d ɛ m ˈ p oʊ t ən s / , США : / ˈ aɪ d ə m -/ ) — это свойство определенных операций в математике и информатике , благодаря которому их можно применять многократно, не изменяя результат за пределами первоначального применения. Понятие идемпотентности возникает в ряде мест в абстрактной алгебре (в частности, в теории проекторов и операторов замыкания ) и функциональном программировании (в котором оно связано со свойством ссылочной прозрачности ).

Этот термин был введен американским математиком Бенджамином Пирсом в 1870 году. в контексте элементов алгебр, которые остаются инвариантными при возведении в положительную целочисленную степень и буквально означает «(качество обладания) той же силой» от idem + potence (та же + мощность).

Определение

Элемент $x$ из набора $S$ оснащен бинарным оператором $\cdot$ называется идемпотентным относительно $\cdot$ если

$x\cdot x=x$.

Бинарная операция $\cdot$ называется идемпотентным, если

$x\cdot x=x$ для всех $x\in S$.

Примеры

• В моноиде $(\mathbb {N} ,\times )$ натуральных чисел с умножением , только $0$ и $1$ являются идемпотентными. Действительно, $0\times 0=0$ и $1\times 1=1$.
• В моноиде $(\mathbb {N} ,+)$ натуральных чисел со сложением , только $0$ является идемпотентным. Действительно, 0 + 0 = 0 .
• В магме $(M,\cdot )$, элемент идентификации $e$ или поглощающий элемент $a$, если он существует, идемпотентен. Действительно, $e\cdot e=e$ и $a\cdot a=a$.
• В группе $(G,\cdot )$, идентификационный элемент $e$ единственный идемпотентный элемент. Действительно, если $x$ является элементом $G$ такой, что $x\cdot x=x$, затем $x\cdot x=x\cdot e$ и наконец $x=e$ умножив слева на элемент обратный $x$.
• В моноидах $({\mathcal {P}}(E),\cup )$ и $({\mathcal {P}}(E),\cap )$ из силового набора ${\mathcal {P}}(E)$ из набора $E$ с установленным объединением $\cup$ и установить пересечение $\cap$ соответственно, $\cup$ и $\cap$ являются идемпотентными. Действительно, $x\cup x=x$ для всех $x\in {\mathcal {P}}(E)$, и $x\cap x=x$ для всех $x\in {\mathcal {P}}(E)$.
• В моноидах $(\{0,1\},\vee )$ и $(\{0,1\},\wedge )$ с булевой области логической дизъюнкцией $\vee$ и логическое соединение $\wedge$ соответственно, $\vee$ и $\wedge$ являются идемпотентными. Действительно, $x\vee x=x$ для всех $x\in \{0,1\}$, и $x\wedge x=x$ для всех $x\in \{0,1\}$.
• В домене GCD (например, в $\mathbb {Z}$), операции НОД и НОК идемпотентны.
• В булевом кольце умножение идемпотентно.
• В тропическом полукольце сложение идемпотентно.
• В кольце квадратичных матриц определитель равен идемпотентной матрицы 0 или 1. Если определитель равен 1, матрица обязательно является единичной матрицей .

Идемпотентные функции

В моноиде $(E^{E},\circ )$ функций из набора $E$ самому себе (см. возведение в степень ) с функциональной композицией $\circ$, идемпотентными элементами являются функции $f\colon E\to E$ такой, что $f\circ f=f$, это такое, что $f(f(x))=f(x)$ для всех $x\in E$ (другими словами, изображение $f(x)$ каждого элемента $x\in E$ является фиксированной точкой $f$). Например:

• абсолютное значение идемпотентно. Действительно, $\operatorname {abs} \circ \operatorname {abs} =\operatorname {abs}$, то есть $\operatorname {abs} (\operatorname {abs} (x))=\operatorname {abs} (x)$ для всех $x$;
• постоянные функции идемпотентны;
• тождественная функция идемпотентна;
• функции пола потолка , ; и дробной части идемпотентны
• действительная часть функции $\mathrm {Re} (z)$ комплексного числа идемпотентно.
• из функция, порождаемая подгруппой набора степеней группы к себе, идемпотентна;
• функция выпуклой оболочки из степенного множества аффинного пространства над вещественными числами сама по себе идемпотентна;
• замыкающие функции и внутренние степенного множества топологического пространства самому себе идемпотентны;
• звезда Клини и функции Клини плюс степенного множества моноида самому себе идемпотентны;
• идемпотентные эндоморфизмы векторного пространства — это его проекции .

Если набор $E$ имеет $n$ элементы, мы можем разделить его на $k$ выбранные фиксированные точки и $n-k$ нефиксированные точки под $f$, а потом $k^{n-k}$ — количество различных идемпотентных функций. Следовательно, учитывая все возможные разбиения,

$\sum _{k=0}^{n}{n \choose k}k^{n-k}$

— общее количество возможных идемпотентных функций на множестве. Целочисленная последовательность количества идемпотентных функций, заданная приведенной выше суммой для n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... начинается с 1, 1, 3, 10, 41. , 196, 1057, 6322, 41393, ... (последовательность A000248 в OEIS ).

Ни свойство быть идемпотентным, ни свойство не быть не сохраняется при композиции функций. В качестве примера для первого, $f(x)=x$ мод 3 и $g(x)=\max(x,5)$ оба идемпотентны, но $f\circ g$ нет, хотя $g\circ f$ бывает. В качестве примера последнего можно привести функцию отрицания $\neg$ в булевой области не идемпотентен, но $\neg \circ \neg$ является. Аналогично, унарное отрицание $-(\cdot )$ действительных чисел не идемпотентно, но $-(\cdot )\circ -(\cdot )$ является. В обоих случаях композиция представляет собой просто тождественную функцию , которая является идемпотентной.

Значение информатики

См. также: Ссылочная прозрачность , Повторный вход (подпрограмма) , Стабильная сортировка и Разделение командных запросов.

В информатике термин идемпотентность может иметь разное значение в зависимости от контекста, в котором он применяется:

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

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

информатики

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

Однако последовательность идемпотентных подпрограмм, в которой хотя бы одна подпрограмма отличается от других, не обязательно является идемпотентной, если более поздняя подпрограмма в последовательности меняет значение, от которого зависит более ранняя подпрограмма - идемпотентность не замыкается при последовательной композиции . Например, предположим, что начальное значение переменной — 3, и существует последовательность подпрограмм, которая считывает переменную, затем изменяет ее на 5, а затем читает ее снова. Каждый шаг в последовательности идемпотентен: оба шага чтения переменной не имеют побочных эффектов, а шаг изменения переменной на 5 всегда будет иметь одинаковый эффект, независимо от того, сколько раз он выполняется. Тем не менее, выполнение всей последовательности один раз дает результат (3, 5), а выполнение ее второй раз дает результат (5, 5), поэтому последовательность не является идемпотентной.

int x = 3;
void inspect() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { inspect(); change(); inspect(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}

В протоколе передачи гипертекста (HTTP) идемпотентность и безопасность являются основными атрибутами, разделяющими методы HTTP . Из основных методов HTTP GET, PUT и DELETE должны быть реализованы идемпотентным образом в соответствии со стандартом, но POST не обязательно. GET извлекает состояние ресурса; PUT обновляет состояние ресурса; и DELETE удаляет ресурс. Как и в примере выше, чтение данных обычно не имеет побочных эффектов, поэтому оно идемпотентно (фактически нуллипотентно ). Обновление и удаление данных данных обычно идемпотентны, если запрос однозначно идентифицирует ресурс и только этот ресурс снова в будущем. PUT и DELETE с уникальными идентификаторами сводятся к простому случаю присвоения переменной значения или нулевого значения соответственно и являются идемпотентными по той же причине; конечный результат всегда тот же, что и результат первоначального выполнения, даже если ответ отличается.

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

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

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

Ожидается , что при переформатировании вывода симпатичная печать будет идемпотентной. Другими словами, если результат уже «красивый», симпатичному принтеру делать нечего.

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

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

Прикладные примеры

Типичная кнопка пешеходного перехода является примером идемпотентной системы.

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

См. также

• Биупорядоченный набор
• Оператор закрытия
• Фиксированная точка (математика)
• Идемпотент кода
• Идемпотентный анализ
• Идемпотентная матрица
• Идемпотентное отношение - обобщение идемпотентности на бинарные отношения.
• Идемпотент (теория колец)
• Инволюция (математика)
• Итерированная функция
• Список матриц
• Нильпотентный
• Чистая функция
• Ссылочная прозрачность

Дальнейшее чтение

• « Идемпотент » в Бесплатном онлайн-словаре по информатике
• Гудирл, КР (1991), регулярные кольца фон Неймана (2-е изд.), Малабар, Флорида: Robert E. Krieger Publishing Co. Inc., стр. xviii+412, ISBN  978-0-89464-632-4 , МР   1150975
• Гунавардена, Джереми (1998), «Введение в идемпотентность» (PDF) , в Гунавардене, Джереми (ред.), Идемпотентность. На основе семинара, Бристоль, Великобритания, 3–7 октября 1994 г. , Кембридж: Cambridge University Press , стр. 1–49, Zbl   0898.16032.
• «Идемпотент» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Хазевинкель, Михель ; Губарени, Надя; Кириченко В.В. (2004), Алгебры, кольца и модули. Том. 1 , Математика и ее приложения, вып. 575, Дордрехт: Kluwer Academic Publishers, стр. xii+380, ISBN  978-1-4020-2690-4 , МР   2106764
• Лам, Тай (2001), Первый курс по некоммутативным кольцам , Тексты для выпускников по математике, том. 131 (2-е изд.), Нью-Йорк: Springer-Verlag, стр. xx+385, doi : 10.1007/978-1-4419-8616-0 , ISBN.  978-0-387-95183-6 , МР   1838439
• Ланг, Серж (1993), Алгебра (Третье изд.), Ридинг, Массачусетс: Аддисон-Уэсли, ISBN  978-0-201-55540-0 , Збл   0848.13001 р. 443
• Пирс, Бенджамин. Линейная ассоциативная алгебра 1870.
• Польчино Мильес, Сезар; Сегал, Сударшан К. (2002), Введение в групповые кольца , алгебры и приложения, том. 1, Kluwer Academic Publishers, стр. 127 , ISBN.  978-1-4020-0238-0 , МР   1896125