Proseminar Parallele Algorithmen, SS 99
Parallele Algorithmen

Veranstaltung: Proseminar, SS 99
Professur: Komplexität und Algorithmen
Dozent: Prof. Dr. Torben Hagerup
Zeit und Ort: Do 12-14 Uhr, SR 307
Vorbesprechung: 10. Februar 1999, 12.30 Uhr, SR 307
Studienabschnitt: Grundstudium
Scheinerwerb: Bei erfolgreichem Vortrag und aktiver Teilnahme
Voraussetzungen: Theoretische Informatik 1
Inhalt: Parallele Algorithmen sind solche, die von mehreren kooperierenden Prozessoren ausgeführt werden können. Parallele Algorithmen sind dann von Interesse, wenn eine herkömmliche, sequentielle Bearbeitung des vorliegenden Problems zu langsam wäre (Bsp.: In der Meteorologie. Es hat keinen Wert, die Wettervorhersage für morgen in 14 Tagen zu erhalten). Im Proseminar werden wir vornehmlich ausgewählte Kapitel aus dem Buch von JáJá lesen und uns der Parallelverarbeitung von der theoretischen Seite aus nähern. Wir werden fundamentale parallele Algorithmen sowie auch Grenzen der effizienten Parallelisierung behandeln.
Literatur: J. JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992.
Vortragsthemen A. Einführung
B. List ranking
C. Die Euler-Tour-Technik und Auswertung von Ausdrücken
D. Obere und untere Schranken für Suchen und Bestimmung des Maximums
E. Tiefste gemeinsame Vorfahren und Teilfolgenminima
F. Mischen und Sortieren
G. Eine untere Schranke für die Berechnung des Oders
H. Zusammenhangskomponenten
I. Zweifache Zusammenhangskomponenten
J. Konvexe Hülle und Schnitt von Halbräumen
K. Simulation zwischen PRAMs
L. P-Vollständigkeit