Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

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

VL Logik und Komplexität

Aktuelles

  • Die Folien aus der Online-Sprechstunde zur Übung am 28.04. finden Sie hier.
  • Die Veranstaltung findet statt, bei Interesse melden Sie sich bitte über AGNES an.
  • Viele wichtige Informationen zur Veranstaltung finden Sie hier auf der Webseite, die regelmäßig aktualisiert wird. Ergänzend dazu werden manche Teile der Veranstaltung über die Moodle-Plattform durchgeführt; bitte schreiben Sie sich dort bis 24.04.2020 in den Kurs unter https://moodle.hu-berlin.de/enrol/index.php?id=95632 ein. Der Einschreibeschlüssel wird an die über AGNES eingeschriebenen Studierenden verschickt und kann auch per Mail an Jens Keppeler erfragt werden.
  • Auf Grund der aktuellen Situation wird die Veranstaltung online durchgeführt:
    Im Logbuch werden regelmäßig Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Di+Do 11-13 Uhr) finden Online-Treffen mittels Zoom statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird.
    Das erste solche Online-Treffen fand am Dienstag, den 28.04.2020 statt. Zugangsdaten erhalten Sie über Moodle.

Einführung

Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziertheit der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der Informatik eine Rolle, zum Beispiel in der Theorie formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang mit automatischer Verifikation.

Themen dieser Vorlesung sind beispielsweise:

  • Erweiterungen der Logik erster Stufe: Logik zweiter Stufe, Fixpunktlogiken
  • Automatentheorie und Logik: logische Charakterisierung der regulären Sprachen (z.B. die Sätze von Büchi und Doner, Thatcher & Wright)
  • deskriptive Komplexitätstheorie: logische Charakterisierungen von Komplexitätsklassen (z.B. die Sätze von Fagin und Immerman & Vardi)
  • Endliche Modelltheorie: Trennungsresultate zwischen logisch definierten Klassen endlicher Strukturen, 0-1-Gesetze

Ziel dieser Veranstaltung ist, den Zusammenhang zwischen der logischen Beschreibbarkeit und der Berechnungskomplexität von Problemen zu verstehen.


Inhalte

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.

Als Literatur werden Teile des Skripts [S-LuK] und der Bücher [L] und [EF] empfohlen.

 


Logbuch

Im Logbuch werden regelmäßig Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Di+Do 11-13 Uhr) finden Online-Treffen mittels Zoom statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird.
Das erste solche Online-Treffen fand am Dienstag, den 28.04.2020 statt. Zugangsdaten erhalten Sie über Moodle.


Termine

 

Vorlesung (Online-Treffen, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird)
Dienstags 11:00-13:00 und
Donnerstags 11:00-13:00
über zoom (Zugangsdaten sind über moodle erhältlich)

Dozentin: Prof. Dr. Nicole Schweikardt

 
Übung (Online-Treffen zur Besprechung der Übungsaufgaben)
Dienstags 15:00-17:00
über Zoom (Zugangsdaten sind über Moodle erhältlich)

Übungsleiter: Jens Keppeler


Übungsblätter

Ab dem 28.04.20 wird wöchentlich (jeden Dienstag) ein Übungsblatt hier online bereit gestellt. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

 

  • Blatt 1 (ausgegeben am 28.04.; abzugeben bis 05.05. 15:00 Uhr über Moodle)
  • Blatt 2 (ausgegeben am 05.05.; abzugeben bis 12.05. 15:00 Uhr über Moodle)
  • Blatt 3 (ausgegeben am 12.05.; abzugeben bis 19.05. 15:00 Uhr über Moodle)
  • Blatt 4 (ausgegeben am 19.05.; abzugeben bis 26.05. 15:00 Uhr über Moodle)

 

Die Folien aus der Online-Sprechstunde zur Übung am 28.04. finden Sie hier.


Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungen und Übungen vermittelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Pergl angefragt werden.

Voraussetzung für die Zulassung zur Prüfung ist:

  • Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen.

 

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden dienstags online bereit gestellt. Jedes Blatt enthält mehrere Aufgaben, die alle bis zur nächsten Übungsstunde zu bearbeiten sind. Eine Aufgabe auf jedem Blatt ist besonders gekennzeichnet als die Aufgabe, deren Lösung von jeder Teilnehmer*in schriftlich abzugeben ist. Die Abgabe einer Lösung erfolgt über Moodle in Form einer pdf-Datei; ob die Lösung mit LaTeX oder handschriftlich erstellt ist, ist egal - wichtig ist nur, dass sie gut lesbar ist und mit ausreichend breiten Rändern versehen ist, damit vom Übungsleiter Texte zur Korrektur und Bewertung auf der pdf-Datei eingefügt werden können. Die rechtzeitig und in der richtigen Form eingereichten Lösungen dieser Aufgabe werden vom Übungsleiter korrigiert und bewertet und bilden die Grundlage zum Erwerb der Zulassung zur Prüfung. 

 


Literatur

 

[L] Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004. Die für die Vorlesung relevanten Teile des Buchs sind unter dem mit "Download table of contents and a sample chapter" beschrifteten Link erhältlich.
[EF]

Heinz-Dieter Ebbinghaus und Jörg Flum. Finite Model Theory. Springer-Verlag, 2. Auflage, 1999. Für Angehörige der HU Berlin ist das Buch hier erhältlich: https://link.springer.com/book/10.1007/3-540-28788-4

Loggen Sie Sich dazu auf der Seite über Log InLog in via Shibboleth or Athens, bei Or, find your institution (via Shibboleth) über Humboldt Universität zu Berlin auf Log in via Shibboleth mit Ihrem CMS-Account ein.

[EFT] Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Einführung in die Mathematische Logik. 6. Auflage, Springer Spektrum, 2018.
Für Angehörige der HU Berlin ist das Buch online hier erhältlich: https://link.springer.com/book/10.1007%2F978-3-662-58029-5. Loggen Sie Sich dazu auf der Seite über Log In, Log in via Shibboleth or Athens, bei Or, find your institution (via Shibboleth) über Humboldt Universität zu Berlin auf Log in via Shibboleth mit Ihrem CMS-Account ein.
[FG] Jörg Flum und Martin Grohe, Parameterized Complexity Theory. Springer-Verlag, 2005.
[G] Martin Grohe, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017. LINK.. Springer-Verlag, 2005.
[I] Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999.
[S-LuK] Nicole Schweikardt, Skript zur Vorlesung "Logik und Komplexität" im Sommersemester 2007, Humboldt-Universität zu Berlin. Link
[S-LI] Nicole Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2014/15, Humboldt-Universität zu Berlin. Link
[F] E. Grädel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema und S. Weinstein, Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[G] E. Grädel, Finite Model Theory and Descriptive Complexity. Kapitel 3 des Buchs [F].
[K] P. Kolaitis, On the expressive power of logics on finite models. Kapitel 2 des Buchs [F].

 


 

[LICS] IEEE Symposium on Logic in Computer Science (LICS)
[EACSL] European Association for Computer Science Logic (EACSL)