Idempotenz

An/Aus Knöpfe eines Zuges Zielzeichen Schalttafel. Drücken Sie die An Taste (grün) ist eine idempotente Operation, da sie den gleichen Effekt hat, unabhängig davon, ob es einmal oder mehrmals ausgeführt wird. Ebenso drücken Aus ist idempotent.

Idempotenz (Vereinigtes Königreich: /ˌɪdɛmˈpoʊtəns/,^[1] UNS: /ˈaɪdəm-/)^[2] ist das Eigentum von bestimmt Operationen in Mathematik und Informatik wobei sie mehrmals angewendet werden können, ohne das Ergebnis über die anfängliche Anwendung hinaus zu ändern. Das Konzept der Idempotenz ergibt sich an einer Reihe von Orten an Zusammenfassung Algebra (insbesondere in der Theorie von Projektoren und Verschlussbetreiber) und Funktionelle Programmierung (in dem es mit der Eigenschaft von verbunden ist Referenztransparenz).

Der Begriff wurde vom amerikanischen Mathematiker eingeführt Benjamin Peirce 1870^[3] im Kontext von Elementen von Algebren, die in einer positiven ganzzahligen Kraft invariant bleiben und wörtlich "(die Qualität der gleichen Kraft) der gleichen Kraft" bedeutet idem + Potenz (gleiche + Kraft).

Definition

Ein Element ${\ displayStyle x}$ eines Satzes ${\ displayStyle S}$ ausgestattet mit einem Binärbetreiber ${\ displayStyle \ cdot}$ wird gesagt, dass idempotent unter ${\ displayStyle \ cdot}$ wenn^[4][5]

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

Das Binäroperation ${\ displayStyle \ cdot}$ wird gesagt, dass idempotent wenn^[6][7]

${\ displayStyle x \ cdot x = x}$ für alle ${\ displayStyle x \ in s}$.

Beispiele

• In dem Monoid ${\ displayStyle (\ mathbb {n}, \ times)}$ des natürliche Zahlen mit Multiplikation, nur 0 und 1 sind idempotent. In der Tat, ${\ displayStyle 0 \ Times 0 = 0}$ und ${\ displayStyle 1 \ Times 1 = 1}$, was nicht für andere natürliche Zahlen gilt.
• In einem Magma ${\ displayStyle (m, \ cdot)}$, ein Identitätselement ${\ displayStyle e}$ oder an absorbierendes Element ${\ displayStyle a}$, wenn es existiert, ist idempotent. In der Tat, ${\ displayStyle e \ cdot e = e}$ und ${\ displayStyle a \ cdot a = a}$.
• In einem Gruppe ${\ displayStyle (g, \ cdot)}$, das Identitätselement ${\ displayStyle e}$ ist das einzige idempotente Element. In der Tat, wenn ${\ displayStyle x}$ ist ein Element von ${\ displayStyle g}$ so dass ${\ displayStyle x \ cdot x = x}$, dann ${\ displayStyle x \ cdot x = x \ cdot e}$ und schlussendlich ${\ displayStyle x = e}$ durch multiplizieren links von der umgekehrtes Element von ${\ displayStyle x}$.
• In den Monoiden ${\ displayStyle ({\ mathcal {p}} (e), \ cup)}$ und ${\ displayStyle ({\ mathcal {p}} (e), \ cap)}$ des Leistungssatz ${\ displayStyle {\ mathcal {p}} (e)}$ des Satzes ${\ displayStyle e}$ mit Set Union ${\ displayStyle \ cup}$ und Schnittpunkt setzen ${\ displayStyle \ cap}$ beziehungsweise, ${\ displayStyle \ cup}$ und ${\ displayStyle \ cap}$ sind idempotent. In der Tat, ${\ displayStyle x \ cup x = x}$ für alle ${\ displaystyle x \ in {\ mathcal {p}} (e)}$, und ${\ displayStyle x \ cap x = x}$ für alle ${\ displaystyle x \ in {\ mathcal {p}} (e)}$.
• In den Monoiden ${\ displayStyle (\ {0,1 \}, \ vee)}$ und ${\ displayStyle (\ {0,1 \}, \ Wedge)}$ des Boolesche Domain mit logische Disjunktion ${\ displayStyle \ vee}$ und logische Konjunktion ${\ displayStyle \ Wedge}$ beziehungsweise, ${\ displayStyle \ vee}$ und ${\ displayStyle \ Wedge}$ sind idempotent. In der Tat, ${\ displayStyle x \ vee x = x}$ für alle ${\ displaystyle x \ in \ {0,1 \}}$, und ${\ displayStyle x \ Wedge x = x}$ für alle ${\ displaystyle x \ in \ {0,1 \}}$.
• In einem Boolean Ring, Multiplikation ist idempotent.
• In einem Tropical SemingAddition ist idempotent.

