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)
• Blatt 2: [pdf] (Abgabe bis 18.05., 13 Uhr)
• Blatt 3: [pdf] (Abgabe bis 08.06., 13 Uhr)
• Blatt 4: [pdf] (Abgabe bis 22.06., 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 Vorlesung am 15.06. fällt krankheitsbedingt aus
• Die Übung der Gruppe 05 (Jan Wasserscheidt, Fr. 09:45 Uhr) verschiebt sich vom 19.06. auf 26.06.
• Die kleinen Übungen am Donnerstag, den 14.05., verschieben sich aufgrund des Feiertags um eine Woche nach hinten auf den 21.05.
• 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 mit ausgewähltem Aufgabenpool ist verfügbar: [pdf]

Hinweise zur Klausur

Die Klausur geht insgesamt 120 Minuten und es sind 100 Punkte erreichbar. Sie ist allerdings als Überhangsklausur konzipiert, das heißt, man muss nicht jede Aufgabe lösen, um eine gute Note zu erhalten! Mit 40 Punkten hat man sicher bestanden. Bearbeitet die Klausur nicht einfach von vorn nach hinten, sondern schaut, welche Aufgaben einem am besten liegen und bearbeitet diese zuerst.

Die Klausur wird 5 Teilgebiete mit jeweils 20 Punkten beinhalten, die ggf auf verschiedene Aufgaben aufgeteilt werden können. Die 5 Teilgebiete sind die folgenden:

• Turing-Maschinen und Grammatiken (z.B. Modellieren, Analysieren)
• (Un-)Entscheidbarkeit (z.B. Reduktionen, PCP, SvR, ...)
• Komplexität 1 (L/NL oder P/NP) (z.B. Analyse, Reduktionen, Membership, Hardness, ...)
• Komplexität 2 (P/NP oder PSPACE/NPSPACE) (z.B. Analyse, Reduktionen, Membership, Hardness, ...)
• Weiterführendes (z.B. Einordnung neuer Komplexitätsklassen, Simulation von Turing Maschinen, ...)

Da ein Cheat-Sheet in die Klausur genommen werden darf, werden wenige bis gar keine Wissensfragen in der Klausur vorkommen. Der Fokus liegt auf Verständnisfragen, dem Anwenden von Theoremen und Algorithmen, sowie Transferwissen.

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