Theoretische Informatik 2 SS24

Theoretische Informatik 2 SS24

News

9. Juli - Lösungen für die Probeklausur sind nun verfügbar.  Die Raumverteilung für die Klausur:  Prüflinge mit Vornamen A-I werden in UP 3.007 geprüft.  Beginnt Ihr Vorname mit J-Z, dann schreiben Sie die Prüfung im Audimax.

25. Juni - Als Vorbereitung für die Prüfung am 16. Juli steht eine Probeklausur zur Verfügung.  Sie wird voraussichtlich am 9. Juli behandelt.

24. Juni - Die dieswöchigen kleinen Übungen mit Eren Keskin verschieben sich um eine Woche.  Sie finden nicht am 26. und 27. Juni (11:30 bzw. 16:45 Uhr), sondern am 3. und 4. Juli statt.

17. Juni - Die Aufgabenstellung zu Blatt 5, Aufgabe 2 wurde korrigiert.  Ab morgen bis zum Ende der Vorlesungszeit wird Thomas Haas an Stelle von Prof. Meyer die Vorlesung halten.

15. April - Die VIPS-Gruppen sind nun freigeschaltet.  Auch das erste Aufgabenblatt ist zum Download verfügbar.

8. April - Um sich für die kleinen Übungen anzumelden, tragen Sie sich in diese Stud.IP-Veranstaltung ein.  Die VIPS-Gruppen werden in Kürze freigeschaltet.  Das erste Aufgabenblatt wird am 15. April herausgegeben.  Die kleinen Übungen starten ab dem 2. Mai.  Die kleinen Übungen am 1. Mai werden auf den 8. Mai verschoben.

25. März  - Die Vorlesung startet am 8. April.

Organisation

  • Dozent und Prüfer der Vorlesung ist Prof. Dr. Roland Meyer.
  • Leiter der Übungen ist René Maseli.
  • Eintrag im Vorlesungsverzeichnis: Vorlesung, kleine Übung, Prüfung
  • Stud.IP-Veranstaltungen: Vorlesung, kleine Übung.
  • Vorlesung: Montags, 13:15 - 14:45 in PK 11.1
  • Vorlesung / Große Übung: Dienstags, 13:15 - 14:45 in UP 3.007
  • Kleine Übung: Mittwochs, 11:30 - 13:15 mit Eren Keskin in IZ 358 (8. Mai, 15. Mai, 29. Mai, 12. Juni, 26. Juni, 10. Juli)
  • Kleine Übung: Donnerstags, 15:00 - 16:30 mit Jan Wasserscheidt in IZ 358 (2. Mai, 16. Mai, 30. Mai, 13. Juni, 27. Juni, 11. Juli)
  • Kleine Übung: Donnerstags, 16:45 - 18:15 mit Eren Keskin in IZ 358 (2. Mai, 16. Mai, 30. Mai, 13. Juni, 27. Juni, 11. Juli)
  • Kleine Übung: Freitag, 13:15 - 14:45 mit Fabian Kollhoff in IZ 358 (3. Mai, 17. Mai, 31. Mai, 14. Juni, 28. Juni, 12. Juli)
  • Sprechstunde: Mittwoch, 18:30 - 19:30 mit René Maseli in IZ 358.

 

Modul

Es handelt sich um eine (4+2) Veranstaltung. Um das Modul erfolgreich abzuschließen, sind zwei Leistungen zu erbringen:

  • Prüfungsleistung: Zu erbringen durch Bestehen einer schriftlichen Abschlussprüfung am 16. Juli.
  • Studienleistung: Im zweiwöchigen Rhythmus werden auf dieser Seite Übungsblätter mit Hausaufgaben online gestellt.  Diese Hausaufgaben werden in Vierer-Gruppen bearbeitet und abgegeben.  Unvollständige Gruppen bzw. Einzelpersonen werden zu Vierer-Gruppen zusammengefasst. Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 50% der Übungsaufgaben.

 

Material

Vorlesungsablauf

Datum Thema
8. April Intro
9. April CSL und TM
15. April Satz von Kuroda, Determinismus
16. April Übung 1: CSL und LBA
22. April Satz von Immermann & Szelepcsényi
23. April Entscheidbarkeit
29. April Rekursiv-aufzählbare Sprachen
30. April Übung 2: Alphabetsreduktion, Mehrband-TM
6. Mai Die universelle TM, Unentscheidbarkeit
7. Mai Reduktion, PCP
13. Mai Satz von Rice
14. Mai Übung 3: Berechenbare Funktionen
27. Mai Probleme von CFL
28. Mai Übung 4: Reduktionen
3. Juni Komplexität, Landau-Notation
4. Juni Komplexitätsklassen
10. Juni Landkarte der Komplexitätstheorie
11. Juni Übung 5: Komplexitätsanalyse, NL-Vollständigkeit
17. Juni L, NL, Reduktionen, Vollständigkeit
18. Juni PATH, 2-SAT
24. Juni P, NP
25. Juni Übung 6: NP-Vollständigkeit
1. Juli SAT, Hamiltonian Cycle
2. Juli Zertifikate
8. Juli QBF, Satz von Savitch
9. Juli Hierarchiesätze, Klausurvorbereitung
16. Juli Klausur

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.
  • A. M. Turing: On Computable Numbers, with an application to the Entscheidungsproblem. [DOI] [PDF]