Datenstrukturen und Algorithmen

1 Einführung.- 1.1 Algorithmen und ihre Analyse.- 1.2 Datenstrukturen, Algebren, Abstrakte Datentypen.- 1.3 Grundbegriffe.- 1.4 Weitere Aufgaben.- 1.5 Literaturhinweise.- 2 Programmiersprachliche Konzepte für Datenstrukturen.- 2.1 Datentypen in Java.- 2.2 Dynamische Datenstrukturen.- 2.3 Weitere Konzepte zur Konstruktion von Datentypen.- 2.4 Literaturhinweise.- 3 Grundlegende Datentypen.- 3.1 Sequenzen (Folgen, Listen).- 3.2 Stacks.- 3.3 Queues.- 3.4 Abbildungen.- 3.5 Binäre Bäume.- 3.6 (Allgemeine) Bäume.- 3.7 Weitere Aufgaben.- 3.8 Literaturhinweise.- 4 Datentypen zur Darstellung von Mengen.- 4.1 Mengen mit Durchschnitt, Vereinigung, Differenz.- 4.2 Dictionaries: Mengen mit INSERT, DELETE, MEMBER.- 4.3 Priority Queues: Mengen mit INSERT, DELETEMIN.- 4.4 Partitionen von Mengen mit MERGE, FIND.- 4.5 Weitere Aufgaben.- 4.6 Literaturhinweise.- 5 Graphen und Graph-Algorithmen.- 5.1 Gerichtete Graphen.- 5.2 (Speicher-) Darstellungen von Graphen.- 5.3 Graphdurchlauf.- 5.4 Bestimmung kürzester Wege von einem Knoten zu allen anderen.- 5.5 Bestimmung kürzester Wege zwischen allen Knoten im Graphen.- 5.6 Transitive Hülle.- 5.7 Starke Komponenten.- 5.8 Ungerichtete Graphen.- 5.9 Minimaler Spannbaum (Algorithmus von Kruskal).- 5.10 Weitere Aufgaben.- 5.11 Literaturhinweise.- 6 Sortieralgorithmen.- 6.1 Einfache Sortierverfahren: Direktes Auswählen und 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.- 6.6 Weitere Aufgaben.- 6.7 Literaturhinweise.- 7 Geometrische Algorithmen.- 7.1 Plane-Sweep-Algorithmen für orthogonale Objekte in der Ebene.- 7.2Divide-and-Conquer-Algorithmen für orthogonale Objekte.- 7.3 Suchen auf Mengen orthogonaler Objekte.- 7.4 Plane-Sweep-Algorithmen für beliebig orientierte Objekte.- 7.5 Weitere Aufgaben.- 7.6 Literaturhinweise.- 8 Externes Suchen und Sortieren.- 8.1 Externes Suchen: B-Bäume.- 8.2 Externes Sortieren.- 8.3 Weitere Aufgaben.- 8.4 Literaturhinweise.- Mathematische Grundlagen.- Lösungen zu den Selbsttestaufgaben.- Literatur.