Algorithmen und Datenstrukturen sind Thema dieses Buches. Algorithmen arbeiten auf Datenstrukturen und Datenstrukturen enthalten Algorithmen als Komponenten; insofern sind heide untrennbar miteinander verknüpft. In der Einleitung wollen wir diese Begriffe etwas beleuchten und sie einordnen in eine "Umgebung" eng damit zusammenhängender Konzepte wie Funktion, Prozedur, Abstrakter Datentyp, Datentyp, Algebra, Typ (in einer Programmiersprache), Klasse und Modul. Wie für viele fundamentale Begriffe der Informatik gibt es auch für diese beiden, also für Algorithmen und Datenstrukturen, nicht eine einzige, scharfe, allgemein akzeptierte Definition. Vielmehr werden sie in der Praxis in allerlei Bedeutungsschattierungen ver wendet; wenn man Lehrbücher ansieht, findet man durchaus unterschiedliche "Definitio nen". Das Diagramm in Abbildung 1. 1 und spätere Bemerkungen dazu geben also die persönliche Sicht der Autoren wieder. ADT (Abstrakter Datentyp) Mathematik Funktion Algebra (Datentyp ) Implementierung . ----'---________ -'-__ ---, Thema des Algorithmik I Algorithmus ~ Datenstruktur Buches speikation Implementierung Programmierung Prozedur, Funktion, Typ, Modul, Klasse Methode Abbildung 1. 1: Abstraktionsebenen von Algorithmen und Datenstrukturen Das Diagramm läßt sich zunächst zerlegen in einen linken und einen rechten Teil; der linke Teil hat mit Algorithmen, der rechte mit Datenstrukturen zu tun. Weiterhin gibt es drei Abstraktionsebenen. Die abstrakteste Ebene ist die der Mathematik bzw. der forma len Spezifikation von Algorithmen oder Datenstrukturen. Ein Algorithmus realisiert eine Funktion, die entsprechend eine Spezifikation eines Algorithmus darstellt. Ein Algorith- 2 KAPITEL 1 EINFÜHRUNG mus stellt seinerseits eine Spezifikation einer zurealisierenden Prozedur (oder Funktion oder Methode im Sinne einer Programmiersprache) dar.

Wer programmiert muss Algorithmen entwerfen. Hier lernt man wie es geht.

Autorentext

Prof. Dr. Hartmut Güting, Fernuniversität Hagen
Dr. Stefan Dieker, Fernuniversität Hagen

Klappentext

Effiziente Algorithmen und Datenstrukturen bilden ein zentrales Thema der Informatik. Wer programmiert, sollte zu den wichtigsten Problembereichen grundlegende Lösungsverfahren kennen. Dieses Buch vermittelt entsprechende Kenntnisse und Fähigkeiten. Es setzt Akzente in der klaren Trennung zwischen Datentyp und Datenstruktur als Implementierung eines Datentyps und in der Beschreibung von Algorithmen auf angemessenem Abstraktionsniveau; einen besonderen thematischen Schwerpunkt bilden geometrische Algorithmen. Die jetzt neu bearbeitete Auflage des Buches benutzt Java als Implementierungssprache.

Inhalt
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.