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

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

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

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

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

Определение

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

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

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

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

Примеры

• В моноиде натуральных чисел с умножением только 0 и 1 идемпотентны. Действительно, и . ${\displaystyle (\mathbb {N} ,\times )}$ ${\displaystyle 0\times 0=0}$ ${\displaystyle 1\times 1=1}$
• В моноиде +) натуральных чисел со сложением только 0 идемпотентен. Действительно, 0 + 0 = 0 . ${\displaystyle (\mathbb {N} ,}$
• В магме единичный элемент или поглощающий элемент , если он существует, идемпотентен. Действительно, и . ${\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\}}$
• В домене НОД (например , в ) операции НОД и LCM идемпотентны. ${\displaystyle \mathbb {Z} }$
• В булевом кольце умножение идемпотентно.
• В тропическом полукольце сложение идемпотентно.
• В кольце квадратичных матриц определитель идемпотентной матрицы равен 0 или 1. Если определитель равен 1, матрица обязательно является единичной матрицей . ^{[ нужна цитата ]}

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

В моноиде функций из множества в себя (см. возведение множества в степень ) с функциональной композицией идемпотентными элементами являются функции такие, что , ^[8] то есть такое, что для всех (другими словами, образ каждого элемента является фиксированным точка ) . Например: ${\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 {\mathcal {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 ).

Ни свойство быть идемпотентным, ни свойство не быть не сохраняется при композиции функций. ^[9] В качестве примера первого, mod 3 и оба являются идемпотентами, но это не так, ^[10] хотя это так. ^[11] В качестве примера последнего, функция отрицания в логической области не является идемпотентной, но является идемпотентной. Точно так же унарное отрицание действительных чисел не является идемпотентным, но является идемпотентным. В обоих случаях композиция представляет собой просто тождественную функцию , которая является идемпотентной. ${\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), поэтому последовательность не является идемпотентной.

интервал х = 3 ; void read () { printf ( «%d \n » , x ); } недействительное изменение () { х = 5 ; } Недействительная последовательность () { прочитать (); изменять (); читать (); }                    int main () { последовательность (); // печатаем последовательность "3\n5\n" (); // печатает "5\n5\n" return 0 ; }        

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

1. «идемпотентность». Оксфордский словарь английского языка (3-е изд.). Издательство Оксфордского университета. 2010.
2. «Идемпотент». Мерриам-Вебстер . Архивировано из оригинала 19 октября 2016 г.
3. Полчино и Сегал 2002, с. 127.
4. Валенца, Роберт (2012). Линейная алгебра: введение в абстрактную математику. Берлин: Springer Science & Business Media. п. 22. ISBN 9781461209010. Элемент s магмы такой, что ss = s , называется идемпотентным .
5. Донедду, Альфред (1976). Polynômes et algèbre linéaire (на французском языке). Париж: Вюиберт. п. 180. Soit M un magma, обратите внимание на мультипликативность. По имени идемпотента M tout élement a de M tel que a ² = a .
6. Джордж Гретцер (2003). Общая теория решеток . Базель: Биркхойзер.Здесь: Раздел 1.2, п.5.
7. Гаррет Биркгоф (1967). Теория решетки . Публикации коллоквиума. Том. 25. Провиденс: Ам. Математика. Соц.. Здесь: Раздел I.5, стр.8.
8. Это уравнение между функциями. Две функции равны, если их области определения и диапазоны совпадают, а их выходные значения совпадают во всей области определения.
9. Если и коммутируют при композиции (т.е. если ), то идемпотентность обоих и подразумевает идемпотентность , поскольку , используя ассоциативность композиции. ${\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}$
10. например , но ${\displaystyle f(g(7))=f(7)=1}$ ${\displaystyle f(g(1))=f(5)=2\neq 1}$
11. также показывает, что коммутация и не является необходимым условием сохранения идемпотентности. ${\displaystyle f}$ ${\displaystyle g}$
12. IETF, Протокол передачи гипертекста (HTTP/1.1): семантика и контент, заархивированные 8 июня 2014 г. на Wayback Machine . См. также Протокол передачи гипертекста .
13. «Идемпотентные методы». Протокол передачи гипертекста (HTTP/1.1): семантика и содержание. сек. 4.2.2. дои : 10.17487/RFC7231 . RFC 7231. Он знает, что повторение запроса будет иметь тот же запланированный эффект, даже если исходный запрос был успешным, хотя ответ может отличаться.
14. Джон Оустерхаут . «Пейджинг по требованию».
15. Марк А. де Круйф. «Компиляторное построение идемпотентных областей и приложения в архитектурном проектировании». 2012. с. 10.
16. «Информация/инструкции по техническим характеристикам пассажирского лифта с тяговым механизмом» (PDF) . Департамент труда Северной Каролины, Лифтовое бюро . 2002. Архивировано из оригинала (PDF) 23 мая 2011 г.Например, эта проектная спецификация включает подробный алгоритм того, когда кабины лифта будут реагировать на последующие вызовы службы поддержки.

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

• «идемпотент» в Бесплатном онлайн-словаре по информатике
• Гудирл, КР (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