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

Собственность операций

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

Идемпотентность ( UK : / ˌ ɪ d ɛ m ˈ p oʊ t ən s / , ^[1] US : / ˈ aɪ d ə m - / ) ^[2] — свойство некоторых операций в математике и информатике , при котором они могут применяться многократно без изменения результата за пределами первоначального применения. Понятие идемпотентности возникает в ряде мест в абстрактной алгебре (в частности, в теории проекторов и операторов замыкания ) и функциональном программировании (в котором оно связано со свойством ссылочной прозрачности ).

Термин был введен американским математиком Бенджамином Пирсом в 1870 году ^{[3] [4]} в контексте элементов алгебр, которые остаются инвариантными при возведении в положительную целую степень, и буквально означает «(свойство иметь) ту же самую силу», от idem + potence (тот же самый + сила).

Определение

Элемент множества, снабженный бинарным оператором, называется идемпотентным относительно, если ^{[5] [6]} ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle \cdot }$ ${\displaystyle \cdot }$

${\displaystyle x\cdot x=x}$.

Бинарная операция называется идемпотентной, если [ ^{7] [8]} ${\displaystyle \cdot }$

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

Примеры

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

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

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

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

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

${\displaystyle \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 ).

Ни свойство быть идемпотентным, ни свойство не быть не сохраняется при композиции функций. ^[10] В качестве примера для первого, mod 3 и оба идемпотентны, но не являются, ^[11] хотя случается, что являются. ^[12] В качестве примера для последнего, функция отрицания в булевой области не является идемпотентной, но является. Аналогично, унарное отрицание действительных чисел не является идемпотентным, но является. В обоих случаях композиция является просто функцией тождества , которая является идемпотентной. ${\displaystyle f(x)=x}$ ${\displaystyle g(x)=\max(x,5)}$ ${\displaystyle f\circ g}$ ${\displaystyle g\circ f}$ ${\displaystyle \neg }$ ${\displaystyle \neg \circ \neg }$ ${\displaystyle -(\cdot )}$ ${\displaystyle -(\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 (); // выводит "3\n5\n" sequence (); // выводит "5\n5\n" return 0 ; }        

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

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

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

В архитектуре загрузки-хранения инструкции, которые могут вызвать ошибку страницы, являются идемпотентными. Поэтому, если происходит ошибка страницы, операционная система может загрузить страницу с диска, а затем просто повторно выполнить ошибочную инструкцию. В процессоре, где такие инструкции не являются идемпотентными, работа с ошибками страниц становится гораздо сложнее. ^{[15] [16]}

При переформатировании вывода ожидается, что pretty-printing будет идемпотентным. Другими словами, если вывод уже "красивый", то pretty-printer ничего делать не должен. ^{[ нужна цитата ]}

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

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

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

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

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

Смотрите также

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

Ссылки

1. "idempotence". Оксфордский словарь английского языка (3-е изд.). Oxford University Press. 2010.
2. "идемпотент". Merriam-Webster . Архивировано из оригинала 2016-10-19.
3. Оригинальная рукопись лекции 1870 года перед Национальной академией наук (Вашингтон, округ Колумбия, США): Пирс, Бенджамин (1870) «Линейная ассоциативная алгебра» Со страниц 16-17: «Когда выражение, возведенное в квадрат или в любую более высокую степень, исчезает, его можно назвать нильпотентным ; но когда оно возводится в квадрат или в более высокую степень, оно дает себя в качестве результата, его можно назвать идемпотентным .
   Определяющие уравнения нильпотентных и идемпотентных выражений соответственно A ⁿ = 0 и A ⁿ = A; но в отношении идемпотентных выражений всегда будет предполагаться, что они имеют вид A ⁿ = A, если иное не указано особо».
   • Напечатано: Пирс, Бенджамин (1881). «Линейная ассоциативная алгебра». American Journal of Mathematics . 4 (1): 97–229. doi :10.2307/2369153. JSTOR  2369153. См. стр. 104.
   • Перепечатано: Пирс, Бенджамин (1882). Линейная ассоциативная алгебра (PDF) . Нью-Йорк, Нью-Йорк, США: Д. Ван Ностранд. стр. 8.
4. Полчино и Сехгал 2002, стр. 127.
5. Валенца, Роберт (2012). Линейная алгебра: введение в абстрактную математику. Берлин: Springer Science & Business Media. стр. 22. ISBN 9781461209010Элемент s магмы, такой что ss = s , называется идемпотентным .
6. Донедду, Альфред (1976). Polynômes et algèbre linéaire (на французском языке). Париж: Вюиберт. п. 180. Soit M un magma, обратите внимание на мультипликативность. По имени идемпотента M tout élement a de M tel que a ² = a .
7. Джордж Гретцер (2003). Общая теория решеток . Базель: Birkhäuser. ISBN 978-3-7643-6996-5.Здесь: Раздел 1.2, стр.5.
8. Гаррет Биркгофф (1967). Теория решеток . Colloquium Publications. Том 25. Providence: Am. Math. Soc.. Здесь: Раздел I.5, стр.8.
9. Это уравнение между функциями. Две функции равны, если их области определения и диапазоны совпадают, а их выходные значения совпадают на всей их области определения.
10. Если и коммутируют относительно композиции (т.е. если ), то из идемпотентности обоих и следует идемпотентность , поскольку , используя ассоциативность композиции. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\circ g=g\circ f}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\circ g}$ ${\displaystyle (f\circ g)\circ (f\circ g)=f\circ (g\circ f)\circ g=f\circ (f\circ g)\circ g=(f\circ f)\circ (g\circ g)=f\circ g}$
11. например , но ${\displaystyle f(g(7))=f(7)=1}$ ${\displaystyle f(g(1))=f(5)=2\neq 1}$
12. также показывая, что коммутация и не является необходимым условием сохранения идемпотентности ${\displaystyle f}$ ${\displaystyle g}$
13. IETF, Протокол передачи гипертекста (HTTP/1.1): Семантика и контент Архивировано 2014-06-08 на Wayback Machine . См. также Протокол передачи гипертекста .
14. "Идемпотентные методы". Протокол передачи гипертекста (HTTP/1.1): семантика и содержимое. раздел 4.2.2. doi : 10.17487/RFC7231 . RFC 7231. Он знает, что повторение запроса будет иметь тот же предполагаемый эффект, даже если исходный запрос был успешным, хотя ответ может отличаться.
15. Джон Оустерхаут . «Пейджинг по требованию».
16. Марк А. де Крюйф. «Построение компилятором идемпотентных регионов и применение в проектировании архитектуры». 2012. С. 10.
17. "Информация/инструкции по техническим характеристикам пассажирского лифта с редукторной тягой" (PDF) . Департамент труда Северной Каролины, Бюро лифтов . 2002. Архивировано из оригинала (PDF) 23.05.2011.Например, данная спецификация проекта включает в себя подробный алгоритм того, когда кабины лифта будут реагировать на последующие вызовы на обслуживание.

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

• "idempotent" в Free On-line Dictionary of Computing
• Goodearl, KR (1991), Регулярные кольца фон Неймана (2-е изд.), Malabar, FL: 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
• Лэм, TY (2001), Первый курс по некоммутативным кольцам , Graduate Texts in Mathematics, т. 131 (2-е изд.), Нью-Йорк: Springer-Verlag, стр. xx+385, doi :10.1007/978-1-4419-8616-0, ISBN 978-0-387-95183-6, г-н  1838439
• Ланг, Серж (1993), Алгебра (третье изд.), Чтение, Массачусетс: Addison-Wesley, ISBN 978-0-201-55540-0, ЗБЛ  0848.13001стр. 443
• Пирс, Бенджамин. Линейная ассоциативная алгебра 1870.
• Polcino Milies, César; Sehgal, Sudarshan K. (2002), Введение в групповые кольца, алгебры и приложения, т. 1, Kluwer Academic Publishers, стр. 127, ISBN 978-1-4020-0238-0, г-н  1896125