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

Aktuelles

• Die Vorlesung am 27.6.24 findet statt.
• 19.6.24: Wir haben Hinweise zur Prüfungsanmeldung ergänzt.
• Am Dienstag, den 18.6.24 wird an Stelle der Übungsstunde eine zusätzliche Vorlesungsstunde stattfinden.
• Am Dienstag, den 4.6.24 fand an Stelle der Übungsstunde eine zusätzliche Vorlesungsstunde statt. Zum Ausgleich fand am Donnerstag, den 6.6.24 an Stelle der Vorlesungsstunde eine Übungsstunde statt.
• Das zu Beginn des Semesters angekündigte Präsenzübungsblatt entfällt; es wird durch ein normales Übungsblatt ersetzt.
• Am Dienstag, den 28.5.24 wird an Stelle der Übungsstunde eine zusätzliche Vorlesungsstunde stattfinden.
• Am Dienstag, den 14.5.24 wird an Stelle der Übungsstunde eine zusätzliche Vorlesungsstunde stattfinden.
• Am Dienstag, den 7.5.24 fällt die Vorlesung aus; die Übung findet statt!
• Am Dienstag, den 23.4.24 fällt die Vorlesung aus. Die Übung findet statt!
• Am Dienstag, den 23.4.24 fand die erste Übungsstunde statt.
• Die Eröffnungsvorlesung fand am Dienstag, den 16.04.24 ab 09:15 Uhr statt; direkt im Anschluss daran fand an Stelle einer Übungsstunde am 16.04.24 eine weitere Vorlesungsstunde stattt. Die erste Übungsstunde findet am Dienstag, den 23.04.2024 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

Die mathematische Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen, insbesondere der Ausdrucksstärke von formalen Sprachen und Beweissystemen sowie den Möglichkeiten und Grenzen des automatischen Schließens. In dieser Vorlesung werden ausgewählte Kapitel der mathematischen Logik und deren Anwendungen in der Informatik im Kontext von Lokalitätsresultaten behandelt.

Themen der Vorlesung sind u.a. die Sätze von Gaifman und Hanf und die Anwendung von Lokalitätsresultaten zum Nachweis von Nicht-Ausdrückbarkeitsresultaten und zum Beweis von algorithmischen Meta-Theoremen.

Die Vorlesung richtet sich an fortgeschrittene Studierende in einem Masterstudiengang, die sich im Bereich der Logik spezialisieren wollen. Voraussetzung für die Teilnahme an der Veranstaltung sind Kenntnisse, die in der Vorlesung "Logik in der Informatik" vermittelt werden.

Inhalte

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

• Kapitel 0: Einleitung und Grundbegriffe (handschriftliche Notizen)
• Kapitel 1: Hanf-Normalform und Hanf-Lokalität (handschriftliche Notizen)
• Kapitel 2: Feferman-Vaught Zerlegungen (handschriftliche Notizen)
• Kapitel 3: Gaifman-Normalform und Gaifman-Lokalität (handschriftliche Notizen)
• Kapitel 4: Untere Schranken für die Größe von Formeln in Normalform (handschriftliche Notizen)
• Exkurs zum Thema Baumzerlegungen (handschriftliche Notizen)
• Kapitel 5: Model-Checking für FO und FO+MOD auf Klassen von beschränkter lokaler Baumweite (handschriftliche Notizen, Teil 1)

Beachten Sie: In den Vorlesungsstunden 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 Vorlesungsstunden vermittelte Material durchzuarbeiten. Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

Logbuch

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

Termine

Vorlesung

Dienstags 09:00-11:00 im ESZ (Rudower Chaussee 26), Raum 1.303 und
Donnerstags 09:00-11:00 im ESZ (Rudower Chaussee 26), Raum 1.303

Dozentin: Prof. Dr. Nicole Schweikardt

Übung

Dienstags 11:00-13:00 im ESZ (Rudower Chaussee 26), Raum 1.303

Dozent: Benjamin Scheidt

Übungsblätter

Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben und in der darauf folgenden Woche in der Übungsstunde besprochen. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

