Komplexität und Logik (Seminar)

Die Veranstaltung wird zunächst online beginnen. Der Link wird über Moodle mitgeteilt.
Im Laufe des Semesters wird die Veranstaltung dann voraussichtlich in Präsenz durchgeführt. Dies wird rechtzeitig bekannt gegeben.

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
 
Termine

Di., 16:00 – 18:00 Uhr

Vortragsplan für das Semester

24.05.2022 Benjamin Böhm: Einführung

14.06.2022 Markus Schlegel: Lineare Codes

21.06.2022 Maximilian Stock: Hamming-Codes

28.06.2022 Anne Götz: Reed-Muller-Codes

12.07.2022 Thomas Fischer: Faltungscodes

Literatur		 Computational Complexity: A Modern Approach Sanjeev Arora, Boaz Barak Cambridge University Press, 2009

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