Idempotence
En mathématiques et en informatique, l'idempotence signifie qu'une opération a le même effet qu'on l'applique une ou plusieurs fois. Par exemple, la valeur absolue est idempotente : , les deux membres étant égaux à 5. On retrouve ce concept en algèbre générale, en particulier dans la théorie des opérateurs de projection et des opérateurs de clôture, mais aussi en informatique, en particulier en programmation fonctionnelle.
En mathématiques
Définition
Un élément x d'un magma (M, •) est dit idempotent si[1] - [2] :
- x • x = x.
Si tous les éléments de M sont idempotents pour •, alors • est dite idempotente.
Exemples
- Dans un magma (M, •), l'élément neutre e ou l'élément absorbant a, s'il existe, est un élément idempotent. En effet, e • e = e et a • a = a.
- Dans tout magma associatif fini (E, •) non vide, il existe un élément idempotent. En effet, si a est un élément quelconque de E, alors la suite des puissances de a est non injective, donc il existe deux entiers strictement positifs n et p tels que an+p = an, si bien que anp est idempotent.
- Dans un groupe (G, •), l'élément neutre e est le seul élément idempotent. En effet, si x est un élément de G tel que x • x = x, alors x • x = x • e et on en déduit x = e en simplifiant à gauche par x (c'est-à-dire en composant à gauche par l'élément symétrique de x).
- Dans le monoïde (ℕ, ×), les éléments idempotents sont 0 et 1.
- Dans les monoïdes (𝒫(E), ∪) et (𝒫(E), ∩) de l'ensemble des parties d'un ensemble E muni de l'union ensembliste ∪ et de l'intersection ensembliste ∩ respectivement, tout élément est idempotent.
- Dans les monoïdes ({0, 1}, ∨) et ({0, 1}, ∧) du domaine booléen muni de la disjonction logique ∨ et de la conjonction logique ∧ respectivement, tout élément est idempotent.
- Dans le monoïde (EE, ∘) des applications d'un ensemble E dans lui-même muni de la composition de fonctions ∘, les éléments idempotents sont les applications f : E → E telles que f ∘ f = f, autrement dit telles que pour tout élément x de E, f(f(x)) = f(x) (l'image de tout élément de E par f est un point fixe de f). Par exemple :
- l'application identité est idempotente ;
- les applications constantes sont idempotentes ;
- les applications partie entière par défaut, partie entière par excès et partie fractionnaire sont idempotentes ;
- l'application valeur absolue est idempotente ;
- l'application sous-groupe engendré de l'ensemble des parties d'un groupe dans lui-même est idempotente ;
- l'application enveloppe convexe de l'ensemble des parties d'un espace affine réel dans lui-même est idempotente ;
- les applications adhérence et intérieur de l'ensemble des parties d'un espace topologique dans lui-même sont idempotentes ;
- les applications étoile de Kleene et plus de Kleene de l'ensemble des parties d'un monoïde dans lui-même sont idempotentes ;
- les endomorphismes idempotents d'un espace vectoriel sont ses projecteurs.
En informatique
En informatique, le terme peut avoir un sens différent selon le contexte, mais reste néanmoins proche du sens mathématique :
- en programmation impérative, une routine
fest idempotente si l'état du système reste le même après un ou plusieurs appels (par exemple :f(x); f(x);), autrement dit si la fonction de l'espace des états du système dans lui-même associée à la routine est idempotente au sens mathématique.
- en programmation fonctionnelle, une fonction pure est idempotente si elle est idempotente au sens mathématique.
Par exemple : rechercher le nom d'un client dans une base de données est typiquement idempotent, car cela ne change pas la base de données. Passer une commande n'est pas idempotent, car plusieurs invocations résulteront en plusieurs commandes. Annuler une commande au contraire est idempotent car la commande reste annulée quel que soit le nombre d'invocations.
Autre exemple : le tri d'une liste d'éléments est une procédure idempotente. Une fois la liste triée, le fait de la trier à nouveau ne changera pas l'ordre des éléments ; la liste ne sera donc pas modifiée.
Un script SQL d'insertion dans une base de données peut être écrit de manière à être idempotent : les commandes d'insertions peuvent être écrites avec des conditions empêchant la réinsertion de ces mêmes enregistrements. Ce script peut alors être exécuté plusieurs fois sur la même base de données sans aucun risque de duplication de données. Ceci est intéressant dans le cas d'un système qui évolue et qui nécessite de nouvelles insertions lors de nouvelles versions. Ceci permet également aux utilisateurs du logiciel de faire évoluer leur installation à leur rythme, sans devoir toujours passer de la version n à la version n + 1.
Notes et références
- Alfred Doneddu, Polynômes et algèbre linéaire, 1976, p. 180, « Soit M un magma, noté multiplicativement. On nomme idempotent de M tout élément a de M tel que a2 = a. » [lire en ligne]
- Robert J. Valenza, Linear Algebra: An Introduction to Abstract Mathematics, 2012, p. 22, « An element s of a magma such that ss = s is called idempotent. » [lire en ligne]