Algorithmen kapieren

1 - Cover [Seite 1]
2 - Lob für die erste Auflage [Seite 3]
3 - Titel [Seite 5]
4 - Inhaltsverzeichnis [Seite 7]
5 - Vorwort [Seite 13]
6 - Geleitwort [Seite 15]
7 - Einleitung [Seite 17]
7.1 - Verwendung dieses Buchs [Seite 18]
7.2 - Wer sollte dieses Buch lesen? [Seite 18]
7.3 - Aufbau dieses Buchs: Überblick [Seite 18]
7.4 - Konventionen und Downloads [Seite 20]
7.5 - Über den Autor [Seite 20]
7.6 - Über den Fachkorrektor [Seite 20]
7.7 - Danksagungen [Seite 21]
8 - Kapitel 1: Einführung in Algorithmen [Seite 23]
8.1 - 1.1 Einführung [Seite 23]
8.1.1 - 1.1.1 Performance [Seite 24]
8.1.2 - 1.1.2 Problemlösungen [Seite 24]
8.2 - 1.2 Binäre Suche [Seite 25]
8.2.1 - 1.2.1 Eine bessere Suchmethode [Seite 27]
8.2.2 - 1.2.2 Laufzeit [Seite 32]
8.3 - 1.3 Landau-Notation [Seite 33]
8.3.1 - 1.3.1 Die Laufzeiten von Algorithmen nehmen unterschiedlich schnell zu [Seite 33]
8.3.2 - 1.3.2 Visualisierung verschiedener Laufzeiten [Seite 36]
8.3.3 - 1.3.3 Die Landau-Notation beschreibt die Laufzeit im Worst Case [Seite 37]
8.3.4 - 1.3.4 Typische Laufzeiten gebräuchlicher Algorithmen [Seite 38]
8.3.5 - 1.3.5 Das Problem des Handlungsreisenden [Seite 40]
8.4 - 1.4 Zusammenfassung [Seite 42]
9 - Kapitel 2: Selectionsort [Seite 43]
9.1 - 2.1 Die Funktionsweise des Arbeitsspeichers [Seite 44]
9.2 - 2.2 Arrays und verkettete Listen [Seite 46]
9.2.1 - 2.2.1 Verkettete Listen [Seite 47]
9.2.2 - 2.2.2 Arrays [Seite 48]
9.2.3 - 2.2.3 Terminologie [Seite 50]
9.2.4 - 2.2.4 Einfügen in der Mitte einer Liste [Seite 51]
9.2.5 - 2.2.5 Löschen [Seite 53]
9.3 - 2.3 Was wird häufiger verwendet: Arrays oder Listen? [Seite 53]
9.4 - 2.4 Selectionsort [Seite 57]
9.5 - 2.5 Zusammenfassung [Seite 62]
10 - Kapitel 3: Rekursion [Seite 63]
10.1 - 3.1 Rekursion [Seite 64]
10.2 - 3.2 Basisfall und Rekursionsfall [Seite 67]
10.3 - 3.3 Der Stack [Seite 68]
10.3.1 - 3.3.1 Der Aufruf-Stack [Seite 69]
10.3.2 - 3.3.2 Der Aufruf-Stack mit Rekursion [Seite 72]
10.4 - 3.4 Zusammenfassung [Seite 76]
11 - Kapitel 4: Quicksort [Seite 77]
11.1 - 4.1 Teile und herrsche [Seite 78]
11.2 - 4.2 Quicksort [Seite 86]
11.3 - 4.3 Landau-Notation im Detail [Seite 91]
11.3.1 - 4.3.1 Mergesort und Quicksort im Vergleich [Seite 92]
11.3.2 - 4.3.2 Average Case und Worst Case im Vergleich [Seite 94]
11.4 - 4.4 Zusammenfassung [Seite 98]
12 - Kapitel 5: Hashtabellen [Seite 99]
12.1 - 5.1 Hashfunktionen [Seite 102]
12.2 - 5.2 Anwendungsfälle [Seite 107]
12.2.1 - 5.2.1 Hashtabellen zum Nachschlagen verwenden [Seite 107]
12.2.2 - 5.2.2 Doppelte Einträge verhindern [Seite 109]
12.2.3 - 5.2.3 Hashtabellen als Cache verwenden [Seite 111]
12.2.4 - 5.2.4 Zusammenfassung [Seite 114]
12.2.5 - 5.2.5 Kollisionen [Seite 114]
12.3 - 5.3 Performance [Seite 117]
12.3.1 - 5.3.1 Der Auslastungsfaktor [Seite 119]
12.3.2 - 5.3.2 Eine gute Hashfunktion [Seite 121]
12.4 - 5.4 Zusammenfassung [Seite 122]
13 - Kapitel 6: Breitensuche [Seite 125]
13.1 - 6.1 Einführung in Graphen [Seite 126]
13.2 - 6.2 Was ist ein Graph? [Seite 128]
13.3 - 6.3 Breitensuche [Seite 130]
13.3.1 - 6.3.1 Den kürzesten Pfad finden [Seite 132]
13.3.2 - 6.3.2 Warteschlangen [Seite 134]
13.4 - 6.4 Implementierung des Graphen [Seite 135]
13.5 - 6.5 Implementierung des Algorithmus [Seite 138]
13.5.1 - 6.5.1 Laufzeit [Seite 143]
13.6 - 6.6 Zusammenfassung [Seite 146]
14 - Kapitel 7: Bäume [Seite 147]
14.1 - 7.1 Dein erster Baum [Seite 148]
14.1.1 - 7.1.1 Dateiverzeichnisse [Seite 148]
14.2 - 7.2 A Space Odyssey: Gefunden mit der Tiefensuche [Seite 152]
14.2.1 - 7.2.1 Eine bessere Definition von Bäumen [Seite 156]
14.3 - 7.3 Binärbäume [Seite 156]
14.4 - 7.4 Huffman-Codierung [Seite 157]
14.5 - 7.5 Zusammenfassung [Seite 163]
15 - Kapitel 8: Balancierte Bäume [Seite 165]
15.1 - 8.1 Ein Balanceakt [Seite 166]
15.1.1 - 8.1.1 Schnelleres Einfügen mit Bäumen [Seite 166]
15.2 - 8.2 Kürzere Bäume sind schneller [Seite 170]
15.3 - 8.3 AVL-Bäume: eine Form von balancierten Bäumen [Seite 173]
15.3.1 - 8.3.1 Rotationen [Seite 173]
15.3.2 - 8.3.2 Woher weiß der AVL-Baum, wann es Zeit für eine Rotation ist? [Seite 176]
15.4 - 8.4 Splay-Bäume [Seite 181]
15.5 - 8.5 B-Bäume [Seite 183]
15.5.1 - 8.5.1 Welchen Vorteil bieten B-Bäume? [Seite 184]
15.6 - 8.6 Zusammenfassung [Seite 186]
16 - Kapitel 9: Der Dijkstra-Algorithmus [Seite 189]
16.1 - 9.1 Anwendung des Dijkstra-Algorithmus [Seite 190]
16.2 - 9.2 Terminologie [Seite 195]
16.3 - 9.3 Eintauschen gegen ein Klavier [Seite 197]
16.4 - 9.4 Negativ gewichtete Kanten [Seite 204]
16.5 - 9.5 Implementierung [Seite 207]
16.6 - 9.6 Zusammenfassung [Seite 218]
17 - Kapitel 10: Greedy-Algorithmen [Seite 219]
17.1 - 10.1 Das Stundenplanproblem [Seite 219]
17.2 - 10.2 Das Rucksackproblem [Seite 222]
17.3 - 10.3 Das Mengenüberdeckungsproblem [Seite 224]
17.3.1 - 10.3.1 Approximationsalgorithmen [Seite 225]
17.4 - 10.4 Zusammenfassung [Seite 231]
18 - Kapitel 11: Dynamische Programmierung [Seite 233]
18.1 - 11.1 Das Rucksackproblem [Seite 233]
18.1.1 - 11.1.1 Die einfache Lösung [Seite 234]
18.1.2 - 11.1.2 Dynamische Programmierung [Seite 235]
18.2 - 11.2 Häufig gestellte Fragen zum Rucksackproblem [Seite 243]
18.2.1 - 11.2.1 Was geschieht beim Hinzufügen eines Gegenstands? [Seite 243]
18.2.2 - 11.2.2 Was geschieht, wenn die Reihenfolge der Zeilen geändert wird? [Seite 246]
18.2.3 - 11.2.3 Kann man das Gitter auch spaltenweise (statt zeilenweise) befüllen? [Seite 247]
18.2.4 - 11.2.4 Was geschieht, wenn man ein leichteres Objekt hinzufügt? [Seite 247]
18.2.5 - 11.2.5 Kann man Teile eines Gegenstands stehlen? [Seite 248]
18.2.6 - 11.2.6 Optimierung des Reiseplans [Seite 248]
18.2.7 - 11.2.7 Handhabung voneinander abhängiger Objekte [Seite 250]
18.2.8 - 11.2.8 Ist es möglich, dass die Lösung mehr als zwei Teil-Rucksäcke erfordert? [Seite 251]
18.2.9 - 11.2.9 Ist es möglich, dass die beste Lösung den Rucksack nicht vollständig füllt? [Seite 251]
18.3 - 11.3 Der längste gemeinsame Teilstring [Seite 252]
18.3.1 - 11.3.1 Erstellen des Gitters [Seite 253]
18.3.2 - 11.3.2 Befüllen des Gitters [Seite 254]
18.3.3 - 11.3.3 Die Lösung [Seite 255]
18.3.4 - 11.3.4 Die längste gemeinsame Teilfolge [Seite 256]
18.3.5 - 11.3.5 Die längste gemeinsame Teilfolge - Lösung [Seite 258]
18.4 - 11.4 Zusammenfassung [Seite 259]
19 - Kapitel 12: k-nächste Nachbarn [Seite 261]
19.1 - 12.1 Klassifikation von Orangen und Grapefruits [Seite 261]
19.2 - 12.2 Entwicklung eines Empfehlungssystems [Seite 263]
19.2.1 - 12.2.1 Merkmalsextraktion [Seite 265]
19.2.2 - 12.2.2 Regression [Seite 270]
19.2.3 - 12.2.3 Auswahl geeigneter Merkmale [Seite 272]
19.3 - 12.3 Einführung in Machine Learning [Seite 273]
19.3.1 - 12.3.1 OCR [Seite 274]
19.3.2 - 12.3.2 Entwicklung eines Spamfilters [Seite 275]
19.3.3 - 12.3.3 Vorhersage der Entwicklung des Aktienmarkts [Seite 276]
19.4 - 12.4 Ablauf des Trainings für ein ML-Modell im Überblick [Seite 276]
19.5 - 12.5 Zusammenfassung [Seite 278]
20 - Kapitel 13: Die nächsten Schritte [Seite 281]
20.1 - 13.1 Lineare Regression [Seite 281]
20.2 - 13.2 Invertierte Indizes [Seite 283]
20.3 - 13.3 Die Fourier-Transformation [Seite 284]
20.4 - 13.4 Nebenläufige Algorithmen [Seite 284]
20.5 - 13.5 Map/Reduce [Seite 286]
20.5.1 - 13.5.1 Warum sind verteilte Algorithmen nützlich? [Seite 286]
20.6 - 13.6 Bloom-Filter und HyperLogLog [Seite 286]
20.6.1 - 13.6.1 Bloom-Filter [Seite 288]
20.6.2 - 13.6.2 HyperLogLog [Seite 288]
20.7 - 13.7 HTTPS und der Diffie-Hellman-Schlüsselaustausch [Seite 289]
20.8 - 13.8 Locality-Sensitive Hashing [Seite 293]
20.9 - 13.9 Min-Heaps und Prioritätswarteschlangen [Seite 294]
20.10 - 13.10 Lineare Programmierung [Seite 296]
20.11 - 13.11 Epilog [Seite 297]
21 - Anhang A: Performance von AVL-Bäumen [Seite 299]
22 - Anhang B: NP-schwere Probleme [Seite 301]
22.1 - B.1 Entscheidungsprobleme [Seite 302]
22.2 - B.2 Das Erfüllbarkeitsproblem [Seite 303]
22.3 - B.3 Schwer zu lösen, schnell zu verifizieren [Seite 306]
22.4 - B.4 Reduktionen [Seite 308]
22.5 - B.5 NP-schwer [Seite 309]
22.6 - B.6 NP-vollständig [Seite 310]
22.7 - B.7 Zusammenfassung [Seite 311]
23 - Anhang C: Lösungen zu den Übungen [Seite 313]
23.1 - Kapitel 1 [Seite 313]
23.2 - Kapitel 2 [Seite 314]
23.3 - Kapitel 3 [Seite 317]
23.4 - Kapitel 4 [Seite 318]
23.5 - Kapitel 5 [Seite 319]
23.6 - Kapitel 6 [Seite 320]
23.7 - Kapitel 9 [Seite 322]
23.8 - Kapitel 10 [Seite 323]
23.9 - Kapitel 11 [Seite 324]
23.10 - Kapitel 12 [Seite 324]
24 - Stichwortverzeichnis [Seite 327]