Theoretical Computer Science

Vorlesung: Theoretische Informatik 1

Wintersemester 2020/21

News

28. März

Die Klausureinsicht wird online über den BBB-Raum der Klausur stattfinden.
Um an der Klausureinsicht teilzunehmen, müsst ihr einen Termin mit Thomas Haas per E-Mail vereinbaren. Mögliche Termine sind Mittwoch und Donnerstag jeweils von 12:00 Uhr bis 16:00 Uhr.
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.
Erscheint pünktlich, aber nicht zu früh, zu eurem Termin. Frühzeitige Versuche dem BBB-Raum beizutreten werden abgelehnt.

26. März

Die Klausurergebnisse sind da. Eine Liste der Ergebnisse finden Sie auf stud.ip unter der Veranstaltung der Klausur, in der Sie eingetragen wurden.
Eine anonyme Statistik der Klausur finden Sie hier.
Informationen zur Klausureinsicht werden noch veröffentlicht.

17. Februar

Während der Prüfungszeit könnt ihr den BBB-Raum zum Stellen von Fragen verwenden.
Der Link zu diesem Raum wird auch auf der Klausur zu finden sein.

15. Februar

Falls noch Fragen zum Stoff oder den Altklausuraufgaben auftreten, könnt ihr bis Prüfung den RocketChat verwenden, um diese zu stellen oder euch auszutauschen.

14. Februar

Alle für die Prüfung angemeldeten Studenten sollten nun in Stud.ip einem neuen Kurs zugeordnet sein.
Bitte überprüft, dass ihr alle diesen Kurs seht. Zu Beginn der Prüfung werden dort unter Files/Dateien die nötigen Ordner und Dateien sichtbar.

10. Februar

Das Video zu Hausaufgabe 4 ist online.
Für Hausaufgabe 5 wird es kein Video geben. Stattdessen ist die Musterlösung dazu online.

9. Februar

Wir empfehlen zur Vorbereitung auf die Prüfung das Durcharbeiten der weiter unten verlinkten Altklausuren aus den vergangenen Jahren.

8. Februar

WICHTIG: Es gibt neue Informationen zu der Klausur (weiter unten auf der Seite). Lest diese bitte durch.
Ergänzung: Tablets zur Bearbeitung der Klausur sind auch erlaubt. Die Abgabe kann als .pdf erfolgen. Prinzipiell muss die Klausur nicht handschriftlich bearbeitet werden, aber es wird stark empfohlen. Das Erstellen von Tabellen/Automaten/Formeln kostet sonst zu viel Zeit.
Update: Die Extrazeit wird auf 60 Minuten verlängert. Studenten, die keine telefonische Verbindung haben, können auf Anfrage ihre Klausur in der Uni schreiben. Meldet euch dazu bis zum Ende der Woche bei uns.

27. Januar

Die große Übung ist online.

26. Januar

Krankheitsbedingt erscheint die große Übung erst morgen.

22. Januar

Das (lang ersehnte) Tutorium zu Hausaufgabenblatt 3 ist nun online.
Die Klausur wird voraussichtlich online stattfinden. Genauere Informationen werden noch veröffentlicht.

19. Januar

Das 5. und letzte(!) Hausaufgabenblatt ist nun online. Anstelle des nächsten Hausaufgabentermins werden wir versuchen eine Live-Veranstaltung durchzuführen.

12. Januar

Die fünfte große Übung ist nun online.

15. Dezember

Das 4. Hausaufgabenblatt ist nun online. Die Abgabe dieser Hausaufgabe ist erst im nächsten Jahr.
Habt eine frohe Weihnacht und rutscht gut ins neue Jahr!

08. Dezember

Die vierte große Übung ist nun online.
Das Tutorium zu Hausaufgabenblatt 2 ist nun online.

01. Dezember

Das 3. Hausaufgabenblatt ist nun online.

27. November

Es gibt die Möglichkeit anonym eine Lehrevaluation (abgeschlossen) durchzuführen.
Bitte besucht den Link und füllt den Evaluationsbogen bis zum Freitag, den 11. Dezember aus.

24. November

Die dritte große Übung ist nun online.
Das Tutorium zum ersten Hausaufgabenblatt ist online.

20. November

Es gibt Details zur Abschlussklausur.

17. November

Das 2. Hausaufgabenblatt ist nun online.

10. November

Die zweite große Übung ist nun online.

3. November

Das 1. Hausaufgabenblatt ist nun online.

2. November

Die Gruppeneinteilung für die Hausaufgabengruppen ist nun fertig. Wem noch keine Gruppe zugeordnet worden ist, obwohl er sich angemeldet hat, soll sich bei Thomas Haas melden.

27. Oktober

Die erste große Übung ist nun online.

26. Oktober

Das Skript wurde aktualisiert. Eine Notiz zur heutigen Vorlesung wurde hinzugefügt.

19. Oktober

