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.

Effiziente Algorithmen und Datenstrukturen sind ein zentrales Thema der Informatik. Beide Themen sind untrennbar miteinander verknüpft, denn Algorithmen arbeiten auf Datenstrukturen und Datenstrukturen enthalten wiederum Algorithmen als Komponenten. Dieses Buch vermittelt grundlegende Lösungsverfahren zu den wichtigsten Problembereichen bei der Arbeit mit Datenstrukturen und Algorithmen. Leser lernen neue Algorithmen zu entwerfen und ihre Kosten in Bezug auf Laufzeit und Speicherplatz zu analysieren.Die Autoren führen in programmiersprachliche Konzepte für Datenstrukturen ein und erläutern Datentypen, die die Bausteine für die Implementierung komplexer Algorithmen und Datenstrukturen bilden. Neben der Darstellung von Sortieralgorithmen und Graphen setzt das Buch mit Kapiteln zu geometrischen Algorithmen und Techniken zur Kürzeste-Wege-Suche mittels Kontraktionshierarchien einige besondere Schwerpunkte. Jedes Kapitel schließt mit Aufgaben und Literaturhinweisenfür alle, die die Thematik vertiefen wollen. Alle Programmbeispiele in dem Buch sind in Java formuliert. Grundlage des Buchs sind Veranstaltungen zu Datenstrukturen und zu geometrischen Algorithmen, die Ralf Hartmut Güting seit vielen Jahren an der Fernuniversität Hagen anbietet. Der Stoff umfasst eine einsemestrige vierstündige Vorlesung. Für die Neuauflage wurde das Lehrbuch erweitert und aktualisiert. Es richtet sich an Softwareentwickler und dient als Lehrbuch im Studiengang Informatik.

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.

Effiziente Algorithmen und Datenstrukturen sind ein zentrales Thema der Informatik. Beide Themen sind untrennbar miteinander verknüpft, denn Algorithmen arbeiten auf Datenstrukturen und Datenstrukturen enthalten wiederum Algorithmen als Komponenten. Dieses Buch vermittelt grundlegende Lösungsverfahren zu den wichtigsten Problembereichen bei der Arbeit mit Datenstrukturen und Algorithmen. Leser lernen neue Algorithmen zu entwerfen und ihre Kosten in Bezug auf Laufzeit und Speicherplatz zu analysieren.Die Autoren führen in programmiersprachliche Konzepte für Datenstrukturen ein und erläutern Datentypen, die die Bausteine für die Implementierung komplexer Algorithmen und Datenstrukturen bilden. Neben der Darstellung von Sortieralgorithmen und Graphen setzt das Buch mit Kapiteln zu geometrischen Algorithmen und Techniken zur Kürzeste-Wege-Suche mittels Kontraktionshierarchien einige besondere Schwerpunkte. Jedes Kapitel schließt mit Aufgaben und Literaturhinweisenfür alle, die die Thematik vertiefen wollen. Alle Programmbeispiele in dem Buch sind in Java formuliert. Grundlage des Buchs sind Veranstaltungen zu Datenstrukturen und zu geometrischen Algorithmen, die Ralf Hartmut Güting seit vielen Jahren an der Fernuniversität Hagen anbietet. Der Stoff umfasst eine einsemestrige vierstündige Vorlesung. Für die Neuauflage wurde das Lehrbuch erweitert und aktualisiert. Es richtet sich an Softwareentwickler und dient als Lehrbuch im Studiengang Informatik.