Th. Ottmann (Hrsg.):
Prinzipien des Algorithmenentwurfs

Inhaltsverzeichnis

1
Das Divide-and-Conquer-Prinzip
Thomas Ottmann, Universität Freiburg
1
  1. Drei Beispiele: Turnierplan, Aktienkurse, ToH
    1. Erstes Beispiel: Turnierplan
    2. Zweites Beispiel: Aktienkurse
    3. Drittes Beispiel: Towers of Hanoi (ToH)
  2. Formulierung und Bewertung des Divide-and-Conquer-Prinzips
  3. Suchen und Sortieren: Quicksort, Selection
    1. Strategien für die Pivotwahl
  4. Geometrisches Divide-and-Conquer
    1. Das Liniensegment-Schnittproblem
    2. Voronoi-Diagramm
  5. Mathematische Probleme
    1. Matrizenmultiplikation
    2. Polynomprodukt und FFT
  6. Literaturverzeichnis
1
1
3
4
5
7
10
11
14
16
17
17
19
24
2
Das Backtrack-Prinzip
Thomas Ottmann, Universität Freiburg
25
  1. Ein konkretes Beispiel: Das Vier-Damen-Problem
  2. Formulierung der Lösung als rekursive Prozedur
  3. Formale Fassung des Prinzips als Programmrahmen
  4. Anwendungen auf weitere Probleme
  5. Erweiterungen
  6. Literaturverzeichnis
25
26
28
30
33
35
3
Dynamisches Programmieren
Anne Brüggemann-Klein, TU München
37
  1. Die Technik des dynamischen Programmierens
  2. Fibonacci-Zahlen
  3. Parsen kontextfreier Grammatiken
  4. Editierdistanz
  5. Vergleich mit Divide and Conquer
  6. Geschichtliches
  7. Literaturverzeichnis
37
37
39
42
46
46
47
4
Randomisierte Algorithmen
Thomas Roos, ETH Zürich
49
  1. Randomisierung
    1. Einführung
    2. Klassen und Analyse
    3. Grundlagen der Wahrscheinlichkeitstheorie
  2. Randomisierter Binärbaum
    1. Problemstellung und Algorithmus
    2. Analyse der Laufzeit
    3. Analyse der Baumhöhe
    4. Hochwahrscheinlichkeitsanalyse
  3. Randomisierter Primzahltest
    1. Einführung
    2. Analyse
    3. Algorithmus von Miller-Rabin
    4. Fehleranalyse
  4. Résumé
    1. Konstruktionsparadigmen
    2. Vergleich
  5. Literaturverzeichnis
49
49
50
51
54
54
55
57
59
60
60
61
62
64
65
65
66
66
5
Das Sweep-Verfahren
Rolf Klein, Fern-Universität Hagen
67

  1. Einführung
  2. Sweep im Eindimensionalen
    1. Das Maximum einer Menge von Objekten
    2. Das dichteste Paar einer Menge von Zahlen
    3. Die maximale Teilsumme
  3. Sweep in der Ebene
    1. Das dichteste Punktepaar in der Ebene
    2. Schnittpunkte von Liniensegmenten
  4. Literaturverzeichnis
67
67
67
68
69
71
72
78
89
6
Amortisierte Analyse
Kurt Mehlhorn, MPI Saarbrücken
91
  1. Einleitung
  2. Der Binärzähler
  3. 2-5-Bäume
  4. Das Sortieren vorsortierter Folgen
  5. Amortisierte Kosten, eine abstrakte Betrachtung
  6. Geschichtlicher Rückblick
  7. Literaturverzeichnis
91
91
93
97
99
102
102
7
Parallele Präfix-Summation
Peter Widmayer, Roger Peter Wattenhofer, ETH Zürich
103
  1. Grundbegriffe des parallelen Rechnens
    1. Summe in einem Array
    2. Ein Modell einer parallelen Maschine
    3. Effizienz von PRAM-Algorithmen
    4. Ein Beispiel: Minimum in einem Array
    5. Weitere PRAM-Modelle
  2. Der Präfix-Summen-Algorithmus
    1. Ein Beispiel
    2. Der Algorithmus
    3. Brents Lemma
  3. Anwendungen der Präfix-Summen
    1. Komprimieren eines dünn besetzten Arrays
    2. Komprimieren einer verketteten Liste
    3. Simulation eines endlichen Automaten
    4. Addier-Schaltung
  4. Literaturverzeichnis
104
104
107
107
108
110
111
111
112
114
116
116
117
118
119
121
8
Online-Algorithmen
Sven Schuierer, Universität Freiburg
123
  1. Einleitung
  2. Definitionen
    1. Zwei Beispiele
  3. Seitenaustauschstrategien
    1. Least-Recently-Used
    2. Der optimale Offline-Algorithmus MIN
    3. Eine untere Schranke
  4. Randomisierte Online-Algorithmen
    1. Der Algorithmus Marking
    2. Die Kosten von Marking
    3. Die Kosten von MIN
  5. Andere Bereiche für Online-Algorithmen
  6. Literaturverzeichnis
123
124
124
126
128
132
134
135
136
137
141
143
144
9
Heuristische Suche
Thomas Ottmann, Jürgen Eckerle, Universität Freiburg
145
  1. Zustandsraum
  2. Suche in explizit und implizit gegebenen Graphen
  3. Implizite Graphsuche
    1. Breiten- und Tiefensuche
  4. Bestensuche
  5. Bestensuche mit Duplikatselimination
  6. Heuristiken
  7. Varianten der heuristischen Suche
    1. IDA*
    2. Speicherbeschränkte und bidirektionale Suche
  8. Literaturverzeichnis
145
150
152
155
157
161
165
170
170
171
171
10
Aufspannende Bäume minimalen Gewichts
Dorothea Wagner, Universität Konstanz
173
  1. Einführung
  2. Die Färbungsmethode von Tarjan
  3. Der Algorithmus von Kruskal
  4. Der Algorithmus von Prim
  5. Greedy-Verfahren und Matroide
173
174
179
180
181
182
11
Neuronale Netze
Alois Heinz, Universität Freiburg
185
  1. Einführung
  2. Anwendungen
    1. Funktionsapproximation
    2. Klassifikation
  3. Definitionen
    1. Neuronen-Verhalten
    2. Netzstrukturen
  4. Berechenbare Funktionen
  5. Komplexität der Berechnungen
  6. Lernen
    1. Lernverfahren im Überblick
    2. Perzeptron-Lernen
    3. Lernen durch Fehleroptimierung
    4. Ein direktes Lernverfahren
    5. Gradientenbestimmung
    6. Gradientenbasierte Lernverfahren
  7. Kommentierte Literaturhinweise
  8. Literaturverzeichnis
185
186
186
187
188
189
192
193
197
199
199
200
203
206
208
211
214
216
Über die Autoren 219
Index 223
Über die Multimedia-CDs 229

[Hauptseite] [Vorwort] [Über die Autoren] [Über die Multimedia-CDs]