Vorlesung Grundlagen der Theoretischen Informatik (SS 2019)

Aktuelles

Die Klausureinsicht findet am Donnerstag, den 05.09.2019, von 14:00 bis 15:00 in H-C 3305 statt.

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey
• Vorlesungstermine:
  • Dienstag, 14:00-16:00, in AR-D 5103 (roter Hörsaal)
  • Donnerstag, 14:00-16:00, in PB-I 001 Hörsaal
• Übungen:
  • Montag, 8:00-10:00, in H-C 6336/37
  • Dienstag, 16:00-18:00, in H-F 116
  • Mittwoch, 12:00-14:00, in H-C 7326
  • Mittwoch, 16:00-18:00, in H-C 6336/37
  • Donnerstag, 10:00-12:00, in H-C 6336/37

Es darf ein (beidseitig) handschriftlich beschriebenes DIN-A4-Blatt mit in die Klausur genommen werden.

Einige Themen

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

---

Folien (Version vom 08.04.2018)

---

Übungsblätter

• 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

---

Lösungen

• Blatt 14

Lehrbücher

• Uwe Schöning, Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag

---