Идемпотентность
Идемпоте́нтность (лат. idem «тот же самый» + potens «способный») — свойство объекта или операции при повторном применении операции к объекту давать тот же результат, что и при первом. Термин предложил американский математик Бенджамин Пирс (англ. Benjamin Peirce) в статьях 1870-х годов.
Примеры идемпотентных операций:
- сложение с нулём: [math]\displaystyle{ a = a + 0 = (a+0) + 0 = ((a+0)+0) + 0 = \dots }[/math];
- умножение на единицу: [math]\displaystyle{ x = x * 1 = (x*1) * 1 = ( (x*1) * 1 ) * 1 = \dots }[/math];
- модуль числа: [math]\displaystyle{ |x| = | (|x|) | = | ( | (|x|) | ) | = \dots }[/math];
- выбор максимального значения: [math]\displaystyle{ \max(x,y) = \max( \max(x,y), y ) = \max( x, \max(x,y) ) }[/math];
- вычисление наибольшего общего делителя: [math]\displaystyle{ \operatorname{gcd}(x,y) = \operatorname{gcd}( \operatorname{gcd}(x,y), y ) = \operatorname{gcd}( x, \operatorname{gcd}(x,y) ) }[/math];
- сложение по модулю 2 с нулём: [math]\displaystyle{ a = a \oplus 0 = ( a \oplus 0 ) \oplus 0 = \dots }[/math];
- нахождение остатка от деления: [math]\displaystyle{ r = a\mod b = ( a\mod b )\mod b = \dots }[/math];
- возведение в степень единицы: [math]\displaystyle{ a^1 = (a^1)^1 = ((a^1)^1)^1 \dots }[/math].
Элемент
Идемпотентный элемент (идемпотент) в алгебре — элемент полугруппы, сохраняющийся при умножении самого на себя: [math]\displaystyle{ e^2=e }[/math]. Теорема об идемпотенте гласит: в конечной полугруппе есть идемпотент.
Идемпотентный элемент [math]\displaystyle{ e }[/math] содержит идемпотентный элемент [math]\displaystyle{ f }[/math] (обозначается [math]\displaystyle{ e\geqslant f }[/math]), если [math]\displaystyle{ ef=e=fe }[/math]. Отношение [math]\displaystyle{ \geqslant }[/math] является отношением частичного порядка в множестве [math]\displaystyle{ E }[/math] идемпотентных элементов и называется естественным частичным порядком на множестве [math]\displaystyle{ E }[/math].
Два идемпотентных элемента ассоциативного кольца (которое будет полугруппой по умножению) [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] называются ортогональными, если [math]\displaystyle{ u v = 0 = v u }[/math].
Операция
Идемпотентная бинарная операция в математике — операция, относительно которой всякий элемент обладает идемпотентностью в вышеназванном смысле:
- [math]\displaystyle{ \forall x: \quad x \cdot x = x }[/math].
Этим свойством обладают, например, логическое И и логическое ИЛИ.
Идемпотентная унарная операция — операция, для которой выполняется [math]\displaystyle{ \forall x: f(f(x)) = f(x) }[/math], или [math]\displaystyle{ f \circ f = f }[/math].
Из линейных операторов в [math]\displaystyle{ \mathbb{R}^n }[/math] идемпотентны только тождественный оператор, нулевой оператор и параллельная проекция. Поэтому проектор в алгебре — в том числе в бесконечномерных пространствах — определяется как [math]\displaystyle{ P \circ P = P }[/math].
В информатике
Идемпотентная операция в информатике — действие, многократное повторение которого эквивалентно однократному.
Примером такой операции могут служить GET-запросы в протоколе HTTP. По спецификации, сервер должен возвращать идентичные ответы на идентичные GET-запросы (при условии, что ресурс не изменился). Это позволяет корректно кэшировать эти ответы, снижая нагрузку на сеть.
Для препроцессора языка Си директива «#include "xxx.h"» является идемпотентной, если в заголовочном файле есть защита от двойного включения.
Литература
- Peirce B. Linear Associative Algebra. 1870.
- Gunawardena, Jeremy (1998), An introduction to idempotency, in Gunawardena, Jeremy, Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994, Cambridge: Cambridge University Press, с. 1–49, <http://www.hpl.hp.com/techreports/96/HPL-BRIMS-96-24.pdf>
- Идемпотентность — статья из Математической энциклопедии. Иванова О. А.