Dr. R. Winter

Seminar

Parallele Komplexitätsklassen

Hauptstudium Informatik

Alternierende Turingmaschinen
Simulation von deterministischen und nichtdeterministischen Turingmaschinen durch alternierende
Hierarchien von Komplexitätsklassen
Parallele Berechnungen in polylogarithmischer Zeit. Verwendung des Schaltkreismodells
Klassen NC und AC
Das RAM-Modell und parallele RAM's
Vergleich von Turingmaschine, PRAM und Schaltkreis
Vergleich verschiedener PRAM-Versionen
Zeitbeschränkte PRAM's
Block-RAM's

Literatur: