Theoretische Informatik 2

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

Vorlesungen

• Vorlesung 0: [pdf]
• Vorlesung 1: [pdf]
• Vorlesung 2: [pdf]
• Vorlesung 3: [pdf]
• Vorlesung 4: [pdf]

Große Übungen

• Demnächst

Hausaufgaben

• Blatt 1: [pdf] (Abgabe bis 05.05.25, 13 Uhr)

• [Skript] aus dem Sommer 2024
• 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.

Klausur

Die Klausur findet voraussichtlich am 22.07.25 um 08:00 Uhr statt. Die Raumaufteilung wird spätestens einen Tag vor der Klausur bekanntgegeben. Bitte seid 15 Minuten vorher anwesend. Mitzubringen sind:

• Studierendenausweis
• Dokumentenechter Stift (u.a. kein Bleistift, Füller oder Rotstifte)
• Wörterbuch (falls nötig) auf Papier ohne Notizen

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

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