HEINZ NIXDORF INSTITUT
Universität-GH Paderborn
Theoretische Informatik
AG Meyer auf der Heide

Komplexitätstheorie für paralleles Rechnen

Vorlesung, SS 96

Miroslaw Kutylowski

Prüfungsgebiet:

Komplexitätstheorie (2 Stunden), im Gebiet Theoretische Informatik ,
im Vertiefungsgebiet sind 2 Stunden prüfbar, die Vorlesung ist für Vertiefungsgebiet Parallelels Rechnen besonders geeignet.

Termine

Vorlesung (V2)

 
Mi  11:00 - 13:00     F2.211 (Fürstenallee)              M. Kutylowski

Übung

keine

Die erste Vorlesung findet am 24.04.96 statt.

Wo erreichen Sie mich:

Miroslaw Kutylowski: Raum F1.219, Tel. 6461, login mirekk,
Sprechstunde: Dienstag, 9:00-11:00,

Inhalt der Vorlesung

alternierende Turing Maschinen
P-Vollständigkeit und unparallelisierbare Probleme
NC- und AC-Klassen
Komplexität für shared memory-Maschinen

Literatur

R.Reischuk, Einführung in die Komplexitätstheorie, Teubner Verlag, ISBN 3-519-02275-3 (nur ausgewählte Kapitel)
J.Reif (Ed.), Synthesis of parallel algorithms, Morgan Kaufmann, ISBN 1-55860-135-X (nur ausgewählte Kapitel)
A.Gibbons, P.Spirakis (Eds.), Lectures on parallel computation, Cambridge University Press, ISBN 0-521-41556-X (nur ausgewählte Kapitel)

WWW-Seiten

Zu der Veranstaltung existiert eine WWW Seite.

Außerdem wird es (hoffentlich) eine elektronische Mitschrift geben. Sie wird nach jeder Vorlesung erstellt. Ihre Mitarbeit ist dabei notwendig.

Scheinerwerb

nicht möglich

Grundkentnisse

Der Kurs setzt grundlegende Kentnisse in der Theoretischen Informatik. Die Kentnisse aus Grundstudium-Vorlesung Theoretische Informatik reichen. Keine besondere Kentnisse über parallele Alogithmen werden vorausgesetzt.