Datenstrukturen und Algorithmen

1 Einführung.- 1.1 Algorithmen und ihre Analyse.- 1.2 Datenstrukturen, Algebren, Abstrakte Datentypen.- 1.3 Grundbegriffe.- Aufgaben.- Literaturhinweise.- 2 Programmiersprachliche Konzepte zur Konstruktion von Datenstrukturen.- 2.1 Atomare Typen.- 2.2 Typkonstruktoren / Strukturierte Typen.- 2.3 Zeigertypen.- Literaturhinweise.- 3 Grundlegende Datentypen.- 3.1 Sequenzen (Folgen, Listen).- 3.1.1 Modelle.- 3.1.2 Implementierungen.- 3.2 Stacks.- 3.3 Queues.- 3.4 Abbildungen.- 3.5 Binäre Bäume.- 3.6 (Allgemeine) Bäume.- Aufgaben.- Literaturhinweise.- 4 Datentypen zur Darstellung von Mengen.- 4.1 Mengen mit Durchschnitt, Vereinigung, Differenz.- 4.2 Dictionaries: Mengen mit INSERT, DELETE, MEMBER.- 4.2.1 Einfache Implementierungen.- 4.2.2 Hashing.- 4.2.3 Binäre Suchbäume.- 4.2.4 AVL-Bäume.- 4.3 Priority Queues: Mengen mit INSERT, DELETEMIN.- 4.4 Partitionen von Mengen mit MERGE, FIND.- Aufgaben.- Literaturhinweise.- 5 Graphen und Graph-Algorithmen.- 5.1 Gerichtete Graphen.- 5.1.1 (Speicher-) Darstellungen von Graphen.- 5.1.2 Graphdurchlauf.- 5.1.3 Bestimmung kürzester Wege von einem Knoten im Graphen zu allen anderen.- 5.1.4 Bestimmung kürzester Wege zwischen allen Knoten im Graphen.- 5.1.5 Transitive Hülle.- 5.1.6 Starke Komponenten.- 5.2 Ungerichtete Graphen.- 5.2.1 Minimaler Spannbaum (Algorithmus von Kruskal).- Aufgaben.- Literaturhinweise.- 6 Sortieralgorithmen.- 6.1 Einfache Sortierverfahren: Direktes Auswählen und direktes Einfügen.- 6.2 Divide-and-Conquer-Methoden: Mergesort und Quicksort.- 6.3 Verfeinertes Auswählen und Einfügen: Heapsort und Baumsortieren.- 6.4 Untere Schranke für allgemeine Sortierverfahren.- 6.5 Sortieren durch Fachverteilen: Bucketsort und Radixsort.- Aufgaben.- Literaturhinweise.- 7 Geometrische Algorithmen.- 7.1 Plane-Sweep-Algorithmen für Mengen orthogonaler Objekte in der Ebene.- 7.1.1 Das Segmentschnitt-Problem.- 7.1.2 Das Rechteckschnitt-Problem.- 7.1.3 Das Maßproblem.- 7.2 Divide-and-Conquer-Algorithmen für orthogonale Objekte in der Ebene.- 7.2.1 Das Segmentschnitt-Problem.- 7.2.2 Das Maßproblem.- 7.2.3 Das Konturproblem.- 7.3 Suchen auf Mengen orthogonaler Objekte.- 7.4 Plane-Sweep-Algorithmen für beliebig orientierte Objekte.- Aufgaben.- Literaturhinweise.- 8 Externes Suchen und Sortieren.- 8.1 Externes Suchen: B-Bäume.- 8.2 Externes Sortieren.- Aufgaben.- Literaturhinweise.- Mathematische Grundlagen.- I Einige Summenformeln.- II Einige Grundlagen der Wahrscheinlichkeitsrechnung und Kombinatorik.- III Umgang mit Binomialkoeffizienten.- IV Harmonische Zahlen.- V Umwandlung von Rekursion in eine Summe.- VI Fibonacci-Zahlen.- Literatur.