|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Di 08:30 - 10:00, Hörsaal 1221
Fr 08:30 - 10:00, Hörsaal 0220
Beginn: 5. November
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mi 12:00 - 14:00, Raum S2229
Ü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
|
|
|
Empfehlenswert für:
Grundlagen 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.
Der zweite Teil der Vorlesung findet im kommenden Sommersemester statt.
|
|
|
Themenübersicht:
- Grundlagen
- Notationen, Landau-Symbole
- Felder und Matrizen
- Sortieren auf linearem Feld
- Wortorientierter Algorithmus
- Bitorientierter Algorithmus
- Untere Schranken
- Gegenbeispiel - Abzählen
- Eigenschaften des Netzwerk-Modells
- Ganzzahlige Arithmetik
- Carry-Lookahead-Adder
- Präfix-Berechnungen
- Segmentiertes Präfix
- Carry-Save-Adder
- Parallele Multiplikation zweier Zahlen, Konvolution
- Matrix-Algorithmen
- Matrix-Vektor-, Matrix-Matrix-Produkt
- Algorithmen für Dreiecksmatrizen
- Gauß-Elimination, mit Anwendungen: Matrix-Invertierung,
Rangbestimmung, Determinante
- Graph-Algorithmen
- Transitive Hülle
- Zusammenhangskomponenten
- Kürzeste Pfade
- BFS-Spannbäume
- Minimale Spannbäume, auf Gitter
- Mehr über Sortieren auf dem Gitter
- Odd-even transposition sort
- Ein $\sqrt{n}(1+\log n)$ Sortieralgorithmus
- Ein $3\sqrt{n} + o(\sqrt{n})$ Sortieralgorithmus
- Packet Routing
- Greedy Algorithmen, Analyse des einfachen
2D greedy Algorithmus
- Greedy Algorithmen im Durchschnitt
(n Pakete mit zufälligen Zieladressen)
Eine Chernoff-Schranke
- Randomisierte Routing-Algorithmen
- Deterministische Routing-Algorithmen mit
kleinen Warteschlangen
- Ein Off-line Algorithmus, der Heiratssatz
- Andere Rounting-Modelle und Algorithmen
- Bild-Analyse und geometrische Algorithmen
- Komponentenbestimmung
- Die Hough-Transformation
- Nächste Nachbarn
- Konvexe Hülle
- Ausblick auf andere Architekturen:
höherdimensionale Felder, Tori, Hex-Gitter, MOT
- Hyperwürfel und hyperwürfelartige Netzwerke
- Der n-dimensionale (binäre) Hyperwürfel
- Definitionen und Eigenschaften
- Einbettung von Feldern in den Hyperwürfel
M(3,5) nicht Teilgraph von H(4)
- Einbettung vollständiger Binärbäume
- Paritätsargument
- DRCBT(r) ist Teilgraph des H(r)
- Binomialbaum-Einbettung, normale
Hyperwürfelalgorithmen
- Dynamische Einbettung des DRCBT
- Einbettung beliebiger Binärbäume
- Der Flip-Bit-Algorithmus, Analyse
- Eine untere Schranke für Algorithmen ohne Migration
- Ein optimaler deterministischer Algorithmus
für beliebige Binärbäume
- Optimale Dynamisierung
- Butterfly, CCC, Benes-Netzwerk
- Das Butterfly-Netzwerk
- Das Cube-Connected-Cycles-Netzwerk
- Das Benes-Netzwerk (auch geschlossen)
|
|
|
Weiterführende bzw. vertiefende Vorlesungen:
Parallele Algorithmen II
Parallele und verteilte Programmierung
Effiziente Algorithmen und
Datenstrukturen
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
|
