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

Aktuelles  Einführung  Inhalte  Logbuch  Termine  Übungsblätter  Prüfung  Literatur  Links

Aktuelles

• 18.07.23: Die mündlichen Prüfungen (im Juli 2023 und im Oktober 2023) zum Modul "Logik und Komplexität" werden alle in Raum 3.408 im Johann von Neumann-Haus stattfinden.
• 08.06.23: Unter Prüfung gibt es neue Hinweise zu der Modulabschlussprüfung und zur Prüfungsanmeldung.
• Der 90-minütige Test, dessen Bestehen ein Teil der Voraussetzung zur Zulassung zur Modulabschlussprüfung ist, wurde am Dienstag, den 06.06.23 von 9:15 bis 10:45 Uhr geschrieben (in Präsenz in Raum 1'306 im ESZ).

• Die Eröffnungsvorlesung fand am Dienstag, den 18.04.2023 ab 09:15 Uhr statt. Die erste Übungsstunde fand am Dienstag, den 25.04.2023 im Anschluss an die Vorlesung statt.

• Die Veranstaltung wird in Präsenz durchgeführt.
• Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

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.

Beachten Sie: In den Vorlesungs- und Übungsstunden wird hauptsächlich an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten. Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

Logbuch

Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Termine

Die Eröffnungsvorlesung fand am Dienstag, den 18.04.2023 um 09:15 Uhr statt.

Vorlesung

Dienstags 09:15-11:00 im Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1´306 und
Donnerstags 11:15-13:00 im Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1´306

Dozentin: Prof. Dr. Nicole Schweikardt

Übung

Dienstags 11:00-13:00, Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1´306

Übungsleitung: Benjamin Scheidt

Übungsblätter

Ab der zweiten Vorlesungswoche wird  i.d.R. wöchentlich (jeden Dienstag) ein Übungsblatt bereit gestellt. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

Das aktuelle Übungsblatt wird jeweils hier ab Dienstag nachmittag online bereitgestellt.

• Blatt 1 (bereitgestellt am 25.04.23; zu bearbeiten bis 02.05.23)
• Blatt 2 (bereitgestellt am 02.05.23; zu bearbeiten bis 09.05.23)
• Blatt 3 (bereitgestellt am 09.05.23; zu bearbeiten bis 16.05.23)
• Blatt 4v2 (bereitgestellt am 16.05.23; zu bearbeiten bis 23.05.23) A4 wurde auf ein späteres Blatt verschoben.
• Blatt 5 (bereitgestellt am 23.05.23; zu bearbeiten bis 30.05.23)
• Blatt 6 (bereitgestellt am 30.05.23; zu bearbeiten bis 06.06.23)
• Blatt 7 (bereitgestellt am 13.06.23; zu bearbeiten bis 20.06.23)
• Blatt 8 (bereitgestellt am 20.06.23; zu bearbeiten bis 27.06.23)
• Blatt 9 (bereitgestellt am 27.06.23; zu bearbeiten bis 04.07.23)
• Blatt 10 (bereitgestellt am 04.07.23; zu bearbeiten bis 11.07.23)

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. 

Auf der Webseite des Prüfungsbüros finden Sie den vollständigen Prüfungsplan (inkl. Prüfungszeitraum, Prüfungsterminen und Anmeldefristen) und Hinweise zur Prüfungsan- und -abmeldung. Die Prüfungen im Modul "Logik und Komplexität" finden im Juli 2023 (18., 19., 20.7.23) und Oktober 2023 (11., 12.10.23) statt; Die Prüfungen für dieses Modul finden in Raum 3.408 statt.

Hinweise zur Prüfungsanmeldung:

1. Die Modulabschlussprüfung (kurz: MAP) wird als mündliche Prüfung durchgeführt. Dafür müssen Sie sich in AGNES anmelden – die Frist für die Anmeldung zum 1. Prüfungszeitraum endet am 25. Juni 2023! Direkt anschließend an Ihre Anmeldung in AGNES müssen Sie einen konkreten Prüfungstermin über den Lehrstuhl vereinbaren (per Email an Petra Kämpfer mit Dr. André Frochaux und Prof. Nicole Schweikardt in cc). Nennen Sie dabei bitte Ihren Namen, Matrikelnummer und das Modul ("Logik und Komplexität") und bitten Sie darum, einen konkreten Prüfungstermin (Tag und Uhrzeit) zugeteilt zu bekommen. Wichtig: zur ordnungsgemäßen Anmeldung zur MAP ist beides nötig: fristgerechte Anmeldung in AGNES und Vereinbarung eines konkreten Prüfungstermins.
2. In AGNES melden Sie sich zwar für den Dienstag, den 18.7.23 an, der Termin kann aber an einem beliebigen Tag innerhalb des Prüfungszeitraumes 18.-20.07.23 liegen und wird Ihnen vom Lehrstuhl zugeteilt.
3. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur MAP zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum Ende des Semesters nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass dadurch Nachteile für Sie entstehen). Umgekehrt ist der 25. Juni 2023 eine harte Frist: Danach ist keine Anmeldung mehr möglich!
4. Die Frist zum Rücktritt von der Prüfung entnehmen Sie der Webseite des Prüfungsbüros. Sollten Sie vor Ablauf der Frist zurücktreten wollen, AGNES Ihnen den Rücktritt jedoch nicht mehr ermöglichen (bspw. weil in AGNES der "Tag X" als Prüfungsdatum steht, Ihre Prüfung jedoch erst am "Tag X+1" stattfindet), melden sie sich per Mail an das Prüfungsbüro (mit Prof. Schweikardt im CC) von der Prüfung ab.

Voraussetzung für die Zulassung zur Modulabschlussprüfung

1. Bestehen eines 90-minütigen schriftlichen Tests, der am Dienstag, den 06.06.23 von 9:15 bis 10:45 Uhr geschrieben wurde und
2. 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 nach der Vorlesung online zur Verfügung gestellt. Das jeweilige Übungsblatt wird in der Übungsstunde der darauf folgenden Woche besprochen. Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:

• Variante A:
  Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde ab.
• Variante B:
  Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übungsstunde in eine vom Übungsleiter bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile) für gerechtfertigt halten. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein.

Literatur

Online-Zugang über VPN

Einige der Bücher sind für Angehörige der HU Berlin online erhältlich (siehe Verlinkung). Loggen Sie Sich dazu auf der Seite via Shibboleth mit ihrem CMS-Account ein (über Log In, Access via your institution, Find your institution: Humboldt Universität zu Berlin). Alternativ können Sie ggf. über eine VPN-Verbindung über das HU-Netz direkt darauf zugreifen. Zur Einrichtung eines VPN-Zugangs siehe die Anleitung des CMS.

Links