Algorithmen und Datenstrukturen für Dummies

Dieses Buch führt Sie sachte in die Denkweisen des Fachs "Algorithmen und Datenstrukturen" ein. Es erklärt Informatik-Anfängern Terminologie, Notation und zentrale Inhalte des Fachgebiets auf anschauliche und sehr unterhaltsame Weise. Ein Fokus sind die Techniken und Tricks, die Sie brauchen, um effiziente Algorithmen und Datenstrukturen zu bauen. Sie werden auch in die Lage versetzt, Pseudocode in der typischen akademischen Darstellung zu verstehen und in unterschiedlichen Programmiersprachen zu realisieren oder umgekehrt grundlegende algorithmische Ideen als Pseudocode zu dokumentieren.

Einleitung 17
Ü ber dieses Buch 17
Tö richte Annahmen ü ber den Leser 19
Wie dieses Buch aufgebaut ist 19
Symbole, die in diesem Buch verwendet werden 20
Wie es weitergeht 21
Teil I Grundbegriffe 23
Kapitel 1 Algorithmen 25
Das sind Algorithmen 25
Algorithmen lö sen Probleme 26
Algorithmen basieren auf einem einfachen Maschinenmodell 30
Algorithmen sind bewertbar 32
Algorithmen agieren in Modellwelten 32
Algorithmen sind keine Programme 33
Algorithmen klar beschreiben 35
Sprechen Sie Pseudocode? 35
Mathematische Ausdrü cke sind erlaubt 37
Algorithmen sprechen sogar Deutsch 37
Algorithmen sind Lö sungen, keine Probleme 38
Algorithmen haben zä hlbare Schritte 39
Algorithmen sollten korrekt sein 40
Algorithmen kö nnen sich aufhä ngen 41
Das Halteproblem ist unlö sbar 42
Algorithmen richtig verstehen 43
Kapitel 2 Qualitä t von Algorithmen 47
So gut sind Algorithmen 47
Wer ist der Leichteste? 48
Laufzeiten vergleichen 50
Laufzeitanalysen 53
Lineare Laufzeiten 53
Oh du groß es O! 55
Arten der Laufzeitanalyse 57
Laufzeiten konkret bestimmen 59
Faustregel 1: Bei Schleifen muss man multiplizieren 59
Faustregel 2: Der stä rkste Summand dominiert 61
Vorsicht vor versteckten Kosten 61
Randomisierte Laufzeitanalyse 62
Das Auswahlproblem 63
QuickSelect: Ein randomisierter Algorithmus 63
Amortisierte Laufzeitanalyse 66
Ein Binä rzä hler an der Fassade 66
Ein sparsamer Stapel 69
Die Potenzialmethode 71
Kapitel 3 Daten und ihre Struktur 75
Aus Daten Strukturen bauen 75
Datenstrukturen: die Essenz 76
Datenstrukturen im Pseudocode 78
Algebraische Datentypen 92
Funktion folgt Struktur 97
Endrekursive und linear-rekursive Funktionen 98
Linear-rekursive Funktionen und die Akkumulatortechnik 101
Strukturelle Rekursion 103
Teilen und Herrschen 105
Strukturen durchlaufen: Iteratoren und Traversierungen 106
Teil II Algorithmen in Den Gä rten Der Strukturen 111
Kapitel 4 Listen: Immer einer nach dem anderen 113
Listen: Datenmodell und Implementierung 116
Datenabstraktion: Was Listen so kö nnen sollen 118
Alles ist ewig und Rekursion ist gut 129
Listen in Funktionalistan 131
Persistente Datenstrukturen 143
Ordnung herstellen: imperativ und funktional 145
Nicht alles ist ewig und Form ist nicht Inhalt 152
Warteschlange als funktionale Datenabstraktion 152
Warteschlangen mit Amortisation 155
Rü ckblick: Imperative und funktionale Algorithmen 157
Kapitel 5 Bä ume: Immer einer ü ber dem anderen 161
Wo ist die Kokosnuss? 162
Baumtraversierungen 163
Mit Stapeln in die Tiefe tauchen 168
Mit Warteschlangen in die Breite gehen 173
Die Kleinen nach links, die Groß en nach rechts 176
Binä re Suchbä ume 177
Verzeichnisse als Suchbä ume 179
Bä ume verkleiden sich gerne mal 181
Tries 182
Prioritä tswarteschlangen 184
Bä ume als Datenmodell 189
Ausdrucksbä ume 190
Mit Stapeln ü bersetzen und auswerten 191
Kapitel 6 Graphen: Jeder mit jedem 195
Im Irrgarten der sozialen Netzwerke 196
Ein kurzer Blick in die Welt der Graphen 198
Einflussnahme als Graphenproblem 202
Graphen traversieren 203
Datenstrukturen fü r Graphen 206
Nachbarschaften dokumentieren 207
Daten und Probleme machen Graphen 210
Was nicht passt, wird passend gemacht 212
Erst die Schuhe, dann das Hemd - oder wie? 214
Topologische Sortierung, ein guter Start in den Tag 214
Liste folgt Funktional 216
Array folgt Imperativ 217
Teil III Probleme Und Ihre Lö sungen 221
Kapitel 7 Sortieren 223
Alles in Ordnung 223
Das Sortierproblem 224
SelectionSort: So lange wä hlen, bis es passt 227
Laufzeit von SelectionSort 228
MergeSort: Geteiltes Leid ist halb sortiert 229
Sortierte Teilarrays verschmelzen mit Merge 230
Teilen und Herrschen 232
Laufzeit von MergeSort 232
QuickSort: Quick and Easy 234
Partition teilt das Array auf 234
Sortieren mit QuickSort 235
Worst-Case-Laufzeit von QuickSort 236
Randomisierung 237
HeapSort: Ein Haufen Arbeit 237
Die Datenstruktur Heap 238
Der Heap als Priority Queue 239
Besser sortieren mit dem Heap 240
Die maximale Sortiergeschwindigkeit 241
Sortieren in Linearzeit 244
CountingSort: Sortieren durch Zä hlen 244
Sortieren nach Ziffern 245
Stabile Sortierverfahren 247
RadixSort: Mehrfach ziffernweise sortieren 248
Weitere Sortieralgorithmen 249
BubbleSort: Nachbarn vertauschen 249
Gnomesort: Immer hin und her 250
InsertionSort: Spielkarten dazwischen schieben 251
Kapitel 8 Rucksack packen 253
Wie man einen Koffer packt 253
Das Rucksackproblem 253
Das Wichtigste zuerst einpacken 255
Alles ausprobieren 257
Suchen im Entscheidungsbaum 258
Den Suchraum begrenzen 261
Probleme langsam wachsen lassen 264
Wachsende Probleme klug speichern 267
Sich dem Optimum annä hern 270
Lineare Optimierung 274
Optimierung von Produktionsmengen 274
Ein System von Ungleichungen 275
Ziel: Gewinnmaximierung 275
Ganzzahlige lineare Optimierung 276
Das Rucksackproblem als ILP 277
Kapitel 9 Mengen und ihre Speicherung 279
Ich bin eine Menge 281
Imperative Datenabstraktion fü r Mengen 283
Funktionale Datenabstraktion fü r Mengen 285
Gut gehackt ist schnell gefunden 290
Hashfunktionen 292
Hashtabellen 293
Garantiert gut gehackt 298
Derselbe ist nicht immer der Gleiche 300
Viel ist oft eine Menge 304
Wer Ordnung hä lt, ist nur zu faul zum Suchen 306
Bä ume balancieren 308
Rot-Schwarz-Bä ume 311
Kapitel 10 Verbindungen finden 321
Kü rzeste Pfade 322
Alle kü rzesten Pfade von einem Start aus 322
Vom Vertrauten ins Unbekannte 325
Kü rzester Pfad zu allen Knoten 328
Dijkstras Algorithmus 330
Datenstrukturen fü r Dijkstras Algorithmus 333
Verbundenes aufspü ren 334
Verbundene Komponenten identifizieren 335
Datenstrukturen bei der Berechnung verbundener Komponenten 338
Disjunkte Mengen als Datenstruktur 340
Laufzeiten 344
Spann mir einen Graphen auf 345
Minimaler Spannbaum 346
Kruskals Algorithmus 347
Teil IV Algorithmische Techniken 351
Kapitel 11 Probleme totschlagen 353
Erschö pfende Suche 354
Die ü blichen Verdä chtigen: Kombinatorische Objekte 355
Konzentrierte oder weit ausschweifende Suche 358
Die erschö pfende Suche nach acht friedlichen Damen 362
Iterative und rekursive Erzeugung des Suchraums 364
Schleifen rekursiv erzeugen 364
Einen baumartigen Suchraum rekursiv erzeugen 366
Backtracking 369
Kandidaten nicht stü ckweise bewertbar: kein Backtracking 371
Backtracking als Suche im Zustandsraum 373
Verzweigen und Begrenzen 375
Erschö pfende und Backtracking-Suche im Irrgarten 375
Optimierungen und Bewertungsfunktionen 377
Komplexitä tsklassen: Schwere Probleme fü hren zu anstrengender Arbeit 380
Schwer ist, was den Besten schwerfä llt 380
Ein Labyrinth der Kameras 382
Das nichtdeterministische Orakel 383
Schwer, schwerer, NP-schwer 385
Wie man mit schweren Problemen umgeht 387
NP-schwer hoffnungslos 387
Gute Ideen sind kein Hexenwerk 390
Kapitel 12 Teilen und Herrschen 393
Aufgaben auf Mitarbeiter abwä lzen 393
Das Einwohnermeldeamt von Bü rokrazien 393
Das Prinzip Teilen und Herrschen 395
Laufzeiten bei Teilen und Herrschen 396
Das Mastertheorem 397
Fall 1: Der Chef arbeitet mehr 398
Fall 2: Der Chef arbeitet gleich viel 399
Fall 3: Der Chef arbeitet weniger 400
Gibt es noch weitere Fä lle? 401
So bestimmt man, welcher Fall vorliegt 401
Binä rsuche 403
Der Suchbaum in einfach 403
Grenzen des Suchbereichs 405
Weitere Beispiele fü r Teilen und Herrschen 407
Sortieren 407
Matrizen multiplizieren 408
Minimaler Punktabstand 409
Kapitel 13 Dynamisches Programmieren 411
Ein profitabler Bauauftrag 411
Das Maximale-Teilsumme-Problem 412
Gier hilft nicht 412
Rohe Gewalt hilft eher 413
Inkrementelle Gewalt ist weniger roh 413
Ein Stü ck abschneiden und Herrschen 414
Zwischenergebnisse merken 416
Den Algorithmus vom Kopf auf die Fü ß e stellen 418
Der ultimative Maximale-Teilsumme-Algorithmus 418
Probleme wachsen lassen 419
Das Prinzip des dynamischen Programmierens 419
Beispiel 1: Minimum 420
Beispiel 2: Fibonacci-Zahlen 421
Beispiel 3: Rucksack packen 424
Vergleich von Texten 424
Die Editierdistanz 425
Strings alignieren 426
Arbeitsteilung auf der Alignmentbaustelle 427
Optimale Alignments mit dynamischem Programmieren 428
Der Weg zum Optimum 431
Entscheidungen merken 431
Den Pfad zurü ckfinden 433
Kapitel 14 Nä herungslö sungen 437
Heuristiken 437
Interpolationssuche 438
Heuristisches Verzweigen und Begrenzen 441
Der A*-Algorithmus 443
Approximation 446
TSP: Die kü rzeste Rundreise 446
Gierige Heuristik 447
Lokale Suche 449
Approximation ohne Heuristik 450
Gier 453
Das Wechselgeldproblem 455
Das Problem der Mengenü berdeckung 458
Gier in Perfektion 461
Huffman-Codierung 461
Teil V Der Top-Ten-Teil 465
Kapitel 15 Zehn Datenabstraktionen und Datenstrukturen 467
Stapel 468
Warteschlange 469
Prioritä tswarteschlange 469
Liste 470
Array 471
Menge 471
Verzeichnis 472
Relation 472
Graph 473
Baum 474
Kapitel 16 Zehn Ratschlä ge, wenn (bevor) der kleine Frust kommt 475
Rekursion ist deine Freundin 475
Mathematik ist einfach 476
Pseudocode ist verstehbar 477
Abstraktion ist gut 477
Sei auch mal funktional 478
Ein Bild sagt mehr als 1000 Worte 478
Vieles ist solides Handwerk 479
Es geht auch um Kreativitä t 479
Unterscheide Datenmodell und Datenstruktur 480
Was schwierig aussieht, ist oft auch schwierig 480
Stichwortverzeichnis 481