Inhaltverzeichnis Copyright© 2007 by Doina Logofătu
GELEITWORT von Dr. Eric Müller VII
VORWORT IX
DANKSAGUNG XI
1 ALGORITHMEN – GRUNDLEGENDE KONZEPTE 1
Abstammung des Wortes Algorithmus 1
Alternative Definitionen 1
Beispiele für Algorithmen 2
Euklidischer Algorithmus 2
Das Sieb des Eratosthenes 3
Binäre Suche 4
Rezept für Tiramisu 6
Vom Problem zur Lösung 7
Eigenschaften eines Algorithmus 10
Algorithmik 10
Das RAM-Rechnermodell 11
Die Komplexität von Algorithmen 12
Optimalität, Reduktion, Beispiele 14
Wachstum von O(g(n)) 17
Die reelle Zeit eines Algorithmus (polynomial vs. exponentiell) 17
Klassifizierung der Probleme (P, NP, NP-vollständig, NP-hart) 18
Probleme NP-vollständig (NP-complete) 19
Das Erfüllbarkeitsproblem (SAT) 20
Die Klasse der NP-hart Probleme 21
Aufgaben 22
2 VERSCHACHTELTE SCHACHTELN 25
Problembeschreibung 25
Problemanalyse und Entwurf der Lösung 26
Der Algorithmus 27
Das Programm 29
Die Programmanalyse 32
Aufgaben 37
Anmerkungen 38
3 GREEDY 39
Grundlagen 39
Problem 1. Rucksackproblem 40
Problem 2. Kartenfärbung 43
Problem 3. Springer auf dem Schachbrett 45
Problem 4. Minimaler Spannbaum (Kruskal-Algorithmus) 48
Problem 5. Huffman-Kodierung 56
4 DATA ORDERING PROBLEM 65
Problembeschreibung 65
Problemdomäne, Definitionen 66
DOP und DOPI sind NP-vollständig 71
Algorithmen für DOP und DOPI 72
Zufällige-Lösung-Algorithmen (RAN) 73
Exakt-Algorithmen (EX) 74
Greedy_Min-Algorithmen (GM) 74
Greedy_Min Simplified-Algorithmen (GMS) 75
Algorithmen mit unterer Schranke (LB) 75
Implementierungsdetails 77
Programm 84
Auswertung der Ergebnisse 94
Aufgaben 96
5 REKURSION 99
Vollständige Induktion 99
Rekursion: Grundlagen 105
Problem 1. Quersumme und Spiegelung einer natürlichen Zahl 106
Problem 2. Die Zahl 4 108
Problem 3. Rest großer Potenzen 111
Problem 4. Die Torte (lineare Rekursion) 115
Problem 5. Die Ackermannfunktion
(verschachtelte Rekursion, "compound recursion") 118
Problem 6. Rekursive Zahlenumwandlung
(Dezimalsystem in System mit Basis P) 120
Problem 7. Summe zweier Wurzeln (verzweigte Rekursion) 123
Problem 8. Collatz-Funktion (nicht-monotone Rekursion) 125
Problem 9. Quadrate und Quadrätchen 127
Problem 10. Quadrate (direkte Rekursion) 130
Problem 11. Quadrate und Kreise (indirekte Rekursion) 133
Problem 12. Die Koch’sche Schneeflockenkurve 135
6 TEILE UND HERRSCHE 145
Grundlagen 145
Problem 1. Größter gemeinsamer Teiler mehrerer Zahlen 146
Problem 2. Die Türme von Hanoi 148
Problem 3. Integral mit Trapezregel 150
Problem 4. Quicksort 152
Problem 5. Mergesort (Sortieren durch Verschmelzen) 155
Problem 6. Quad-Bäume 157
Problem 7. Diskrete Fourier-Transformation (DFT) 162
7 BACKTRACKING 169
Problem 1. Das Problem der n Damen 169
Allgemeine Bemerkungen zum Backtracking-Verfahren 175
Problem 2. Das Problem der n Türme 178
Problem 3. Das Problem der Türme auf den ersten m Reihen 179
Problem 4. Das Problem der aufsteigenden Türme
auf den ersten m Reihen 180
Problem 5. Die Freundschafts-Jugendherberge 181
Problem 6. Partitionen einer natürlichen Zahl 182
Problem 7. Erdkunde-Referate 185
Problem 8. Alle Wege des Springers 188
Problem 9. Das Fotoproblem 191
Problem 10. Der ausbrechende Ball 193
Problem 11. Orangensport 196
Problem 12. Testmusterkompaktierung 205
Problem 13. Sudoku 214
Problem 14. Das Haus des Nikolaus 221
Noch 10 Probleme 224
8 DYNAMISCHE PROGRAMMIERUNG 231
1. Ursprung des Konzeptes 231
2. Optimalitätsprinzip 231
3. Überlappung der Probleme, Speicherung der optimalen
Teilproblemlösungen (Memoization) 232
4. Einführendes Beispiel – die Fibonacci-Folge 232
5. Bottom-up versus top-down 234
6. Vergleich mit anderen Verfahren 234
Aufgaben 235
Problem 1. Das Zählen der Kaninchen 236
Problem 2. Längste aufsteigende Teilfolge 240
Problem 3. Längste gemeinsame Teilfolge (LCS) 245
Problem 4. Zahlen-Dreieck 249
Problem 5. Domino 253
Problem 6. Verteilung der Geschenke 258
Problem 7. Ähnliche Summe 261
Problem 8. Schotten auf dem Oktoberfest 266
Problem 9. Springer auf dem Schachbrett 275
Problem 10. Summen von Produkten 280
Problem 11. Minimale Triangulierung eines konvexen Vielecks 286
Problem 12. Multiplikation einer Matrizenfolge 291
Problem 13. Edit-Distanz 297
Problem 14. Arbitrage 305
9 POTENZSUMMEN 311
Problembeschreibung 311
Problemanalyse. Algebraische Modellierung 311
Von der Rekursionsgleichung zum Algorithmus 313
Der Algorithmus 316
Programm 318
Aufgaben 321
STICHWORTVERZEICHNIS 327