Datenstrukturen und Algorithmen

Das Buch ist im Rahmen des http://medoc.informatik.tu-muenchen.de/deutsch/medoc.html>MeDoc-Projektes in die elektronische Informatik-Bibliothek aufgenommen worden.

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.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.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.2 Ungerichtete Graphen.- 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.2 Divide-and-Conquer-Algorithmen für orthogonale Objekte in der Ebene.- 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 EinigeGrundlagen der Wahrscheinlichkeitsrechnung und Kombinatorik.- III Umgang mit Binomialkoeffizienten.- IV Harmonische Zahlen.- V Umwandlung von Rekursion in eine Summe.- VI Fibonacci-Zahlen.- Literatur.