Details

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

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".

DE