1 Kleine Aufgaben

23

1.1 Die Fibonacci-Folge

23

1.1.1 Ein erster rekursiver Ansatz

23

1.1.2 Abbruchbedingungen verwenden

25

1.1.3 Memoisation eilt zu Hilfe

27

1.1.4 Fibonacci leicht gemacht

29

1.1.5 Fibonacci-Zahlen mit einem Stream erzeugen

30

1.2 Triviale Komprimierung

31

1.3 Unknackbare Verschlüsselung

36

1.3.1 Die Daten bereitstellen

37

1.3.2 Entschlüsseln und verschlüsseln

38

1.4 Pi berechnen

40

1.5 Die Türme von Hanoi

42

1.5.1 Die Türme modellieren

43

1.5.2 Türme von Hanoi lösen

43

1.6 Anwendungen im Alltag

46

1.7 Übungsaufgaben

47

2 Suchaufgaben

49

2.1 DNA-Suche

49

2.1.1 DNA speichern

50

2.1.2 Lineare Suche

52

2.1.3 Binärsuche

53

2.1.4 Ein generisches Beispiel

57

2.2 Labyrinthe lösen

59

2.2.1 Ein Zufallslabyrinth erzeugen

62

2.2.2 Weitere Labyrinth-Hilfsfunktionen

64

2.2.3 Tiefensuche

65

2.2.4 Breitensuche

70

2.2.5 A*-Suche

75

2.3 Missionare und Kannibalen

82

2.3.1 Darstellung der Aufgabe

82

2.3.2 Lösung

85

2.4 Anwendungen im Alltag

89

2.5 Übungsaufgaben

89

3 Bedingungserfüllungsprobleme

91

3.1 Ein Framework für Bedingungserfüllungsprobleme schreiben

92

3.2 Die Landkarte Australiens einfärben

98

3.3 Das Acht-Damen-Problem

101

3.4 Wortsuche

104

3.5 SEND+MORE=MONEY

112

3.6 Leiterplatten-Layout

115

3.7 Bedingungserfüllungsproblem im Alltag

115

3.8 Übungsaufgaben

116

4 Graphenprobleme

117

4.1 Eine Landkarte als Graph

117

4.2 Ein Framework für Graphen schreiben

120

4.2.1 Mit Edge und UnweightedGraph arbeiten

126

4.3 Den kürzesten Pfad finden

128

4.3.1 Wiedersehen mit der Breitensuche

129

4.4 Die Kosten für den Aufbau des Netzwerks minimieren

131

4.4.1 Mit Gewichten arbeiten

131

4.4.2 Den minimalen Spannbaum finden

136

4.5 Den kürzesten Pfad in einem gewichteten Graphen finden

143

4.5.1 Der Dijkstra-Algorithmus

143

4.6 Graphenprobleme im Alltag

150

4.7 Übungsaufgaben

151

5 Genetische Algorithmen

153

5.1 Biologischer Hintergrund

153

5.2 Ein generischer genetischer Algorithmus

155

5.3 Ein naiver Test

164

5.4 Wiedersehen mit SEND+MORE=MONEY

167

5.5 Listenkomprimierung optimieren

172

5.6 Kritik an genetischen Algorithmen

176

5.7 Genetische Algorithmen im Alltag

178

5.8 Übungsaufgaben

179

6 k-Means-Clustering

181

6.1 Vorbereitungen

182

6.2 Der k-Means-Clustering-Algorithmus

185

6.3 Gouverneure nach Alter und Längengrad clustern

193

6.4 Michael-Jackson-Alben nach Länge clustern

199

6.5 k-Means-Clustering-Probleme und -Erweiterungen

201

6.6 k-Means-Clustering im Alltag

202

6.7 Übungsaufgaben

203

7 Einfache neuronale Netzwerke

205

7.1 Biologische Grundlagen?

206

7.2 Künstliche neuronale Netzwerke

207

7.2.1 Neuronen

208

7.2.2 Schichten

209

7.2.3 Backpropagation

210

7.2.4 Das große Ganze

214

7.3 Vorbereitungen

215

7.3.1 Skalarprodukt

215

7.3.2 Die Aktivierungsfunktion

216

7.4 Das Netzwerk aufbauen

218

7.4.1 Neuronen implementieren

218

7.4.2 Schichten implementieren

220

7.4.3 Das Netzwerk implementieren

222

7.5 Klassifikationsprobleme

227

7.5.1 Daten normalisieren

227

7.5.2 Die klassische Iris-Datenmenge

229

7.5.3 Wein klassifizieren

234

7.6 Neuronale Netzwerke beschleunigen

238

7.7 Probleme und Erweiterungen neuronaler Netzwerke

239

7.8 Neuronale Netzwerke im Alltag

241

7.9 Übungsaufgaben

242

8 Adversarial Search

243

8.1 Grundkomponenten von Brettspielen

243

8.2 Tic Tac Toe

245

8.2.1 Den Zustand von Tic Tac Toe verwalten

246

8.2.2 Minimax

251

8.2.3 Minimax mit Tic Tac Toe testen

254

8.2.4 Eine Tic-Tac-Toe-KI entwickeln

257

8.3 Vier gewinnt

260

8.3.1 Der Vier-gewinnt-Spielmechanismus

260

8.3.2 Eine Vier-gewinnt-KI

268

8.3.3 Minimax mit Alpha-Beta-Suche verbessern

270

8.4 Minimax-Verbesserungen über die Alpha-Beta-Suche hinaus

272

8.5 Adversarial Search im Alltag

273

8.6 Übungsaufgaben

274

9 Weitere Aufgaben

277

9.1 Das Rucksackproblem

277

9.2 Das Problem des Handlungsreisenden

284

9.2.1 Der naive Ansatz

285

9.2.2 Die nächste Stufe erklimmen

292

9.3 Merkhilfen für Telefonnummern

292

9.4 Anwendungen im Alltag

296

9.5 Übungsaufgaben

297

Anhang

299

A Interview mit Brian Goetz 301

299

B Glossar 317

299

C Weiterführende Ressourcen 323

299