Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Vorlesung: Theoretische Informatik 1

Wintersemester 2023/24

News

12. März
nr.titleavg.med.
1Det.8,49
2CYK8,29
3Arden8,69
4Trip.7,18
5Pump.5,77
6PDA4,96
7Verb.2,92
8Quiz3,03
9MyNe.3,83
10Gram.1,41
total45,446
1,0 1,3 1,7 2,0 2,3 2,7 3,0 3,3 3,7 4,0 5,0 ≥85 ≥80 ≥75 ≥70 ≥65 ≥60 ≥55 ≥50 ≥45 ≥40 ≥0 0 5 10 15 20 25 30 35 Die Prüfungsergebnisse der Abschlussklausur vom 8. März sind nun verfügbar: Eine Klausureinsicht wird am 25. März um 13:15 Uhr im Raum IZ 358 stattfinden. Bei weiteren Fragen wenden Sie sich an René Maseli.
Eine Übersicht ist hier bereitgestellt. Die Bestehensquote beträgt 73%.
6. März
Die Raumverteilung für die Prüfung lautet wiefolgt: Teilnehmer, dessen Nachname mit A-K beginnt, schreiben die Klausur in UP 3.007 (Universitätsplatz, unter dem Audimax), . Beginnt Ihr Nachname stattdessen mit L-Z, schreiben Sie sie in der Sporthalle Campus Nord (Bienroder Weg 83) .
9. Februar
Es sind nun Lösungsvorschläge zur Probeklausur verfügbar. Außerdem gibt es Notizen zur großen Übung vom 29. Januar.
31. Januar
Die Probeklausur ist nun verfügbar. In der Vorlesung am 6. Februar werden die Aufgaben behandelt.
23. Januar
In den letzten beiden Wochen wechseln große Übung und Vorlesung. Also findet am 29. Januar eine große Übung, und am 5. Februar eine Vorlesung statt.
8. Januar
Das fünfte Blatt ist nun online.
22. Dezember
Die Notizen der Großen Übung sind nun verfügbar und finden sich in der Tabelle unter Übung.
24. Oktober
Die Daten bezüglich der Vorlesung haben sich nach hinten verschoben.
18. Oktober
Die kleinen Übungen sind nun festgelegt. Sie können sich außerdem nun in die Stud.IP-Veranstaltung eintragen, wo ab dem 30. Oktober die Anmeldung zu den kleinen Übungen freigeschaltet wird.
9. Oktober
Webseite wurde erstellt und veröffentlicht. Die Informationen sind alle noch vorläufig.

Organisation

Vorlesung

Wir bieten ein geTeXtes Skript an (aktualisiert am 14.11.2023). Ein Foliensatz steht ebenfalls zur Verfügung (Stand 07.02.2022). Falls Sie Fehler in den Notizen finden, kontaktieren Sie bitte René Maseli.

Zudem gibt es handschriftliche Notizen zu einzelnen Themen der Vorlesung.

  1. Fixpunkte
    Achtung: In den Aufzeichnungen sind Pre und Post-Fixpunkt vertauscht. Die Aufzeichnungen sind korrekt, benutzen aber eine mit dem Skript inkonsistente Notation.
  2. Datenflussanalyse
  3. Folien zu Datenflussanalyse
  4. Folien zu regulären Sprachen und weiterführenden Resultaten
  5. Regular languages and finite automata
  6. Equivalence
  7. Homomorphisms
  8. Complexity of problems for regular languages
  9. Minimization
  10. Pumping lemma for regular languages and ultimate periodicity
  11. Overview of the results for regular languages
  12. Reduktionssysteme, Kontextfreie Grammatiken und die Chomsky Hierarchie
  13. Normal forms for context-free grammars
  14. Pumping lemmas for context-free languages
  15. Pushdown automata and context-free languages
  16. Closure properties of context-free languages
  17. Deterministic context-free languages and complementation
  18. Decision algorithms for context-free languages
  19. Context-sensitive languages
  20. Satz von Immermann und Szelepcsényi

Aufzeichnungen von vergangenen Vorlesungen werden hier als Videos angeboten.

2021-10-26
Organisatorisches (neu).
Partielle Ordnungen und Verbände.
2021-11-01
Fixpunkte und Stetigkeit.
Achtung: In der Vorlesung sind die Bezeichnungen für Pre-Fixpunkt und Post-Fixpunkt im Vergleich zum Skript vertauscht. Alle Beweise sind immer noch korrekt. Es handelt sich lediglich um eine Notation, die inkonsistent zum Skript ist. Ersetzt jedes Vorkommen von Pre/Post-Fixpunkt durch das entsprechende Gegenstück, dann stimmt es mit dem Skript überein.
2021-11-08 + 09
Satz von Kleene und While-Programme,
Datenflussanalyse: Grundlagen.
2021-11-15
Reaching Definitions und Sprachen - Teil 1,
Reaching Definitions und Sprachen - Teil 2,
Reaching Definitions und Sprachen - Teil 3.
2021-11-22 + 23
Reguläre Sprachen und endliche Automaten,
Ardens Lemma und Charakterisierung von regulären Sprachen.
2021-11-29
DFAs und Automaten mit internen Transitionen.
2021-12-06 + 07
Homomorphismen,
Entscheidbarkeit von Problemen regulärer Sprachen.
2021-12-13
Satz von Myhill-Nerode.
2021-12-20 + 21
Minimale DFAs,
Konstruktion von minimalen DFAs.
2022-01-10
Pumping Lemma,
Sonderausgabe: Ersetzungssysteme und Grammatiken.
2022-01-17 + 18
Chomsky-Normalform,
CYK und Greibach-Normalform.
2022-01-24
Pushdown-Automaten.
2022-01-31 + 02-01
Abschlusseigenschaften von kontextfreien Sprachen,
Pumping Lemma für kontextfreie Sprachen.
2022-02-14
Entscheidbarkeit von Problemen kontextfreier Sprachen.

Hier finden Sie weitere Videos, die Ihnen hoffentlich das Verständnis erleichtern.

  1. 2021-11-11: Fixpunkte.
  2. 2021-11-23: Datenflussanalyse.
  3. 2022-02-16: Tripelkonstruktion. Es hat sich leider ein kleiner Fehler eingeschlichen, auf Seite 6 muss drei Mal das Nicht-Terminal (q2, ♯, q2) durch (q2, A, q2) ersetzt werden.

Übung

Die Übungsblätter werden während des Semesters hier und im Virtuellen Prüfsystem zur Verfügung gestellt. Die Notizen der großen Übungen werden sich hier ebenfalls finden lassen. Zum Bestehen der Studienleistung werden mindestens 50% der erreichbaren Punkte benötigt. Kontaktieren Sie bei Fragen zu den Übungsblättern Ihren Tutor oder René Maseli.

Ausgabe Große Übung Abgabe Aufgabenblatt Downloads
1. 30. Oktober 9. November Deutsch English
2. 10. November 13. November 23. November Deutsch English Tutorium
3. 24. November 27. November 7. Dezember Deutsch English Tutorium (geändert: 2024-01-29)
4. 8. Dezember 11. Dezember 21. Dezember Deutsch English Tutorium
5. 8. Januar 8. Januar 18. Januar Deutsch English Tutorium
6. 19. Januar 22. Januar 1. Februar Deutsch English Tutorium
29. Januar Tutorium

Prüfung

Literatur