Theoretische Informatik 1 WS24/25

Theoretische Informatik 1 WS24/25

News

29. Januar: Lösungsvorschläge für die Probeklausur sind hier verfügbar.

20. Januar: Nächste Woche werden an den Vorlesungstermine eine Probeklausur vorgestellt.  Die Aufgaben stehen Ihnen hier zum Download bereit.

9. Januar: Der Lerntreff um 08:00 Uhr fällt morgen, den 10.01., aus.

16. Dezember: Diesen Mittwoch, den 18.12., wechseln die kleinen Übungen in den Raum 811.

10. Dezember: Die kleinen Übungen nächste Woche Mittwoch, den 18.12. werden ebenfalls im Raum 812 stattfinden.  Des Weiterem ist Blatt 7 hier verfügbar (de) (en).

12. November:  Wegen einer Terminkollision mit einer einmaligen Veranstaltung findet der Übungsbetrieb morgen, am Mittwoch, im Raum 812 statt (selbes Gebäude, Mühlenpfordstraße 23, 8. Stock).  Das betrifft die beiden Übungen ab 15:00 und ab 16:45.

5. November:  Mit der Ausgabe des zweiten Aufgabenblattes steigt der Übungsbetrieb auf das folgende Punkteschema um:  Kreuzen Sie gelöste wöchentliche Aufgaben an und arbeiten Sie in Ihrer kleinen Übung mit, um Punkte zu bekommen.  Sie benötigen mindestens 50 von insgesamt 100 Punkten.  Das erste Blatt wurde dabei mit 4 Punkten gewichtet.

23. Oktober:  Der Start der kleinen Übungen am Donnerstag wird auf morgen vorgezogen.  Die Übungen am Mittwoch und Freitag starten erst in der nächsten Woche.  Weitere Infos im Stud.IP.

21. Oktober:  Die großen Übungen finden jeden zweiten Dienstag anstelle einer Vorlesung statt.  Die Erste ist am 29. Oktober.  Weiteres dazu finden Sie im Vorlesungsverlauf.  Sie können sich nun zu den kleinen Übungen anmelden.  Diese starten ab dem 29. Oktober.

2. Oktober:  Die erste Vorlesung findet am Montag, den 21. Oktober, statt.

1. Oktober: Die Informationen auf dieser Seite sind noch vorläufig.  Insbesondere die Termine für die kleinen Übungen werden noch angepasst.

Organisation

Die Vorlesung wird von Prof. Dr. Roland Meyer 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 (4212010):

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

Kleine Übung (4212046):

  • Di, 08:00 - 09:30 in IZ 358 mit Minseo Kim, beginnend am 29. Oktober
  • Di, 09:45 - 11:15 in IZ 358 mit Bastian Bosse-Graf, beginnend am 29. Oktober
  • Mi, 15:00 - 16:30 in IZ 358 mit Minseo Kim, beginnend am 30. Oktober
  • Mi, 16:45 - 18:15 in IZ 358 mit Elias Kaiser, beginnend am 30. Oktober
  • Do, 09:45 - 11:15 in IZ 358 mit Elias Kaiser, beginnend am 24. Oktober
  • Do, 11:30 - 13:00 in IZ 358 mit Luca Thomas, beginnend am 24. Oktober
  • Do, 13:15 - 14:45 in IZ 358 mit Caroline Krebs, beginnend am 24. Oktober
  • Do, 15:00 - 16:30 in IZ 160 mit Bastian Bosse-Graf, beginnend am 24. Oktober
  • Do, 16:45 - 18:15 in IZ 358 mit Elias Kaiser, beginnend am 24. Oktober
  • Fr, 11:30 - 13:00 in IZ 358 mit Caroline Krebs, beginnend am 1. November
  • Fr, 13:15 - 14:45 in IZ 358 mit Elias Kaiser, beginnend am 1. November
  • Fr, 15:00 - 16:30 in IZ 358 mit Luca Thomas, beginnend am 1. November

Lerntreff Theorie:

  • Fr, 08:00 - 09:30 in IZ 358 mit René Maseli

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

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

Die Prüfung findet am Freitag, den 28. Februar 2025, von 11:00 bis 13:00 im Audimax und UP 3.007 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
21. Okt. Partielle Ordnungen und Verbände
22. Okt. Fixpunkte und Stetigkeit
28. Okt. Satz von Kleene
29. Okt. Große Übung 1
4. Nov. While-Programme
5. Nov. Datenfluss-Analysen
11. Nov. Reguläre Sprachen
12. Nov. Große Übung 2
18. Nov. Endliche Automaten und Arden's Lemma
19. Nov. Abschlusseigenschaften Regulärer Sprachen
25. Nov. Satz von Myhill & Nerode
26. Nov. Große Übung 3
2. Dez. Minimale DFAs
3. Dez. Pumping-Lemma für reguläre Sprachen
9. Dez. Formale Grammatiken und kontextfreie Sprachen
10. Dez. Große Übung 4
16. Dez. Chomsky-Normalform und Greibach-Normalform
17. Dez. Geschichte der Informatik
6. Jan. Pumping-Lemma für kontextfreie Sprachen
7. Jan. Große Übung 5
13. Jan. CYK-Algorithmus
14. Jan. Pushdown-Automaten
20. Jan. Charakterisierung kontextfreier Sprachen
21. Jan. Große Übung 6
27. Jan. Abschlusseigenschaften für kontextfreie Sprachen
28. Jan. 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).