Algorithmen und Datenstrukturen für Dummies

Andreas Gogol-Döring ist Professor für Informatik und Bioinformatik an der TH Mittelhessen. Thomas Letschert war ebenfalls fast 30 Jahre Professor für Informatik an der TH Mittelhessen und dort zuletzt verantwortlich für das Modul "Algorithmen und Datenstrukturen".

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