Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Vorlesung: Theoretische Informatik 1

Wintersemester 2021/22

News

9. März
NrDurchschnittMedian
1Determ.8,510
2CYK8,49
3Arden7,99
4Tripel7,39
5Par. Ord.3,43
6Automaten1,70
7Nichtreg.2,80
8Quiz2,52
9Fixpunkt0,80
10k-ausd. NFA0,30
total43,545
bestanden50,248
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 37 0 0 10 20 30 Die Klausureinsicht wird online stattfinden. Um an der Einsicht teilzunehmen, müssen Sie einen Termin mit René Maseli per E-Mail vereinbaren. Da immer nur jeweils eine Person gleichzeitig an der Einsicht teilnehmen kann, ist die Einsichtsdauer strikt beschränkt. Je nach Andrang, wird die Dauer zwischen 10 und 20 Minuten ausfallen. Erscheinen Sie pünktlich, aber nicht zu früh, zu Ihrem Termin. Frühzeitige Versuche dem Raum beizutreten werden abgelehnt.
Ihr eigenes Ergebnis können Sie in Ihrer Klausur-Veranstaltung im StudIP einsehen. Eine Übersicht ist hier bereitgestellt. Die Bestehensquote beträgt 77%.
23. Februar
Hier findet sich eine Umfrage zur Beurteilung der Vorlesung. Es würde uns freuen, wenn Sie teilnehmen könnten.
22. Februar
Es gibt ein zusätzliches Video zu Myhill-Nerode und dem Pumping Lemma.
22. Februar
Sie müssen die Prüfung selbstständig absolvieren. Dies müssen Sie in Form einer Selbstständigkeitserklärung (PDF, dt/eng) bestätigen. Es ist unbedingt notwendig, dass Sie diese Erklärung unterschreiben und zwischen dem 24. Februar, 14:00 Uhr, und dem 25. Februar, 14:00 Uhr, digital einreichen. Dazu wird Ihnen ein weiteres Verzeichnis zu Verfügung gestellt. Sie müssen das Dokument nicht ausdrucken; es reicht ein handschriflicher Zettel mit den gleichen Angaben und dem Text: Diese Prüfung habe ich selbstständig, ohne fremde Hilfe und ohne unerlaubte Hilfsmittel abgelegt. Der mit dieser Erklärung verbundenen Folgen bin ich mir bewusst. (weitere Informationen)
17. Februar
Ab sofort sollten alle Teilnehmer der Prüfung in einer weiteren StudIP-Veranstaltung eingetragen worden sein: Prüfung / Examination: Theoretische Informatik 1. Falls Sie so eine Veranstaltung nicht finden, aber sich über das HIS angemeldet haben, wenden Sie sich unverzüglich an René Maseli.
Der BigBlueButton Raum zur Klausur kann unter diesem Link gefunden werden. Dieser Raum wird kurz vor Beginn der Klausur zugänglich sein. Bei Zutritt müssen Sie auf die Bestätigung des Moderators warten. Wir lassen immer nur eine Person gleichzeitig in den Raum um Fragen zu stellen, daher kann Ihre Zutrittsanfrage abgelehnt werden. Versuchen Sie es dann einfach etwas später nochmal (erfahrungsgemäß passiert dies selten/gar nicht).
17. Februar
Es gibt ein zusätzliches Video zur Automatenkonstruktion.
16. Februar
Es gibt ein neues Video zur Tripelkonstruktion, das Ihnen die Sprachäquivalenz von CFGs und PDAs näher bringen soll. 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.
07. Februar
Zur Vorbereitung auf die Prüfung, finden ab jetzt jeden Mittwoch um 18.00 Uhr Fragerunden mit Roland Meyer, René Maseli und Thomas Haas statt. Wir sprechen in diesem

BBB-Raum.

Nutzen Sie bitte die Gelegenheit, Fragen zu stellen. Sofern Sie außerhalb dieser Termine Fragen haben, schreiben Sie uns dreien gerne eine Mail oder stellen Sie Ihre Frage im Chat und wir beantworten sie schnellstmöglich.

Denken Sie bitte daran, dass Ihnen zur Vorbereitung Altklausuren zur Verfügung stehen. Sie sollten diese Klausuren bearbeiten und sich mit Rückfragen bei uns melden.