Idempotente Funktionen

Im Monoid ${\ displayStyle (e^{e}, \ circ)}$ des Funktionen von einem Set ${\ displayStyle e}$ für sich selbst mit Funktionszusammensetzung ${\ displayStyle \ circ}$, idempotente Elemente sind die Funktionen ${\ displayStyle f \ colon e \ bis e}$ so dass ${\ displayStyle f \ circ f = f}$,^[8] das ist so, dass ${\ displayStyle f (f (x)) = f (x)}$ für alle ${\ displayStyle x \ in e}$ (Mit anderen Worten das Bild ${\ displayStyle f (x)}$ von jedem Element ${\ displayStyle x \ in e}$ ist ein Fixpunkt von ${\ displayStyle f}$). Zum Beispiel:

• das absoluter Wert ist idempotent. In der Tat, $oder$, das ist $oder$ für alle ${\ displayStyle x}$;
• Konstante Funktionen sind idempotent;
• das Identitätsfunktion ist idempotent;
• das Boden, Decke und Bruchteil Funktionen sind idempotent;
• das Untergruppe generiert Die Funktion vom Leistungssatz einer Gruppe zu sich selbst ist idempotent;
• das konvexer Rumpf Funktion aus dem Leistungssatz von a Offine Space über dem Real für sich selbst ist idempotent;
• das Schließung und Innere Funktionen des Leistungssatzes von a topologischer Raum für sich selbst sind idempotent;
• das Kleene Star und Kleene Plus Funktionen des Leistungssatzes eines Monoids für sich selbst sind idempotent;
• die idempotent Endomorphismen von a Vektorraum sind seine Projektionen.

Wenn das Set ${\ displayStyle e}$ hat ${\ displayStyle n}$ Elemente, wir können es aufteilt ${\ displayStyle K}$ ausgewählte Fixpunkte und ${\ displayStyle n-k}$ Nicht fixierte Punkte unter ${\ displayStyle f}$, und dann ${\ displayStyle k^{n-k}}$ ist die Anzahl der verschiedenen idempotenten Funktionen. Daher berücksichtigen Sie alle möglichen Partitionen,

${\ displayStyle \ sum _ {k = 0}^{n} {n \ wählen K} k^{n-k}}$

ist die Gesamtzahl möglicher idempotenter Funktionen auf dem Satz. Das Ganzzahlsequenz der Anzahl der idempotenten Funktionen n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... beginnt mit 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ... (Sequenz A000248 in dem Oeis).

Weder die Eigenschaft, idempotent zu sein noch nicht zu sein, wird unter Funktionszusammensetzung bewahrt.^[9] Als Beispiel für erstere, ${\ displayStyle f (x) = x}$ Mod 3 und ${\ displayStyle g (x) = \ max (x, 5)}$ sind beide idempotent, aber ${\ displayStyle f \ circ g}$ ist nicht,^[10] obwohl ${\ displayStyle g \ circ f}$ ist zufälligerweise.^[11] Als Beispiel für letztere die Negationsfunktion ${\ displayStyle \ neg}$ Auf der Booleschen Domain ist nicht idempotent, sondern ${\ displaystyle \ neg \ circ \ neg}$ ist. In ähnlicher Weise die Unary Negation ${\ displayStyle -(\ cdot)}$ realer Zahlen ist nicht idempotent, sondern ${\ displayStyle -(\ cdot) \ circ -(\ cdot)}$ ist. In beiden Fällen ist die Zusammensetzung einfach die Identitätsfunktion, was idempotent ist.

Informatik Bedeutung

Im Informatik, der Begriff idempotenz kann je nach Kontext, in dem es angewendet wird, eine andere Bedeutung haben:

• in Imperative Programmierung, a Subroutine mit Nebenwirkungen ist idempotent, wenn mehrere Aufrufe an die Unterroutine den gleichen Effekt auf den Systemzustand haben wie ein einzelner Aufruf, mit anderen Worten, wenn die Funktion vom Systemzustandsraum zu sich selbst, der mit der Unterroutine verbunden ist Definition;
• in Funktionelle Programmierung, a reine Funktion ist idempotent, wenn es im mathematischen Sinne in der mathematischen Sinne idempotent ist Definition.

Dies ist in vielen Situationen eine sehr nützliche Eigenschaft, da eine Operation so oft wie nötig wiederholt oder wiederholt werden kann, ohne unbeabsichtigte Auswirkungen zu verursachen. Bei nicht-idempotenten Operationen muss der Algorithmus möglicherweise verfolgen, ob der Betrieb bereits ausgeführt wurde oder nicht.

