Bhargava Algorithmen kapieren

Visuell lernen und verstehen mit Illustrationen, Alltagsbeispielen und Python-Code
2024
ISBN: 978-3-7475-0909-8
Verlag: mitp Verlags GmbH & Co.KG
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 336 Seiten

Reihe: mitp Professional

• Visuelle Erläuterungen mit über 400 anschaulichen Illustrationen
• Mit einfachen Beispielen aus dem Alltag und zahlreichen Übungen
• Ausführlich kommentierter Beispielcode in Python

Algorithmen kapieren ohne graue Theorie

Ab sofort sind Algorithmen nicht mehr langweilig und trocken! Mit diesem Buch wird es dir leichtfallen, ihre Funktionsweise zu verstehen. Alle Algorithmen werden mithilfe von Beispielen aus dem täglichen Leben erläutert, z.B. der Unterschied zwischen Arrays und verketteten Listen anhand der Aufgabe, freie Plätze in einem Kinosaal zu finden.

Für den Einsatz in der Praxis

Du lernst die wichtigsten Algorithmen kennen, die dir dabei helfen, deine Programme zu beschleunigen, deinen Code zu vereinfachen und die gängigsten Aufgaben bei der Programmierung zu lösen. Dabei beginnst du mit einfachen Aufgaben wie Sortieren und Suchen. Mit diesen Grundlagen gerüstet kannst du auch schwierigere Aufgaben wie Datenkomprimierung oder künstliche Intelligenz in Angriff nehmen.

Visuell und praxisnah

Zu allen Erläuterungen findest du anschauliche Illustrationen und Diagramme sowie ausführlich kommentierten Beispielcode in Python. Übungsaufgaben mit Lösungen für jedes Kapitel helfen dir, dein Wissen zu testen und zu festigen.

Aus dem Inhalt:

• Such-, Sortier- und Graphenalgorithmen
• Performance von Algorithmen analysieren (Landau-Notation)
• Arrays, verkettete Listen und Hashtabellen
• Bäume und balancierte Bäume
• Rekursion und Stacks
• Quicksort und das Teile-und-herrsche-Verfahren
• Dijkstra-Algorithmus für die Ermittlung des kürzesten Pfads
• Approximationsalgorithmen und NP-vollständige Probleme
• Greedy-Algorithmen
• Dynamische Programmierung
• Klassifikation und Regression mit dem k-Nächste-Nachbarn-Algorithmus

Stimmen zum Buch

»Das Buch schafft das Unmögliche: Mathe macht Spaß und ist einfach.« (– Sander Rossel, COAS Software Systems)

»Algorithmen sind nicht langweilig! Die Lektüre des Buchs hat mir und meinen Studenten Spaß gemacht und war lehrreich.« (– Christopher Haupt, Mobirobo, Inc.)

»Heutzutage gibt es praktisch keinen Aspekt des Lebens, der nicht durch einen Algorithmus optimiert wird. Dieses Buch sollte Ihre erste Wahl sein, wenn Sie eine gut erklärte Einführung in dieses Thema suchen.« (– Amit Lamba, Tech Overture, LLC)

Zielgruppe

Einsteiger in die Programmierung und Studenten

Autoren/Hrsg.

Bhargava, Aditya Y.

Inhaltsverzeichnis

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

Über Autor(innen)

Aditya Bhargava ist Softwareentwickler und beschäftigt sich nicht nur mit Informatik, sondern auch mit bildender Kunst. Er bloggt über Programmierung unter adit.io.