Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Seminar Aktuelle Themen der Theoretischen Informatik: Logik und Komplexität

Wintersemester 2023/24
 

Aktuelles

  • 16.01.24: am Mittwoch, den 17.01.24 findet kein Seminar-Vortrag statt; der Vortrag wird verschoben auf den 31.01.24.
  • 22.11.23: Ergänzung zu Thema 4: Eine etwas leichter zugängliche Einführung des Begriffs "Transduktion" findet sich in den Kapiteln 1.7.1 und 1.7.2 (Seiten 59-67) des Buchs "Graph Structure and Monadic Second-Order Logic — a Language Theoretic Approach" von Bruno Courcelle und Joost Engelfriet (Cambridge University Press 2012; eine Vorabversion findet sich hier: [LINK]).
  • Die Vorbesprechung und Themenvergabe fand in der zweiten Vorlesungswoche, am Mittwoch, den 25.10.2023, um 13:30-15:00 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.
  • Das Seminar wird in Präsenz durchgeführt.
  • Die Latex-Vorlage, mit der die Seminar-Ausarbeitungen erstellt werden sollen, finden Sie hier: [Link]

Thema

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Theoretischen Informatik, insbesondere der Logik und Komplexitätstheorie erarbeitet. Ziele sind das Kennenlernen neuer Forschungsergebnisse der Theoretischen Informatik, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Beweistechniken, sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.

Das Seminar richtet sich an fortgeschrittene Studierende in einem Masterstudiengang, die sich im Bereich Theoretische Informatik spezialisieren wollen. Die Teilnahme am Seminar setzt sehr gute und zumindest in einem der o.g. Bereiche auch tiefer gehende Kenntnisse der Theoretischen Informatik voraus.

Ort & Zeit

Zeit und Raum
mittwochs, 13:30-15:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408.
Dozentin:
Prof. Dr. Nicole Schweikardt

Themen

Dieses Seminar richtet sich an Studierende, die bereits das Modul "Logik und Komplexität" absolviert haben oder sich anderweitig vergleichbare Vorkenntnisse erarbeitet haben.

Konkrete Themen, die im Seminar behandelt werden:

 

Literatur

[Grohe]

Martin Grohe, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017. [Link]
[Libkin] Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004. [Link]