Veranstaltungsart und -inhalt

• Formalisierung von Problemen mittels Sprachen
• Formale Grammatiken
• reguläre Sprachen, endliche Automaten
• kontextfreie Sprachen, Kellerautomaten
• sequentielle Berechnungsmodelle: Turing-Maschinen, Registermaschinen
• sequentielle Komplexitätsklassen
• Simulation, Reduktion, Vollständigkeit
• (Un-)Entscheidbarkeit und Aufzählbarkeit
• Halteproblem und Church-Turing These

• theoretische Grundlagen der Syntax und der operationalen Semantik von Programmiersprachen kennen
• Möglichkeiten und Grenzen der Informatik verstehen
• algorithmische Probleme modellieren und mit geeigneten Werkzeugen lösen können
• algorithmische Probleme nach ihrer Komplexität klassifizieren können

• Übungs- und Programmieraufgaben, Protokoll, aktive Übungsgruppenteilnahme

• Klausur

• Logik für Informatiker
• Algorithmen und Datenstrukturen

• J. Hopcroft, J. Ullman, R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison Wesley 2001
• R. Reischuk, Komplexitätstheorie, Band I, Teubner 1998
• Savage: Models of Computation, Addison Wesley 1998
• Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit, Teubner 1992
• C. Papadimitriou: Computational Complexity, Addison Wesley 1994
• E. Rich, Automata, Computability, and Complexity, Pearson 2008

Vorlesung

Übung