Vorlesung Grundlagen der Theoretischen Informatik (SS 2022)

 

Wichtige Informationen

Das Modul Grundlagen der Theoretischen Informatik ist Teil der alten Bachelor Informatik Prüfungsordnung 2021. Studierende die nach der neuen Bachelor Informatik Prüfungsordnung 2021 studieren und die Vorlesung Formale Sprachen und Automaten hören wollen, können an der Vorlesung Grundlagen der Theoretischen Informatik teilnehmen und diese bis zur Vorlesung 22 (d.h. die ersten 11 Wochen) teilnehmen.

Der Inhalt für die neue Vorlesung  Formale Sprachen und Automaten wird durch die Vorlesungsfolien 1-367 abgedeckt. Die Folien 290-302 zu deterministisch kontextfreien Sprachen sind nicht relevant für die Klausur. 

Für die Klausur in Grundlagen der Theoretischen Informatik sind außerdem die Folien 451-465 (Beweis von Satz 18) sowie die Folien 547-574 zur Komplexitätstheorie nicht relevant für die Klausur.

 

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey
• Vorlesungstermine:
  • Dienstag, 14:15-15:45, H-C 3305
  • Donnerstag, 14:15-15:45, PB-C 101
• Der erste Vorlesungstermin ist am 5. April.
• Übungen:
  • Mittwoch, 10:15-11:45, H-C 7327
  • Mittwoch, 12:15-13:45, AR-HB 0120
  • Donnerstag, 08:15-09:45, H-B 6414
  • Freitag, 12:15-13:45, H-C 7327
• Alle Übungsgruppen beginnen in der Woche von 11. April bis 15. April.

 

Einige Themen

• Formale Sprachen
• Chomsky Hierarchie
• Endliche Automaten
• Kontextfreie Grammatiken
• Kellerautomaten
• Berechenbarkeit und Unentscheidbarkeit
• Komplexität, insbesondere P versus NP

 

Folien

 

 Übungsblätter Formale Sprachen und Automaten

• Blatt 1
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5
• Blatt 6
• Blatt 7
• Blatt 8
• Blatt 9
• Blatt 10
• Blatt 11

• Blatt 12
• Blatt 13
• Blatt 14

 

Lehrbücher

• Uwe Schöning, Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag
• Lutz Priese, Katrin Erk, Theoretische Informatik: Eine umfassende Einführung, Springer
• Alexander Asteroth, Christel Baier, Theoretische Informatik, Pearson Studium