Wintersemester 98/99

Dr. R. Winter


Vorlesung (3 + 1)

Parallele Modelle und Algorithmen

Hauptstudium Informatik

Inhalt:

Für jeden Typ von Parallelrechner gibt es Aufgabenklassen, die damit besonders gut bewältigt werden können, andere dagegen nicht. Nach dem Vergleich verschiedener theoretischer Modelle für Parallelrechner soll die Komplexität algorithmischer Prozesse bei hoher Parallelisierung untersucht werden. Wir betrachten nicht nur den Fall beschränkter Parallelität (feste Anzahl Prozessoren), sondern auch Maschinen mit unbeschränkter Parallelität.
Mit der Gegenüberstellung von vernünftigen sequentiellen und vernünftigen parallelen Modellen (1. und 2. Maschinenklasse) werden wir den Zusammenhang zwischen sequentiellem Speicherplatz- und parallelem Rechenzeitbedarf untersuchen.
Probleme, für die man effiziente sequentielle Lösungsverfahren kennt, sollen bzgl. ihrer parallelen Komplexität klassifiziert werden (parallele Berechnungen in polylogarithmischer Zeit).

Literatur:

Bemerkungen





0.	Einfhrung




1.	Turingmaschinen


1.1.	Mehrkopf-Turingmaschinen ohne separates Eingabeband
1.2.	Zeit- und Bandkomplexität bei O-Turingmaschinen
1.3.	Mehrkopf-Turingmaschinen mit separatem Eingabeband
1.4.	Komplexität bei E-Turingmaschinen
1.5.	Vergleich von Turingmaschinen hinsichtlich ihrer Komplexität und Parallelarbeit


2.	Zellularräme


2.1.	Arbeitsweise von Zellularrämen
2.2.	Spracherkennung mit Zellularrämen und ihre Komplexität
2.3.	Zusammenhang zwischen Zellularrämen und Turingmaschinen
2.4.	Das Firing Squad Synchronization Problem
2.5.	Mustererkennung und Mustermanipulation in 2-dimensionalen Zellularrämen
2.6.	Erkennung formaler Sprachen mit 2-dimensionalen Zellularrämen


3.	Systeme von Turing-Automaten


3.1.	Aufbau und Arbeitsweise
3.2.	Erkennung formaler Sprachen und ihre Komplexität
3.3.	Vergleich von Systemen von Turing-Automaten mit Turingmaschinen
3.4.	Vergleich von Systemen von Turing-Automaten mit Zellularautomaten
3.5.	Das Synchronisationsproblem fr Systeme von Turing-Automaten


4.	Parallele Registermaschinen


4.1.	Sequentielle Registermaschinen
4.2.	Parallele CREW-Registermaschinen
4.3.	SIMD- und MIMD-Rechner
4.4.	Konflikte beim Speicherzugriff - verschiedene PRAM-Versionen
4.5.	Spracherkennung durch PRAM
4.6.	Vergleich von PRAM mit sequentiellen TM (parallele Zeit = sequentieller Raum)
4.7.	Vergleich verschiedener PRAM-Versionen hinsichtlich ihrer Komplexität (weggelassen)


5.	Schaltkreisfamilien


5.1.	Definitionen zu Schaltkreisen und Schaltkreisfamilien (mit Beispiel)
5.2.	Komplexitätsmaße bei Schaltkreisen und Schaltkreisfamilien
5.3.	Uniforme Schaltkreisfamilien
5.4.	Vergleich von uniformen Schaltkreisfamilien und Turingmaschinen


6.	Systolische Trellisautomaten


6.1.	Definition und Arbeitsweise
6.2.	Arten von Trellisautomaten und Vergleich
6.3.	Trellisautomaten und Zellularautomaten
6.4.	Pipelineverarbeitung bei Trellisautomaten


7.	Alternierende Turingmaschinen


7.1.	Begriff der alternierenden Turingmaschine und Komplexitätsmaße
7.2.	Bandkompression und Beschleunigung auf alternierenden Turingmaschinen
7.3.	Bandreduktion bei ATM
7.4.	Komplexität bei DTM, NDTM und ATM
7.5.	Sequentielle und parallele Komplexitätsklassen mit Hierarchiebetrachtungen
7.6.	Polynomiale Zeithierarchie


8.	Maschinenklassen und parallele Berechnungshypothesen


8.1.	Maschinenklassen
8.2.	Verhältnis zwischen erster und zweiter Maschinenklasse
8.3.	Parallele Berechnungshypothesen


9.	Parallele Berechnungen in polylogarithmischer Zeit


9.1.	Die Klasse NC
9.2.	Die Klasse AC
9.3.	RNC-Algorithmen


10.	Komplexität von Spielen

Literatur

R. Winter