Algorithmen und Datenstrukturen für Dummies

Einleitung 17

UEber dieses Buch 17

Toerichte Annahmen ueber 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 loesen 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 Ausdruecke sind erlaubt 37

Algorithmen sprechen sogar Deutsch 37

Algorithmen sind Loesungen, keine Probleme 38

Algorithmen haben zaehlbare Schritte 39

Algorithmen sollten korrekt sein 40

Algorithmen koennen sich aufhaengen 41

Das Halteproblem ist unloesbar 42

Algorithmen richtig verstehen 43

Kapitel 2 Qualitaet von Algorithmen 47

So gut sind Algorithmen 47

Wer ist der Leichteste? 48

Laufzeiten vergleichen 50

Laufzeitanalysen 53

Lineare Laufzeiten 53

Oh du grosses O! 55

Arten der Laufzeitanalyse 57

Laufzeiten konkret bestimmen 59

Faustregel 1: Bei Schleifen muss man multiplizieren 59

Faustregel 2: Der staerkste Summand dominiert 61

Vorsicht vor versteckten Kosten 61

Randomisierte Laufzeitanalyse 62

Das Auswahlproblem 63

QuickSelect: Ein randomisierter Algorithmus 63

Amortisierte Laufzeitanalyse 66

Ein Binaerzaehler 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 Gaerten Der Strukturen 111

Kapitel 4 Listen: Immer einer nach dem anderen 113

Listen: Datenmodell und Implementierung 116

Datenabstraktion: Was Listen so koennen 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

Rueckblick: Imperative und funktionale Algorithmen 157

Kapitel 5 Baeume: Immer einer ueber 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 Grossen nach rechts 176

Binaere Suchbaeume 177

Verzeichnisse als Suchbaeume 179

Baeume verkleiden sich gerne mal 181

Tries 182

Prioritaetswarteschlangen 184

Baeume als Datenmodell 189

Ausdrucksbaeume 190

Mit Stapeln uebersetzen 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 fuer 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 Loesungen 221

Kapitel 7 Sortieren 223

Alles in Ordnung 223

Das Sortierproblem 224

SelectionSort: So lange waehlen, 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 Zaehlen 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 annaehern 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 fuer Mengen 283

Funktionale Datenabstraktion fuer 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 haelt, ist nur zu faul zum Suchen 306

Baeume balancieren 308

Rot-Schwarz-Baeume 311

Kapitel 10 Verbindungen finden 321

Kuerzeste Pfade 322

Alle kuerzesten Pfade von einem Start aus 322

Vom Vertrauten ins Unbekannte 325

Kuerzester Pfad zu allen Knoten 328

Dijkstras Algorithmus 330

Datenstrukturen fuer Dijkstras Algorithmus 333

Verbundenes aufspueren 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

Erschoepfende Suche 354

Die ueblichen Verdaechtigen: Kombinatorische Objekte 355

Konzentrierte oder weit ausschweifende Suche 358

Die erschoepfende 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 stueckweise bewertbar: kein Backtracking 371

Backtracking als Suche im Zustandsraum 373

Verzweigen und Begrenzen 375

Erschoepfende und Backtracking-Suche im Irrgarten 375

Optimierungen und Bewertungsfunktionen 377

Komplexitaetsklassen: Schwere Probleme fuehren zu anstrengender Arbeit 380

Schwer ist, was den Besten schwerfaellt 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 abwaelzen 393

Das Einwohnermeldeamt von Buerokrazien 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 Faelle? 401

So bestimmt man, welcher Fall vorliegt 401

Binaersuche 403

Der Suchbaum in einfach 403

Grenzen des Suchbereichs 405

Weitere Beispiele fuer 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 Stueck abschneiden und Herrschen 414

Zwischenergebnisse merken 416

Den Algorithmus vom Kopf auf die Fuesse 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 zurueckfinden 433

Kapitel 14 Naeherungsloesungen 437

Heuristiken 437

Interpolationssuche 438

Heuristisches Verzweigen und Begrenzen 441

Der A*-Algorithmus 443

Approximation 446

TSP: Die kuerzeste Rundreise 446

Gierige Heuristik 447

Lokale Suche 449

Approximation ohne Heuristik 450

Gier 453

Das Wechselgeldproblem 455

Das Problem der Mengenueberdeckung 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

Prioritaetswarteschlange 469

Liste 470

Array 471

Menge 471

Verzeichnis 472

Relation 472

Graph 473

Baum 474

Kapitel 16 Zehn Ratschlaege, 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 Kreativitaet 479

Unterscheide Datenmodell und Datenstruktur 480

Was schwierig aussieht, ist oft auch schwierig 480

Stichwortverzeichnis 481