Die Autorin vermittelt ein solides Verständnis der wichtigen Programmiermethoden, algorithmischer/mathematischer Basiskonzepte (z. B. Kombinatorik, Backtracking, Dynamische Programmierung) und der Java-spezifischen Elemente. Die sorgfältig ausgewählten Problemstellungen erleichtern den Lesern die Verknüpfung von Praxisbeispiel und allgemeiner Theorie. Den Schwerpunkt bilden Anwendungsbeispiele, die vollständig behandelt werden: von der Problem-Analyse bis zum Java-Programm. Mit komplettem Listing des Java-Programms zu jedem gelösten Problem. Quelle: Verlagstext
/ AUS DEM INHALT: / / /
Inhaltsverzeichnis:
1 Algorithmen - grundlegende Konzepte 1
Abstammung des Wortes Algorithmus 1
Alternative Definitionen 1
Beispiele für Algorithmen 2
Vom Problem zur Lösung 7
Eigenschaften eines Algorithmus 10
Algorithmik 10
Das RAM-Rechnermodell 11
Die Komplexität der Algorithmen 12
Optimalität, Reduktion, Beispiele 14
Wachstum von 0(g(n)) - vergleichendes Beispiel 17
Die reelle Zeit eines Algorithmus (polynomial vsexponentiell) 17
Klassifizierung der Probleme (P, NP, NP-vollständig, NP-hard) 18
Probleme NP-vollständig (NP-complete) 19
Das Erfüllbarkeitsproblem (SAT) 20
Die Klasse der NP-hard Probleme 21
Aufgaben 21
2 Verschachtelte Schachteln 25
Problembeschreibung 25
Problemanalyse und Entwurf der Lösung 26
Der Algorithmus 27
Das Programm 29
Die Programmanalyse 31
Aufgaben, Problemstellungen 36
Anmerkungen 37
3 Greedy 39
Grundlagen 39
Greedy-Algorithmen 39
Problem 1Rucksackproblem 40
Problem 2Kartenfärbung 43
Problem 3Springer auf dem Schachbrett 45
Problem 4Minimaler Spannbaum (Kruskal-Algorithmus) 48
Ein Wald mit drei Bäumen 49
Minimaler Spannbaum 49
Problem 5Huffman-Kodierung 55
4 Data Ordering Problem 63
Problembeschreibung 63
Problemdomäne, Definitionen 64
XIV Grundlegende Algorithmen mit Java
DOP und DOPI sind NP-vollständig 69
Algorithmen für DOP und DOPI 70
Zufällige-Lösung-Algorithmen (RAN) 71
Exakt-Algorithmen (EX) 72
Greedy_Min-Algorithmen (GM) 72
Greedy_Min Simplified-Algorithmen (GMS) 73
Algorithmen mit unterer Schranke (LB) 73
Implementierungsdetails 75
Programm 82
Auswertung der Ergebnisse 92
Aufgaben 94
5 Rekursion 97
Vollständige Induktion 97
Rekursion: Grundlagen 103
Problem 1Quersumme und Spiegelung einer natürlichen Zahl 104
Problem 2Die Zahl 4 106
Problem 3Rest großer Potenzen 108
Problem 4Die Torte (lineare Rekursion) 113
Problem 5Die Ackermannfunktion 115
Problem 6Rekursive Zahlenumwandlung (Dezimalsystem in System mit Basis p) 117
Problem 7Summe zweier Wurzeln (verzweigte Rekursion) 120
Problem 8Collatz-Funktion (nicht-monotone Rekursion) 122
Problem 9Quadrate und Quadrätchen 124
Problem 10Quadrate (direkte Rekursion) 127
Problem 11Quadrate und Kreise (indirekte Rekursion) 130
Problem 12Die Koch'sche Schneeflockenkurve 131
6 Teile und Herrsche 141
Grundlagen 141
Problem 1Größter gemeinsamer Teiler mehrerer Zahlen 142
Problem 2Die Türme von Hanoi 144
Problem 3Integral mit Trapezregel 146
Problem 4QuickSort 148
Problem 5MergeSort (Sortieren durch Verschmelzen) 151
Problem 6Quad-Bäume 153
Problem 7Diskrete Fourier-Transformation (DFT) 157
7 Backtracking 165
Problem 1Das Problem der n Damen 165
Allgemeine Bemerkungen zum Backtracking-Verfahren 171
Problem 2Das Problem der n Türme 173
Problem 3Das Problem der Türme auf den ersten m Reihen 174
Problem 4Das Problem der aufsteigenden Türme auf den ersten m Reihen 175
Problem 5Die Freundschafts-Jugendherberge 176
Inhaltsverzeichnis XV
Problem 6Partitionen einer natürlichen Zahl 177
Problem 7Erdkunde-Referate 180
Problem 8Alle Wege des Springers 183
Problem 9Das Fotoproblem 186
Problem 10Der ausbrechende Ball 188
Problem 11Orangensport 191
Problem 12Testmusterkompaktierung 200
Problem 13Sudoku 209
Problem 14Das Haus des Nikolaus 216
Noch 10 Probleme 218
8 Dynamische Programmierung 225
Grundlagen, Eigenschaften des Verfahrens 225
Problem 1Das Zählen der Kaninchen 230
Problem 2Längste aufsteigende Teilfolge 234
Problem 3Längste gemeinsame Teilfolge (LCS) 238
Problem 4Zahlen-Dreieck 243
Problem 5Domino 246
Problem 6Verteilung der Geschenke 251
Problem 7Ähnliche Summe 254
Problem 8Schotten auf dem Oktoberfest 259
Problem 9Springer auf dem Schachbrett 268
Problem 10Summen von Produkten 273
Problem 11Minimale Triangulierung eines konvexen Vielecks 278
Problem 12Multiplikation einer Matrizenfolge 284
Problem 13Edit-Distanz 289
Problem 14Arbitrage 297
9 Potenzsummen 301
Problembeschreibung 301
ProblemanalyseAlgebraische Modellierung 301
Von der Rekursionsgleichung zum Algorithmus 303
Der Algorithmus 306
Programm 308
Aufgaben 311
Literaturverzeichnis 313
Stichwortverzeichnis 317