Proseminar Parallele Algorithmen, SS 99

Vortragsthemen

A. Einführung

Dieser Vortrag erklärt zuerst den Begriff der Parallelverarbeitung und bespricht Gründe, warum wir uns mit parallelen Algorithmen beschäftigen sollten. Danach werden verschiedene Varianten des Berechnungsmodells der parallelen Random-Access-Maschine (PRAM) eingeführt, einige wichtige Eigenschaften von PRAMs werden besprochen, und ein Algorithmus für das fundamentale Präfixsummenproblem wird vorgestellt.

B. List ranking

Dieser Vortrag soll zwei fundamentale Techniken beschreiben, Pfadverdoppelung und Symmetrieauflösung, und Algorithmen für die Rangbestimmung in Listen vorstellen, die auf diesen Techniken basieren. Primärliteratur: JáJá, Abschnitte 2.2, 2.7 und 3.1. Das Ergebnis aus Abschnitt 3.1.2 soll erwähnt werden, aber Beschreibung und Analyse des dort vorgestellten Algorithmus wird nicht erwartet.

C. Die Euler-Tour-Technik und Auswertung von Ausdrücken

Dieser Vortrag soll die für die parallele Behandlung von Bäumen unentbehrliche Euler-Tour-Technik vorstellen. Danach soll ein Algorithmus für die Auswertung von arithmetischen Ausdrücken beschrieben und analysiert werden, der als wichtige Komponenten die Euler-Tour-Technik und die im vorigen Vortrag beschriebene Rangbestimmung in Listen benutzt. Primärliteratur: JáJá, Abschnitte 3.2 und 3.3.

D. Obere und untere Schranken für Suchen und Bestimmung des Maximums

In diesem Vortrag sollen zunächst ein Algorithmus für die Suche in einer sortierten Folge und ein schneller Algorithmus für die Bestimmung des Maximums einer Menge beschrieben werden. Danach soll gezeigt werden, daß diese Algorithmen unter gewissen Annahmen optimal sind. Primärliteratur: JáJá, Abschnitte 2.6, 4.1 und 4.6 bis einschließlich 4.6.3.

E. Tiefste gemeinsame Vorfahren und Teilfolgenminima

Dieser Vortrag soll das Problem der Berechnung tiefster gemeinsamer Vorfahren in einem Baum einführen und es auf das Problem zurückführen, Anfragen nach Minima in Teilfolgen zu beantworten. Danach soll ein Algorithmus für das letztere Problem mit logarithmischer Laufzeit beschrieben werden. Erwartet wird außerdem zumindest eine Skizze eines schnelleren Algorithmus. Primärliteratur: JáJá, Abschnitt 3.4.

F. Mischen und Sortieren

Dieser Vortrag soll Algorithmen für die beiden Probleme Mischen von sortierten Folgen sowie Sortieren beschreiben. Primärliteratur: JáJá, Abschnitte 2.4, 4.2 ohne 4.2.4 sowie 4.3. Das Ergebnis aus Abschnitt 4.3.2 soll erwähnt werden, aber Beschreibung und Analyse des dort vorgestellten Algorithmus wird nicht erwartet.

Dieses Thema kann wahlweise von zwei Personen bearbeitet werden (Doppelvortrag). Dann soll zusätzlich der Inhalt des folgenden Artikels vorgestellt werden: T. Hagerup and C. Rüb, Optimal merging and sorting on the EREW PRAM, Information Processing Letters 33 (1989), pp. 181-185.

G. Eine untere Schranke für die Berechnung des Oders

Dieser Vortrag soll zeigen, daß eine PRAM, die kein gleichzeitiges Schreiben erlaubt, Omega(log n) Zeit braucht, um das Oder von n Bits zu berechnen. Primärliteratur: JáJá, Abschnitt 10.2.

H. Zusammenhangskomponenten

Dieser Vortrag soll Algorithmen für die Berechnung der Zusammenhangskomponenten von ungerichteten Graphen vorstellen. Primärliteratur: JáJá, Abschnitt 5.1.

I. Zweifache Zusammenhangskomponenten

Dieser Vortrag soll Algorithmen für die Berechnung der zweifachen Zusammenhangskomponenten (Blöcke) von ungerichtete Graphen vorstellen. Primärliteratur: JáJá, Abschnitt 5.3.

J. Konvexe Hülle und Schnitt von Halbräumen

Der Vortrag soll Algorithmen für das geometrische Problem der Berechnung der konvexen Hülle einer Punktmenge in der Ebene beschreiben. Danach soll gezeigt werden, wie die Bestimmung des Schnittes von Halbräumen in der Ebene auf dieses Problem zurückgeführt werden kann. Primärliteratur: JáJá, Abschnitte 2.3 und 6 bis einschließlich 6.2.2.

K. Simulation zwischen PRAMs

Dieser Vortrag soll Simulationen der mächtigeren Varianten der PRAM auf schwächeren Varianten untersuchen. Um wieviel unterscheiden sich die Varianten? Primärliteratur: JáJá, Abschnitt 10.1.

L. P-Vollständigkeit

Dieser Vortrag soll den Begriff der P-Vollständigkeit erläutern und zeigen, daß das Problem, einen Schaltkreis auszuwerten, P-vollständig ist. P-vollständige Probleme sind sequentiell nicht weiter schwierig, aber alles deutet darauf hin, daß sie von keinen effizienten parallelen Algorithmen gelöst werden. Primärliteratur: JáJá, Abschnitt 10.5. Abschnitt 10.5.6 darf sehr oberflächlich und ohne Beweise behandelt werden. Dieses Thema sollte von einem Teilnehmer bearbeitet werden, der schon die Vorlesung Theoretische Informatik 2 gehört hat.