Beispiele für Informatik

Eine Funktion, die den Namen und die Adresse eines Kunden in a nachschlagen Datenbank ist normalerweise idempotent, da sich die Datenbank nicht ändert. In ähnlicher Weise ist eine Anfrage zur Änderung der Adresse eines Kunden in XYZ in der Regel idempotent, da die endgültige Adresse gleich ist, egal wie oft die Anfrage eingereicht wird. Eine Kundenanfrage zur Aufgabe einer Bestellung ist jedoch in der Regel nicht idemPotent, da mehrere Anfragen zu mehreren Bestellungen führen. Eine Anfrage zur Stornierung einer bestimmten Bestellung ist idempotent, da unabhängig davon, wie viele Anfragen die Bestellung gestellt werden, storniert bleibt.

Eine Sequenz von idempotenten Subroutinen, bei denen sich mindestens eine Unterroutine von den anderen unterscheidet, ist jedoch nicht unbedingt idempotent, wenn eine spätere Unterroutine in der Sequenz einen Wert ändert, von dem ein früherer Unterprogramm abhängt -Idempotenz wird unter sequentieller Zusammensetzung nicht geschlossen. Nehmen wir beispielsweise an, der Anfangswert einer Variablen beträgt 3 und es gibt eine Subroutine -Sequenz, die die Variable liest, sie dann auf 5 ändert und dann erneut liest. Jeder Schritt in der Sequenz ist idempotent: Beide Schritte Das Lesen der Variablen haben keine Nebenwirkungen und der Schritt, der die Variable in 5 ändert, hat immer den gleichen Effekt, egal wie oft sie ausgeführt wird. Dennoch erzeugt die Ausführung der gesamten Sequenz einmal die Ausgabe (3, 5), erzeugt sie jedoch ein zweites Mal die Ausgabe (5, 5), sodass die Sequenz nicht idempotent ist.

