Links und Funktionen
Inhaltsbereich

Formale Sprachen und Komplexität (FSK)

Vorlesung, 3(+1)-std., Blanchette; Übungen 2-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 (3V) und den Übungen (2Ü) 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