Die Vorlesung wird in Form von Videos zu Verfügung gestellt, die mit Inhaltsbeschreibung im Lehrplan stehen. Außerdem gibt es eine erweiterte Inhaltsübersicht mit Inhaltsverzeichnissen zu den meisten Videos. Zu den Vorlesungsterminen (Mo und Mi 10:15-11:00) gibt es die Möglichkeit, Fragen zu stellen. Diese Termine finden per Webex statt. https://fu-berlin.webex.com/fu-berlin/j.php?MTID=m324e73321f67ce5d19c659b1c94edcb0. Das Passwort lautet Turingmaschine, Zugangscode 121 132 9883.

Inhalt:

• Theoretische Rechnermodelle
  • Automaten
  • formale Sprachen
  • Grammatiken und die Chomsky-Hierarchie
  • Turing-Maschinen
  • Berechenbarkeit
• Einführung in die Komplexität von Problemen

Literatur

• Uwe Schöning, Theoretische Informatik kurzgefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexität, Pearson Studium, 3. Auflage, 2011
• Ingo Wegener: Theoretische Informatik - Eine algorithmenorientierte Einführung, 2. Auflage, Teubner, 1999
• Michael Sipser, Introduction to the Theory of Computation, 2nd ed., Thomson Course Technology, 2006
• Wegener, Kompendium theoretische Informatik - Eine Ideensammlung, Teubner 1996