Die Studierenden sollen einen der Grundpfeiler der Informatik als Wissenschaft, nämlich die theoretische Modellierung von Berechenbarkeit durch verschiedene Algorithmenmodelle, verstehen lernen. Dies umfasst das Verstehen und Anwenden von Formalisierungen, das Umsetzen sowie sichere Umgehen mit mathematischen Arbeitsweisen in der theoretischen Informatik, und das Erkennen der Stärken und der Begrenzungen der wichtigsten Maschinenmodelle. Folgende Themen werden in der Vorlesung behandelt:

• Reguläre Sprachen; deterministische und nicht-deterministische endliche Automaten; Minimalisierung; Abschlusseigenschaften regulärer Sprachen;
• Push-Down Automaten und kontextfreie Grammatiken; Normalformen; algorithmische Fragestellungen zu kontextfreien Sprachen; Abschlusseigenschaften;
• Turing-Maschine; Berechenbarkeit von Wortfunktionen; Entscheidungsprobleme; rekursive Aufzählbarkeit und Entscheidbarkeit; Halteproblem für Turing-Maschinen; Satz von Rice; Reduktion; allgemeine Grammatiken;
• linear-beschränkte Turing-Maschinen; Chomsky-Hierarchie;
• Simulation von Automaten durch Grammatiken und umgekehrt;
• Primitiv-rekursive und μ–rekursive Funktionen

• Informatik B.Sc. und Diplom Pflichtfach im Grundstudium
• IMT M.Sc. PO 2008 Wahlpflichtfach
  Komplex Methodische Grundlagen
• Mathematik B.Sc. und Diplom
• Modul: 11787, 8 LP, 4 SWS VL, 2 SWS UE, 2 SWS Tutorium

• Vorleistung
  Erfolgreiche Bearbeitung von Hausaufgaben und/oder erfolgreiche Bearbeitung von Hörsaaltestaten jeweils während eines Vorlesungstermins
  (Die Art der Voraussetzung wird zu Semesterbeginn bekannt gegeben.) Eine erbrachte Vorleistung zählt für das Semester, in dem sie erbracht wurde, und das anschließende Sommersemester. Wird die Veranstaltung danach wieder in einem Wintersemetser angeboten, ist die Vorleistung erneut zu erbringen.
• Abschlussklausur:  
  Im zweiten Prüfungszeitraum.
  Es wird einen Termin zur Einsicht in die Klausur geben.
• Benotung des Moduls:
  Die Note ergibt sich aus der Abschlussklausur.
• Wiederholungsklausur
  Im zweiten Prüfungszeitraum des Sommersemesters.
  Bearbeitungszeit: 120 Minuten
  Der Stoff des gesamten Moduls ist Prüfungsstoff. An der Wiederholungsklausur kann nur teilgenommen werden, wenn schon ein Fehlversuch vorliegt. Es müssen genügend Übungsaufgaben erfolgreich bearbeitet worden sein.

• Alexander Asteroth, Christel Baier: Theoretische Informatik: eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen, Pearson Studium 2002.
• Katrin Erk, Lutz Priese: Theoretische Informatik - Eine umfassende Einführung, eXamen.press, 2008. [auf dem Campus online lesbar]
• Dirk W. Hoffmann: Theoretische Informatik, Hanser, 2009.
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, 3., aktualisierte Auflage, Pearson Studium 2011.
• Juraj Hromkovic Theoretische Informatik Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie, Teubner, 2007. [auf dem Campus online lesbar]
• Dexter C. Kozen: Automata and Computability, Springer 1997.
• Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1981.
• John E. Savage: Models of computation: Exploring the Power of Computing, Addison-Wesley, 1998. [elektronisch verfügbar auf der Webseite von Prof. John Savage, Computer Science Department, Brown University]
• Michael Sipser: Introduction to the Theory of Computation, 3rd Edition, Cengage Learning 2013.