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

Kursbeginn: 10:15, 19.4.2023 (Mittwoch) T9/Gr. Hörsaal

Klausur: 10:00, 17.7.2023 (Montag) Henry-Ford-Bau

Nachklausur: 10:00, 13.10.2023 (Freitag) T9/Gr. Hörsaal