• Blatt 1 (zu bearbeiten bis 30.4)
• Blatt 2 (zu bearbeiten bis 7.5)
• Blatt 3 (zu bearbeiten bis 21.5)
• Blatt 4 (zu bearbeiten bis 4.6)
• Blatt 5 (zu bearbeiten bis 11.6)
• Blatt 6 (zu bearbeiten bis 25.6)
• Blatt 7 (zu bearbeiten bis 2.7)

Prüfung

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

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Auf der Seite des Prüfungsbüros finden Sie den vollständigen Prüfungsplan (inkl. Prüfungszeitraum, Anmeldefristen).

Die Prüfungen im Juli 2024 (18.-19.7.) und Oktober 2024 (11.10.) für dieses Modul finden im Johann-von-Neumann-Haus (Rudower Chaussee 25) im Haus 3 in der 4. Etage statt. Die genaue Raumnummer erhalten Sie von uns per Mail.

Voraussetzung für die Zulassung zur Modulabschlussprüfung

1. Erreichen von mindestens 50 Prozent aller Übungspunkte — um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen — und
2. Erreichen von mindestens 40 Prozent der Punkte eines gesonderten Präsenzübungsblattes, welches in der Mitte des Semesters bearbeitet wird. TRUE

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 um 09:15, vor Beginn der Vorlesung am Dienstag, 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.

Hinweise zur Prüfungsanmeldung

Gehen Sie zur Prüfungsanmeldung bitte folgendermaßen vor:

1. Melden Sie sich zunächst in AGNES für die Prüfung an – die Frist für die Anmeldung zum 1. Prüfungszeitraum endet am 24. Juni 2024! Für jeden Prüfungstag gibt es eine separaten Eintrag. Melden Sie sich nur für einen der Tage an. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur Modulabschlussprüfung zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum 16.7.24 nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass dadurch Nachteile für Sie entstehen). Umgekehrt ist der 24. Juni 2024 eine harte Frist: Danach ist für den ersten Prüfungszeitraum keine Anmeldung mehr möglich!
2. Nach Ende der Anmeldefrist werden wir im Moodle-Kurs unter "Organisatorisches" ein Planer-Element freischalten, in dem Sie ein Zeitfenster an Ihrem Prüfungstag buchen; Sie müssen dies bis spätestens 4.7.24 tun. Klicken Sie hierfür im Planer für das gewünschte Zeitfenster auf "Zeitfenster buchen". Das von Ihnen gewählte Zeitfenster sollte dann oben auf der Seite angezeigt werden. Falls Sie sich verklickt haben, können Sie die Buchung mittels "Buchung abbrechen" rückgängig machen.
3. Nach Ihrer Buchung schicken wir Ihnen eine Mail an die in Moodle hinterlegte Mailadresse (für gewöhnlich Ihre CMS-Adresse), in welcher wir Ihnen Prüfungstag, -zeit und -raum mitteilen. Sie können dann Ihre Buchung in Moodle nicht mehr ändern.

WICHTIG: zur ordnungsgemäßen Anmeldung zur Prüfung ist beides nötig: eine fristgerechte Anmeldung in AGNES und die Vereinbarung eines konkreten Prüfungstermins.

Wenn Sie bis zum 4.7.24 kein Zeitfenster über Moodle gebucht haben, schicken wir Ihnen eine Mail mit einem von uns festgelegten Zeitfenster zu.

Die Frist zum Rücktritt von der Prüfung entnehmen Sie der Webseite des Prüfungsbüros. Falls ein fristgerechter Rücktritt in AGNES nicht möglich ist, wenden Sie sich bitte ans Prüfungsbüro.

Literatur

Zugang zur Online-Literatur

Einige der Bücher sind für Angehörige der HU Berlin online erhältlich (siehe Verlinkung). Loggen Sie sich dazu auf der Springerlink-Seite via Shibboleth mit ihrem CMS-Account ein (über Log In, Access via your institution bzw. Shibboleth-Login, 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