Algorithmen in Python

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