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

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

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

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

Определение [ править ]

Элемент х из магмы ( М , •) называется идемпотентом , если: ^{[4] [5]}

х • х = х .

Если все элементы идемпотентны относительно •, то • называется идемпотентным. Формула ∀ x , x • x = x называется законом идемпотентности для •. ^{[6] [7]}

Примеры [ править ]

• Натуральное число 1 является идемпотентным элементом по отношению к умножению (поскольку 1 × 1 = 1), и поэтому равно 0 (поскольку 0 × 0 = 0), но никакое другое натуральное число не является (например, 2 × 2 = 2 не выполняется ). По последней причине умножение натуральных чисел не является идемпотентной операцией. Более формально, в моноиде ( ℕ , ×) идемпотентные элементы равны 0 и 1.
• В магме ( M , •) единичный элемент e или поглощающий элемент a , если он существует, идемпотентен. В самом деле, e • e = e и a • a = a .
• В группе ( G , •) единичный элемент e является единственным идемпотентным элементом. Действительно, если х является элементом G таким образом, что х • х = х , то х • х = х • е и , наконец , х = е умножения слева на обратный элемент из х .
• Взятие пересечения x ∩ y двух множеств x и y является идемпотентной операцией, поскольку x ∩ x всегда равно x . Это означает, что выполняется закон идемпотентности ∀ x , x ∩ x = x . Аналогично, объединение двух множеств - идемпотентная операция. Формально в моноидах (𝒫 ( E ), ∪) и (𝒫 ( E ), ∩) степенного множества множества E с объединением множеств ∪ и пересечением множеств∩ соответственно все элементы идемпотентны; следовательно, ∪ и - идемпотентные операции на ( E ).
• В моноидах ({0, 1}, ∨) и ({0, 1}, ∧) булевой области с логической дизъюнкцией ∨ и логической конъюнкцией ∧ соответственно все элементы идемпотентны.
• В булевом кольце умножение идемпотентно.
• В тропическом полукольце сложение идемпотентно.

Идемпотентные функции [ править ]

В моноиде ( E ^E , ∘) функций из множества E в себя с функциональной композицией ∘ идемпотентными элементами являются функции f : E → E такие, что f ∘ f = f , другими словами такие, что для всех x в E , F ( F ( х )) = е ( х ) (изображение каждого элемента в Й является фиксированной точкой из F ). Например:

• Принимая абсолютное значение абс ( х ) ^[8] из с целого числа х является функцией идемпотентная по следующей причине: абс ( абс ( х )) = абс ( х ) истинно для каждого целого числа х . ^[9] Это означает, что выполняется abs ∘ abs = abs ^[10] , то есть abs является идемпотентным элементом во множестве всех функций (от целых до целых) ^[11] относительно композиции функций. Следовательно, абс удовлетворяет приведенному выше определению идемпотентной функции.

Другие примеры включают:

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

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

${\ displaystyle \ sum _ {k = 0} ^ {n} {n \ select k} k ^ {nk}}$

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

Ни свойство быть идемпотентным, ни свойство не быть не сохраняется при композиции функций. ^[12] В качестве примера для первого, f ( x ) = x mod 3 и g ( x ) = max ( x , 5) оба идемпотентны, но f ∘ g нет, ^[13] хотя g ∘ f случается с быть. ^[14] В качестве примера последнего, функция отрицания ¬ в булевой области не идемпотентна, а ¬ ∘ ¬ такова. Точно так же унарное отрицание - () действительных чисел не идемпотентно, но - () ∘ - () есть.

Значение информатики [ править ]

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

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

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

Примеры информатики [ править ]

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

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

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

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

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

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

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

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

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

Прикладные примеры [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

Поищите идемпотентность в Викисловаре, бесплатном словаре.

В Викиучебнике есть больше по теме: Идемпотентность

В Викиверситете есть учебные ресурсы о Portal: Computer Science

• « Идемпотент » в FOLDOC
• Goodearl, KR (1991), регулярные кольца фон Неймана (2-е изд.), Малабар, Флорида: Robert E. Krieger Publishing Co. Inc., стр. Xviii + 412, ISBN 978-0-89464-632-4, Руководство по ремонту  1150975
• Gunawardena, Джереми (1998), «Введение в идемпотентность» (PDF) , в Gunawardena, Jeremy (ed.), Idempotency. По материалам семинара, Бристоль, Великобритания, 3–7 октября 1994 г. , Кембридж: Cambridge University Press , стр. 1–49, Zbl  0898.16032
• «Идемпотент» , Энциклопедия математики , EMS Press , 2001 [1994]
• Hazewinkel, Michiel ; Губарени, Надия; Кириченко В. В. Алгебры, кольца и модули (2004) . т. 1 , Математика и ее приложения, 575 , Dordrecht: 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, MR  1838439
• Лэнг, Серж (1993), Алгебра (Третье изд.), Чтение, Массачусетс: Addison-Wesley, ISBN 978-0-201-55540-0, Zbl  0848,13001п. 443
• Пирс, Бенджамин. Линейная ассоциативная алгебра 1870.
• Польчино Милиес, Сезар; Сегал, Сударшан К. (2002), Введение в групповые кольца , алгебры и приложения, 1 , Dordrecht: Kluwer Academic Publishers, стр. Xii + 371, DOI : 10.1007 / 978-94-010-0405-3 , ISBN 978-1-4020-0238-0, Руководство по ремонту  1896125