zum Inhalt springen

Vorlesung und Übungen "Theoretische Informatik"

Dozent: Prof. Dr. Michael Jünger

Mo 12-13:30 Uhr im HS 301 Pohligstr. 1
Mi 12-13:30 Uhr im HS 301 Pohligstr. 1

Beginn: 04.04.2011

 

Inhalte

Folgende Themen werden in der Vorlesung behandelt: Formale Sprachen, Chomsky-Hierarchie, reguläre Sprachen, kontextfreie Sprachen und Kellerautomaten, Normalformen, deterministische, kontextfreie Sprachen, Top Down-Parsing, Einführung in die Berechenbarkeit, Turing-Maschinen, Typ-0- und Typ-1-Sprachen, Unentscheidbare Probleme, Einführung in die Komplexitätstheorie, NP-Vollständigkeit und der Satz von Cook, Klassifikation von Problemen nach Speicherbedarf, Online Algorithmen, Probabilistische Algorithmen.

Übungen zur Theoretischen Informatik (gemeinsam mit Dipl.-Inf. Daniel Schmidt)

In den Übungen wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben werden unter Anleitung eines Tutors besprochen. Die Übungen finden wöchentlich statt.