Algebra des Programmierens - Cheatsheet

Definition und Eigenschaften von algebraischen Strukturen

Definition:

Grundlegende Objekte in der Algebra, verwendet zur Beschreibung und Untersuchung von Berechnungen, Transformationen und symmetrischen Mustern.

Details:

• Halbgruppe: Menge mit assoziativer Verknüpfung.
• Monoid: Halbgruppe mit neutralem Element.
• Gruppe: Monoid, in dem jedes Element ein Inverses hat.
• Ring: Menge mit zwei Operationen (Addition und Multiplikation); (R,+) ist eine abelsche Gruppe, (R,*) eine Halbgruppe, Distributivgesetz gilt.
• Körper: Ring, in dem jeder von null verschiedene Elemente ein multiplikatives Inverses hat.
• Algebra: Vektorraum über einem Körper mit einer bilinearen Multiplikation.

Operationen mit Mengen wie Vereinigung, Durchschnitt und Differenz

Definition:

Operationen mit Mengen sind grundlegende Konzepte in der Algebra. Sie umfassen die Vereinigung, den Durchschnitt und die Differenz von Mengen.

Details:

• Vereinigung (\textit{Union}): Die Vereinigung zweier Mengen \textit{A} und \textit{B} enthält alle Elemente, die in \textit{A} oder \textit{B} oder in beiden enthalten sind. \( A \bigcup B \)
• Durchschnitt (\textit{Intersection}): Der Durchschnitt zweier Mengen \textit{A} und \textit{B} enthält nur die Elemente, die sowohl in \textit{A} als auch in \textit{B} enthalten sind. \( A \bigcap B \)
• Differenz (\textit{Difference}): Die Differenz der Mengen \textit{A} und \textit{B} enthält die Elemente, die in \textit{A}, aber nicht in \textit{B} enthalten sind. \( A - B \)

Definition und Eigenschaften von Relationen

Definition:

Eine Relation ist eine Menge von geordneten Paaren (a, b) aus zwei Mengen A und B.

Details:

• Notation: \(\text{R} \subseteq A \times B\)
• Reflexivität: \(\forall a \in A : (a,a) \in R\)
• Symmetrie: \(\forall a,b \in A : (a,b) \in R \Rightarrow (b,a) \in R\)
• Antisymmetrie: \(\forall a,b \in A : (a,b) \in R \wedge (b,a) \in R \Rightarrow a = b\)
• Transitivität: \(\forall a,b,c \in A : (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R\)
• Beispiele: Gleichheitsrelation, Ordnungsrelation

Gruppen, Ringe und Körper in der algebraischen Strukturen

Definition:

In der Vorlesung Algebra des Programmierens geht es um die grundlegenden algebraischen Strukturen: Gruppen, Ringe und Körper.

Details:

• Gruppen: Ein Tupel \(G, \cdot\)\ mit einer Menge G und einer Verknüpfung \( \cdot \) so dass gilt: Assoziativität, neutrales Element, Inverses Element.
• Ringe: Ein Tupel \(R, +, \cdot\)\ mit einer Menge R und zwei Verknüpfungen \( + , \cdot \), so dass (R, +) eine abelsche Gruppe und (R, \cdot \) ein Monoid ist, Distributivität gilt.
• Körper: Ein Tupel \(K, +, \cdot\)\ mit einer Menge K und zwei Verknüpfungen \( + , \cdot \), so dass (K, +, \cdot\) ein Ring ist und \( K^* = K \backslash \{0\} \) bzgl. \( \cdot \) eine abelsche Gruppe ist.

Homomorphiesätze und deren Anwendungen

Definition:

Homomorphiesätze sind zentrale Konzepte in der Algebra und betreffen Strukturerhaltende Abbildungen zwischen algebraischen Strukturen. Sie spielen eine wichtige Rolle in der Informatik bei der Programmverifikation und im Bereich der funktionalen Programmierung.

Details:

• Ein Homomorphismus ist eine Abbildung zwischen zwei algebraischen Strukturen, die die Struktur respektiert.
• Wichtige Homomorphiesätze: Erster, Zweiter und Dritter Isomorphiesatz.
• Anwendungen: Vereinfachung von Algorithmen, Beweis von Eigenschaften von Datenstrukturen, Optimierung von Programmen.
• Erster Isomorphiesatz: Wenn \( \phi : G \to H \) ein Homomorphismus ist, dann ist \( G/\ker(\phi) \) isomorph zu \( \mathrm{im}(\phi) \).
• Zweiter Isomorphiesatz: \( (H \cap N)/N \cong HN/N \) für jede Untergruppe \(H\) und Normalteiler \(N\) in Gruppe \(G\).
• Dritter Isomorphiesatz: Für zwei Normalteiler \(N\) und \(M\) von \(G\) mit \(N \subseteq M\) ist \(G/M \cong (G/N)/(M/N)\).

Kartesisches Produkt und Potenzmenge in der Mengenlehre

Definition:

Kartesisches Produkt: Menge aller möglichen geordneten Paare aus zwei Mengen. Potenzmenge: Menge aller Teilmengen einer Menge.

Details:

• Kartesisches Produkt:
• Definiert als:

  A \times B = \big\{ (a, b) \mid a \in A, b \in B \big\}

• Beispiel:

  A = \{1, 2\}, B = \{x, y\} \Rightarrow A \times B = \{(1, x), (1, y), (2, x), (2, y)\}

• Potenzmenge:
• Definiert als:

  \text{P}(A) = \{ B \mid B \subseteq A \}

• Anzahl der Elemente:

  |\text{P}(A)| = 2^{|A|}

• Beispiel:

  A = \{1, 2\} \Rightarrow \text{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}

Polynomringe und ihre Eigenschaften

Definition:

Ein Polynomring ist ein Ring, der aus Polynomen besteht, klassisch der Form \(R[x]\), wobei \(R\) ein Grundring ist.

Details:

• Form: \(R[x]\)
• Addition: komponentenweise
• Multiplikation: distributiv
• Nullpolynom: alle Koeffizienten sind Null
• Eins-Polynom: konstantes Polynom mit Eins als Koeffizient
• Grad eines Polynoms: höchster Exponent mit nicht-Null Koeffizient
• Ist \(R\) ein Integritätsring, ist auch \(R[x]\) ein Integritätsring

Isomorphismen und ihre Eigenschaften

Definition:

Isomorphismen sind strukturerhaltende Abbildungen zwischen zwei algebraischen Strukturen (wie Gruppen, Ringen etc.), die sowohl injektiv als auch surjektiv und damit bijektiv sind.

Details:

• Erhalten die Struktur der Operationen bei: \( f(a \bullet b) = f(a) \bullet f(b) \)
• Bijektiv: sowohl injektiv (eineindeutig) als auch surjektiv (auf).
• Inverse Abbildung existiert und ist ebenfalls ein Homomorphismus.
• Algebraische Strukturen sind isomorph, wenn sie im Wesentlichen gleich sind, aber eventuell unterschiedlich dargestellt werden.
• Notation: \( f: A \cong B \)