|
Vorwort |
5 |
|
|
Inhaltsverzeichnis |
11 |
|
|
I Grundlegende Konzepte |
19 |
|
|
1 Vorbemerkungen und Überblick |
21 |
|
|
1.1 Informatik, Algorithmen und Datenstrukturen |
21 |
|
|
1.2 Historischer Überblick: Algorithmen |
23 |
|
|
1.3 Historie von Programmiersprachen und Java |
24 |
|
|
1.4 Grundkonzepte der Programmierung in Java |
27 |
|
|
2 Algorithmische Grundkonzepte |
33 |
|
|
2.1 Intuitiver Algorithmusbegriff |
33 |
|
|
2.1.1 Beispiele für Algorithmen |
33 |
|
|
2.1.2 Bausteine für Algorithmen |
37 |
|
|
2.1.3 Pseudocode-Notation für Algorithmen |
39 |
|
|
2.1.4 Struktogramme |
44 |
|
|
2.1.5 Rekursion |
44 |
|
|
2.2 Sprachen und Grammatiken |
47 |
|
|
2.2.1 Begriffsbildung |
48 |
|
|
2.2.2 Reguläre Ausdrücke |
49 |
|
|
2.2.3 Backus-Naur-Form (BNF) |
50 |
|
|
2.3 Elementare Datentypen |
52 |
|
|
2.3.1 Datentypen als Algebren |
52 |
|
|
2.3.2 Signaturen von Datentypen |
53 |
|
|
2.3.3 Der Datentyp bool |
54 |
|
|
2.3.4 Der Datentyp integer |
55 |
|
|
2.3.5 Felder und Zeichenketten |
56 |
|
|
2.4 Terme |
58 |
|
|
2.4.1 Bildung von Termen |
58 |
|
|
2.4.2 Algorithmus zur Termauswertung |
60 |
|
|
2.5 Datentypen in Java |
61 |
|
|
2.5.1 Primitive Datentypen |
61 |
|
|
2.5.2 Referenzdatentypen |
64 |
|
|
2.5.3 Operatoren |
67 |
|
|
3 Algorithmenparadigmen |
71 |
|
|
3.1 Überblick über Algorithmenparadigmen |
71 |
|
|
3.2 Applikative Algorithmen |
72 |
|
|
3.2.1 Terme mit Unbestimmten |
72 |
|
|
3.2.2 Funktionsdefinitionen |
73 |
|
|
3.2.3 Auswertung von Funktionen |
73 |
|
|
3.2.4 Erweiterung der Funktionsdefinition |
75 |
|
|
3.2.5 Applikative Algorithmen |
76 |
|
|
3.2.6 Beispiele für applikative Algorithmen |
77 |
|
|
3.3 Imperative Algorithmen |
85 |
|
|
3.3.1 Grundlagen imperativer Algorithmen |
85 |
|
|
3.3.2 Komplexe Anweisungen |
88 |
|
|
3.3.3 Beispiele für imperative Algorithmen |
91 |
|
|
3.4 Das logische Paradigma |
97 |
|
|
3.4.1 Logik der Fakten und Regeln |
97 |
|
|
3.4.2 Deduktive Algorithmen |
99 |
|
|
3.5 Weitere Paradigmen |
103 |
|
|
3.5.1 Genetische Algorithmen |
104 |
|
|
3.5.2 Neuronale Netze |
107 |
|
|
3.6 Umsetzung in Java |
110 |
|
|
3.6.1 Ausdrücke und Anweisungen |
111 |
|
|
3.6.2 Methoden |
118 |
|
|
3.6.3 Applikative Algorithmen und Rekursion |
124 |
|
|
4 Literaturhinweise zum Teil I |
131 |
|
|
II Algorithmen |
133 |
|
|
5 Ausgewählte Algorithmen |
135 |
|
|
5.1 Suchen in sortierten Folgen |
135 |
|
|
5.1.1 Sequenzielle Suche |
136 |
|
|
5.1.2 Binäre Suche |
138 |
|
|
5.2 Sortieren |
142 |
|
|
5.2.1 Sortieren: Grundbegriffe |
142 |
|
|
5.2.2 Sortieren durch Einfügen |
143 |
|
|
5.2.3 Sortieren durch Selektion |
145 |
|
|
5.2.4 Sortieren durch Vertauschen: BubbleSort |
147 |
|
|
5.2.5 Sortieren durch Mischen: MergeSort |
149 |
|
|
5.2.6 QuickSort |
153 |
|
|
5.2.7 Sortierverfahren im Vergleich |
157 |
|
|
6 Formale Algorithmenmodelle |
161 |
|
|
6.1 Registermaschinen |
161 |
|
|
6.2 Abstrakte Maschinen |
170 |
|
|
6.3 Markov-Algorithmen |
174 |
|
|
6.4 Church'sche These |
180 |
|
|
6.5 Interpreter für formale Algorithmenmodelle in Java |
182 |
|
|
6.5.1 Java: Markov-Interpreter |
182 |
|
|
6.5.2 Registermaschine in Java |
184 |
|
|
7 Eigenschaften von Algorithmen |
191 |
|
|
7.1 Berechenbarkeit und Entscheidbarkeit |
191 |
|
|
7.1.1 Existenz nichtberechenbarer Funktionen |
192 |
|
|
7.1.2 Konkrete nichtberechenbare Funktionen |
194 |
|
|
7.1.3 Das Halteproblem |
196 |
|
|
7.1.4 Nichtentscheidbare Probleme |
198 |
|
|
7.1.5 Post'sches Korrespondenzproblem |
199 |
|
|
7.2 Korrektheit von Algorithmen |
201 |
|
|
7.2.1 Relative Korrektheit |
201 |
|
|
7.2.2 Korrektheit von imperativen Algorithmen |
202 |
|
|
7.2.3 Korrektheitsbeweise für Anweisungstypen |
205 |
|
|
7.2.4 Korrektheit imperativer Algorithmen an Beispielen |
207 |
|
|
7.2.5 Korrektheit applikativer Algorithmen |
212 |
|
|
7.3 Komplexität |
214 |
|
|
7.3.1 Motivierendes Beispiel |
214 |
|
|
7.3.2 Asymptotische Analyse |
215 |
|
|
7.3.3 Komplexitätsklassen |
219 |
|
|
7.3.4 Analyse von Algorithmen |
222 |
|
|
8 Entwurf von Algorithmen |
225 |
|
|
8.1 Entwurfsprinzipien |
225 |
|
|
8.1.1 Schrittweise Verfeinerung |
225 |
|
|
8.1.2 Einsatz von Algorithmenmustern |
228 |
|
|
8.1.3 Problemreduzierung durch Rekursion |
228 |
|
|
8.2 Algorithmenmuster: Greedy |
229 |
|
|
8.2.1 Greedy-Algorithmen am Beispiel |
229 |
|
|
8.2.2 Greedy: Optimales Kommunikationsnetz |
231 |
|
|
8.2.3 Verfeinerung der Suche nach billigster Kante |
232 |
|
|
8.3 Rekursion: Divide-and-conquer |
234 |
|
|
8.3.1 Das Prinzip „Teile und herrsche“ |
235 |
|
|
8.3.2 Beispiel: Spielpläne für Turniere |
236 |
|
|
8.4 Rekursion: Backtracking |
238 |
|
|
8.4.1 Prinzip des Backtracking |
239 |
|
|
8.4.2 Beispiel: Das Acht-Damen-Problem |
241 |
|
|
8.5 Dynamische Programmierung |
243 |
|
|
8.5.1 Das Rucksackproblem |
244 |
|
|
8.5.2 Rekursive Lösung des Rucksackproblems |
245 |
|
|
8.5.3 Prinzip der dynamischen Programmierung |
246 |
|
|
9 Verteilte Berechnungen |
249 |
|
|
9.1 Kommunizierende Prozesse |
249 |
|
|
9.2 Modell der Petri-Netze |
250 |
|
|
9.2.1 Definition von Petri-Netzen |
250 |
|
|
9.2.2 Formalisierung von Petri-Netzen |
254 |
|
|
9.2.3 Das Beispiel der fünf Philosophen |
256 |
|
|
9.3 Programmieren nebenläufiger Abläufe |
258 |
|
|
9.3.1 Koordinierte Prozesse |
259 |
|
|
9.3.2 Programmieren mit Semaphoren |
260 |
|
|
9.3.3 Philosophenproblem mit Semaphoren |
262 |
|
|
9.3.4 Verklemmungsfreie Philosophen |
264 |
|
|
9.4 Beispielrealisierung in Java |
266 |
|
|
10 Literaturhinweise zum Teil II |
273 |
|
|
III Datenstrukturen |
275 |
|
|
11 Abstrakte Datentypen |
277 |
|
|
11.1 Signaturen und Algebren |
278 |
|
|
11.2 Algebraische Spezifikation |
280 |
|
|
11.2.1 Spezifikationen und Modelle |
281 |
|
|
11.2.2 Termalgebra und Quotiententermalgebra |
282 |
|
|
11.2.3 Probleme mit initialer Semantik |
285 |
|
|
11.3 Beispiele für abstrakte Datentypen |
286 |
|
|
11.3.1 Der Kellerspeicher (Stack) |
287 |
|
|
11.3.2 Beispiel für Kellernutzung |
289 |
|
|
11.3.3 Die Warteschlange (Queue) |
293 |
|
|
11.4 Entwurf von Datentypen |
294 |
|
|
12 Klassen, Schnittstellen und Objekte in Java |
297 |
|
|
12.1 Grundzüge der Objektorientierung |
297 |
|
|
12.2 Klassen und Objekte in Java |
300 |
|
|
12.3 Vererbung |
305 |
|
|
12.4 Abstrakte Klassen und Schnittstellen |
312 |
|
|
12.5 Ausnahmen |
315 |
|
|
12.6 Umsetzung abstrakter Datentypen |
317 |
|
|
13 Grundlegende Datenstrukturen |
323 |
|
|
13.1 Stack und Queue als Datentypen |
323 |
|
|
13.1.1 Implementierung des Stacks |
327 |
|
|
13.1.2 Implementierung der Queue |
328 |
|
|
13.1.3 Bewertung der Implementierungen |
330 |
|
|
13.2 Verkettete Listen |
331 |
|
|
13.3 Doppelt verkettete Listen |
338 |
|
|
13.4 Das Iterator-Konzept |
343 |
|
|
13.5 Java Collection Framework |
346 |
|
|
13.6 J2SE 5.0 und Generics |
350 |
|
|
14 Bäume |
353 |
|
|
14.1 Bäume: Begriffe und Konzepte |
353 |
|
|
14.2 Binärer Baum: Datentyp und Basisalgorithmen |
356 |
|
|
14.2.1 Der Datentyp „Binärer Baum“ |
356 |
|
|
14.2.2 Algorithmen zur Traversierung |
361 |
|
|
14.3 Suchbäume |
366 |
|
|
14.3.1 Suchen in Suchbäumen |
367 |
|
|
14.3.2 Einfügen und Löschen |
370 |
|
|
14.3.3 Komplexität der Operationen |
375 |
|
|
14.4 Ausgeglichene Bäume |
376 |
|
|
14.4.1 Rot-Schwarz-Bäume |
377 |
|
|
14.4.2 AVL-Bäume |
386 |
|
|
14.4.3 B-Bäume |
394 |
|
|
14.5 Digitale Bäume |
407 |
|
|
14.5.1 Tries |
408 |
|
|
14.5.2 Patricia-Bäume |
414 |
|
|
14.6 Praktische Nutzung von Bäumen |
415 |
|
|
14.6.1 Sortieren mit Bäumen: HeapSort |
415 |
|
|
14.6.2 Sets mit binären Suchbäumen |
421 |
|
|
15 Hashverfahren |
427 |
|
|
15.1 Grundprinzip des Hashens |
427 |
|
|
15.2 Grundlagen und Verfahren |
428 |
|
|
15.2.1 Hashfunktionen |
428 |
|
|
15.2.2 Behandlung von Kollisionen |
430 |
|
|
15.2.3 Aufwand beim Hashen |
434 |
|
|
15.2.4 Hashen in Java |
436 |
|
|
15.3 Dynamische Hashverfahren |
440 |
|
|
15.3.1 Grundideen für dynamische Hashverfahren |
441 |
|
|
15.3.2 Erweiterbares Hashen |
444 |
|
|
15.3.3 Umsetzung des erweiterbaren Hashens |
446 |
|
|
16 Graphen |
451 |
|
|
16.1 Arten von Graphen |
451 |
|
|
16.1.1 Ungerichtete Graphen |
452 |
|
|
16.1.2 Gerichtete Graphen |
453 |
|
|
16.1.3 Gewichtete Graphen |
454 |
|
|
16.2 Realisierung von Graphen |
455 |
|
|
16.2.1 Knoten- und Kantenlisten |
455 |
|
|
16.2.2 Adjazenzmatrix |
456 |
|
|
16.2.3 Graphen als dynamische Datenstrukturen |
456 |
|
|
16.2.4 Transformationen zwischen Darstellungen |
457 |
|
|
16.2.5 Vergleich der Komplexität |
458 |
|
|
16.2.6 Eine Java-Klasse für Graphen |
458 |
|
|
16.3 Ausgewählte Graphenalgorithmen |
461 |
|
|
16.3.1 Breitendurchlauf |
461 |
|
|
16.3.2 Tiefendurchlauf |
465 |
|
|
16.3.3 Zyklenfreiheit und topologisches Sortieren |
469 |
|
|
16.4 Algorithmen auf gewichteten Graphen |
472 |
|
|
16.4.1 Kürzeste Wege |
473 |
|
|
16.4.2 Dijkstras Algorithmus |
474 |
|
|
16.4.3 A*-Algorithmus |
477 |
|
|
16.4.4 Kürzeste Wege mit negativen Kantengewichten |
484 |
|
|
16.4.5 Maximaler Durchfluss |
487 |
|
|
16.4.6 Der Ford-Fulkerson-Algorithmus |
489 |
|
|
16.5 Weitere Fragestellungen für Graphen |
493 |
|
|
17 Suchen in Texten |
497 |
|
|
17.1 Probleme der Worterkennung |
497 |
|
|
17.2 Knuth-Morris-Pratt |
499 |
|
|
17.3 Boyer-Moore |
503 |
|
|
17.4 Pattern Matching |
509 |
|
|
17.4.1 Reguläre Ausdrücke |
509 |
|
|
17.4.2 Endliche Automaten |
510 |
|
|
17.4.3 Java-Klassen für reguläre Ausdrücke |
516 |
|
|
17.4.4 Ähnlichkeit von Zeichenketten: Die Levenshtein-Distanz |
517 |
|
|
18 Literaturhinweise zum Teil III |
521 |
|
|
A Quelltext der Klasse IOUtils |
523 |
|
|
Abbildungsverzeichnis |
527 |
|
|
Tabellenverzeichnis |
533 |
|
|
Algorithmenverzeichnis |
535 |
|
|
Beispielverzeichnis |
537 |
|
|
Programmverzeichnis |
539 |
|
|
Literaturverzeichnis |
541 |
|
|
Index |
545 |
|