Algorithmisches Beweisen (Vorlesung)
Die Folien zu dieser Vorlesung finden Sie hier.
|
Modultitel (deutsch) |
Algorithmisches Beweisen |
|
Modultitel (englisch) |
Proof Complexity and Solving |
|
Modul-Verantwortliche/r |
Olaf Beyersdorff |
|
Empfohlene bzw. erwartete Vorkenntnisse |
FMI-IN0001 Algorithmen und Datenstrukturen FMI-IN0005 Automaten und Berechenbarkeit |
|
Art des Moduls (Pflicht-, Wahlpflicht- oder Wahlmodul) |
Wahlpflichtmodul (TIA, ALG) für den M.Sc. Informatik Wahlpflichtmodul für den B.Sc. Informatik Wahlpflichtmodul (Bereich Informatik) für den M.Sc. Bioinformatik Wahlpflichtmodul (Angewandte Mathematik, Vertiefung Algorithmik, Nebenfach Informatik) für den M.Sc. Mathematik Wahlpflichtmodul (Nebenfach Informatik) für den B.Sc. Mathematik Wahlpflichtmodul für den B.Sc. Wirtschaftswissenschaften, Schwerpunkt IMS[External link Wahlpflichtmodul für den B.A. Ergänzungsfach Informatik |
|
Dauer des Moduls |
1 Semester |
|
Zusammensetzung des Moduls / Lehrformen (V, Ü, S, Praktikum, …) |
4 V +2 Ü |
|
Leistungspunkte (ECTS credits) |
6 LP |
|
Inhalte |
Einführung in die Beweiskomplexität und algorithmische Aspekte von SAT mit den Themen:
|
|
Lern- und Qualifikationsziele |
Vertiefte Kenntnisse in Theoretischer Informatik, Logik und der algorithmischen Lösung von Erfüllbarkeitsproblemen. Befähigung zur beweistheoretischen Einordnung konkreter Formelklassen Kenntnisse über Techniken zum Nachweis unterer Schranken Einsichten in Chancen und Grenzen moderner SAT-Solver |
|
Empfohlene Literatur |
Uwe Schöning, Jacobo Toran: Das Erfüllbarkeitsproblem SAT, Lehmanns 2012 Jan Krajicek: Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge University Press, 1995 Stasys Jukna: Boolean Function Complexity, Springer 2012 |