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 |