Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Skript Effiziente Algorithmen und Datenstrukturen

Stand: 18. Dezember 1997

1.2 Analyse von Algorithmen ???

1.3 Elementare Datenstrukturen ???

1.4 Amortisierte Laufzeit ???

2. Höhere Datenstrukturen JensErnst

2.1 Suchbäume ''

2.1.1 Höhenbalancierte Bäume - (a,b)-Bäume ''

2.1.1 Selbstorganisierende binäre Suchbäume - Splay Trees Alexander Hall

2.2 Vorrangwarteschlangen - Priority Queues Gramsch

2.2.1 Fibonacci Heaps ''

2.2.2 Buckets Viktor Schuppan

2.2.3 Radix Heaps Thomas Schickinger

2.3 Mengen / Union-Find Strukturen Gerhard Müller

2.3.1 Grundversion ''

2.3.2 Path Compression ''

3. Grundlegende algorithmische Prinzipien Christian Kettner

3.1 Greedy Algorithmen ''

3.2 Divide and Conquer ''

3.3 Dynamische Programmierung ''

4. Sortieren und Selektieren Armin Amon

4.1 Sortieren ''

4.1.1 Radix Sorts ''

4.1.2 Quicksort Wolfgang Mayerle

4.1.3 Exkurs: Randomisierte Algorithmen Markus Neuhauser

4.2 Selektieren Volker Heun

4.2.1 Algorithmus von Blum-Floyd-Pratt-Rivest-Tarjan ''

4.2.2 Ein randomisierter Algorithmus Peter Trunk

4.2.3 Untere Schranke für das Median Problem ''

5. Elementare Graphenalgorithmen Stefan Pfingstl

5.1 Grundlagen ''

5.2 Das Kürzeste-Wege-Problem ''

5.2.1 Der Algorithmus von Dijkstra ''

5.2.2 Die Algorithmen von Floyd-Warshall und Bellman-Ford Franz Indra

5.2.3 Digraphen mit negativen Kantengewichten ''

5.3 Transitive Hülle Florian Lindauer

5.4 Minimal spannende Bäume Maximilian Fischer

6 Wie funktioniert ... ???

6.1 fgrep ???

6.2 compress Stephan Schierlinger