Theoretische Informatik 2

• Turing Maschinen
• Chomsky-Hierarchie
• Entscheidbarkeit
• Berechenbarkeit
• Komplexitätstheorie
• NP-Vollständigkeit

Vorlesungen

• [Skript] aus dem Sommer 2024
• Vorlesung 00: [pdf]
• Vorlesung 01: [pdf]
• Vorlesung 02: [pdf]
• Vorlesung 03: [pdf]
• Vorlesung 04: [pdf]
• Vorlesung 05: [pdf]
• Vorlesung 06: [pdf]
• Vorlesung 07: Kapitel 4.D im Skript
• Vorlesung 08: [pdf]
• Vorlesung 09: [pdf]
• Vorlesung 10: [pdf]
• Vorlesung 11: [pdf]
• Vorlesung 12: [pdf]
• Vorlesung 13: [pdf]
• Vorlesung 14: Kapitel 9.D und 9.E im Skript
• Vorlesung 15: [pdf]
• Vorlesung 16: [pdf]
• Vorlesung 17: [pdf]
• Vorlesung 18: [pdf]
• Vorlesung 19: [pdf]

Große Übungen

• Übung 1: [pdf]
• Übung 2: [pdf] (Danke für den Mitschrieb!)
• Übung 3: [pdf]
• Übung 4: [pdf]

Hausaufgaben

• Blatt 1: [pdf] (Abgabe bis 05.05.25, 13 Uhr)
• Blatt 2: [pdf] (Abgabe bis 19.05.25, 13 Uhr)
• Blatt 3: [pdf] (Abgabe bis 02.06.25, 13 Uhr)
• Blatt 4: [pdf] (Abgabe bis 23.06.25, 13 Uhr) Stand 6.6.25: Bitte ladet euch das Blatt erneut herunter. In der letzten Aufgabe gab es einen Schreibfehler bzgl der Laufzeit.
• Blatt 5: [pdf] (Abgabe bis 07.07.25, 13 Uhr)

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

Neuigkeiten

Die Klausurergebnisse sind im TU Connect eingetragen. Eine uneindeutige Ergebnisliste kann HIER heruntergeladen werden. Als Code wurde der erste Buchstabe des Vornamens plus die letzte Ziffer der Matrikelnummer verwendet. (Das ist mit der eigenen Note zusammen oft eindeutig; nur im 5.0 Bereich nicht.) Weitere Statistiken zur Klausur gibt es HIER.

Die Evaluation ist da und kann HIER heruntergeladen werden. Die Ergebnisse werden voraussichtlich am 15.07. in der Vorlesung besprochen.

Klausur

Die Klausur findet am 22.07.25 um 08:00 Uhr im Audimax statt.

Bitte seid 15 Minuten vorher anwesend. Mitzubringen sind:

• Studierendenausweis
• Dokumentenechter Stift (u.a. kein Bleistift, Füller oder Rotstifte)
• Ein handschriftlich (nicht elektronisch oder über Tablet, o.Ä.), beidseitig beschriebenes Blatt DIN-A4.
• Wörterbuch (falls nötig) auf Papier ohne Notizen

Andere Hilfmittel sind nicht zugelassen. Papier wird von uns gestellt.

Klausureinsicht

Die Einsicht der Klausur findet am 07.08.25 ab 13:30 Uhr im Raum IZ 305 statt. Bitte bringt euren Studierendenausweis mit. Während der Einsicht darf nur die eigene Klausur eingesehen werden, d.h. Notizen, Fotos, Reden, usw. ist während der Einsicht nicht erlaubt. Fragen an uns dürfen natürlich gestellt werden.

Mailingliste

Es gibt eine Mailingliste zur Veranstaltung. Bitte registriert euch dort. Wir versenden darüber Informationen. Es werden nur tubs-Adressen freigegeben. Bei Problemen wendet euch per Mail an Arne Schmidt. Hier geht es zur [Mailingliste].