Algorithmen kapieren (eBook)

Aditya Bhargava ist Softwareentwickler, der sich nicht nur mit Informatik, sondern auch mit bildender Kunst befasst. Er bloggt über Programmierung unter adit.io.

Cover 1
Titel 4
Impressum 5
Inhaltsverzeichnis 6
Vorwort 12
Einleitung 14
Überblick 15
Verwendung dieses Buchs 16
Wer sollte dieses Buch lesen? 16
Konventionen und Downloads 17
Über den Autor 17
Danksagungen 18
Kapitel 1: Einführung in Algorithmen 20
1.1 Einführung 20
1.1.1 Performance 21
1.1.2 Problemlösungen 21
1.2 Binäre Suche 22
1.2.1 Eine bessere Suchmethode 24
Übungen 28
1.2.2 Laufzeit 29
1.3 Landau-Notation 30
1.3.1 Die Laufzeiten von Algorithmen nehmen unterschiedlich schnell zu 30
1.3.2 Visualisierung verschiedener Laufzeiten 33
1.3.3 Die Landau-Notation beschreibt die Laufzeit im Worst Case 34
1.3.4 Typische Laufzeiten gebräuchlicher Algorithmen 35
Übungen 36
1.3.5 Das Problem des Handlungsreisenden 37
1.4 Zusammenfassung 39
Kapitel 2: Selectionsort 40
2.1 Die Funktionsweise des Arbeitsspeichers 41
2.2 Arrays und verkettete Listen 43
2.2.1 Verkettete Listen 44
2.2.2 Arrays 45
2.2.3 Terminologie 46
Übung 47
2.2.4 Einfügen in der Mitte einer Liste 48
2.2.5 Löschen 49
Übungen 50
2.3 Selectionsort 52
Beispielcode 56
2.4 Zusammenfassung 57
Kapitel 3: Rekursion 58
3.1 Rekursion 59
3.2 Basisfall und Rekursionsfall 62
3.3 Der Stack 63
3.3.1 Der Aufruf-Stack 64
Übung 67
3.3.2 Der Aufruf-Stack mit Rekursion 67
Übung 71
3.4 Zusammenfassung 71
Kapitel 4: Quicksort 72
4.1 Teile und herrsche 73
Übungen 80
4.2 Quicksort 81
4.3 Landau-Notation im Detail 86
4.3.1 Mergesort und Quicksort im Vergleich 87
4.3.2 Average Case und Worst Case im Vergleich 89
Übungen 93
4.4 Zusammenfassung 93
Kapitel 5: Hashtabellen 94
5.1 Hashfunktionen 97
Übungen 100
5.2 Anwendungsfälle 101
5.2.1 Hashtabellen zum Nachschlagen verwenden 101
5.2.2 Doppelte Einträge verhindern 103
5.2.3 Hashtabellen als Cache verwenden 105
5.2.4 Zusammenfassung 108
5.2.5 Kollisionen 108
5.3 Performance 111
5.3.1 Der Auslastungsfaktor 113
5.3.2 Eine gute Hashfunktion 115
Übungen 115
5.4 Zusammenfassung 116
Kapitel 6: Breitensuche 118
6.1 Einführung in Graphen 119
6.2 Was ist ein Graph? 121
6.3 Breitensuche 122
6.3.1 Den kürzesten Pfad finden 125
6.3.2 Warteschlangen 127
Übungen 128
6.4 Implementierung des Graphen 128
6.5 Implementierung des Algorithmus 131
6.5.1 Laufzeit 136
Übung 136
6.6 Zusammenfassung 139
Kapitel 7: Der Dijkstra-Algorithmus 140
7.1 Anwendung des Dijkstra-Algorithmus 141
7.2 Terminologie 146
7.3 Eintauschen gegen ein Klavier 148
7.4 Negativ gewichtete Kanten 155
7.5 Implementierung 158
Übung 168
7.6 Zusammenfassung 169
Kapitel 8: Greedy-Algorithmen 170
8.1 Das Stundenplanproblem 170
8.2 Das Rucksackproblem 173
Übungen 175
8.3 Das Mengenüberdeckungsproblem 175
8.3.1 Approximationsalgorithmen 176
Übungen 182
8.4 NP-vollständige Probleme 182
8.5 Das Problem des Handlungsreisenden – Schritt für Schritt 184
8.5.1 Wie lassen sich NP-vollständige Probleme erkennen? 188
Übungen 190
8.6 Zusammenfassung 190
Kapitel 9: Dynamische Programmierung 192
9.1 Das Rucksackproblem 192
9.1.1 Die einfache Lösung 193
9.1.2 Dynamische Programmierung 194
9.2 Häufig gestellte Fragen zum Rucksackproblem 202
9.2.1 Was geschieht beim Hinzufügen eines Gegenstands? 202
Übung 205
9.2.2 Was geschieht, wenn die Reihenfolge der Zeilen geändert wird? 205
9.2.3 Kann man das Gitter auch spaltenweise (statt zeilenweise) befüllen? 206
9.2.4 Was geschieht, wenn man ein leichteres Objekt hinzufügt? 206
9.2.5 Kann man Teile eines Gegenstands stehlen? 207
9.2.6 Optimierung des Reiseplans 207
9.2.7 Handhabung voneinander abhängiger Objekte 209
9.2.8 Ist es möglich, dass die Lösung mehr als zwei Teil-Rucksäcke erfordert? 210
9.2.9 Ist es möglich, dass die beste Lösung den Rucksack nicht vollständig füllt? 210
Übung 210
9.3 Der längste gemeinsame Teilstring 211
9.3.1 Erstellen des Gitters 212
9.3.2 Befüllen des Gitters 213
9.3.3 Die Lösung 214
9.3.4 Die längste gemeinsame Teilfolge 215
9.3.5 Die längste gemeinsame Teilfolge – Lösung 217
Übung 218
9.4 Zusammenfassung 218
Kapitel 10: k-nächste Nachbarn 220
10.1 Klassifikation von Orangen und Grapefruits 220
10.2 Entwicklung eines Empfehlungssystems 222
10.2.1 Merkmalsextraktion 224
Übungen 228
10.2.2 Regression 228
10.2.3 Auswahl geeigneter Merkmale 231
Übung 231
10.3 Einführung in Machine Learning 232
10.3.1 OCR 232
10.3.2 Entwicklung eines Spamfilters 233
10.3.3 Vorhersage der Entwicklung des Aktienmarkts 234
10.4 Zusammenfassung 234
Kapitel 11: Die nächsten Schritte 236
11.1 Bäume 236
11.2 Invertierte Indizes 239
11.3 Die Fourier-Transformation 240
11.4 Nebenläufige Algorithmen 241
11.5 MapReduce 242
11.5.1 Warum sind verteilte Algorithmen nützlich? 242
11.5.2 Die map-Funktion 243
11.5.3 Die reduce-Funktion 243
11.6 Bloom-Filter und HyperLogLog 244
11.6.1 Bloom-Filter 246
11.6.2 HyperLogLog 246
11.7 Die SHA-Algorithmen 247
11.7.1 Dateien vergleichen 247
11.7.2 Passwörter überprüfen 248
11.8 Locality-Sensitive Hashing 249
11.9 Diffie-Hellman-Schlüsselaustausch 250
11.10 Lineare Programmierung 251
11.11 Epilog 252
Anhang: Lösungen zu den Übungen 254
Kapitel 1 254
Kapitel 2 255
Kapitel 3 258
Kapitel 4 259
Kapitel 5 260
Kapitel 6 261
Kapitel 7 263
Kapitel 8 264
Kapitel 9 265
Kapitel 10 266
Stichwortverzeichnis 268