Algorithmen bilden das Herzstück jeder nichttrivialen Anwendung von Computern, und die Algorithmik ist ein modernes und aktives Gebiet der Informatik. Daher sollte sich jede Informatikerin und jeder Informatiker mit den algorithmischen Grundwerkzeugen auskennen. Dies sind Strukturen zur effizienten Organisation von Daten, häufig benutzte Algorithmen und Standardtechniken für das Modellieren, Verstehen und Lösen algorithmischer Probleme. Dieses Buch ist eine straff gehaltene Einführung in die Welt dieser Grundwerkzeuge, gerichtet an Studierende und im Beruf stehende Experten, die mit dem Programmieren und mit den Grundelementen der Sprache der Mathematik vertraut sind. Die einzelnen Kapitel behandeln Arrays und verkettete Listen, Hashtabellen und assoziative Arrays, Sortieren und Auswählen, Prioritätswarteschlangen, sortierte Folgen, Darstellung von Graphen, Graphdurchläufe, kürzeste Wege, minimale Spannbäume und Optimierung. Die Algorithmen werden auf moderne Weise präsentiert, mit explizit angegebenen Invarianten, und mit Kommentaren zu neueren Entwicklungen wie Algorithm Engineering, Speicherhierarchien, Algorithmenbibliotheken und zertifizierenden Algorithmen. Die Algorithmen werden zunächst mit Hilfe von Bildern, Text und Pseudocode erläutert; dann werden Details zu effizienten Implementierungen gegeben, auch in Bezug auf konkrete Sprachen wie C++ und Java. Quelle: Verlagstext
/ AUS DEM INHALT: / / /
Inhaltsverzeichnis:
1 Vorspeise: Arithmetik für ganze Zahleil 1
1.1 Addition 2
1.2 Multiplikation: Die Schulmethode 3
1.3 Ergebnisprüfung 7
1.4 Eine rekursive Version der Schulmethode 8
1.5 Karatsuba-Multiplikation 10
1.6 Algorithm Engineering 13
1.7 Die Programme 15
1.8 Beweise für Lemma 1.5 und Satz 1.7 18
1.9 Implementierungsaspekte 20
1.10 Historische Anmerkungen und weitere Ergebnisse 21
2 Einleitung 23
2.1 Asymptotische Notation 24
2.2 Das Maschinenmodell 28
2.3 Pseudocode 32
2.4 Erstellung korrekter Algorithmen und Programme 39
2.5 Ein Beispiel: Binäre Suche 42
2.6 Grundlagen der Algorithmenanalyse 44
2.7 Analyse des mittleren Falles 52
2.8 Randomisierte Algorithmen 57
2.9 Graphen 61
2.10 P und NP 68
2.11 Implementierungsaspekte 72
2.12 Historische Anmerkungen und weitere Ergebnisse 73
3 Darstellung von Folgen durch Arrays und verkettete Listen 75
3.1 Verkettete Listen 76
3.2 Unbeschränkte Arrays 83
3.3 *Amortisierte Analyse 90
3.4 Stapel und Warteschlangen 94
3.5 Listen und Arrays im Vergleich 98
3.6 Implementierungsaspekte 99
3.7 Historische Anmerkungen und weitere Ergebnisse 101
4 Hashtabellen und assoziative Arrays 103
4.1 Hashing mit Verkettung 106
4.2 Universelles Hashing 109
4.3 Hashing mit linearem Sondieren 115
4.4 Verkettung und lineares Sondieren im Vergleich 117
4.5 *Perfektes Hashing 118
4.6 Implementierungsaspekte 121
4.7 Historische Anmerkungen und weitere Ergebnisse 123
5 Sortieren und Auswählen 127
5.1 Einfache Sortierverfahren 130
5.2 Mergesort - ein 0(/i log n)-Sortieralgorithmus 132
5.3 Eine untere Schranke 135
5.4 Quicksort 138
5.5 Das Auswahlproblem 145
5.6 Brechen der unteren Schranke 147
5.7 *Externes Sortieren 150
5.8 Implementierungsaspekte 155
5.9 Historische Anmerkungen und weitere Ergebnisse 157
6 Prioritätswarteschlangen 161
6.1 Binärheaps 163
6.2 Adressierbare Prioritätswarteschlangen 169
6.3 *Externspeicher 177
6.4 Implementierungsaspekte "o 179
6.5 Historische Anmerkungen und weitere Ergebnisse 180
7 Sortierte Folgen 183
7.1 Binäre Suchbäume 186
7.2 (a, £)-Bäume und Rot-Schwarz-Bäume 189
7.3 Weitere Operationen 197
7.4 Amortisierte Analyse von Einfügungen und Löschungen 200
7.5 Erweiterte Suchbäume 203
7.6 Implementierungsaspekte 205
7.7 Historische Anmerkungen und weitere Ergebnisse 208
8 Darstellung von Graphen 211
8.1 Ungeordnete Kantenfolgen 212
8.2 Adjazenzarrays - Statische Graphen 213
8.3 Adjazenzlisten - Dynamische Graphen 214
8.4 Adjazenzmatrizen 216
8.5 Implizite Darstellungen 217
8.6 Implementierungsaspekte 218
8.7 Historische Anmerkungen und weitere Ergebnisse 219
9 Graphdurchläufe 221
9.1 Breitensuche 222
9.2 Tiefensuche 224
9.3 Implementierungsaspekte 239
9.4 Historische Anmerkungen und weitere Ergebnisse 240
10 Kürzeste Wege 243
10.1 Von Grundbegriffen zu einer allgemeinen Methode 245
10.2 Gerichtete azyklische Graphen 249
10.3 Nichtnegative Kantenkosten (Der Algorithmus von Dijkstra) 250
10.4 *Durchschnittsanalyse des Algorithmus von Dijkstra 254
10.5 Monotone ganzzahlige Prioritätswarteschlangen 256
10.6 Beliebige Kantenkosten (Der Algorithmus von Bellman und Ford) 263
10.7 Kürzeste Wege zwischen allen Knotenpaaren und Knotenpotenziale 265
10.8 Kürzeste-Wege-Anfragen 267
10.9 Implementierungsaspekte 273
10.10 Historische Anmerkungen und weitere Ergebnisse 274
11 Minimale Spannbäume 277
11.1 Schnitteigenschaft und Kreiseigenschaft 278
11.2 Der Algorithmus von Jarnfk-Prim 280
11.3 Der Algorithmus von Kruskal 281
11.4 Die Union-Find-Datenstruktur 283
11.5 *Externspeicher 289
11.6 Anwendungen 292
11.7 Implementierungsaspekte 295
11.8 Historische Anmerkungen und weitere Ergebnisse 296
12 Generische Ansätze für Optimierungsprobleme 299
12.1 Lineare Programmierung - ein Black-Box-Lösungsverfahren 301
12.2 Greedy-Algorithmen - Nie zurückschauen! 307
12.3 Dynamische Programmierung - Schrittweiser Aufbau 311
12.4 Systematische Suche - Im Zweifelsfall: Volle Rechenpower! 316
12.5 Lokale Suche-Global denken, lokal handeln! 321
12.6 Evolutionäre Algorithmen 333
12.7 Implementieningsaspekte 335
12.8 Historische Anmerkungen und weitere Ergebnisse 336
A Anhang 339
A1 Mathematische Symbole 339
A.2 Mathematische Begriffe 341
A.3 Grundlagen aus der Wahrscheinlichkeitsrechnung 342
A.4 Einige nützliche Formeln und Abschätzungen 347
Literaturverzeichnis
Sachverzeichnis