Seminar Logik in der Informatik - Logik

Seminar im SoSe 2014

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung des Seminars durch Dipl.-Inf. Lucas Heimberg

Aktuelles

Das Seminar findet am 30.7.2014 von 10:00-16:00 Uhr in SR 11 (an Stelle von R 117) statt. Von 13:00-14:30 Uhr ist eine Mittagspause geplant.
Mittwoch, den 30.04.2014, 13:15-15:00, Raum 117:
Vorbesprechung, Anmeldung, Themenvergabe und Festlegung weiterer Termine

Einführung

Im Seminar werden aktuelle Themen aus dem Bereich Logik in der Informatik behandelt.
Lernziele: Kenntnis grundlegender Methoden und Verfahren, Einübung von Literatursuche und -analyse sowie Präsentationstechniken. Theoretische Kompetenz; autodidaktische Kompetenz.

Kürzel laut Studienordnung: B-LI-BS, M-LI-S, Bioinf Modul 21, MaM-LOG-gs. Creditpoints: 5 (4 in MaM-LOG-gs). SWS: 2 S.

Ort und Zeit

Das Seminar ist als Blockseminar organisiert. Das Seminar findet i.d.R. in Raum 117, Robert-Mayer-Str. 11-15 statt.
Termine:

Mittwoch, den 30.04.2014, 13:15-15:00, Raum 117:
Vorbesprechung, Anmeldung, Themenvergabe und Festlegung weiterer Termine
"Deadline 1": bis spätestens Freitag, 13.6.2014:
Treffen jedes Seminarteilnehmers mit einem der Organisatoren des Seminars: Klärung von Detailfragen zum Vortragsthema und Vorlage eines groben Konzepts zum Vortrag und zur schriftlichen Ausarbeitung des Vortragsthemas
"Deadline 2": bis spätestens Dienstag, 1.7.2014:
Abgabe der schriftlichen Ausarbeitung des Vortragsthemas bei den Organisatoren des Seminars (Layout: wie in der Layout-Vorlage angegeben)
"Deadline 3": bis spätestens Dienstag, 22.7.2014:
Treffen jedes Seminarteilnehmers mit einem der Organisatoren des Seminars: Vorlage eines detaillierten Vortragskonzepts inkl. Vortragsfolien
Mittwoch, 30.7.2014, 10:00-16:00:
Blockseminar mit Vorträgen der am Seminar teilnehmenden Studierenden (in Raum 117)

Unterstützung

Während der Vorlesungszeit stehen jeden Mittwoch von 15:00 bis 15:45 Termine bei Nicole Schweikardt zur Verfügung, während denen Seminarteilnehmer Fragen zur Literatur klären können. Falls Sie einen solchen Termin wahrnehmen wollen, melden Sie sich bitte spätestens am Tag vorher per Email an.

Einige generelle Informationen darüber, wie man gute Vorträge im Fach Informatik halten kann, finden sich hier.

Einführende Literatur

Zur Vorbereitung aufs Seminar wird empfohlen, die Logik-Kapitel der Vorlesung Diskrete Modellierung sowie einige grundlegende Kapitel der Vorlesung Logik in der Informatik durchzuarbeiten.

Vortragsthemen und Literatur

Classifying Regular Events in Symbolic Logic (Wolfgang Thomas 1980)
Insbes.: Kapitel 1, Kapitel 5, Kapitel 2 - und für Studierende in einem Master-Studiengang auch Kapitel 3.
Betreuerin: Nicole Schweikardt
First-order queries on structures of bounded degree are computable with constant delay (Arnaud Durand, Etienne Grandjean 2007)
Insbes.: Kapitel 1, Kapitel 2.1 ohne 2.1.1, Kapitel 2.2 - und für Studierende in einem Master-Studiengang auch Kapitel 3.1 und 3.2.
Betreuerin: Nicole Schweikardt
Enumerating Answers to First-Order Queries over Databases of Low Degree (Arnaud Durand, Nicole Schweikardt, Luc Segoufin 2014) - Vergeben
Insbes.: Kapitel 1-3.
Betreuerin: Nicole Schweikardt
Shrinking Games and Local Formulas (H. Jerome Keisler, Wafik Boulos Lotfallah 2003)
Insbes.: Kapitel 1-5.
Betreuer/in: TBA
An existential locality theorem (Martin Grohe, Stefan Wöhrle 2001) - Vergeben
Insbes.: Kapitel 1-3.
Betreuerin: Nicole Schweikardt
An optimal construction of Hanf sentences (Benedikt Bollig, Dietrich Kuske 2012)
Zusätzliches Material: Appendix A von "An optimal Gaifman normal form construction for structures of bounded degree" (Lucas Heimberg, Dietrich Kuske, Nicole Schweikardt 2013).
Betreuer/in: TBA
Counting modulo quantifiers on finite structures (Juha Nurmonen 2000), Teil 1: Nurmonens Verallgemeinerung des Satzes von Hanf für Modulo-Zählquantoren
Insbes.: Kapitel 1-3.
Betreuer/in: TBA
Counting modulo quantifiers on finite structures (Juha Nurmonen 2000), Teil 2: Anwendungen
Insbes.: Kapitel 4-6.
Betreuer/in: TBA
On Preservation under Homomorphisms and Unions of Conjunctive Queries (Albert Atserias, Anuj Dawar, Phokion Kolaitis 2006) - Vergeben
Insbes.: Kapitel 1, Kapitel 2.1 und 2.2, Kapitel 3, Kapitel 4.
Betreuer: Lucas Heimberg
Homomorphism preservation on quasi-wide structures (Anuj Dawar 2010) - Vergeben
Insbes.: Kapitel 1-3 und 5.
Betreuer: Lucas Heimberg
Preservation under extensions on well-behaved finite structures (Albert Atserias, Anuj Dawar, Martin Grohe 2008), Teil 1: Azyklische Strukturen
Insbes.: Kapitel 1-3.
Betreuer/in: TBA
Preservation under extensions on well-behaved finite structures (Albert Atserias, Anuj Dawar, Martin Grohe 2008), Teil 2: "Weite" Strukturen und planare Graphen
Insbes.: Kapitel 4 und 6.
Betreuer/in: TBA

Verbindliche Regeln zum Bestehen des Moduls

Um das Modul zu bestehen sind nötig:

Einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas; Layout: wie in der Layout-Vorlage angegeben,
Anwesenheit bei mindestens 75% aller Vorträge und
Einhalten der drei oben genannten Deadlines.

Es werden eine Note für den Vortrag und eine Note für die schriftliche Ausarbeitung vergeben. Die Gesamtnote setzt sich folgendermaßen zusammen:

Falls einer der folgenden 4 Fälle eintritt, so ist die Gesamtnote eine 5.0 und das Modul wird als "nicht bestanden" gewertet:
1. Der Teilnehmer war an weniger als 75% der Vorträge anwesend.
2. Der Teilnehmer erhielt für seinen Vortrag die Note 5.0.
3. Der Teilnehmer erhielt für seine schriftliche Ausarbeitung die Note 5.0.
4. Der Teilnehmer hat mindestens eine der drei oben genannten Deadlines nicht eingehalten.
Falls keiner der obigen 4 Fälle eintritt, so wird ein Seminarschein erteilt bzw. das Modul wird als "bestanden" gewertet, und die Gesamtnote setzt sich zu 2/3 aus der Note für den Vortrag und zu 1/3 aus der Note für die schriftliche Ausarbeitung zusammen.