In der ersten Woche wird es nur eine Vorlesung am Dienstag (20. Oktober) geben.
Die erste große Übung findet nächste Woche (27. Oktober) statt. Nach der ersten Vorlesung wird ein unbewertetes Übungsblatt zur Vorlesung hochgeladen, welches in der darauffolgenden großen Übung besprochen wird.
Die ersten (richtigen) Hausaufgaben wird es erst in 2 Wochen geben.
Meldet euch bitte bis dahin für die kleinen Übungen mit euren Gruppen an, wenn es noch nicht geschehen ist.

12. 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.

Organisation

• Die Vorlesungen und Großübungen werden von Peter Chini und Thomas Haas gehalten.
  Der Modulverantwortliche und Prüfer ist Prof. Dr. Roland Meyer.
• Einträge im Vorlesungsverzeichnis: Vorlesung, Großübung, Übung in Kleingruppen.
• Die Termine für Vorlesung und Großübung sind
  • Montag, 13:15 - 14:45,
  • Dienstag, 15:00 - 16:30 alle 14 Tage.
  Aufgrund der momentanen Situation, werden zu den entsprechenden Zeiten Videos der Vorlesung bzw. großen Übung auf dieser Webseite online gestellt.
• Vorlesung und Großübung finden im zweiwöchigen Wechsel statt. In der ersten Vorlesungswoche findet eine Vorlesung (Di.) statt und keine große Übung. Danach wird folgender Turnus eingehalten: In der nächsten Woche Vorlesung (Mo.) und große Übung (Di.), danach zwei Vorlesungen (Mo. und Di.), danach wieder Vorlesung (Mo.) und große Übung (Di.) usw.

Übungen

• Große Übung, gehalten von Thomas Haas, wird alternierend mit der Vorlesung am Dienstag hochgeladen:
  • Dienstag, 15:00 - 16:30 alle 14 Tage, an den Tagen an denen keine Vorlesung stattfindet.
• Im zweiwöchigen Rhythmus werden auf dieser Seite Übungsblätter mit Hausaufgaben online gestellt. Diese Hausaufgaben werden in 4er Gruppen bearbeitet und abgegeben.
  Um euch bei den kleinen Übungen anzumelden, schickt bitte eine E-Mail an "thohaas@tu-braunschweig.de" mit den Daten aller Gruppenmitglieder in folgendem Format (eine Zeile pro Person):
  • Vorname, Nachname, Matrikelnummer, E-Mail Adresse
  Bitte besprecht vorher untereinander was für Gruppen ihr bildet und sendet nur eine E-Mail pro Gruppe.
  Unvollständige Gruppen bzw. Einzelpersonen werden zu 4er Gruppen zusammengefasst.
  Anschließend werden alle Gruppen auf die 3 Tutoren aufgeteilt.
• In den kleinen Übungen werden die Hausaufgaben besprochen. Die kleinen Übungen werden von diversen Tutoren gehalten. Statt mehreren Tutorien werden die Tutoren abwechselnd ein Tutorium aufnehmen und auf dieser Seite für alle Studenten zugänglich machen. Die Tutoren sind:
  • Frieso Gerken (friesogerken@web.de)
  • Widukind Stöter (w.stoeter@tu-braunschweig.de)
  • Aleksandr Efremov (a.efremov@tu-bs.de)
• Die Hausaufgabenabgabe und Korrektur erfolgt ausschließlich online. Scannt dazu eure handschriftlichen Hausaufgaben ein oder erstellt diese direkt in digitaler Form als .pdf (z.B. mit LateX), und sendet diese an den euch zugeteilten Tutor per E-Mail.

Vorlesungsvideos

• Woche 1: Partielle Ordnungen und Verbände.
• Woche 2: 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.
• Woche 3: Satz von Kleene und While-Programme,
  Datenflussanalyse: Grundlagen.
• Woche 4: Reaching Definitions und Sprachen - Teil 1,
  Reaching Definitions und Sprachen - Teil 2,
  Reaching Definitions und Sprachen - Teil 3.
• Woche 5: Reguläre Sprachen und endliche Automaten,
  Ardens Lemma und Charakterisierung von regulären Sprachen.
• Woche 6: DFAs und Automaten mit internen Transitionen.
• Woche 7: Homomorphismen,
  Entscheidbarkeit von Problemen regulärer Sprachen.
• Woche 8: Satz von Myhill-Nerode.
• Woche 9: Minimale DFAs,
  Konstruktion von minimalen DFAs.
• Schöne Ferien: Wintergruß.
• Woche 10: Pumping Lemma,
  Sonderausgabe: Ersetzungssysteme und Grammatiken.
• Woche 11: Chomsky-Normalform,
  CYK und Greibach-Normalform.
• Woche 12: Pushdown-Automaten.
• Woche 13: Abschlusseigenschaften von kontextfreien Sprachen,
  Pumping Lemma für kontextfreie Sprachen.
• Woche 14: Entscheidbarkeit von Problemen kontextfreier Sprachen.

Große Übungen

• Übung 1: Besprechung von Blatt 0
• Übung 2.1: Available-Expression Analyse
  Übung 2.2: Busy-Expression Analyse