8. Dezember
Es finden zu folgenden Zeiten offene kleine Übungen statt: dienstags 11:30 mit Jan Steiner, mittwochs 11:30 mit Dennis Dinh, donnerstags 11:30 mit Jakob Tepe und freitags 15:00 mit Dogukan Hizir. Die Teilnahme ist nicht verpflichtend. Sie können auch problemlos die Übung eines anderen Tutors besuchen.
7. Dezember
Ab sofort können die Abgaben im StudIP hinterlegt werden.
27. November
Das Video zum ersten Aufgabenblatt ist online.
23. November
Es gibt ein neues Video zur Datenflussanlayse, das Ihnen das Verständnis erleichtern soll.
23. November
In der reaktivierten StudIP-Veranstaltung findet gerade eine Termin-Umfrage bezüglich der kleinen Übungen statt. Wenn Sie Interesse an einem Zeitslot haben, in denen Sie sich mit Ihrem Tutor austauschen können, nehmen Sie bitte daran teil.
11. November
Es gibt ein neues Video zu Fixpunkten, das Ihnen das Verständnis erleichtern soll.
09. November
Das erste Aufgabenblatt ist online.
03. November
Der Foliensatz beginnt mit den Regulären Sprachen, um ein wenig Vorsprung zu haben. Die Inhalte zu Verbänden werden nachgetragen.
27. Oktober
Wenn Sie sich ein wenig Programmier-Erfahrung aneignen wollen oder schon darüber verfügen, können Sie mit dem Java-Projekt Lifa endliche Automaten bauen, ihre Transitionsgraphen ausdrucken lassen und mit den Methoden aus der Vorlesung transformieren. Sie benötigen dafür eine Installation von GraphViz.
11. Oktober
Die Vorlesungen, großen Übungen und kleinen Übungen werden aufgrund der momentanen Situation nur online angeboten. Dazu werden hier auf dieser Seite die jeweiligen Veranstaltungen in Videoform hochgeladen. Die Hausaufgabenabgabe und Korrektur wird ebenso online stattfinden. Das heißt, die Hausaufgaben müssen entweder eingescannt werden oder direkt z.B. über LateX als .pdf erstellt werden. Weitere Informationen zum Übungsbetrieb folgen später.

Organisation

Vorlesung

Die Vorlesungen werden als Videos hier angeboten.
  1. 2021-10-26: Organisatorisches (neu).
    Partielle Ordnungen und Verbände.
  2. 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.
  3. 2021-11-08 + 09: Satz von Kleene und While-Programme,
    Datenflussanalyse: Grundlagen.
  4. 2021-11-15: Reaching Definitions und Sprachen - Teil 1,
    Reaching Definitions und Sprachen - Teil 2,
    Reaching Definitions und Sprachen - Teil 3.
  5. 2021-11-22 + 23: Reguläre Sprachen und endliche Automaten,
    Ardens Lemma und Charakterisierung von regulären Sprachen.
  6. 2021-11-29: DFAs und Automaten mit internen Transitionen.
  7. 2021-12-06 + 07: Homomorphismen,
    Entscheidbarkeit von Problemen regulärer Sprachen.
  8. 2021-12-13: Satz von Myhill-Nerode.
  9. 2021-12-20 + 21: Minimale DFAs,
    Konstruktion von minimalen DFAs.
  10. 2022-01-10: Pumping Lemma,
    Sonderausgabe: Ersetzungssysteme und Grammatiken.
  11. 2022-01-17 + 18: Chomsky-Normalform,
    CYK und Greibach-Normalform.
  12. 2022-01-24: Pushdown-Automaten.
  13. 2022-01-31 + 02-01: Abschlusseigenschaften von kontextfreien Sprachen,
    Pumping Lemma für kontextfreie Sprachen.
  14. 2022-02-14: Entscheidbarkeit von Problemen kontextfreier Sprachen.

Weitere Videos

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.

Große Übung

Die großen Übungen werden im Videoformat hier bereitgestellt.
  1. 2021-11-02: Verbände mp4 html
  2. 2021-11-16: Datenfluss-Analyse mp4 png
  3. 2021-11-30: Arden's Lemma, Potenzmengenkonstruktion mp4 png
  4. 2021-12-14: Shuffle, Myhill-Nerode mp4 png
  5. 2022-01-11: Minimerung, Pumping Lemma, Kontextfreie Grammatiken mp4 png
  6. 2022-01-25: CYK-Algorithmus, Pushdown-Automaten mp4 png
  7. 2022-02-15: Tripelkonstruktion mp4 png
  8. 2022-02-17: Automatenkonstruktion mp4

kleine Übung

Die Übungsblätter werden während des Semesters hier zur Verfügung gestellt. Zum Bestehen der Studienleistung werden mindestens 50%, also 100 Punkte benötigt. Kontaktieren Sie bei Fragen zu den Übungsblättern Ihren Tutor oder René Maseli.
  1. 2021-11-09 de en (Abgabe 2021-11-18) mov
  2. 2021-11-23 de en (Abgabe 2021-12-02) mp4 pdf
  3. 2021-12-07 de en (Abgabe 2021-12-16) mov mp4
  4. 2021-12-21 de en (Abgabe 2022-01-13) mp4
  5. 2022-01-18 de en (Abgabe 2022-01-27) mp4
  6. 2022-02-01 de en (Abgabe 2022-02-10) m4v

Foliensatz

Ein Foliensatz steht ebenfalls zur Verfügung (Stand 07.02.2022).

Vorlesungsnotizen

Wir bieten ein geTeXtes Skript an (aktualisiert am 07.02.2022).

Falls Sie Fehler in den Notizen finden, kontaktieren Sie bitte René.

Zudem gibt es handschriftliche Notizen zu einzelnen Themen der Vorlesung.

Modul

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

Prüfung

Literatur