Inhaltsverzeichnis
Vorwort V
I Grundlagen
1 Die Rolle von Algorithmen in der elektronischen Datenverarbeitung 5
1.1 Algorithmen 5
1.2 Algorithmen als Technologie 10
2 Ein einführendes Beispiel 15
2.1 Sortieren durch Einfügen 15
2.2 Analyse von Algorithmen 21
2.3 Entwurf von Algorithmen 27
3 Wachstum von Funktionen 41
3.1 Asymptotische Notation 41
3.2 Standardnotationen und Standardfunktionen 51
4 Rekursionsgleichungen 61
4.1 Die Substitutionsmethode 62
4.2 Die Rekursionsbaum-Methode 66
4.3 Die Mastermethode 72
4.4 * Beweis des Mastertheorems 75
5 Probabilistische Analyse und randomisierte Algorithmen 89
5.1 Bewerberproblem 89
5.2 Indikatorfunktionen 92
5.3 Randomisierte Algorithmen 96
5.4 * Probabilistische Analyse und mehr zur Verwendung der Indikatorfunktion 103

II Sortieren und Ranggrößen 119
6 Heapsort 125
6.1 Heaps 125
6.2 Aufrechterhaltung der Heap-Eigenschaft 128
6.3 Konstruktion eines Heap 130
6.4 Der Heapsort-Algorithmus 133
6.5 Prioritätswarteschlangen 135
7 Quicksort 143
7.1 Beschreibung von Quicksort . . 143
7.2 Die Performanz von Quicksort 147
7.3 Eine randomisierte Version von Quicksort 151
7.4 Analyse von Quicksort 152
8 Sortieren in linearer Zeit 163
8.1 Untere Schranken für das Sortieren 163
8.2 Countingsort 166
8.3 Radixsort 168
8.4 Bucketsort 171
9 Mediane und Ranggrößen 181
9.1 Minimum und Maximum 181
9.2 Auswahlin linearer erwarteter Zeit 183
9.3 Auswahl in linearer Zeit für den schlechtesten Fall 187

