Оглавление
Gunter Saake. Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen
Vorwort
Vorwort zur 5. Auflage
Vorwort zur 4. Auflage
Vorwort zur 3. Auflage
Vorwort zur 2. Auflage
Vorwort zur 1. Auflage
Danksagungen
Inhaltsverzeichnis
1Vorbemerkungen und Überblick
1.1Informatik, Algorithmen und Datenstrukturen
1.2Historischer Überblick: Algorithmen
1.3Historie von Programmiersprachen und Java
1.4Grundkonzepte der Programmierung in Java
Definition 1.1 Programm
Programm 1.1 »Hello World!« in Java
2Algorithmische Grundkonzepte
2.1Intuitiver Algorithmusbegriff
2.1.1Beispiele für Algorithmen
Beispiel 2.1 Intuitiver Algorithmenbegriff
Beispiel 2.2 Bekannte Algorithmen
Beispiel 2.3 Nichdeterministischer Ablauf
Beispiel 2.4 Nichtdeterminierter vs. determinierter Algorithmus
Beispiel 2.5 Funktionen zu den Beispielalgorithmen
2.1.2Bausteine für Algorithmen
2.1.3Pseudocode-Notation für Algorithmen
Sequenz
Bedingte Anweisungen
Schleifen / Iteration
Varianten der Iteration
2.1.4Struktogramme
2.1.5Rekursion
Algorithmus 2.1 Türme von Hanoi (rekursiv)
2.2Sprachen und Grammatiken
2.2.1Begriffsbildung
2.2.2Reguläre Ausdrücke
2.2.3Backus-Naur-Form (BNF)
Beispiel 2.6 Syntax für Pseudocode-Algorithmen
2.3Elementare Datentypen
2.3.1Datentypen als Algebren
2.3.2Signaturen von Datentypen
Beispiel 2.7 Datentyp für natürliche Zahlen
2.3.3Der Datentyp bool
2.3.4Der Datentyp integer
2.3.5Felder und Zeichenketten
2.4Terme
2.4.1Bildung von Termen
Definition 2.1 Definition vonint-Termen
2.4.2Algorithmus zur Termauswertung
2.5Datentypen in Java
2.5.1Primitive Datentypen
2.5.2Referenzdatentypen
2.5.3Operatoren
3Algorithmenparadigmen
3.1Überblick über Algorithmenparadigmen
3.2Applikative Algorithmen
3.2.1Terme mit Unbestimmten
3.2.2Funktionsdefinitionen
Definition 3.1 Funktionsdefinitionen
Beispiel 3.1 Beispiele für Funktionsdefinitionen
3.2.3Auswertung von Funktionen
Beispiel 3.2 Funktionsaufrufe
3.2.4Erweiterung der Funktionsdefinition
Beispiel 3.3 Erweiterte Funktionsdefinition
Beispiel 3.4 Rekursive Funktionsdefinition
3.2.5Applikative Algorithmen
Definition 3.2 Applikativer Algorithmus
Beispiel 3.5 Undefinierte Ergebnisse
3.2.6Beispiele für applikative Algorithmen
Beispiel 3.6 Fakultätfunktion n!
Beispiel 3.7 Fibonacci-Zahlen
Beispiel 3.8 Produkt nur unter Verwendung der Addition
Beispiel 3.9 Größter gemeinsamer Teiler ggT
Beispiel 3.10 Applikativer Algorithmus mit mehreren Funktionen
Beispiel 3.11 Primzahltest
Beispiel 3.12 Terminierung und undefinierte Funktionen
Beispiel 3.13 McCarthys 91-Funktion
Beispiel 3.14 Algorithmus mit kniffeliger Bedeutung
Beispiel 3.15 Ackermannn-Funktion
3.3Imperative Algorithmen
3.3.1Grundlagen imperativer Algorithmen
Definition 3.3 Variablen
Definition 3.4 Zustände
Definition 3.5 Ausdrücke
Beispiel 3.16 Zustand
Beispiel 3.17 Berechnung eines Wertes
Beispiel 3.18 Transformation von Anweisungen
3.3.2Komplexe Anweisungen
Definition 3.6 Semantik imperativer Algorithmen
3.3.3Beispiele für imperative Algorithmen
Beispiel 3.19 Fakultätfunktion
Beispiel 3.20 Fibonacci-Zahlen
Beispiel 3.21 Größter gemeinsamer Teiler (euklidischer Algorithmus)
Beispiel 3.22 ggT mittels Division
Beispiel 3.23 Bestimmung der Semantik eines imperativen Algorithmus
3.4Das logische Paradigma
3.4.1Logik der Fakten und Regeln
3.4.2Deduktive Algorithmen
Definition 3.7 Deduktiver Algorithmus
3.5Weitere Paradigmen
3.5.1Genetische Algorithmen
Algorithmus 3.1 Grundprinzip genetischer Algorithmen
3.5.2Neuronale Netze
3.6Umsetzung in Java
3.6.1Ausdrücke und Anweisungen
Ausdrücke
Blöcke
Bedingte Anweisungen
Schleifen
3.6.2Methoden
Programm 3.1 Imperative Berechnung der Fakultät
3.6.3Applikative Algorithmen und Rekursion
Programm 3.2 Rekursive Berechnung der Fakultät
Programm 3.3 Programm zum Darstellen des Pythagoras-Baumes
Programm 3.4 Hauptprogramm für den Pythagoras-Baum
4Literaturhinweise zum Teil I
5Ausgewählte Algorithmen
5.1Suchen in sortierten Folgen
5.1.1Sequenzielle Suche
Algorithmus 5.1 Sequenzielles Suchen
Programm 5.1 Sequenzielle Suche
5.1.2Binäre Suche
Algorithmus 5.2 Binäres Suchen
Programm 5.2 Binäre Suche
5.2Sortieren
5.2.1Sortieren: Grundbegriffe
Beispiel 5.1 Stabilität von Sortierverfahren
5.2.2Sortieren durch Einfügen
Algorithmus 5.3 Sortieren durch Einfügen
Programm 5.3 Implementierung des InsertionSort
5.2.3Sortieren durch Selektion
Algorithmus 5.4 Sortieren durch Selektion
Programm 5.4 Implementierung des SelectionSort
5.2.4Sortieren durch Vertauschen: BubbleSort
Algorithmus 5.5 Sortieren durch Vertauschen
Programm 5.5 Implementierung des BubbleSort
5.2.5Sortieren durch Mischen: MergeSort
Algorithmus 5.6 Mischen von zwei Folgen
Algorithmus 5.7 Sortieren durch Mischen
Programm 5.6 Implementierung des MergeSort
5.2.6QuickSort
Algorithmus 5.8 QuickSort
Algorithmus 5.9 Zerlegen beim QuickSort
Programm 5.7 Implementierung des QuickSort
5.2.7Sortieren durch Verteilen: RadixSort
Programm 5.8 Implementierung des RadixSort
5.2.8Sortierverfahren im Vergleich
SelectionSort
InsertionSort
BubbleSort
MergeSort
QuickSort
RadixSort
6Formale Algorithmenmodelle
6.1Registermaschinen
Definition 6.1 Definition einer Registermaschine
Beispiel 6.1 Registermaschine M1
Definition 6.2 Berechnete Funktion einer Registermaschine
Beispiel 6.2 Registermaschine M2
Beispiel 6.3 Registermaschine M3
Beispiel 6.4 Registermaschine M4
6.2Abstrakte Maschinen
Definition 6.3 Abstrakte Maschine
Definition 6.4 Endkonfiguration
Definition 6.5 Laufzeit einer abstrakten Maschine
Definition 6.6 Berechnete Funktion einer abstrakten Maschine
Beispiel 6.5 Applikativer Algorithmus als abstrakte Maschine
Beispiel 6.6 Imperativer Algorithmus als abstrakte Maschine
6.3Markov-Algorithmen
Beispiel 6.7 Anwendung einer Regel
Definition 6.7 Markov-Algorithmus
Beispiel 6.8 Markov-Tafel für Addition von 1
Beispiel 6.9 Markov-Tafel für Addition im unären System
Beispiel 6.10 Markov-Tafel für Verdopplung einer Strichliste
Beispiel 6.11 Markov-Tafel zur Multiplikation im unären System
Beispiel 6.12 Markov-Tafel für Kopieren einer Zeichenkette
6.4Church’sche These
Definition 6.8 Universelles Algorithmenmodell
6.5Interpreter für formale Algorithmenmodelle in Java
6.5.1Java: Markov-Interpreter
Programm 6.1 Einfacher Markov-Interpreter in Java
6.5.2Registermaschine in Java
Programm 6.2 Klasse für die Konfiguration
Programm 6.3 Schnittstelle für Befehle
Programm 6.4 Implementierung des Befehls LOAD
Programm 6.5 Implementierung des Befehls IF-GOTO
Programm 6.6 Implementierung der Registermaschine
Programm 6.7 Programmausführung mit der Registermaschine
7Eigenschaften von Algorithmen
7.1Berechenbarkeit und Entscheidbarkeit
7.1.1Existenz nichtberechenbarer Funktionen
Satz 7.1 Abzählbarkeit von A
Satz 7.2 Abzählbarkeit der berechenbaren Funktionen
Satz 7.3 Überabzählbarkeit der einstelligen Funktionen
7.1.2Konkrete nichtberechenbare Funktionen
Definition 7.1 Von x berechnete Funktion
Definition 7.2 Urbildbereich einer Funktion
Satz 7.4 Halteproblem
7.1.3Das Halteproblem
Satz 7.5 Allgemeines Halteproblem
7.1.4Nichtentscheidbare Probleme
7.1.5Post’sches Korrespondenzproblem
Beispiel 7.1 Post’sches Korrespondenzproblem
Beispiel 7.2 Post’sches Korrespondenzproblem ohne Lösung
7.2Korrektheit von Algorithmen
7.2.1Relative Korrektheit
7.2.2Korrektheit von imperativen Algorithmen
Beispiel 7.3 Anweisungen über Variablen
Definition 7.3 Partielle Korrektheit
7.2.3Korrektheitsbeweise für Anweisungstypen
Atomare Anweisungen
Sequenzen von Anweisungen
Selektion
Iteration und Schleifeninvarianten
Übertragbarkeit auf imperative Programmiersprachen
7.2.4Korrektheit imperativer Algorithmen an Beispielen
Beispiel 7.4 Korrektheit von MULT
Beispiel 7.5 Korrektheit von XYZ
Beweis der Terminierung von imperativen Algorithmen
Beispiel 7.6 Terminierung von XYZ
7.2.5Korrektheit applikativer Algorithmen
Beispiel 7.7 Beispiel für Induktionsbeweis
7.3Komplexität
7.3.1Motivierendes Beispiel
7.3.2Asymptotische Analyse
Beispiel 7.8 Aufwand für Schleifen
Beispiel 7.9 Rechnen in Größenordnungen I
Definition 7.4 O-Notation
Beispiel 7.10 Rechnen in Größenordnungen II
Beispiel 7.11 Rechnen in Größenordnungen III
7.3.3Komplexitätsklassen
7.3.4Analyse von Algorithmen
(1) for-Schleifen
(2) Geschachtelte for-Schleifen
(3) Nacheinanderausführung
(4) if-else-Bedingungen
8Entwurf von Algorithmen
8.1Entwurfsprinzipien
8.1.1Schrittweise Verfeinerung
Beispiel 8.1 Durch schrittweise Verfeinerung zur Berechnung des Medians
Programm 8.1 Java-Umsetzung des Spielablaufs
8.1.2Einsatz von Algorithmenmustern
8.1.3Problemreduzierung durch Rekursion
8.2Algorithmenmuster: Greedy
8.2.1Greedy-Algorithmen am Beispiel
8.2.2Greedy: Optimales Kommunikationsnetz
8.2.3Verfeinerung der Suche nach billigster Kante
8.3Rekursion: Divide-and-conquer
8.3.1Das Prinzip »Teile und herrsche«
8.3.2Beispiel: Spielpläne für Turniere
8.4Rekursion: Backtracking
8.4.1Prinzip des Backtracking
8.4.2Beispiel: Das Acht-Damen-Problem
8.4.3Beispiel: Tic Tac Toe mit Backtracking
Programm 8.2 Zugberechnung für Tic Tac Toe
8.5Dynamische Programmierung
8.5.1Das Rucksackproblem
8.5.2Rekursive Lösung des Rucksackproblems
8.5.3Prinzip der dynamischen Programmierung
9Parallele und verteilte Berechnungen
9.1Grundlagen
9.2Modell der Petri-Netze
9.2.1Definition von Petri-Netzen
9.2.2Formalisierung von Petri-Netzen
9.2.3Das Beispiel der fünf Philosophen
9.3Programmieren nebenläufiger Abläufe
9.3.1Koordinierte Prozesse
9.3.2Programmieren mit Semaphoren
9.3.3Philosophenproblem mit Semaphoren
9.3.4Verklemmungsfreie Philosophen
9.4Nebenläufige Berechnungen in Java
9.4.1Threads und wechselseitiger Ausschluss
Programm 9.1 Implementierung als Subklasse von Thread
Programm 9.2 Implementierung über Runnable-Schnittstelle
Programm 9.3 Synchronisation von Producer-Consumer
9.4.2Parallelisierung in Java
Programm 9.4 Parallele Berechnung der Fibonacci-Zahlen
Programm 9.5 Thread-Pool zur parallelen Berechnung
9.4.3Das Philosophenproblem in Java
Programm 9.6 Grobstruktur eines Philosophen
Programm 9.7 Implementierung der Gabeln
Programm 9.8 Vollständige Implementierung eines Philosophen
Programm 9.9 Initialisierung der fünf Philosophen
Programm 9.10 Semaphor als Java-Klasse
10Literaturhinweise zum Teil II
11Abstrakte Datentypen
11.1Signaturen und Algebren
Definition 11.1 Signatur
Definition 11.2 Algebra zu einer Signatur
11.2Algebraische Spezifikation
11.2.1Spezifikationen und Modelle
11.2.2Termalgebra und Quotiententermalgebra
Definition 11.3 Termalgebra
Definition 11.4 Quotiententermalgebra
11.2.3Probleme mit initialer Semantik
11.3Beispiele für abstrakte Datentypen
11.3.1Der Kellerspeicher (Stack)
11.3.2Beispiel für Kellernutzung
Keller: Komplexeres Beispiel
11.3.3Die Warteschlange (Queue)
11.4Entwurf von Datentypen
12Klassen, Schnittstellen und Objekte in Java
12.1Grundzüge der Objektorientierung
Definition 12.1 Objekt
Definition 12.2 Klasse
12.2Klassen und Objekte in Java
Programm 12.1 Beispiel einer Klassendefinition
12.3Vererbung
Programm 12.2 Vererbung in Java
12.4Abstrakte Klassen und Schnittstellen
12.5Ausnahmen
Programm 12.3 Definition der MeineException
12.6Umsetzung abstrakter Datentypen
Programm 12.4 Implementierung des ADT RatNumber
12.7Lambda-Ausdrücke
13Grundlegende Datenstrukturen
13.1Stack und Queue als Datentypen
Programm 13.1 Definition der Stack-Schnittstelle
Programm 13.2 Nutzung des Datentyps Stack
Programm 13.3 Definition der Queue-Schnittstelle
13.1.1Implementierung des Stacks
Programm 13.4 Implementierung des Stacks auf Basis eines Feldes
13.1.2Implementierung der Queue
Programm 13.5 Implementierung der Queue auf Basis eines Feldes
13.1.3Bewertung der Implementierungen
13.2Verkettete Listen
Programm 13.6 Definition der Knotenklasse der Liste
Programm 13.7 Definition der Klasse List
Programm 13.8 Implementierung des Stacks auf Basis von List
13.3Doppelt verkettete Listen
Programm 13.9 Klasse Node für eine doppelt verkettete Liste
Programm 13.10 Implementierung der doppelt verketteten Liste
13.4Skip-Listen
Programm 13.11 Implementierung der Skip-Liste
13.5Das Iterator-Konzept
Programm 13.12 Iterator für die Klasse DList
13.6Java Collection Framework
13.7Generics in Java
14Bäume
14.1Bäume: Begriffe und Konzepte
14.2Binärer Baum: Datentyp und Basisalgorithmen
14.2.1Der Datentyp »Binärer Baum«
Programm 14.1 Knotenklasse für BinaryTree
Beispiel für Binärbaum
14.2.2Algorithmen zur Traversierung
Inorder-Durchlauf
Algorithmus 14.1 Inorder-Durchlauf
Preorder-Durchlauf
Algorithmus 14.2 Preorder-Durchlauf
Postorder-Durchlauf
Algorithmus 14.3 Postorder-Durchlauf
Levelorder-Durchlauf
Algorithmus 14.4 Levelorder-Durchlauf
Programm 14.2 Traversierungsmethoden I
Programm 14.3 Traversierung im binären Baum
Programm 14.4 Traversierungsmethoden II
14.3Suchbäume
Programm 14.5 Vergleichsmethode für die Klasse TreeNode
14.3.1Suchen in Suchbäumen
Algorithmus 14.5 Suche im binären Suchbaum (rekursiv)
Algorithmus 14.6 Suche im binären Suchbaum (iterativ)
Algorithmus 14.7 Minimales Element im Suchbaum
Programm 14.6 Suchoperationen für die Klasse BinaryTree
14.3.2Einfügen und Löschen
Programm 14.7 Einfügen für die Klasse BinaryTree
Algorithmus 14.8 Löschen im binären Suchbaum
Programm 14.8 Löschen für die Klasse BinaryTree
14.3.3Komplexität der Operationen
14.4Ausgeglichene Bäume
14.4.1Rot-Schwarz-Bäume
2-3-4-Bäume
Struktur von Rot-Schwarz-Bäumen
Definition 14.1 Rot-Schwarz-Baum
Programm 14.9 Knotenklasse für RedBlackTree
Programm 14.10 Einfügen im Rot-Schwarz-Baum
Programm 14.11 Splitten von 4-Knoten im Rot-Schwarz-Baum
Programm 14.12 Rotation im Rot-Schwarz-Baum
14.4.2AVL-Bäume
Definition 14.2 AVL-Kriterium
Einfügen in AVL-Bäumen
Beispiel 14.1 Rotationen im AVL-Baum
Programm 14.13 Knotenklasse für den AVL-Baum
Programm 14.14 Einfügen im AVL-Baum
Programm 14.15 Rotationen im AVL-Baum
14.4.3B-Bäume
Prinzip des B-Baumes
Definition 14.3 B-Baum
Programm 14.16 Knotenklasse für BTree
Suchen in B-Bäumen
Programm 14.17 Suchen im BTree
Einfügen und Löschen
Programm 14.18 Einfügen im BTree
Programm 14.19 Einfügen und Split im BTree-Knoten
Komplexität der Operationen
14.5Digitale Bäume
14.5.1Tries
Programm 14.20 Knotenklassen für einen binären Trie
Programm 14.21 Einfügemethoden für den binären Trie
Programm 14.22 Suchen im binären Trie
14.5.2Patricia-Bäume
14.6Praktische Nutzung von Bäumen
14.6.1Sortieren mit Bäumen: HeapSort
Algorithmus 14.9 HeapSort
Programm 14.23 Implementierung von HeapSort
14.6.2Sets mit binären Suchbäumen
Programm 14.24 Implementierung von Set auf Basis eines Baumes
Programm 14.25 Iterator für TreeSet
15Hashverfahren
15.1Grundprinzip des Hashens
15.2Grundlagen und Verfahren
15.2.1Hashfunktionen
15.2.2Behandlung von Kollisionen
Verkettung der Überläufer
Lineares Sondieren
Quadratisches Sondieren
15.2.3Aufwand beim Hashen
Aufwand beim Hashen mit Sondieren
15.2.4Hashen in Java
Programm 15.1 Schnittstelle für Hashtabellen
Programm 15.2 Hashtabelle mit Verkettung der Überläufer
Programm 15.3 Hashtabelle mit linearem Sondieren
15.2.5Cuckoo-Hashing
Beispiel 15.1 Cuckoo-Hashing
15.3Dynamische Hashverfahren
15.3.1Grundideen für dynamische Hashverfahren
Erste Idee: Hashfunktionen mit dynamisch erweiterbarem Bildbereich
Zweite Idee: Bucket kann mehr als einen Wert aufnehmen
Dritte Idee: Erweiterung des Bildbereichs nur dort wo nötig
Vierte Idee: Binärer Trie zur Verwaltung der Blöcke
Fünfte Idee: Ausgeglichener Trie als Feld gespeichert
15.3.2Erweiterbares Hashen
15.3.3Umsetzung des erweiterbaren Hashens
Programm 15.4 Klasse für das erweiterbare Hashen
Programm 15.5 Initialisierung beim erweiterbaren Hashen
Programm 15.6 Verdopplung der Indexgröße
Programm 15.7 Einfügen beim erweiterbaren Hashen
Programm 15.8 Split eines Blocks
Lektionen aus erweiterbarem Hashen
16Graphen
16.1Arten von Graphen
16.1.1Ungerichtete Graphen
Definition 16.1 Ungerichteter Graph
16.1.2Gerichtete Graphen
Definition 16.2 Gerichteter Graph
16.1.3Gewichtete Graphen
16.1.4Weitere Eigenschaften von Graphen
16.2Realisierung von Graphen
16.2.1Knoten- und Kantenlisten
16.2.2Adjazenzmatrix
16.2.3Graphen als dynamische Datenstrukturen
16.2.4Transformationen zwischen Darstellungen
16.2.5Vergleich der Komplexität
16.2.6Eine Java-Klasse für Graphen
Programm 16.1 Repräsentation eines Graphen
16.3Ausgewählte Graphenalgorithmen
16.3.1Breitendurchlauf
Algorithmus 16.1 Breitendurchlauf
Programm 16.2 Implementierung des Breitendurchlaufs
16.3.2Tiefendurchlauf
Algorithmus 16.2 Tiefendurchlauf
16.3.3Zyklenfreiheit und topologisches Sortieren
Test auf Zyklenfreiheit
Topologisches Sortieren
16.4Algorithmen auf gewichteten Graphen
16.4.1Kürzeste Wege
16.4.2Dijkstras Algorithmus
Algorithmus 16.3 Dijkstras Algorithmus
16.4.3A*-Algorithmus
Algorithmus 16.4 A*-Algorithmus
Programm 16.3 A*-Suche in Java
16.4.4Kürzeste Wege mit negativen Kantengewichten
Algorithmus 16.5 Bellmann-Ford-Algorithmus
16.4.5Maximaler Durchfluss
Korrekter Durchfluss
Maximaler Durchfluss
16.4.6Der Ford-Fulkerson-Algorithmus für die Bestimmung des maximalen Flusses
16.5Zentralitätsanalyse in Graphen
Programm 16.4 PageRank-Implementierung
16.6Weitere Fragestellungen für Graphen
Problem des Handlungsreisenden
Planare Graphen
Einfärben von Graphen
17Algorithmen auf Texten
17.1Probleme der Worterkennung
Algorithmus 17.1 Brute-Force-Suche in Texten
17.2Knuth-Morris-Pratt
Algorithmus 17.2 Knuth-Morris-Pratt
Programm 17.1 Java-Methoden für denKMP-Algorithmus
17.3Boyer-Moore
Algorithmus 17.3 Boyer-Moore
Programm 17.2 Implementierung des Boyer-Moore-Algorithmus
17.4Pattern Matching
17.4.1Reguläre Ausdrücke
17.4.2Endliche Automaten
Programm 17.3 Simulation eines NEA
17.4.3Java-Klassen für reguläre Ausdrücke
17.5Ähnlichkeit von Zeichenketten
17.5.1Levenshtein-Distanz
Programm 17.4 Implementierung der Levenshtein-Distanz
17.5.2n-Gramme
Beispiel 17.1 3-Gramme für »Qualität«
Beispiel 17.2 Abstand mittels 3-Grammen
Programm 17.5 Implementierung des 3-Gramm-Vergleichs
17.5.3Anwendungen der Ähnlichkeitsvergleiche
18Literaturhinweise zum Teil III
AQuelltext der Klasse IOUtils
Abbildungsverzeichnis
Tabellenverzeichnis
Algorithmenverzeichnis
Beispielverzeichnis
Programmverzeichnis
Literaturverzeichnis
Index. Symbole
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
