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.

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

Inhalt

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 Ide…