int x = 3; Leere lesen() { printf("%d\n", x); } Leere Rückgeld() { x = 5; } Leere Reihenfolge() { lesen(); Rückgeld(); lesen(); } int hauptsächlich() {   Reihenfolge();  // Drucke "3 \ n5 \ n"   Reihenfolge();  // Drucke "5 \ n5 \ n"   Rückkehr 0; } 

In dem Hypertext Transfer Protocol (Http), idempotence und Sicherheit sind die Hauptattribute, die sich trennen HTTP -Methoden. Von den wichtigsten HTTP -Methoden sollte Get, Put und Löschen nach dem Standard auf idempotentes Implementieren implementiert werden, aber Post muss es nicht sein.^[12] Holen Sie sich den Zustand einer Ressource ab; Aktualisierung des Zustands einer Ressource; und löschen löscht eine Ressource. Wie im obigen Beispiel haben Lesendaten normalerweise keine Nebenwirkungen, so dass sie idempotent sind (in der Tat nullipotent). Das Aktualisieren und Löschen einer bestimmten Daten ist in der Regel idempotent, solange die Anfrage die Ressource und nur diese Ressource in Zukunft wieder identifiziert. Setzen und löschen mit eindeutigen Kennungen, die auf den einfachen Fall der Zuordnung zu einer Variablen eines Werts oder des Null-Werts reduzieren, und sind aus dem gleichen Grund idempotent; Das Endergebnis ist immer das gleiche wie das Ergebnis der anfänglichen Ausführung, auch wenn sich die Antwort unterscheidet.^[13]

Verstöße gegen die eindeutige Identifikationsanforderung bei der Lagerung oder Löschung verursachen typischerweise Verstoß gegen die Idempotenz. Zum Beispiel das Speichern oder Löschen eines bestimmten Inhaltssatzes ohne Angabe einer eindeutigen Kennung: Postanforderungen, die nicht idempotent sein müssen, enthalten häufig keine eindeutigen Kennungen, sodass die Erstellung der Kennung an das Empfangssystem delegiert wird, das dann erstellt wird ein entsprechender neuer Datensatz. In ähnlicher Weise können Put- und Löschen von Anforderungen mit unspezifischen Kriterien je nach Status des Systems zu unterschiedlichen Ergebnissen führen - beispielsweise eine Anfrage zum Löschen des neuesten Datensatzes. In jedem Fall werden nachfolgende Ausführungen den Status des Systems weiter ändern, sodass sie nicht idemPotent sind.

Im Ereignisstromverarbeitung, ideMpotence bezieht sich auf die Fähigkeit eines Systems, das gleiche Ergebnis zu erzielen, auch wenn dieselbe Datei, Ereignis oder Nachricht mehr als einmal empfangen wird.

In einem Last -Store -Architektur, Anweisungen, die möglicherweise a verursachen könnten Seitenfehler sind idempotent. Also, wenn ein Seitenfehler auftritt, die Betriebssystem Kann die Seite von der Festplatte laden und dann die fehlerhafte Anweisung einfach erneut ausführen. In einem Prozessor, bei dem solche Anweisungen nicht idempotent sind, ist der Umgang mit Seitenfehlern viel komplexer.^[14][15]

Bei der neu formating outpution, ziemlich gedruckt wird erwartet, dass es idempotent ist. Mit anderen Worten, wenn die Ausgabe bereits "hübsch" ist, sollte es für den hübschen Drucker nichts zu tun haben.

Im Serviceorientierte Architektur (SOA) kann ein ausschließlich aus idempotenter Schritten bestehender mehrstufiger Orchestrierungsprozess ohne Nebenwirkungen wiedergegeben werden, wenn ein Teil dieses Prozesses fehlschlägt.

Viele Operationen, die idempotent sind, haben oft Möglichkeiten, einen Prozess zu "wieder aufnehmen", wenn er unterbrochen wird - Möglichkeiten, die viel schneller abschließen als von Anfang an von vorne zu beginnen. Zum Beispiel, Wiederaufnahme einer DateiübertragungAnwesendDateien synchronisieren, ein ... Erstellen Software Buildinstallieren eine Anwendung und alle ihre Abhängigkeiten mit a Paket-Manager, etc.

Angewandte Beispiele

Ein typischer Zergastknopf ist ein Beispiel für ein idempotentes System

Angewandte Beispiele, auf die viele Menschen in ihrem täglichen Leben begegnen könnten Aufzug Rufen Sie Knöpfe an und Zergrohrknöpfe.^[16] Die anfängliche Aktivierung der Taste verschiebt das System in einen anspruchsvollen Status, bis die Anfrage erfüllt ist. Nachfolgende Aktivierungen der Taste zwischen der anfänglichen Aktivierung und der erfüllten Anforderung haben keinen Einfluss, es sei denn, das System ist so konzipiert, dass die Zeit für die Erfüllung der Anforderung basierend auf der Anzahl der Aktivierungen angepasst wird.

Siehe auch

• Biordered -Set
• Verschlussbetreiber
• Fixpunkt (Mathematik)
• Idempotent eines Code
• Idempotent Analyse
• Idempotente Matrix
• Idempotente Beziehung- Eine Verallgemeinerung der Idempotenz für binäre Beziehungen
• Involution (Mathematik)
• Iterierte Funktion
• Liste der Matrizen
• Nilpotent
• Reine Funktion
• Referenztransparenz

Verweise

Weitere Lektüre

• "idempotent" Bei der Kostenloses Online-Wörterbuch des Computers
• Goodearl, K. R. (1991), Von Neumann reguläre Ringe (2. ed.), Malabar, FL: Robert E. Krieger Publishing Co. Inc., S. xviii+412, ISBN 978-0-89464-632-4, HERR 1150975
• Gunawardena, Jeremy (1998), "Eine Einführung in die Idempotenz" (PDF)in Gunawardena, Jeremy (Hrsg.), Idempotenz. Basierend auf einem Workshop, Bristol, Großbritannien, 3. bis 7. Oktober 1994, Cambridge: Cambridge University Press, S. 1–49, Zbl 0898.16032
• "Idempotent", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• HaMewinkel, Michiel; Gubareni, Nadiya; Kirichenko, V. V. (2004), Algebren, Ringe und Module. vol. 1, Mathematik und seine Anwendungen, Vol. 575, Dordrecht: Kluwer Academic Publishers, S. xii+380, ISBN 978-1-4020-2690-4, HERR 2106764
• Lam, T. Y. (2001), Ein erster Kurs in nichtkommutativen Ringen, Graduiertentexte in Mathematics, Vol. 131 (2 ed.), New York: Springer-Verlag, S. xx+385, doi:10.1007/978-1-4419-8616-0, ISBN 978-0-387-95183-6, HERR 1838439
• Lang, Serge (1993), Algebra (Dritter Aufl.), Reading, Mass.: Addison-Wesley, ISBN 978-0-201-55540-0, Zbl 0848.13001 p. 443
• Peirce, Benjamin. Lineare assoziative Algebra 1870.
• Polcino Milies, César; Sehgal, Sudarshan K. (2002), Eine Einführung in GruppenringeAlgebren und Anwendungen, Vol. 1, Kluwer Academic Publishers, S.127, ISBN 978-1-4020-0238-0, HERR 1896125