Idempotenz - LinkFang.de





Idempotenz


Idempotenz ist ein Begriff aus der Mathematik und Informatik. In der Mathematik bezeichnet man ein Objekt [math]a[/math], das mit einer Verknüpfung [math]\circ[/math] die Eigenschaft [math]a \circ a = a[/math] hat, als idempotent bezüglich dieser Verknüpfung. Ein wichtiger Spezialfall sind idempotente Funktionen bezüglich der Hintereinanderausführung. Analog dazu wird in der Informatik ein Stück Programmcode, das mehrfach hintereinander ausgeführt das gleiche Ergebnis wie bei einer einzigen Ausführung liefert, als idempotent bezeichnet.

Definitionen

Idempotente Elemente

Ein Element [math]a[/math] einer Menge [math]X[/math] heißt idempotent bezüglich einer [math]n[/math]-stelligen Verknüpfung [math]v\colon X^n \rightarrow X,\, n \in \N[/math] und [math]n \gt 1,[/math] falls gilt:

[math]v(a,\dotsc,a) = a.[/math]

Erfüllt dagegen [math]a[/math] für eine einstellige Verknüpfung [math]f\colon X \rightarrow X[/math] die Gleichung

[math]f(a) = a,[/math]

dann ist [math]a[/math] ein Fixpunkt von [math]f.[/math]

Idempotente Funktionen

Man nennt eine einstellige Verknüpfung oder Funktion [math]f\colon\, X \rightarrow X[/math] idempotent, wenn sie bezüglich der Komposition idempotent ist:

[math]f\circ f = f,[/math]

d. h. für alle [math]x \in X[/math] ergibt eine zweimalige Anwendung von [math]f[/math] den gleichen Wert wie die einmalige: [math]f(f(x)) = f(x)[/math].

Idempotente algebraische Strukturen

Sind alle Elemente einer Halbgruppe (oder allgemeiner eines Magmas) [math](S,*)[/math] idempotent bezüglich [math]*[/math], dann wird auch [math](S,*)[/math] selbst idempotent genannt. Alternativ wird eine idempotente Halbgruppe auch oft als ein Band bezeichnet.[1][2] Jedes kommutative Band heißt Halbverband. Man nennt eine Halbgruppe [math](S,*)[/math] global idempotent, falls gilt:

[math]S*S = S[/math] mit [math]S*S := \{a*b \mid a,b \in S\}[/math].

Einen Halbring [math](H,+,\cdot),[/math] einen Fastring [math](F,+,\cdot)[/math] sowie einen Ring [math](R,+,\cdot)[/math] bezeichnet man als idempotent, falls jeweils [math](H,\cdot), (F,\cdot)[/math] bzw. [math](R,\cdot)[/math] idempotent ist. Im Gegensatz dazu ist ein Dioid [math](D,+,0,\cdot,1)[/math] ein Hemiring mit Einselement und idempotenter Addition.

Beispiele

Idempotente Verknüpfungen:

  • Bezüglich der Multiplikation sind die Lösungen [math]0[/math] und [math]1[/math] der Gleichung [math]x^2 = x[/math] die einzigen idempotenten reellen Zahlen.
  • Bezüglich einer zweistelligen Verknüpfung [math]*[/math] ist ein (links- oder rechts-)neutrales Element [math]e[/math] stets idempotent: [math]e * e = e.[/math] In einer Gruppe ist das neutrale Element das einzige idempotente Element.
  • In einem Ring mit Eins sind 0 und 1 stets idempotente Elemente bezüglich der Multiplikation. Falls der Ring kein Körper ist, können auch noch weitere idempotente Elemente existieren. Beispielsweise gilt im Restklassenring [math]\Z / 6\Z[/math]
[math]3 \cdot 3 \equiv 3 \pmod{6}[/math] und [math]4 \cdot 4 \equiv 4 \pmod{6}[/math].
  • Ist [math](V,\cup,\cap)[/math] ein Verband, so sind [math](V,\cup)[/math] und [math](V,\cap)[/math] Halbverbände.
  • Absorbierende Elemente sind immer idempotent.

Idempotente Abbildungen:

Eigenschaften

