Inhaltverzeichnis Copyright© 2006 by Doina Logofătu
GELEITWORT von Dr. Eric Müller VII
VORWORT IX
DANKSAGUNG XI
1 KOMPLEXE KODIERUNG 1
Komplexe Zahlen – kurze Einführung 1
Kodierungsproblem komplexer Zahlen 2
Problemanalyse und Entwurf der Lösung 3
Algorithmus Komplexe_Kodierung 6
Programm Komplexe_Kodierung 6
Programmanalyse 9
Aufgaben 13
Anmerkungen 14
2 VERSCHACHTELTE SCHACHTELN 15
Problembeschreibung 15
Problemanalyse und Entwurf der Lösung 16
Der Algorithmus 17
Das Programm 19
Die Programmanalyse 22
Drei kleine Programmierungstricks 23
Aufgaben, Problemstellungen 24
Anmerkungen 24
3 ZEICHENKETTEN 25
Grundlagen 25
1. Zeichen 25
2. C-Strings 26
3. C++ Strings 27
Aufgaben 32
Problem 1. Sich wiederholende Zeichenketten 33
Problem 2. Das Perlencollier 35
Problem 3. Parkinson 37
Problem 4. Rapunzel im Internet 40
Problem 5. Bridge-Blatt 44
Problem 6. Wo sind die Königinnen? 49
Problem 7. Vogelsprache 55
4 MENGEN UND RELATIONEN 59
Grundlagen 59
1. Element und Menge 59
2. Leere Menge, Teilmenge, Gleichheit 60
3. Schreibweisen 60
4. Mengenoperationen 61
5. Multimengen 63
6. Relationen 63
7. Ordnungen 64
8. Funktionen 64
Aufgaben 65
Problem 1. Cantor-Diagonalisierung 67
Problem 2. Menge und Multimenge 72
Problem 3. Relation und ihre Eigenschaften 75
5 ARITHMETIK UND ALGEBRA 81
Grundlagen 81
1. Teilbarkeit 81
2. Primzahlen 81
3. Fundamentalsatz der Arithmetik 82
4. Division mit Rest, ggT und kgV 83
5. Kongruenzen. Elementare Eigenschaften 84
6. Chinesischer Restsatz 85
7. Fermatsche Sätze 86
8. Die Pell’sche Gleichung 88
9. Satz von Vieta 89
Aufgaben 91
Problem 1. Primzahltest 93
Problem 2. Sieb des Eratosthenes 95
Problem 3. Druck einer Broschüre 99
Problem 4. Primzahlen und Teiler 101
Problem 5. Der alte Gärtner 104
Problem 6. Kätzchen in Hüten 108
Problem 7. Hausnummer 113
Problem 8. Korrekte Nachrichten 115
Problem 9. Anzahl der Teiler 118
Problem 10. Datumsverpackung 121
Problem 11. Die schöne Marie und der schöne Hans 122
Problem 12. Kubische Gleichung 125
Problem 13. Quadrat einer speziellen Zahl 126
Problem 14. Umwandlung einer römischen Zahl in eine Dezimalzahl 128
Problem 15. Umwandlung einer Dezimalzahl in eine römische Zahl 130
Problem 16. Hässliche Zahlen 132
Problem 17. Vögel auf den Bäumen 134
Problem 18. Wieviele sind es mindestens? (chinesischer Restsatz) 136
6 EBENE GEOMETRIE, TRIGONOMETRIE 139
Grundlagen 139
1. Dreiecksgeometrie. 139
2. Berechnung eines beliebigen Dreiecks 140
3. Wichtige trigonometrische Formeln 141
Aufgaben 142
Problem 1. Berechnung des Dreiecks (SSW) 142
Problem 2. Der Kreisumfang 146
Problem 3. Kreise im gleichschenkligen Dreieck 150
7 KOMBINATORIK 153
Grundlagen 153
1. Prinzip von Inklusion und Exklusion 153
2. Das Schubfachprinzip 155
3. Permutationen
(Anordnungen mit Berücksichtigung der Reihenfolge) 158
4. Variationen (Auswahlen mit Beachtung der Reihenfolge) 160
5. Kombinationen (Auswahlen ohne Beachtung der Reihenfolge) 161
6. Binomialkoeffizienten und ihre Anwendungen 162
Aufgaben 164
Problem 1. Alle Teilmengen einer Menge
in lexikographischer Reihenfolge 166
Problem 2. Der Gray-Code (minimale Änderungsreihenfolge) 170
Problem 3. Permutationen in lexikographischer Reihenfolge 173
Problem 4. Ranking einer Permutation in lexikographischer Reihenfolge 175
Problem 5. Unranking einer Permutation in lexikographischer Reihenfolge178
Problem 6. Binomialkoeffizienten 180
Problem 7. Das kleinste Vielfache 186
8 CATALAN-ZAHLEN 189
Einführung 189
Sechs Probleme aus der Catalan-Familie 190
Theorem. P1-P6 und die Catalan-Zahlen 193
Die rekursive Formel 196
Die erzeugende Funktion 197
Noch 4 äquivalente Probleme 199
Algorithmen zur Berechnung der Catalan-Zahlen 200
Zweiter Algorithmus, eine weitere Rekursion 201
Dritter Algorithmus, der ohne Rekursion auskommt 202
Aufgaben 205
9 POTENZSUMMEN 207
Problembeschreibung 207
Problemanalyse. Algebraische Modellierung 207
Von der Rekursionsgleichung zum Algorithmus 209
Der Algorithmus 212
Programm 214
10 ALGORITHMISCHE GEOMETRIE 219
Grundlagen 219
1. Darstellung der Punkte, Quadranten 219
2. Abstand zwischen zwei Punkten 220
3. Gerade in der Ebene 221
4. Abstand eines Punktes zu einer Geraden,
Fläche eines Dreiecks 223
5. Die Ellipse 224
6. Das Außenprodukt 225
7. Die Fläche eines Polygons, Punkt im Inneren eines Polygons 225
8. Nächstes Paar 228
9. Die konvexe Hülle 230
Aufgaben 233
Problem 1. Nächstes Paar 234
Problem 2. Quadrätchen im Kreis 236
Problem 3. Wie sicher sind die Bürger? 241
11 GRAPHEN 251
Grundlagen 251
1. Einführende Begriffe 251
2. Weg, Pfad, Zyklus und Kreis 252
3. Vollständige und bipartite Graphen 253
4. Darstellung der Graphen 254
5. Traversieren von Graphen (BFS und DFS) 256
6. Zusammenhang 258
7. Hamiltonsche und eulersche Graphen 259
8. Bäume und Wälder 260
9. Minimaler Spannbaum 261
Aufgaben 263
Problem 1. Breiten- und Tiefensuche (BFS und DFS) 264
Problem 2. Die kürzesten Pfade 267
Problem 3. Das Alphabet der fremden Sprache 269
Problem 4. Markus besucht seine Freunde 275
Problem 5. Das Haus des Nikolaus 280
12 GREEDY 283
Grundlagen 283
Problem 1. Rucksackproblem 284
Problem 2. Kartenfärbung 286
Problem 3. Springer auf dem Schachbrett 287
13 REKURSION 291
Vollständige Induktion 291
Rekursion: Grundlagen 297
Problem 1. Quersumme und Spiegelung einer natürlichen Zahl 298
Problem 2. Die Zahl 4 300
Problem 3. Rest großer Potenzen 302
Problem 4. Die Torte (lineare Rekursion) 304
Problem 5. Die Ackermannfunktion
(verschachtelte Rekursion, "compound recursion") 306
Problem 6. Rekursive Zahlenumwandlung
(Dezimalsystem in System mit Basis P) 308
Problem 7. Summe zweier Wurzeln (verzweigte Rekursion) 310
Problem 8. Collatz-Funktion (nicht-monotone Rekursion) 311
Problem 9. Quadrate und Quadrätchen 313
Problem 10. Quadrate (direkte Rekursion) 316
Problem 11. Quadrate und Kreise (indirekte Rekursion) 325
Problem 12. Die Koch’sche Schneeflockenkurve 329
14 TEILE UND HERRSCHE 337
Grundlagen 337
Problem 1. Größter gemeinsamer Teiler mehrerer Zahlen 338
Problem 2. Die Türme von Hanoi 340
Problem 3. Integral mit Trapezregel 342
Problem 4. Quicksort 344
Problem 5. Mergesort (Sortieren durch Verschmelzen) 346
Problem 6. Quad-Bäume 348
Problem 7. Diskrete Fourier-Transformation (DFT) 352
15 BACKTRACKING 357
Problem 1. Das Problem der n Damen 357
Allgemeine Bemerkungen zum Backtracking-Verfahren 363
Problem 2. Das Problem der n Türme 365
Problem 3. Das Problem der Türme auf den ersten m Reihen 367
Problem 4. Das Problem der aufsteigenden Türme
auf den ersten m Reihen 368
Problem 5. Die Freundschafts-Jugendherberge 369
Problem 6. Partitionen einer natürlichen Zahl 370
Problem 7. Erdkunde-Referate 373
Problem 8. Alle Wege des Springers 375
Problem 9. Das Fotoproblem 378
Problem 10. Der ausbrechende Ball 379
Problem 11. Olivensport 382
Problem 12. Testmusterkompaktierung 388
Noch 10 Probleme 397
16 DYNAMISCHE PROGRAMIERUNG 403
Grundlagen, Eigenschaften des Verfahrens 403
1. Ursprung des Konzeptes 403
2. Optimalitätsprinzip 403
3. Überlappung des Problems, Speicherung der optimalen
Teilproblemlösungen (Memoization) 404
4. Einführendes Beispiel – die Fibonacci-Folge 404
5. Bottom-up versus top-down 406
6. Vergleich mit anderen Verfahren 407
Aufgaben 407
Problem 1. Das Zählen der Kaninchen 408
Problem 2. Längste aufsteigende Teilfolge 411
Problem 3. Zahlen-Dreieck 415
Problem 4. Domino 418
Problem 5. Verteilung der Geschenke 422
Problem 6. Ähnliche Summe 425
Problem 7. Schotten auf dem Oktoberfest 430
Problem 8. Springer auf dem Schachbrett 437
Problem 9. Summen von Produkten 442
Problem 10. Minimale Triangulierung eines konvexen Vielecks 445
Problem 11. Multiplikation einer Matrizenfolge 451
Problem 12. Edit-Distanz 456
LITERATURVERZEICHNIS 463
STICHWORTVERZEICHNIS 467