Theoretische Informatik 1 WS26/27

Theoretische Informatik 1 WS26/27

News

18. August - Die Informationen auf dieser Seite sind noch vorläufig.

Organisation

Verantwortlich für das Modul ist Prof. Dr. Roland Meyer. Die Vorlesung wird von Eren Keskin gehalten.  Die Übungen werden von René Maseli geleitet.

Wöchentlich werden zwei Vorlesungstermine stattfinden, die Sie durch das Themengebiet führen.  Alle zwei Wochen wird ein Termin davon als Großübung abgehalten, wo speziell Aufgabenbeispiele vorgerechnet werden, die Ihnen bei den Hausaufgaben und zur Klausurvorbereitung helfen sollen.

Vorlesung / Große Übung (wöchentlich): [Stud.IP], [Ablauf]

  • Mo, 13:15 - 14:45 in PK 11.1
  • Di, 15:00 - 16:30 in PK 11.1

Kleine Übung (zweiwöchentlich): [Stud.IP]

  • Gruppen und Termine werden noch bekannt gegeben.

Lerntreff Theorie (wöchentlich):

  • Wird noch bekannt gegeben.

Um das Modul erfolgreich abzuschließen, sind zwei Leistungen zu erbringen:

  • Prüfungsleistung: Zu erbringen durch Bestehen einer schriftlichen Abschlussklausur.
  • Studienleistung: Zu erbringen durch das Erreichen von mindestens 50% der Punkte auf die Übungsaufgaben.

Die Prüfung findet am Freitag, den 5. März 2027 von 11:00 Uhr bis 13:00 Uhr im Audimax und UP 3.007, den Raum darunter, statt.

  • Sie besteht aus 10 Aufgaben zu je 10 Punkten. Die Bearbeitungszeit beträgt 120 Minuten.
  • Als Hilfsmittel sind ausschließlich Sprachwörterbücher sowie ein beidseitig handschriftlich beschriebenes DIN A4-Blatt erlaubt.
  • Zur Vorbereitung auf die Prüfung empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren.

Material

Vorlesungsablauf

Datum Thema
19. Okt. Große Übung 0: Einführung in Beweise
20. Okt. Große Übung 0-1: Induktive Mengen und Beweise
26. Okt. Verbände, Fixpunkte
29. Okt. Satz von Knaster & Tarski
2. Nov. Große Übung 1
3. Nov. Stetigkeit, Satz von Kleene
9. Nov. While-Programme
10. Nov. Datenfluss-Analysen
16. Nov. Große Übung 2
17. Nov. Reguläre Sprachen
23. Nov. Endliche Automaten und Arden's Lemma
24. Nov. Abschlusseigenschaften Regulärer Sprachen
30. Nov. Große Übung 3
1. Dez. Satz von Myhill & Nerode
7. Dez. Minimale DFAs
8. Dez. Pumping-Lemma für reguläre Sprachen
14. Dez. Große Übung 4
15. Dez. Formale Grammatiken, kontextfreie Sprachen
4. Jan. Chomsky Normalform
5. Jan. CYK-Algorithmus
11. Jan. Große Übung 5
12. Jan. Pushdown-Automaten
18. Jan. Charakterisierung kontextfreier Sprachen
19. Jan. Pumping-Lemma für kontextfreie Sprachen
25. Jan. Große Übung 6
26. Jan. Abschlusseigenschaften für kontextfreie Sprachen
1. Feb. Greibach-Normalform
2. Feb. Klausurvorbereitung

Videos

Altklausuren

Literatur

  • U. Schöning: Theoretische Informatik - kurz gefasst. Springer, 2008.
  • J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman, 2002.
  • M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
  • M. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
    Erhältlich als E-Book (auf den Seiten der Universitätsbibliothek, ggf. nur aus dem Uni-Netz).
Letzte Aktualisierung: 24.09.2026