Programmieren trainieren mit Python-AlgorithmenDas Programmiertraining für alle, die ihre ersten Schritte in der Programmierung gemacht haben und jetzt richtig durchstarten wollen! David Kopec stellt Ihnen in diesem Buch eine umfassende, zeitgemäße Auswahl an Algorithmen vor. Beginnen Sie mit einfachen Algorithmen zur Verschlüsselung und für die Suche und vertiefen Sie Ihr Wissen bei genetischen Algorithmen und Neuronalen Netzen. Jede problemlösende Technik wird an einem konkreten Beispiel anschaulich vorgeführt. Darunter sind viele bekannte Klassiker der Informatik, aber auch neue Aufgaben. An zahlreichen Code-Beispielen in Python lernen Sie, wie Sie die Algorithmen implementieren und selbst in Algorithmen denken. So ist das Buch eine wertvolle Hilfe für jeden, der professionell programmieren möchte. Jetzt geht s los: Lösen Sie das Damenproblem, helfen Sie den Missionaren über den Fluss, ohne von Kannibalen zu gefressen werden, und geben Sie dem Dieb Tipps, welche Stücke er in seinen Rucksack packen soll. Programmieren trainieren mit bekannten und modernen Klassikern! Von der Suche bis zu k-Means, vom Dreizeiler bis zur dynamischen Programmierung und KIFür Studium, Coding-Katas, Workouts oder in Eigeninitiative für jeden ist etwas dabeiTitel der Originalausgabe: "Classic Computer Science Problems in Python". Übersetzt aus dem Amerikanischen von Sascha Kersken. Aus dem Inhalt:Die Fibonacci-Folge, einfache Komprimierung, unknackbare Verschlüsselung, Pi berechnenDNS durchsuchen, Wege durchs Labyrinth, FlussüberquerungsrätselDamenproblem, Vier-Farben-Satz, Wortsuchrätselgrafische Algorithmengenetische Algorithmenk-Means-Algorithmen einfache neuronale NetzeTic-tac-toe, Vier gewinntDas Rucksackproblem, Das Problem des Handlungsreisendenund außerdem: zahlreiche Code-Beispiele in Python, Hinweise zum Einsatz der Algorithmen, Übungen und Tipps für die Programmier-Praxis
Inhaltsverzeichnis
Vorwort . . . 13
Einleitung . . . 17
1. Kleine Aufgaben . . . 25
1. 1 . . . Die Fibonacci-Folge . . . 25
1. 2 . . . Triviale Komprimierung . . . 32
1. 3 . . . Unknackbare Verschlüsselung . . . 38
1. 4 . . . Pi berechnen . . . 41
1. 5 . . . Die Türme von Hanoi . . . 43
1. 6 . . . Anwendungen im Alltag . . . 47
1. 7 . . . Übungsaufgaben . . . 48
2. Suchaufgaben . . . 49
2. 1 . . . DNA-Suche . . . 49
2. 2 . . . Labyrinthe lösen . . . 57
2. 3 . . . Missionare und Kannibalen . . . 77
2. 4 . . . Anwendungen im Alltag . . . 82
2. 5 . . . Übungsaufgaben . . . 83
3. Bedingungserfüllungsprobleme . . . 85
3. 1 . . . Ein Framework für Bedingungserfüllungsprobleme schreiben . . . 86
3. 2 . . . Die Landkarte Australiens einfärben . . . 91
3. 3 . . . Das Acht-Damen-Problem . . . 94
3. 4 . . . Wortsuche . . . 97
3. 5 . . . SEND+MORE=MONEY . . . 101
3. 6 . . . Leiterplatten-Layout . . . 103
3. 7 . . . Anwendungen im Alltag . . . 104
3. 8 . . . Übungsaufgaben . . . 105
4. Graphenprobleme . . . 107
4. 1 . . . Eine Landkarte als Graph . . . 107
4. 2 . . . Ein Framework für Graphen schreiben . . . 110
4. 3 . . . Den kürzesten Pfad finden . . . 116
4. 4 . . . Die Kosten für den Aufbau des Netzwerks minimieren . . . 119
4. 5 . . . Den kürzesten Pfad in einem gewichteten Graphen finden . . . 132
4. 6 . . . Anwendungen im Alltag . . . 138
4. 7 . . . Übungsaufgaben . . . 139
5. Genetische Algorithmen . . . 141
5. 1 . . . Biologischer Hintergrund . . . 141
5. 2 . . . Ein generischer genetischer Algorithmus . . . 143
5. 3 . . . Ein naiver Test . . . 151
5. 4 . . . Wiedersehen mit SEND+MORE=MONEY . . . 154
5. 5 . . . Listenkomprimierung optimieren . . . 158
5. 6 . . . Kritik an genetischen Algorithmen . . . 160
5. 7 . . . Anwendungen im Alltag . . . 162
5. 8 . . . Übungsaufgaben . . . 163
6. k-Means-Clustering . . . 165
6. 1 . . . Vorbereitungen . . . 165
6. 2 . . . Der k-Means-Clustering-Algorithmus . . . 168
6. 3 . . . Gouverneure nach Alter und Längengrad clustern . . . 174
6. 4 . . . Michael-Jackson-Alben nach Länge clustern . . . 179
6. 5 . . . K-Means-Clustering-Probleme und -Erweiterungen . . . 181
6. 6 . . . Anwendungen im Alltag . . . 182
6. 7 . . . Übungsaufgaben . . . 183
7. Einfache neuronale Netzwerke . . . 185
7. 1 . . . Biologische Grundlagen? . . . 186
7. 2 . . . Künstliche neuronale Netzwerke . . . 187
7. 3 . . . Vorbereitungen . . . 195
7. 4 . . . Das Netzwerk aufbauen . . . 197
7. 5 . . . Klassifikationsprobleme . . . 204
7. 6 . . . Neuronale Netzwerke beschleunigen . . . 213
7. 7 . . . Probleme und Erweiterungen neuronaler Netzwerke . . . 214
7. 8 . . . Anwendungen im Alltag . . . 215
7. 9 . . . Übungsaufgaben . . . 217
8. Adversarial Search . . . 219
8. 1 . . . Grundkomponenten von Brettspielen . . . 219
8. 2 . . . Tic Tac Toe . . . 221
8. 3 . . . Vier gewinnt . . . 231
8. 4 . . . Minimax-Verbesserungen über die Alpha-Beta-Suche hinaus . . . 240
8. 5 . . . Anwendungen im Alltag . . . 242
8. 6 . . . Übungsaufgaben . . . 243
9. Sonstige Aufgaben . . . 245
9. 1 . . . Das Rucksackproblem . . . 245
9. 2 . . . Das Problem des Handlungsreisenden . . . 251
9. 3 . . . Merkhilfen für Telefonnummern . . . 257
9. 4 . . . Anwendungen im Alltag . . . 260
9. 5 . . . Übungsaufgaben . . . 261
Anhang . . . 263
A . . . Glossar . . . 265
B . . . Weitere Ressourcen . . . 271
C . . . Eine kurze Einführung in Type-Hints . . . 277
Index . . . 285
