| Name des Moduls | [65580] Algorithmisches Beweisen | Bezeichnung des Moduls | FMI-IN0158 |
| Studiengang | [079] - Informatik | ECTS Punkte | 6 |
| Arbeitsaufwand für Selbststudium | 90 | Häufigkeit des Angebotes (Modulturnus) | jedes 2. Semester (jährlich) |
| Arbeitsaufwand in Präsenzstunden | 90 | Dauer des Moduls | 1 |
| Arbeitsaufwand Summe (Workload) | 180 | ||
| Modul-Verantwortliche/r | Prof. Dr. Olaf Beyersdorff |
| Voraussetzung für die Vergabe von Leistungspunkten (Prüfungsform) | Klausur oder mündliche Prüfung (Festlegung erfolgt zu Beginn des Moduls) |
| 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 |
| Voraussetzung für die Zulassung zum Modul | keine |
| Empfohlene bzw. erwartete Vorkenntnisse | FMI-IN0001 Algorithmen und Datenstrukturen FMI-IN0005 Automaten und Berechenbarkeit |
| Art des Moduls (Pflicht-, Wahlpflicht- oder Wahlmodul) | - 079 B.A. Informatik: Wahlpflichtmodul |
| Zusammensetzung des Moduls / Lehrformen (V, Ü, S, Praktikum, …) | 4 SWS Vorlesung |
| 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 |
| Voraussetzung für die Zulassung zur Modulprüfung | Übungskriterien, die zum Veranstaltungsbeginn festgelegt werden |