/ AUS DEM INHALT: / / /
Inhaltsverzeichnis:
Vorwort XIII
I Grundlagen 1
1 Die Rolle von Algorithmen in der elektronischen Datenverarbeitung 5
1.1 Algorithmen 5
1.2 Algorithmen als Technologie 11
2 Ein einführendes Beispiel 17
2.1 Sortieren durch Einfügen 17
2.2 Analyse von Algorithmen 24
2.3 Entwurf von Algorithmen 30
3 Wachstum von Funktionen 45
3.1 Asymptotische Notation 45
3.2 Standardnotationen und Standardfunktionen 55
4 Teile-und-Beherrsche 67
4.1 Das Max-Teilfeld-Problem 70
4.2 Strassens Algorithmus zur Matrizenmultiplikation 77
4.3 Die Substitutionsmethode zum Lösen von Rekursionsgleichungen 85
4.4 Die Rekursionsbaum-Methode zum Lösen von Rekursionsgleichungen .89
4.5 Die Mastermethode zum Lösen von Rekursionsgleichungen 95
4.6 * Beweis des Mastertheorems 99
5 Probabilistische Analyse und randomisierte Algorithmen 115
5.1 Das Bewerberproblem 115
5.2 Indikatorfunktionen 118
5.3 Randomisierte Algorithmen 123
5.4 * Probabilistische Analyse und mehr zur Verwendung der Indikatorfunktion
130
II Sortieren und Ranggrößen 147
6 Heapsort 153
6.1 Heaps 153
6.2 Die Heap-Eigenschaft aufrechterhalten 156
6.3 Einen Heap bauen 158
6.4 Der Heapsort-Algorithmus 161
6.5 Prioritätswarteschlangen ' 162
7 Quicksort 171
7.1 Beschreibung von Quicksort 171
7.2 Die Performanz von Quicksort 175
7.3 Eine randomisierte Version von Quicksort 179
7.4 Analyse von Quicksort 181
8 Sortieren in linearer Zeit 191
8.1 Untere Schranken für das Sortieren 191
8.2 Countingsort 194
8.3 Radixsort 197
8.4 Bucketsort 200
9 Mediane und Ranggrößen 213
9.1 Minimum und Maximum 213
9.2 Auswahl in linearer erwarteter Zeit 215
9.3 Auswahl in linearer Zeit im schlechtesten Fall 219
III Datenstrukturen 227
10 Elementare Datenstrukturen 233
10.1 Stapel und Warteschlangen 233
10.2 Verkettete Listen 237
10.3 Implementierung von Zeigern und Objekten 242
10.4 Darstellung von gerichteten Bäumen 246
11 Hashtabeilen 255
11.1 Adresstabellen mit direktem Zugriff 256
11.2 Hashtabellen 258
11.3 Hashfunktionen 264
11.4 Offene Adressierung 272
11.5 * Perfektes Hashing 280
12 Binäre Suchbäume 289
12.1 Was ist ein binärer Suchbaum? 289
12.2 Abfragen in einem binären Suchbaum 292
12.3 Einfügen und Löschen 296
12.4 * Zufällig erzeugte binäre Suchbäume 302
13 Rot-Schwarz-Bäume 311
13.1 Eigenschaften von Rot-Schwarz-Bäumen 311
13.2 Rotationen 315
13.3 Einfügen eines Knotens 317
13.4 Löschen eines Knotens 325
14 Erweitern von Datenstrukturen 341
14.1 Dynamische Ranggröße 341
14.2 Wie man eine Datenstruktur erweitert 347
14.3 Intervallbäume 350
IV Fortgeschrittene Entwurfs- und Analysetechniken 359
15 Dynamische Programmierung 363
15.1 Schneiden von Eisenstangen 364
15.2 Matrizen-Kettenmultiplikation 374
15.3 Elemente dynamischer Programmierung 381
15.4 Längste gemeinsame Teilsequenz 393
15.5 Optimale binäre Suchbäume 399
16 Greedy-Algorithmen 417
16.1 Ein Aktivitäten-Auswahl-Problem 418
16.2 Elemente der Greedy-Strategie 425
16.3 Huffman-Codierungen 431
16.4 * Matroiden und Greedy-Methoden 440
16.5 * Ein Task-Scheduling-Problem als Matroid 447
17 Amortisierte Analyse 455
17.1 Aggregat-Analyse 456
17.2 Account-Methode 460
17.3 Die Potentialmethode 462
17.4 Dynamische Tabellen 466
V Höhere Datenstrukturen 483
18 B-Bäume 489
18.1 Die Definition von B-Bäumen 493
18.2 Grundoperationen auf B-Bäumen 496
18.3 Löschen eines Schlüssels aus einem B-Baum 504
19 Fibonacci-Heaps 511
19.1 Die Struktur von Fibonacci-Heaps 513
19.2 Operationen der fusionierbaren Heaps 516
19.3 Verringern eines Schlüssels und Entfernen eines Knotens 525
19.4 Beschränkung des maximalen Grades 529
20 van-Emde-Boas-Bäume 539
20.1 Vorbereitende Ansätze 540
20.2 Eine rekursive Datenstruktur 544
20.3 Die van-Emde-Boas-Bäume 553
21 Datenstrukturen disjunkter Mengen 569
21.1 Operationen auf disjunkten Mengen 569
21.2 Darstellung disjunkter Mengen mithilfe verketteter Listen 572
21.3 Wälder disjunkter Mengen 576
21.4 * Analyse der Vereinigung nach dem Rang mit Pfadverkürzung 580
VI Graphenalgorithmen 595
22 Elementare Graphenalgorithmen 599
22.1 Daxstellungen von Graphen "599
22.2 Breitensuche 603
22.3 Tiefensuche 613
22.4 Topologisches Sortieren 622
22.5 Starke Zusammenhangskomponenten 626
23 Minimale Spannbäume 635
23.1 Aufbau eines minimalen Spannbaums 636
23.2 Die Algorithmen von Kruskal und Prim 641
24 Kürzeste Pfade von einem Startknoten aus 655
24.1 Der Bellman-Ford-Algorithmus 663
24.2 Kürzeste Pfade von einem Startknoten aus in DAGs 667
24.3 Dijkstras Algorithmus 670
24.4 Differenzbedingungen und kürzeste Pfade 677
24.5 Beweise der Eigenschaften kürzester Pfade 683
25 Kürzeste Pfade für alle Knotenpaare 697
25.1 Kürzeste Pfade und Matrizenmultiplikation 699
25.2 Der Floyd-Warshall-Algorithmus 705
25.3 Johnsons Algorithmus für dünn besetzte Graphen 713
26 Maximaler Fluss 721
26.1 Flussnetzwerke 722
26.2 Die Ford-Fulkerson-Methode 727
26.3 Maximales bipartites Matching 745
26.4 * Push/Relabel-Algorithmen 749
26.5 * Der Relabel-to-Front-Algorithmus 762
VII Ausgewählte Themen 781
27 Mehrfadige Algorithmen 785
27.1 Grundlagen von dynamischem Multithreading 787
27.2 Mehrfadige Matrizenmultiplikation 806
27.3 Mehrfadiges Sortieren durch Mischen 811
28 Operationen auf Matrizen 827
28.1 Lösen linearer Gleichungssysteme 827
28.2 Matrixinversion 841
28.3 Symmetrische positiv definite Matrizen, Summe der quadratischen Fehler 846
29 Lineare Programmierung 857
29.1 Standard- und SchlupfForm 864
29.2 Darstellung von Problemen als lineare Programme 872
29.3 Der Simplexalgorithmus 878
29.4 Dualität 893
29.5 Die initiale zulässige Basislösung 899
30 Polynome und die FFT 911
30.1 Darstellung von Polynomen 913
30.2 Die DFT und FFT 919
30.3 Effiziente Implementierung der FFT 927
31 Zahlentheoretische Algorithmen 937
31.1 Elementare zahlentheoretische Begriffe 938
31.2 Größter gemeinsamer Teiler 944
31.3 Modulare Arithmetik 950
31.4 Lösen modularer linearer Gleichungen 957
31.5 Der chinesische Restsatz 962
31.6 Potenzen eines Elements 965
31.7 Das RSA-Kryptosystem 970
31.8 * Primzahltests 977
31.9 * Primfaktorzerlegung 987
32 String-Matching 997
32.1 Der naive String-Matching-Algorithmus 999
32.2 Der Rabin-Karp-Algorithmus 1002
32.3 String-Matching mit endlichen Automaten 1007
32.4 * Der Knuth-Morris-Pratt-Algorithmus 1014
33 Algorithmische Geometrie 1025
33.1 Eigenschaften von Strecken 1026
33.2 Bestimmung von Schnittpunkten in einer Menge von Strecken 1032
33.3 Bestimmen der konvexen Hülle 1039
33.4 Berechnung des dichtesten Punktepaares 1050
34 NP-Vollständigkeit 1059
34.1 Polynomielle Zeit 1064
34.2 Verifikation in polynomieller Zeit 1072
34.3 NP-Vollständigkeit und Reduktion 1077
34.4 NP-Vollständigkeitsbeweise 1088
34.5 NP-vollständige Probleme 1096
35 Approximationsalgorithmen 1117
35.1 Das Knotenüberdeckungsproblem 1119
35.2 Das Problem des Handelsreisenden 1122
35.3 Das Mengenüberdeckungsproblem 1128
35.4 Randomisierung und lineare Programmierung 1134
35.5 Das Teilsummenproblem 1139
VIII Anhang 1151
A Summen 1155
A.l Summenformeln und Eigenschaften 1155
A.2 Abschätzungen für Summen 1159
B Mengen usw1169
B.l Mengen 1169
B.2 Relationen 1174
XII Inhaltsverzeichnis
B.3 Funktionen 1176
B.4 Graphen 1178
B.5 Bäume 1183
C Kombinatorik und Wahrscheinlichkeitstheorie 1193
C.l Kombinatorik ; 1193
C.2 Wahrscheinlichkeiten 1199
C.3 Diskrete Zufallsvariablen 1205
C.4 Die geometrische Verteilung und die Binomialverteilung 1211
C.5 * Die Ränder der Binomialverteilung 1217
D Matrizen 1227
D.l Matrizen und Matrizenoperationen 1227
D.2 Elementare Matrizeneigenschaften 1232
Literaturverzeichnis 1241
Index 1265