Komplexität und Logik Seminar

Modultitel (deutsch)

Komplexität und Logik Seminar

Modultitel (englisch)

Complexity and Logic

Modul-Verantwortliche/r

Olaf Beyersdorff

Zusammensetzung des Moduls / Lehrformen  (V, Ü, S, Praktikum, …)

2 S

Leistungspunkte (ECTS credits)

3 LP

Inhalte

Seminar zu wechselnden aktuellen Themen der Logik in der Informatik

Typische Themen sind:

• Verschiedene Logiken: Aussagenlogik, erststufige Logik, QBF, modale, intuitionistische Logiken etc.
• Komplexität dieser Logiken
• Beweiskalküle der Logiken
• Algorithmische Aspekte
• SAT- und QBF Solver
• Beweiskomplexität
• Berechnungskomplexität
• Algebraische Beweissysteme

Di., 16:00 – 18:00 Uhr

03. November 2020:
Einführung: Solving und Beweiskomplexität, Olaf Beyersdorff

10. November 2020:
CDCL und QCDCL, Benjamin Böhm 

17. November 2020:
Symmetrien und Homomorphismen in SAT und QBF, Agnes Schleitzer

24. November 2020:
Dies Academicus

01. Dezember 2020:
Tomas Peitl: Symmetry breaking

08. Dezember 2020:
CNF encodings (Handbook Ch. 2), Herr Haas

15. Dezember 2020:
MaxSAT (Handbook Ch. 19), Herr Wenig

05. Januar 2021

12. Januar 2021:
Further SAT algorithms (ST Ch. 6), Herr Legner

19. Januar 2021:
Local Search (ST Ch. 5), Herr Würflein

26. Januar 2021:
Application: Planning (Handbook Ch. 15), Herr Landmann

02. Februar 2021:
Application: Bounded Model Checking (Handbook Ch. 14)

09. Februar 2021:
Application: Software Verification (Handbook Ch. 16)

[ST] Das Erfüllbarkeitsproblem SAT: Algorithmen und Analysen
Uwe Schöning, Jacobo Toran
Lehmanns, 2012

[Handbook] Handbook of Satisfiability
Editors Biere, A., Heule, M., Van Maaren, H., Walsh, T.
IOS Press, 2009