III Datenstrukturen 195
10 Elementare Datenstrukturen 201
10.1 Stapel und Warteschlangen 201
10.2 Verkettete Listen 205
10.3 Implementierung von Zeigern und Objekten 210
10.4 Darstellung von gerichteten Bäumen 214
11 Hashtabellen 221
11.1 Adresstabellen mit direktem Zugri 222
11.2 Hashtabellen 223
11.3 Hashfunktionen 229
11.4 O ene Adressierung 237
11.5 * Perfektes Hashing 245
12 Binäre Suchbäume 255
12.1 Was ist ein binärerSuchbaum? 255
12.2 Abfragen in einem bin¨
aren Suchbaum 258
12.3 Einfügen und Löschen 262
12.4 * Zufällig erzeugte binäre Suchbäume 266
13 Rot-Schwarz-Bäume 275
13.1 Eigenschaften von Rot-Schwarz-Bäumen 275
13.2 Rotationen 279
13.3 Einfügen 281
13.4 Entfernen 289
14 Erweitern von Datenstrukturen 303
14.1 Dynamische Ranggröße 303
14.2 Wie man eine Datenstruktur erweitert 309
14.3 Intervallbäume 312
IV Fortgeschrittene Entwurfs- und Analysetechniken 321
15 Dynamische Programmierung 325
15.1 Ablaufkoordination von Montagebändern 326
15.2 Matrix-Kettenmultiplikation 333
15.3 Elemente dynamischer Programmierung 340
15.4 Längste gemeinsame Teilsequenz 351
15.5 Optimale binäare Suchbäume 357
16 Greedy-Algorithmen 371
16.1 Ein Aktivitäten-Auswahl-Problem 372
16.2 Elemente der Greedy-Strategie 380
16.3 Human-Codierungen 385
16.4 * Theoretische Grundlagen der Greedy-Methoden . 393
16.5 * Ein Task-Scheduling-Problem 400
17 Amortisierte Analyse 407
17.1 Aggregat-Analyse 408
17.2 Account-Methode 412
17.3 Die Potentialmethode 414
17.4 Dynamische Tabellen 418
V Höhere Datenstrukturen433
18 B-Bäume 439
18.1 Die Definition von B-Bäumen 443
18.2 Grundoperationen auf B-Bäumen 446
18.3 Entfernen eines Schlüssels aus einem B-Baum 453
19 Binomiale Heaps 461
19.1 Binomiale Bäume und binomiale Heaps 463
19.2 Operationen auf binomialen Heaps 467
20 Fibonacci-Heaps 481
20.1 Die Struktur von Fibonacci-Heaps 482
20.2 Operationen der fusionierbaren Heaps 484
20.3 Verringern eines Schlüssels und Entfernen eines Knotens 493
20.4 Beschränkung des maximalen Grades 497
21 Datenstrukturen disjunkter Mengen 503
21.1 Operationen auf disjunkten Mengen 503
21.2 Darstellung disjunkter Mengen mithilfe verketteter Listen 507
21.3 Wälder disjunkter Mengen 510
21.4 * Analyse der Vereinigung nach dem Rang mit Pfadverkürzung 514
VI Graphenalgorithmen 527
22 Elementare Graphenalgorithmen 531
22.1 Darstellungen von Graphen 531
22.2 Breitensuche 535
22.3 Tiefensuche 544
22.4 Topologisches Sortieren 553
22.5 Starke Zusammenhangskomponenten 556
23 Minimale Spannbäume 565
23.1 Aufbau eines minimalen Spannbaums 566
23.2 Die Algorithmen von Kruskal und Prim 571
24 Das Problem der kürzesten Pfade bei einem einzigen Startknoten 583
24.1 Der Bellman-Ford-Algorithmus 591
24.2 Kürzeste Pfade von einem einzigen Startknoten aus in ger. azykl. Graphen 595
24.3 Der Dijkstra-Algorithmus 598
24.4 Differenzbedingungen und kürzeste Pfade 604
24.5 Beweise der Eigenschaften kürzester Pfade 610
25 Das Problem der kürzesten Pfade für alle Knotenpaare 623
25.1 Kürzeste Pfade und Matrixmultiplikation 625
25.2 Der Floyd-Warshall-Algorithmus 631
25.3 Johnsons Algorithmus für dünn besetzte Graphen 638
26 Maximaler Fluss 647
26.1 Flussnetzwerke 648
26.2 Die Ford-Fulkerson-Methode 654
26.3 Maximalesbipartites Matching 668
26.4 * Push/Relabel-Algorithmen 673
26.5 * Der Relabel-to-Front-Algorithmus 685
VII Ausgewählte Themen 703
27 Sortiernetzwerke 707
27.1 Vergleichsnetzwerke 707
27.2 Das Null-Eins-Prinzip 712
27.3 Ein bitonisches Sortiernetzwerk 715
27.4 Ein Mischnetzwerk 719
27.5 Ein Sortiernetzwerk 721
28 Matrixoperationen 727
28.1 Eigenschaften von Matrizen 727
28.2 StrassensAlgorithmus zur Matrixmultiplikation 737
28.3 Lösung linearer Gleichungssysteme 744
28.4 Matrixinversion 757
28.5 Symmetrische, positiv determinierte Matrizen, Methode der kleinsten Quadrate 762
29 Lineare Programmierung 773
29.1 Standard- und Schlupfformen 780
29.2 Die Darstellung von Problemen durch lineare Programme 788
29.3 Der Simplexalgorithmus 793
29.4 Dualität 808
29.5 Die initiale zulässige Basislösung 814
30 Polynome und die FFT 825
30.1 Darstellung von Polynomen 827
30.2 DFT und FFT 833
30.3 E ziente Implementierung der FFT 841
31 Zahlentheoretische Algorithmen 851
31.1 Elementare zahlentheoretische Begriffe 852
31.2 Größter gemeinsamer Teiler 858
31.3 Modulare Arithmetik 864
31.4 Lösen modularer linearer Gleichungen 871
31.5 Der chinesische Restsatz 875
31.6 Potenzen eines Elements 878
31.7 Das RSA-Verschlüsselungssystem 883
31.8 * Primzahltests 890
31.9 * Primfaktorzerlegung 899
32 String-Matching 909
32.1 Der naive String-Matching-Algorithmus 911
32.2 Der Rabin-Karp-Algorithmus 913
32.3 String-Matching mit endlichen Automaten 919
32.4 * DerKnuth-Morris-Pratt-Algorithmus 925
33 Algorithmische Geometrie 935
33.1 Eigenschaften von Strecken 936
33.2 Schnittpunkt eines beliebigen Streckenpaares 942
33.3 Bestimmen der konvexen Hülle 949
33.4 Berechnung des dichtesten Punktepaares 959
34 NP-Vollständigkeit969
34.1 Polynomiale Zeit 974
34.2 Verifikation in polynomialer Zeit 982
34.3 NP-Vollständigkeit und Reduktion 986
34.4 NP-Vollständigkeitsbeweise 998
34.5 NP-vollständige Probleme 1005
35 Approximationsalgorithmen 1025
35.1 Das Knotenüberdeckungsproblem 1027
35.2 Das Problem des Handelsreisenden 1030
35.3 Das Mengenüberdeckungsproblem 1036
35.4 Randomisierung und lineare Programmierung 1041
35.5 Das Teilsummenproblem 1046
VIII Anhang: 1057
A Summen 1061
A.1 Summenformeln und Eigenschaften 1061
A.2 Abschätzungen für Summen 1065
B Mengen usw. 1073
B.1 Mengen 1073
B.2 Relationen 1078
B.3 Funktionen 1080
B.4 Graphen 1082
B.5 Bäume 1087
Literaturverzeichnis 1131
Index 1151