|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Di 08:30 - 10:00, Hörsaal 2770
Fr 08:30 - 10:00, Hörsaal 1100
Beginn: 2. Mai
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 10:15 - 12:15, Raum S2225
Übungsleitung:
Tom Friedetzky
Übungsschein: Einen Schein erhält, wer
wenigstens 40% der Punkte zu den Hausaufgaben erreicht und
erfolgreich an der Semestralklausur teilnimmt.
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Stoff des Informatik-Grundstudiums
Vorlesung Parallele Algorithmen
empfehlenswert
|
|
|
Empfehlenswert für:
Grundlegend im Bereich Algorithmen
|
|
|
Inhalt:
Der Zweck dieser Vorlesung ist das Studium fundamentaler Konzepte in der
Parallelrechnung. Es werden Maschinenmodelle, der Entwurf paralleler
Algorithmen und die Grundlagen paralleler Komplexitätstheorie
besprochen.
|
|
|
Themenübersicht:
- Hyperwürfel und hyperwürfelartige Netzwerke
- Shuffle-Exchange und de Bruijn-Netzwerke
- Definitionen und grundlegende Eigenschaften
- The Diaconis Card Tricks:
- Ein Misch-Trick
- Ein Gedankenlese-Trick
- Simulation normaler Hyperwürfel-Algorithmen
- Weitere Einbettungs- und Teilgraph-Resultate
- Die Diskrete Fourier-Transformation (FFT)
- Die algorithmischen Grundlagen
- Implementation auf dem Butterfly- und SE-Netzwerk
- Anwendungen: Konvolution, Polynomarithmetik
- Bitkomplexität der DFT
- Algorithmen für Packet-Routing
- Definitionen, Modelle
- Greedy-Algorithmen, worst-case Instanzen
- Eine untere Schranke für oblivious Routing
- Konzentrations- und Monotones Routing:
- Konzentrationsrouting auf dem Hyperwürfel
- Konzentrationsrouting auf dem Butterfly
- Inverses Konzentrationsrouting
- Monotones Routing
- Verallgemeinertes monotones Routing
- Randomisiertes Routing auf dem Butterfly
- Analyse der Knotenbelastung
- Analyse des Zeitbedarfs
- Andere Contention-Resolution-Protokolle
- Übertragung auf den Hyperwürfel
- Umwandlung von Worst-case Instanzen in Average-Case Instanzen
- Hashing, $r$-fach unabhängige Hashfunktionen
- Randomisiertes Routing
- Ergänzungen: Ranade's Algorithmus, Combining, Mehrfachkopien
- Sortieren
- Odd-Even-Merge-Sort
- Sortieren kleiner Datenmengen
- Das PRAM-Modell
- Grundlegende Diskussion
- Die Varianten des PRAM-Modells
- Grundlegende Algorithmen
- Censusfunktionen und Präfixberechnung
- Beschleunigte Kaskadierung
- Maximum in konstanter Zeit
- Algorithmus mit doppelt-logarithmischem Zeitbedarf
- Beschleunigte Kaskadierung
- Partitionierung
- Einfacher Merging-Algorithmus
- Optimaler EREW-Merging-Algorithmus
- Symmetrieauflösung
- Die grundlegende Routine
- Ein schneller 3-Färbungsalgorithmus
- Optimaler 3-Färbungsalgorithmus
- Listen und Bäume
- List Ranking
- Ein einfacher LR-Algorithmus
- Ein arbeits- und zeitoptimaler LR-Algorithmus, mit Analyse
- Euler-Tour
- Definition, einfacher Algorithmus
- Berechnung von Baumfunktionen:
- Wurzeln eines Baums
- Postorder-Numerierung
- Knotentiefe
- Baumkontraktion
- Die Rake-Operation
- Auswertung arithmetischer Baumausdrücke
- Lowest Common Ancestors
- Definition
- Der Schieber/Vishkin-Algorithmus
- Sortieralgorithmen
- Definitionen
- Merging-basierte Algorithmen
- Cole's Merge-Sort
- Untere Schranken für die PRAM
- Grundlagen
- Die allgemeine Methode
- Schranken für spezifische Probleme
- P-Vollständigkeit
- Konzepte der Parallelisierbarkeit
- CVP ist P-vollständig
- Anwendungen auf DFS, LP
|
|
|
Weiterführende bzw. vertiefende Vorlesungen:
Effiziente Algorithmen und
Datenstrukturen II
|
|
|
Skript:
kein Skript
|
|
|
Literatur:
- F. Thomson Leighton:
- Introduction to Parallel Algorithms and Architectures:
Arrays - Trees - Hypercubes
Morgan Kaufman Publishers, San Mateo, CA, 1992
- Joseph JáJá:
- Parallel Algorithms
Addison Wesley Publishing Company, 1992
|
|
|
Sprechstunde:
siehe hier
|
