Links und Funktionen
Inhaltsbereich

Theoretische Informatik für Studierende der Medieninformatik (TIMI)

Vorlesung, 2(+1)-std., Blanchette; Übungen 1-std., Lempa, Maio

Inhalt

Die Vorlesung behandelt Grundlagen der theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie. Die Veranstaltung orientiert sich inhaltlich und strukturell am Lehrbuch von Schöning (Theoretische Informatik – kurz gefasst). Themen sind:

  • Automaten und Formale Sprachen:
    Deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Kellerautomaten

  • Berechenbarkeit:
    Turing-Maschinen, Churchsche These, Unentscheidbarkeit, Halteproblem, Reduktionen

  • Komplexität:
    Die Klassen P und NP, NP-vollständige Probleme, Polynomialzeit-Reduktionen

Neben der Vorlesung (2V) und den Übungen (1Ü) wird eine optionale Zentralübung (ca. alle 2 Wochen, 2-stündig) angeboten. Diese dient zum Wiederholen und zum Einüben des Stoffs, aber es wird kein neuer Stoff behandelt.

Organisation

Artikelaktionen

Funktionsleiste