• Registermaschinen und Turingmaschinen als Modelle des Berechenbaren, die Churchsche These und unentscheidbare Probleme

• NP-Vollständigkeit und das P-NP-Problem

• Endliche Automaten

• Grammatiken und die Chomsky-Hierarchie

• Kontextfreie Grammatiken und Kontextfreie Sprachen

• Kellerautomaten

Lernziele und Kompetenzen:

Die Studierenden

• erwerben fundierte Kenntnisse über die Grenzen der Berechenbaren, insbesondere lernen sie, wie man beweist, dass bestimmte Aufgaben unlösbar sind bzw. dass sie vermutlich nicht schnell gelöst werden können;

• lernen die wesentlichen Techniken kennen, mit denen man Programmiersprachen beschreiben und syntaktisch korrekte Programme erkennen kann;

• erwerben fundierte Kenntnisse in den Beweis- und Analyse-Methoden der algorithmisch orientierten Theoretischen Informatik