- Logarithmus - Wichtig
- Potenz - Wichtig
- Geometrische Reihe
- Gaußsche Summenformel
1. Grundlagen
- Begriffe
- Algorithmus
- Datentyp
- Datenstruktur
- Stapel
- Korrektheit und Komplexität
- Totale Korrektheit
- Moore’s Gesetz
- Iterationen
- Rekursionen
- Registermaschine
- Church‘sche These
- Komplexität
- O-Notation - Wichtig
- Übersicht Komplexitätsklassen
- Rekursionsgleichungen - Wichtig - ToDo
- Substitutionsmetode - Wichtig - ToDo
- Iterationsmethode - Wichtig - ToDo
- Master-Theorem - Wichtig - ToDo
- Entwurfsmethode Divide & Conquer
2. Sortieralgorithmen
- Einfache Sortieralgorithmen
- Fortgeschrittene Sortieralgorithmen
- Spezielle Sortieralgorithmen
- Untere Schranke für vergleichsbasiertes Sortieren - Wichtig
- Sortierbäume - Wichtig
3. Dynamische Datenstrukturen
- Stapel
- Schlangen
- Listen
- Bäume
- Baum
- Binärbaum
- Binärer Suchbaum
- Binärer verketteter Suchbaum
- Laufzeit beim Suchen/Einfügen/Löschen - Wichtig
- Durchlaufen von Bäumen
- Höhe eines Baumes
- Links- und rechtsvoll
- Schicht
- Vollständiger Baum
- Wurzel (Bäume)
- Heap
- Graph
4. Suchalgorithmen
- Suchen in Mengen
- Naive Suche
- Suche in sortierten Folgen
- Suche in binären, verketteten Suchbäumen
- Suche in balancierten Bäumen, verketteten Suchbäumen
- AVL-Bäume - Wichtig
- Rot-Schwarz-Bäume
- B-Bäume - Wichtig
- Hashing - Wichtig
- Hashing mit Verkettung
- Geschlossenes Hashing mit offener Adressierung
- Universelles Hashing
- Geburtstagsproblem - Wichtig
- Analysen - Wichtig
- Beispiel: Führen Sie Hashing mit offener Adressierung durch, was ist die mittlere Anzahl an Platzierungsversuchen bei einem konkreten Beispiel
- Skip-Listen
- Suchen in Texten
5. Graphalgorithmen
- Begriffe
- Graph
- Ungerichtete und gerichtete Graphen
- Knoten und Kanten in einem Graph
- Vollständigkeit und Teilgraphen
- Cliquen und gewichtete Graphen
- Wege in Graphen
- Zusammenhängende Graphen und Bäume
- Adjazenzmatrix
- Adjazenzliste
- Dünne und dichte Graphen
- Ablaufalgorithmen
- Topologische Sortierung
- Minimale Spannbäume
- Kürzeste Wege