Am heutigen Termin besprechen wir nochmals kurz alle bearbeiteten Teilgebiete des letzten halben Jahres. Alle hier aufgeführten Themen sind klausurrelevant und müssen ohne Zuhilfenahme von Notizen beschrieben werden können. Dies beinhaltet auch formale Definitionen und Formeln, die wir auswendig beherrschen müssen. Dieser Artikel fasst daher nochmals alle genannten Lernfelder und Inhalte auf.
Rückblick
Teilmengen
- Konzept und Definition von minimal change-Sequenzen
- rank, unrank, successor und predecessor-Funktionen
- Darstellungen von n-Teilmengen (Bit-Arrays und charakteristischer Vektor)
- Darstellungen von k-Teilmengen einer n-Teilmenge
- Rekursive Erzeugung aller Teilmengen (Gray-Code)
- Anzahl der n-Teilmengen und k-Teilmengen bestimmen
- Binomialkoeffizient und Pascalsches Dreieck
Permutationen
- Definition einer Permutation auf n Punkten (kanonischer Start mit 0)
- Anzahl von Permutationen (n!)
- Darstellungen von Permutationen als Liste (einfacher zu speichern) und in Zykelnotation (lesbarer für Menschen)
- Definition der Identität idn
- Multiplikation und Inversion von Permutationen (Aufwand O(n))
- Definitionen und Transformation von Zykeltyp und (Zahl-)Partitionen
- Anzahl von Permutationen mit gleichem Zykeltyp bestimmen: \(\frac{n!}{\prod_{k=1}^{n}(a_k!*k^{a_k})}\)
- Erzeugung aller Permutationen auf n Punkten (Johnson-Trotter)
Gruppen
- Definitionen und Axiome (multiplikative und additive Gruppen)
- Beispiele von Gruppen, Inversen und neutralen Elementen
- Endliche Gruppen
- Ordnung einer Gruppe bestimmen (Anzahl der Elemente in einer Gruppe)
- Definition einer Untergruppe (Teilmenge einer endlichen Gruppe ist dann eine Gruppe, wenn sie Abgeschlossenheit erfüllt)
- Erzeugnis von Gruppenelementen
- Zyklische Gruppe (Gruppe wird von exakt einem Element erzeugt)
- Symmetrische Gruppe Sn
- Untergruppen von Drehgruppen und geometrischen Objekten
- Satz von Lagrange (Untergruppenordnung teilt Gruppenordnung)
- Definition von Nebenklassen
- Berechnung von Transversalen
Gruppenoperationen
- Definitionen von Gruppenoperationen, Bahn und Stabilisator
- Permutationsgruppen auf Graphen und k-Teilmengen anwenden
- Bahnenalgorithmus
- Berechnung des Stabilisators (nach Schreier)
- Anzahl von Fixpunktmengen, Bahnen sowie von nicht-isomorphen Graohen und Halsketten bestimmen