Theoretical Computer Science

Vorlesung: Theoretische Informatik 2

Sommersemester 2019

Neuigkeiten

10. März

Informationen zur Klausur am 19.03.2020 finden Sie auf folgender Seite: Klausur: Theoretische Informatik 2 im WS19/20

06. August

Klausur-Ergebnisse:  neue P.O.   alte P.O.
Einsicht: Mo, 2019-08-12 im IZ 358, von 11 bis 13 Uhr, oder nach Vereinbarung;

15. Juli

Wir bieten am Mittwoch, dem 17.07, ab 16:45 Uhr in Raum PK.2.2 eine zusätzliche Großübung/Fragestunde zur Vorbereitung auf die Abschlussklausur an. (Raum und Uhrzeit im Vergleich zur ursprünglichen Ankündigung geändert.)

15. Juli

Klausur-Termin: 2019-07-23 (Dienstag), 14:00 - 17:00 (Raumresevierung von 13:30 bis 17:30), in zwei der Grotrian-Räume; Verteilung nach geraden/ungeraden Matrikelnummern.

12. Juli

Zur Klausur ist ein handschriftliches Cheat-Sheet von 2 A4-Seiten (oder einer A3-Seite) zugelassen).

Neues Skript aktualisiert, bis zum Beginn von Abschnitt 2.4.1.

17. April

Auf vielfachen Wunsch dürfen die Hausaufgaben doch in 3-er Gruppen abgegeben werden ;-) , möglichst aber nicht gruppenübergreifend.
Der Abgbetermin von Blatt 0 wurde auf Dienstag, 2019-04-23, 13:15 Uhr verschoben, damit die Hiwis nicht über Ostern korrigieren müssen.

15. April

Die Einteilung in die Übungsgruppen steht fest.

• Sie können auf zahnrad.tcs.cs.tu-bs.de einsehen, zu welcher Übung Sie eingeteilt wurden.
• 78% der Studierenden wurden zu einem "bevorzugten" Termin eingeteilt. Alle Links wurden berücksichtigt.
• Wenn Sie Probleme mit der Einteilung haben, melden Sie sich bei Sebastian.

03. April

Die erste Vorlesung findet am Montag, dem 08. April, statt.

Vorlesung

• Der Dozent und Prüfer ist Dr. Jürgen Koslowski.
• Eintrag im Vorlesungsverzeichnis: Vorlesung, Übung.
• Vorlesungstermine:
  • Montag, 13:15 - 14:45 in PK 2.2
  • Dienstag, 13:15 - 14:45 in PK 2.2, alle 14 Tage, und zwar 2019-{04-09, 04-23, 05-07, 05-21, 06-04, 06-25, 07-09}

Übungsbetrieb

• Große Übung, gehalten von Peter Chini, alternierend mit der Vorlesung am Dienstag:
  • Dienstag, 13:15 - 14:45 in PK 2.2, und zwar 2019-{04-16, 04-30, 05-14, 05-28, 06-18, 07-02, 07-16}
  
  
• Kleine Übungen, gehalten von diversen Tutoren:
  
  • Gruppe 0: Mi, 08:00 - 09:30 in IZ 161
  • Gruppe 1: Mi, 11:30 - 13:00 in IZ 305
  • Gruppe 2: Mi, 13:15 - 14:45 in IZ 161
  • Gruppe 3: Do, 15:00 - 16:30 in IZ 161
  • Gruppe 4: Fr,  09:45 - 11:15 in IZ 358

Übungsblätter

• 2019-04-11: Blatt 0
  
• 2019-04-29: Blatt 1
  
• 2019-05-13: Blatt 2
  
• 2019-05-28: Blatt 3
  
• 2019-06-13: Blatt 4 mit ausgewählten Lösungen
  
• 2019-07-02: Blatt 5
  

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

• Termin: 2019-07-23 (Dienstag); weitere Informationen zur Abschlussklausur werden wir Ihnen rechtzeitig zur Verfügung stellen.

Material

• Vorlesungsnotizen (Sommersemester 2017),
  diese dienen als Gerüst für diese VL
• Vorlesungsnotizen (Sommersemester 2018)
• Ergänzungen zu / Abweichungen von den Vorlesungsnotizen zum Sommersemester 2017

• Kontext-sensitive Sprachen
• Satz von Immermann and Szelepcséyi
• Satz von Immerman und Szelepcsényi (2)
• Berechenbarkeit
• Unentscheidbarkeit, die universelle Turing-Maschine, das Halteproblem, Reduktionen
• Das PCP und der Satz von Rice
• Unentscheidbare Probleme kontextfreier Sprachen
• Zeit- und Platzkomplexitätsklassen
• Beziehungen zwischen den robusten Komplexitätsklassen
• L und NL
• P and NP
• PSPACE
• Satz von Savitch
• Platz vs. Zeit, Nichtdeterminismus vs. Determinismus
• Hierarchieresultate für die Zeit- und Platzkomplexitätsklassen
• Translation-Theoreme
• Berechnungsmodelle für L and NL

• Notizen zur Vorlesung Theoretische Informatik 1
• Notizen zur Vorlesung Komplexitätstheorie
• Notizen zu den Vorlesungen Theorischer Informatik 1 & 2 von Prof. Adamek

Literatur

• F. Nielson, H. R. Nielson, C. Hankin: Principles of Program Analysis. Springer, 2005.
• U. P. Khedker, A. Sanyal, B. Karkare: Data Flow Analysis - Theory and Practice. CRC Press, 2009.
• H. Seidl, R. Wilhelm, S. Hack: Übersetzerbau - Analyse und Transformation. Springer, 2010.
• R. Berghammer: Ordnungen, Verbände und Relationen mit Anwendungen. Springer, 2012.
• G. Grätzer: General Lattice Theory. Birkhäuser, 2003.
• G. Birkhoff: Lattice Theory. Providence, 1967.
• 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.