[math]f_A\colon\, K^n \to K^n,\; x \mapsto Ax,[/math]
idempotent ist. Insbesondere sind die Eigenwerte von [math]A[/math] allesamt [math]0[/math] oder [math]1[/math]. Geometrisch können idempotente lineare Abbildungen als Projektion des Vektorraums auf einen Untervektorraum interpretiert werden.
  • Jeder idempotente Ring [math](R,+,\cdot)[/math] ist kommutativ, denn es gilt für alle [math]a,b \in R\colon[/math]
[math]a + 0 + b = a + b = (a+b)\cdot(a + b) = a\cdot(a+b) + b\cdot(a+b) = a\cdot a + a\cdot b + b\cdot a + b\cdot b = a + a\cdot b + b\cdot a + b,[/math]
(zweite und fünfte Gleichung wegen der Idempotenz, dritte und vierte Gleichung wegen der Distributivität), also
[math]0 = a\cdot b + b\cdot a. \quad (1)[/math]
Damit gilt auch, indem man [math]a \leftarrow (a\cdot b)[/math] und [math]b \leftarrow (a\cdot b)[/math] setzt und wiederum die Idempotenz nutzt,
[math]0 = (a\cdot b)\cdot(a\cdot b) + (a\cdot b)\cdot(a\cdot b) = a\cdot b + a\cdot b.[/math]
Folglich ist
[math]a\cdot b = a\cdot b + 0 = a\cdot b + a\cdot b + b\cdot a = 0 + b\cdot a = b\cdot a.[/math]
Insbesondere gilt auch (wegen der Idempotenz und wegen (1) mit [math] b = a[/math])
[math]a + a = a\cdot a + a\cdot a = 0[/math] bzw. [math]\,-a = a.[/math]
  • Ein idempotenter Fastring [math](F,+,\cdot)[/math] ist genau dann kommutativ, wenn er distributiv ist, denn:
Falls [math](F,+,\cdot)[/math] kommutativ ist, gilt für alle [math]a,b,c \in F\colon[/math]
[math]c \cdot (a + b) = (a + b) \cdot c = (a \cdot c) + (b \cdot c) = (c \cdot a) + (c \cdot b).[/math]
Ist hingegen [math](F,+,\cdot)[/math] distributiv, so folgt daraus genau so wie bei einem idempotenten Ring die Kommutativität.

Informatik

In der Informatik wird Idempotenz von Recovery-Maßnahmen bei Datenbanken und Diensten gefordert, um Fehlertoleranz bei einem Absturz während einer Wiederanlaufphase zu gewährleisten. Undo- und Redo-Operationen müssen hier auch bei mehrfacher Hintereinanderausführung dasselbe Resultat zur Folge haben.

Rein lesende Services sind von Natur aus idempotent, da der Zustand der Daten nicht geändert wird. Jeder nicht idempotente schreibende Service kann aus fachlicher Sicht zu einem idempotenten Service gemacht werden.

Beispiel

Bei einem Service zum Verbuchen von Geldbeträgen ist der Aufruf einzahlen(100) nicht idempotent, da bei mehrmaligem Service-Aufruf der Betrag 100 mehrmals eingezahlt wird. Würde man hingegen neuerKontostand(600) aufrufen, so würde bei mehrmaligem Service-Aufruf der Kontostand gleich bleiben. Dieser Aufruf wäre idempotent.

Siehe auch

Literatur

  • Jeremy Gunawardena: An introduction to idempotency in J. Gunawardena (Hrsg.): Idempotency, Cambridge University Press, 1998, ISBN 0-521-55344-X, S. 1–49 (englisch; Vorabveröffentlichung online , PDF-Datei, 414 kB)
  • Munindar Paul Singh, Michael N. Huhns: Service-oriented Computing: Semantics, Processes, Agents. Wiley 2005, ISBN 0470091487, S. 54 (Auszug in der Google-Buchsuche)

Einzelnachweise

  1. L. N. Shevrin: Semi-group of Idempotents. In: Michiel Hazewinkel (Hrsg.): Encyclopaedia of Mathematics. Springer-Verlag, Berlin 2002, ISBN 1-4020-0609-8 (online ).
  2. Günther Eisenreich, Ralf Sube: Langenscheidts Fachwörterbuch Mathematik. Langenscheidt 1996, ISBN 3861170744, S. 381 (Auszug in der Google-Buchsuche)

Kategorien: Algebra

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Idempotenz (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.