Theoretical Computer Science

Vorlesung: Theoretische Informatik 2

Sommersemester 2021

Neuigkeiten

31. August

Für die Klausureinsicht werden die folgenden Termine angeboten: 09.09, 10.09, 13.09 und 14.09, jeweils ab 11:00 Uhr frühestens. Bitte schreibt eine E-Mail an Thomas Haas(t.haas@tu-bs.de) mit den möglichen Terminen, die ihr wahrnehmen könnt. Ihr werdet dann rechtzeitig über euren zugeteilten Termin informiert.
Die Klausureinsicht findet physisch vor Ort statt.

9. August

Die Klausurergebnisse sind nun online. Ihr findet diese auf stud.ip in eurer Klausurgruppe als .pdf Datei.
Aufgrund der Urlaubszeit, wird die Klausureinsicht erst im September stattfinden können.

20. Juli

• 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üsst ihr auf die Bestätigung des Moderators warten. Wir lassen immer nur eine Person gleichzeitig in den Raum um Fragen zu stellen, daher kann eure Zutrittsanfrage abgelehnt werden. Versucht es dann einfach etwas später nochmal (erfahrungsgemäß passiert dies selten/gar nicht).
• Ihr werdet spätestens morgen in eine Gruppe auf Stud.ip eingetragen. Ihr solltet dann auf eurem Stud.ip Account unter dem Reiter Kurse/Courses im SS2021 eine neue Veranstaltung sehen "Examination: Gruppe X". Wenn ihr diese nicht findet, versucht euren Browsercache zu leeren oder sucht mit Hilfe der Suchfunktion nach dieser Veranstaltung. Bestehen weiterhin Probleme so schreibt eine E-Mail an Thomas Haas(t.haas@tu-bs.de).
• Im Falle, dass alles funktioniert, solltet ihr zu Beginn der Klausur (um 10:00 Uhr) 2 Ordner unter dem Reiter Ordner/Files finden. Ein Ordner wird die Klausur und eine Eigenständigkeitserklärung zum Download enthalten. Der andere Ordner wird zur Abgabe der Klausur/Eigenständigkeitserklärung benutzt. Die Eigenständigkeitserklärung muss gedruckt, unterschrieben und dann abfotografiert oder eingescannt hochgeladen werden. Sollte das Drucken nicht möglich sein, dann gibt es eine handgefertige Alternative. Dazu schaut bitte unter Informationen zur Onlineprüfung nach. In der Informationsdatei zur Onlineprüfung unter Punkt III. sind alle Details zu finden.

13. Juli

Die aktuelle Vorlesung über den Satz von Savitch ist die letzte inhaltliche Vorlesung.

1. Juni

Aufgrund von Pfingsten finden diese Woche zwei Vorlesungen statt. Die nächte Großübung findet dann in der nächsten Woche (am 8. Juni) statt.

19. Mai

Die große Übung und die erste kleine Übung sind nun online.

25. April

Unvollständige Hausaufgabengruppen auf Stud.ip wurden zusammengelegt. Gruppenlose Studenten wurden in Gruppen eingetragen.
Bitte überprüft, dass ihr eure Gruppe auf Stud.ip sehen könnt. Tauscht euch untereinander aus und geht sicher, dass ihr zusammen arbeiten könnt.

21. April

Die große Übung ist nun online.

14. April

• Zur Teilnahme an den Hausaufgaben für die Studienleistung, tragt euch bitte auf Stud.ip in der Veranstaltung "Online kleine Übung: Theoretische Informatik 2" ein.
• Tragt euch ebenfalls dort bis zum Freitag, den 23.04 in eine Hausaufgabengruppe ein. Unvollständige Gruppen werden am Ende zusammengelegt.
• Wir bieten einen RocketChat zum Austausch über die Veranstaltung an. Ihr könnte diesen auch gerne zur Findung der Hausaufgabengruppen nutzen.

19. März

Die Informationen auf dieser Seite sind noch vorläufig.

Organisation

Vorlesung

