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

Aktuelles

• 30.6.20: Unter dem Punkt Prüfung stehen nun Informationen zur Modulabschlussprüfung zur Verfügung.
• Die Online-Treffen zur Übung am 23.6. und am 30.6. finden ausnahmsweise um 18:15-19:45 Uhr statt.
• Ende Mai: Die Zugangsdaten zu den Zoom-Meetings für die Online-Treffen zur Vorlesung und Übung haben sich geändert. Bitte nutzen Sie die Moodle-Plattform, um Zugang zu den Meetings zu erhalten.
• 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.

• Kapitel 0: Einleitung
• Kapitel 1: Grundlagen und der Satz von Trakhtenbrot
• Kapitel 2: Logik zweiter Stufe und die Sätze von Büchi und Fagin (handschriftliche Notizen: Teil 1, Teil 2)
• Kapitel 3: Ehrenfeucht-Fraisse Spiele (Abschnitte 3.1 bis 3.5: Skript und Folien, handschriftliche Notizen: Satz von Hanf, Ajtai-Fagin Spiel, Satz von Fraisse)
• Kapitel 4: 0-1-Gesetze
• Kapitel 5: Fixpunktlogiken und der Satz von Immerman und Vardi (handschriftliche Notizen (alle Nummerierungen der Form "4.xy" sind hier durch "5.xy" zu ersetzen))

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)

Übungsleitung: Jens Keppeler (bis Ende Mai); Nicole Schweikardt (ab Juni)

Ü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)
• Blatt 5 (ausgegeben am 26.05.; abzugeben bis 02.06. 15:00 Uhr über Moodle)
• Blatt 6 (ausgegeben am 02.06.; abzugeben bis 09.06. 15:00 Uhr über Moodle)
• Blatt 7 (ausgegeben am 09.06.; abzugeben bis 16.06. 15:00 Uhr über Moodle)
• Blatt 8 (ausgegeben am 16.06.; abzugeben bis 23.06. 15:00 Uhr über Moodle)
• Blatt 9 (ausgegeben am 23.06.; abzugeben bis 30.06. 15:00 Uhr über Moodle)
• Blatt 10 (ausgegeben am 30.06.; abzugeben bis 07.07. 15:00 Uhr über Moodle)
• Blatt 11 (ausgegeben am 07.07.; abzugeben bis 14.07. 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 — Covid-19-bedingt digital über Zoom. Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Pergl angefragt werden: es stehen Prüfungstermine am 23.07.20 und am 9.10.20 zur Verfügung.

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

Links