Theoretische Informatik 2

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

Vorlesungen und Übungen

• [Skript] aus dem Sommer 2024

Hausaufgaben

• Blatt 1: [pdf] (Abgabe bis 04.05., 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

• Bitte meldet euch auf der [Mailingliste] an.
• Die Einteilung in die Übungsgruppen wurde per Mail versandt. Solltet ihr keine Mail erhalten haben, sende bitte eine Mail an Arne Schmidt. Ein Gruppentausch ist in der Regel nur mit einem Tausch einer anderen Person möglich.

Klausur

Die Klausur findet am 25.08. um 10:30 Uhr statt. Die Raumaufteilung wird 1-2 Tage vorher an dieser Stelle bekanntgegeben.

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.

Eine "Muster"-Klausur ist verfügbar: [pdf]

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