VI 23-001

Das Erfüllbarkeitsproblem - ein Triumph für die Theorie und für die Praxis

Vortragende/r:	Prof. Dr. Herbert Vollmer
Institution:	Leibniz Universität Hannover
Datum:	23. März 2019
Zeit:	08:30 - 09:15 Uhr
Raum:	F107

Dieser Vortrag gibt anhand des aussagenlogischen Erfüllbarkeitsproblems eine Einführung in zentrale aktuelle Fragestellungen der theoretischen Informatik, die auch in den Informatik-Unterricht an der Schule einfließen könnten.
Ich werde zunächst das Erfüllbarkeitsproblem SAT formal und anhand von Beispielen einführen. Sodann werde ich die Rolle von SAT im Zusammenhang mit der größten offenen Fragestellung der gesamten Informatik und Mathematik, dem P-NP-Problem, erläutern. Schließlich werde ich zeigen, wie man für interessante Spezialfälle erstaunlich einfach sehr effiziente Lösungsalgorithmen für SAT findet, die auch in der industriellen Praxis (Stichwort: SAT-Solver) eingesetzt werden.
Die angesprochenen Themen sind Schülerinnen und Schüler mit Interesse an mathematischen Fragestellungen vermittelbar und für den Schulunterricht geeignet.