Grundlegende Algorithmen mit Java

Cover......Page 1
Grundlegende
Algorithmen mit Java......Page 4
Geleitwort......Page 7
Vorwort......Page 8
Danksagung......Page 10
Inhaltsverzeichnis......Page 12
Alternative Definitionen......Page 16
Beispiele für Algorithmen......Page 17
Vom Problem zur Lösung......Page 22
Algorithmik......Page 25
Das RAM-Rechnermodell......Page 26
Die Komplexität von Algorithmen......Page 27
Optimalität, Reduktion, Beispiele......Page 29
Die reelle Zeit eines Algorithmus (polynomial vs. exponentiell)......Page 32
Klassifizierung der Probleme (P, NP, NP-vollständig, NP-hart)......Page 33
Probleme NP-vollständig (NP-complete)......Page 34
Das Erfüllbarkeitsproblem (SAT)......Page 35
Die Klasse der NP-harten Probleme......Page 36
Aufgaben......Page 37
Problembeschreibung......Page 40
Problemanalyse und Entwurf der Lösung......Page 41
Der Algorithmus......Page 42
Das Programm......Page 44
Die Programmanalyse......Page 47
Aufgaben......Page 52
Anmerkungen......Page 53
Grundlagen......Page 54
Problem 1. Rucksackproblem......Page 55
Problem 2. Kartenfärbung......Page 58
Problem 3. Springer auf dem Schachbrett......Page 60
Problem 4. Minimaler Spannbaum (Kruskal-Algorithmus)......Page 63
Problem 5. Huffman-Kodierung......Page 71
Problembeschreibung......Page 80
Problemdomäne, Definitionen......Page 81
und DOPI sind NP-vollständig......Page 86
Algorithmen für DOP und DOPI......Page 87
Zufällige-Lösung-Algorithmen (RAN)......Page 88
Exakt-Algorithmen (EX)......Page 89
Algorithmen mit unterer Schranke (LB)......Page 90
Implementierungsdetails......Page 92
Programm......Page 99
Auswertung der Ergebnisse......Page 109
Aufgaben......Page 111
Vollständige Induktion......Page 114
Rekursion: Grundlagen......Page 120
Problem 1. Quersumme und Spiegelung einer natürlichen Zahl......Page 121
Problem 2. Die Zahl 4......Page 123
Problem 3. Rest großer Potenzen......Page 126
Problem 4. Die Torte (lineare Rekursion)......Page 130
Problem 5. Die Ackermannfunktion (Verschachtelte Rekursion, "compound recursion")......Page 133
Problem 6. Rekursive Zahlenumwandlung (Dezimalsystem in System mit Basis p)......Page 135
Problem 7. Summe zweier Wurzeln (verzweigte Rekursion)......Page 138
Problem 8. Collatz-Funktion (nicht-monotone Rekursion)......Page 140
Problem 9. Quadrate und Quadrätchen......Page 142
Problem 10. Quadrate (direkte Rekursion)......Page 145
Problem 11. Quadrate und Kreise (indirekte Rekursion)......Page 148
Problem 12. Die Koch’sche Schneeflockenkurve......Page 150
Grundlagen......Page 160
Problem 1. Größter gemeinsamer Teiler mehrerer Zahlen......Page 161
Problem 2. Die Türme von Hanoi......Page 163
Problem 3. Integral mit Trapezregel......Page 165
Problem 4. QuickSort......Page 167
Problem 5. MergeSort (Sortieren durch Verschmelzen)......Page 170
Problem 6. Quad-Bäume......Page 172
Problem 7. Diskrete Fourier-Transformation (DFT)......Page 177
Problem 1. Das Problem der n Damen......Page 184
Allgemeine Bemerkungen zum Backtracking-Verfahren......Page 190
Problem 2. Das Problem der n Türme......Page 193
Problem 3. Das Problem der Türme auf den ersten m Reihen......Page 194
Reihen......Page 195
Problem 5. Die Freundschafts-Jugendherberge......Page 196
Problem 6. Partitionen einer natürlichen Zahl......Page 197
Problem 7. Erdkunde-Referate......Page 200
Problem 8. Alle Wege des Springers......Page 203
Problem 9. Das Fotoproblem......Page 206
Problem 10. Der ausbrechende Ball......Page 208
Problem 11. Orangensport......Page 211
Problem 12. Testmusterkompaktierung......Page 221
Problem 13. Sudoku......Page 229
Problem 14. Das Haus des Nikolaus......Page 236
Noch 10 Probleme......Page 239
Grundlagen, Eigenschaften des Verfahrens......Page 246
Problem 1. Das Zählen der Kaninchen......Page 251
Problem 2. Längste aufsteigende Teilfolge......Page 255
Problem 3. Längste gemeinsame Teilfolge (LCS)......Page 260
Problem 4. Zahlen-Dreieck......Page 264
Problem 5. Domino......Page 268
Problem 6. Verteilung der Geschenke......Page 273
Problem 7. Ähnliche Summe......Page 276
Problem 8. Schotten auf dem Oktoberfest......Page 281
Problem 9. Springer auf dem Schachbrett......Page 290
Problem 10. Summen von Produkten......Page 295
Problem 11. Minimale Triangulierung eines konvexen Vielecks......Page 301
Problem 12. Multiplikation einer Matrizenfolge......Page 306
Problem 13. Edit-Distanz......Page 312
Problem 14. Arbitrage......Page 320
Problemanalyse. Algebraische Modellierung.......Page 326
Von der Rekursionsgleichung zum Algorithmus......Page 328
Der Algorithmus......Page 331
Programm......Page 333
Aufgaben......Page 336
Literaturverzeichnis......Page 338
Stichwortverzeichnis......Page 342