Wintersemester 96/97

Dr. R. Winter


Vorlesung

Parallele Modelle und Algorithmen

Hauptstudium Informatik





0.	Einführung




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äume


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


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 für 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