Wintersemester 93/94

Dr. R. Winter

Seminar

Theoretische Informatik

Hauptstudium Informatik

Inhalt des Seminars:

Das Seminar schließt sich an die Vorlesung Theoretische Informatik I vom Sommersemester 1993 an.
Literatur:

WEGENER: Theoretische Informatik. Teubner Stuttgart 1993
BÖRGER: Berechenbarkeit, Komplexität, Logik. Vieweg 1992
Spezielle Artikel

Gehaltene Vorträge:

Modifizierte Turingmaschinentypen
Post- und Markow-Algorithmen
Partiell-rekursive Funktionen
Hauptsatz der Algorithmentheorie
Chomsky-Hierarchie formaler Sprachen
Kontextsensitive Sprachen und LBA-Probleme
Inhärent mehrdeutige kontextfreie Sprachen
Nachweis der Nichtentscheidbarkeit der Menge PAL auf einem determinischen PDA
Unentscheidbare Probleme
Effizient lösbare Probleme

R. Winter