1 Kleine Aufgaben

25

1.1 Die Fibonacci-Folge

25

1.1.1 Ein erster rekursiver Ansatz

25

1.1.2 Abbruchbedingungen verwenden

27

1.1.3 Memoisation eilt zu Hilfe

28

1.1.4 Automatische Memoisation

30

1.1.5 Fibonacci leicht gemacht

30

1.1.6 Fibonacci-Zahlen mit einem Generator erzeugen

31

1.2 Triviale Komprimierung

32

1.3 Unknackbare Verschlüsselung

38

1.3.1 Die Daten bereitstellen

38

1.3.2 Entschlüsseln und verschlüsseln

39

1.4 Pi berechnen

41

1.5 Die Türme von Hanoi

43

1.5.1 Die Türme modellieren

44

1.5.2 Türme von Hanoi lösen

45

1.6 Anwendungen im Alltag

47

1.7 Übungsaufgaben

48

2 Suchaufgaben

49

2.1 DNA-Suche

49

2.1.1 DNA speichern

50

2.1.2 Lineare Suche

51

2.1.3 Binärsuche

52

2.1.4 Ein generisches Beispiel

55

2.2 Labyrinthe lösen

57

2.2.1 Ein Zufallslabyrinth erzeugen

58

2.2.2 Weitere Labyrinth-Hilfsfunktionen

60

2.2.3 Tiefensuche

61

2.2.4 Breitensuche

66

2.2.5 A*-Suche

70

2.3 Missionare und Kannibalen

77

2.3.1 Die Aufgabe darstellen

78

2.3.2 Lösung

80

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.2.1 Mit Edge und Graph arbeiten

115

4.3 Den kürzesten Pfad finden

116

4.3.1 Wiedersehen mit der Breitensuche

117

4.4 Die Kosten für den Aufbau des Netzwerks minimieren

119

4.4.1 Mit Gewichten arbeiten

120

4.4.2 Den minimalen Spannbaum finden

124

4.5 Den kürzesten Pfad in einem gewichteten Graphen finden

132

4.5.1 Der Dijkstra-Algorithmus

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.2.1 Neuronen

188

7.2.2 Schichten

189

7.2.3 Backpropagation

190

7.2.4 Das große Ganze

194

7.3 Vorbereitungen

195

7.3.1 Skalarprodukt

195

7.3.2 Die Aktivierungsfunktion

196

7.4 Das Netzwerk aufbauen

197

7.4.1 Neuronen implementieren

197

7.4.2 Schichten implementieren

199

7.4.3 Das Netzwerk implementieren

201

7.5 Klassifikationsprobleme

204

7.5.1 Daten normalisieren

205

7.5.2 Die klassische Iris-Datenmenge

206

7.5.3 Wein klassifizieren

210

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.2.1 Den Zustand von Tic Tac Toe verwalten

221

8.2.2 Minimax

225

8.2.3 Minimax mit Tic Tac Toe testen

228

8.2.4 Eine Tic-Tac-Toe-KI entwickeln

230

8.3 Vier gewinnt

231

8.3.1 Der Vier-gewinnt-Spielmechanismus

232

8.3.2 Eine Vier-gewinnt-KI

238

8.3.3 Minimax mit Alpha-Beta-Suche verbessern

239

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.2.1 Der naive Ansatz

252

9.2.2 Die nächste Stufe erklimmen

257

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