• Die Dozenten der Vorlesung sind Prof. Dr. Roland Meyer, Peter Chini und Thomas Haas.
• Prüfer der Vorlesung ist Prof. Dr. Roland Meyer.
• Eintrag im Vorlesungsverzeichnis: Vorlesung.
• Vorlesungstermine: Die Vorlesungen werden im Videoformat hochgeladen zu den folgenden Zeiten, zu denen normalerweise die Vorlesungen stattfinden würden:
  • Montag, 13:15 - 14:45.
  • Dienstag, 13:15 - 14:45 alle 14 Tage.

Übung

• Große Übung, gehalten von Thomas Haas, wird alternierend mit der Vorlesung am Dienstag hochgeladen:
  • Dienstag, 13:15 - 14:45 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.

Modul

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

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

Vorlesungsvideos

• Woche 1: Intro, CSL und TM.
• Woche 1: Satz von Kuroda und Determinismus in TMs.
• Woche 2: Satz von Immerman und Szelepcsényi.
• Woche 3: Berechenbarkeit I.
• Woche 3: Berechenbarkeit II.
• Woche 4: Entscheidbarkeit.
• Woche 5: Unentscheidbarkeit - Intro, Kodierung von TM, Die universelle TM, Unentscheidbarkeit von ACCEPT, Reduktionen.
• Woche 6: PCP.
• Woche 7: Satz von Rice.
• Woche 8: Unentscheidbare Probleme kontextfreier Sprachen.
• Woche 8: Grundlagen der Komplexitätstheorie - Intro, Landau-Notation, Komplexitätsklassen.
• Woche 9: Grundlagen der Komplexitätstheorie II - Relationen, Komplementklassen, Landkarte der Komplexitätstheorie.
• Woche 10: Reduktionen und die Klassen L und NL - Reduktionen und Vollständigkeit, Path, 2-SAT, Probleme in L.
• Woche 11: P.
• Woche 12: NP - Intro, SAT, HamiltonianCycle, Zertifikate.
• Woche 13: QBF.
• Woche 14: Savitch.
• Informationen zur Klausur: Info.

Große Übungen

• Übung 1: CSL und LBAs
• Übung 2: Berechenbare Funktionen
• Übung 3: Reduktion
• Übung 4: Komplexitätsanalyse
• Übung 5: NL-vollständige Probleme
• Übung 6: NP-vollständige Probleme (3-SAT, 3-COLORABILITY)
  (*3-SAT wurde ebenfalls in der Vorlesung behandelt*)

Übungsblätter

• Hochgeladen: 27.04.2021; Abgabe: 07.05.2021: Blatt 1
  
• Hochgeladen: 11.05.2021; Abgabe: 21.05.2021: Blatt 2
  
• Hochgeladen: 25.05.2021; Abgabe: 04.06.2021: Blatt 3
  
• Hochgeladen: 15.06.2021; Abgabe: 25.06.2021: Blatt 4
  
• Hochgeladen: 29.06.2021; Abgabe: 09.07.2021: Blatt 5
  
• Hochgeladen: 13.07.2021; Abgabe: Keine Abgabe: Blatt 6 (Bonus/unbewertet)
  

• Blatt 1
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5
• Blatt 6

Weitere Materialien

• Aktuelles Skript zu Theoretische Informatik 2 (wird während des Semesters aktualisiert)
• Ältere Versionen der Vorlesungsnotizen: Sommersemester 2017 , Sommersemester 2018 , Sommersemester 2019 .
• Skript zur Vorlesung Theoretische Informatik 1
• Skript zur Vorlesung Komplexitätstheorie

Abschlussklausur

• Die Abschlussklausur findet am Dienstag, dem 27. Juli 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.
• Die Klausur besteht aus (7/10) Aufgaben zu je 10 Punkten, die Bearbeitungszeit beträgt üblicherweise (120/180) Minuten (neue PO/alte PO). Durch die Extrazeit ist die Bearbeitungszeit nun (180/240) Minuten.
• Zur Vorbereitung auf die Abschlussklausur empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren: Sommer 2017 , Winter 2017/18 , Sommer 2018 , Sommer 2019 , Winter 2019/20 , Sommer 2020 , Winter 2020/21 .

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. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
• M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
• I. Wegener: Complexity Theory. Springer, 2005.
• D. Kozen: Automata and Computability. Springer, 1977.
• O. Goldreich: Computational Complexity. Cambridge University Press, 2008.