• Übung 3: Endliche Automaten, Ardens Lemma und Potenzmengenkonstruktion
• Übung 4: Shuffle und Myhill-Nerode
• Übung 5: Minimierung, Pumping Lemma und CFGs
• Übung 6: CYK und PDAs
• Übung 7: Tripelkonstruktion

Übungsblätter

• Hochgeladen: 20.10.2020: Blatt 0 (keine Hausaufgabe)
  
• Hochgeladen: 03.11.2020: Blatt 1 / Sheet 1
  
• Hochgeladen: 17.11.2020: Blatt 2 / Sheet 2
  
• Hochgeladen: 01.12.2020: Blatt 3 / Sheet 3
  
• Hochgeladen: 15.12.2020: Blatt 4 / Sheet 4
  
• Hochgeladen: 19.01.2021: Blatt 5 / Sheet 5
  

• Blatt 1
  
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5 (Musterlösung)
  Achtung: Die Aufgabennummern in der Musterlösung stimmen nicht mit denen der Hausaufgabe überein.

Vorlesungsnotizen

Vorlesungsnotizen (Aktualisiert am 26.10.2020)

Falls Sie Fehler in den Notizen finden, kontaktieren Sie bitte Thomas.

• Fixpunkte
  Achtung: In den Aufzeichnungen sind Pre und Post-Fixpunkt vertauscht. Die Aufzeichnungen sind korrekt, benutzen aber eine mit dem Skript inkonsistente Notation.
• Datenflussanalyse
• Folien zu Datenflussanalyse
• Folien zu regulären Sprachen und weiterführenden Resultaten
• Regular languages and finite automata
• Equivalence
• Homomorphisms
• Complexity of problems for regular languages
• Minimization
• Pumping lemma for regular languages and ultimate periodicity
• Overview of the results for regular languages
• Reduktionssysteme, Kontextfreie Grammatiken und die Chomsky Hierarchie
• Normal forms for context-free grammars
• Pumping lemmas for context-free languages
• Pushdown automata and context-free languages
• Closure properties of context-free languages
• Deterministic context-free languages and complementation
• Decision algorithms for context-free languages
• Context-sensitive languages
• Immermann and Szelepcséyi's theorem

Modul

• Prüfungsleistung: Zu erbringen durch Bestehen einer schriftliche Abschlussklausur zu Beginn des vorlesungsfreien Zeitraums.
• Studienleistung: Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 50% der Übungsaufgaben.

Abschlussklausur

• Die Abschlussklausur findet am Donnerstag, dem 18. Februar 2021, ab 10:00 Uhr statt.
• Die Klausur wird online über Stud.ip in Form einer Take-Home-Klausur stattfinden. Bitte überprüft dazu, dass Ihr Euch auf stud.ip einloggen könnt. Ihr werdet zu diesem Zweck automatisch in eine Klausurveranstaltung eingetragen (wir kündigen an, sobald dies passiert ist). Gasthörer und Austauschstudenten - jeder der nicht über den Standardweg angemeldet ist - sollen sich per E-Mail an t.haas@tu-bs.de nochmals melden.
• Zu Beginn der Klausur werden versteckte Ordner/Dateien automatisch freigegeben. Ihr ladet die Klausur herunter, bearbeitet diese offline (wie gewohnt auf Papier oder auch auf einem Tablet) und ladet dann Scans, Fotos bzw. PDFs Eurer Klausur in dem dafür vorgesehen Abgabeordner hoch. Hierbei ist alles anonym, Studierende können diesen Abgabeordner nicht einsehen. Aufgrund der technischen Besonderheiten wird die Klausurzeit um 60 Minuten verlängert, damit Ihr Zeit habt, Fotos/Scans/PDFs zu erstellen und hochzuladen.
• Während der Klausurzeit wird ein BigBlueButton (BBB) Raum zur Verfügung stehen. Solltet Ihr Fragen haben, könnt Ihr den BBB-Raum betreten, die Fragen stellen und danach den BBB Raum wieder verlassen. Wird der BBB-Raum nach der Beantwortung nicht verlassen, entfernen wir Euch aus dem Raum.
• Sollten technische Probleme Eurerseits auftreten (der Rechner stürzt ab, die Internetverbindung bricht ab), dann macht Beweisfotos der Situation und meldet die Probleme unmittelbar telefonisch unter +49 531-391-9522. Solltet Ihr keine telefonische Verbindung haben, könnt ihr alternativ die Klausur in der Uni schreiben, um technische Probleme zu vermeiden oder persönlich zu melden. In diesem Fall meldet euch bis zum Ende der Woche bei Thomas Haas.
• Details zu der anschließenden Klausureinsicht werden noch besprochen.
• Die Klausur besteht aus 10 Aufgaben zu je 10 Punkten, die Bearbeitungszeit beträgt üblicherweise 120 Minuten. Durch die Extrazeit ist die Bearbeitungszeit nun 180 Minuten.
• Zur Vorbereitung auf die Klausur empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren: Winter 2016/17, Sommer 2017, Winter 2017/18, Sommer 2018, Winter 2018/19, Winter 2019/20.

Literatur

• U. Schöning: Theoretische Informatik - kurzgefasst. 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).