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
 
Termine

Di., 16:00 – 18:00 Uhr

Vortragsplan für das Semester

19.10.2021: Einführung: "Solving und Beweiskomplexität"
Olaf Beyersdorff

26.10.2021:  ,,Automatisieren von Resolution''
L. Spachmann

09.11.2021: Untere Schranken für QCDCL
B. Böhm

16.11.2021: Harte quantifizierte Formeln

A. Schleitzer

23.11.2021: Dies Academicus

30.11.2021: Kommunikationskomplexität: Grundlagen

(Kap. 1.1 + 1.2), Herr Conrad

07.12.2021: Kommunikationskomplexität: Rechtecke und Rang von Matrizen
(Kap. 1.3 + 1.4), Frau Gründel

14.12.2021: Kommunikationskomplexität: Nichtdeterminismus

(Kap. 2), Herr Quander

11.01.2022: Kommunikationskomplexität: Zufall - Teil 1

(Kap. 3), Herr Kasche

18.01.2022: Kommunikationskomplexität: Zufall - Teil 2

(Kap. 3), Herr Kasche

25.01.2022: Kommunikationskomplexität: Mehrparteien

(Kap. 6), Herr Tetkov

01.02.2022: Kommunikationskomplexität: Entscheidungsbäume und Datenstrukture

(Kap. 9), Herr Steinert

08.02.2022: Zusammenhang Beweis- und Kommunikationskomplexität

T. Hoffmann

Literatur		 Communication Complexity Eyal Kushilevitz, Noam Nisan  Cambridge University Press, 1997

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