LFU:online

Absolvent:innen dieses Moduls haben ein Verständnis dafür, wie Zeit- und Platzbedarf von Entscheidungsproblemen formal definiert werden können. Sie kennen die grundlegenden Komplexitätsklassen (P, NP, coNP, PSPACE, etc.) und wie sie zueinander in Zusammenhang stehen und warum. Sie kennen ebenfalls einige wichtige Fragen hierzu, die noch offen sind. Sie kennen repräsentative Probleme für jede Klasse und sind in der Lage, zu argumentieren, warum ein Problem in einer bestimmten Klasse ist oder vollständig für diese Klasse ist.

Berechnungsmodelle; Zeit- und Platzbedarf von Turingmaschinen; Berechnungen in polynomieller Zeit (P, NP, coNP); NP-Vollständigkeit (SAT, 3-SAT, Karps Probleme, Satz von Cook–Levin); Platzklassen und der Satz von Savitch; PSPACE, TQBF, die polynomielle Hierarchie, Alternierung; logarithmische Platzklassen (L und NL); Hierarchiesätze; ausgewählte fortgeschrittene Themen (z.B. Schaltkreiskomplexität, Orakel und Relativisierung, probabilistische Klassen, interaktive Beweise)

Präsentation mit Folien und Tafel. Der Kurs orientiert sich stark an zwei Lehrbüchern (siehe Webseite).

Wöchentliche Hausübungen, deren Lösungen zusammen diskutiert werden.

Gewichtetes Mittel aus Punkten durch wöchentliche Hausaufgabenabgabe und einer schriftlichen Prüfung. Es wird keine Wiederholungsklausur angeboten.

M. Sipser, Introduction to the Theory of Computation, 2014.
S. Arora & B. Barak, Computational Complexity: A Modern Approach, 2007.
D. C. Kozen, Theory of Computation, 2006.

Die Module ‘Einführung in die Theoretische Informatik’ und ‘Diskrete Strukturen’ müssen bestanden sein. Zusätzlich ist es empfehlenswert (wenn auch nicht zwingend notwendig), die ‘Logik’-Vorlesung besucht zu haben.

Insbesondere sollten Student:innen die folgenden Fähigkeiten/das folgende Wissen aufweisen, um in der Vorlesung gut zurechtzukommen:

• Gutes Verständnis von mathematischer Notation, Fähigkeit zum mathematischen Denken, etc.
• Gutes Verständnis grundlegender diskreter Mathematik (weiß, was eine Relation ist, hat schon einmal von Graphfärbung gehört, etc.)
• Vertrautheit mit Aussagenlogik und Prädikatenlogik
• Turingmaschinen
• Kenntnisse über formale Sprachen, Automaten, reguläre Ausdrücke können nützlich sein.

Verfahren zur Vergabe der Plätze bei Lehrveranstaltungen mit Teilnahmebeschränkung (PS, SE, VU, PJ)

Bei Lehrveranstaltungen mit einer beschränkten Zahl von Teilnehmerinnen und Teilnehmern werden die Plätze wie folgt vergeben:

1. Studierende, denen aufgrund der Zurückstellung eine Verlängerung der Studienzeit erwächst, sind bevorzugt zuzulassen.

2. Reicht Z 1 zur Regelung der Zulassung zu einer Lehrveranstaltung nicht aus, so sind an erster Stelle Studierende, für die diese Lehrveranstaltung Teil eines Pflichtmoduls ist, und an zweiter Stelle Studierende, für die diese Lehrveranstaltung Teil eines Wahlmoduls ist, bevorzugt zuzulassen.

3. Reichen Z 1 und 2 zur Regelung der Zulassung zu einer Lehrveranstaltung nicht aus, so werden die vorhandenen Plätze verlost.

Curriculum BA Informatik 2019W