Seminar Logik in der Informatik

Seminar im SoSe 2010

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung des Seminars durch Dipl.-Inf. André Frochaux, Dr. Dominik D. Freydenberger, M.Sc. Frederik Harwath, Dipl.-Inf. Lucas Heimberg, Dr. Mariano Zelke, Prof. Dr. Nicole Schweikardt

Aktuelles

• Terminänderung: Am 23.6.2010 findet kein Vortrag statt. Dafür werden am 30.6.2010 zwei Vorträge stattfinden, und zwar von 14-16 Uhr und von 16-18 Uhr.
• Eine Vorlage zur Anfertigung der Seminarausarbeitung im LaTeX-Format finden Sie hier.
• Der erste Seminartermin (mit Vorbesprechung und Themenvergabe) fand am Mittwoch, den 21.04.2010, 14h15-15h45 in Raum SR 9 statt.
• Das Seminar findet i.d.R. Mittwochs 14h15-15h45 in Raum SR 9, Robert-Mayer-Str. 11-15 statt.

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.  Creditpoints: 4.  SWS: 2 S.

Inhalte

Im SoSe 2010 wollen wir im Seminar "Logik in der Informatik" Teile des folgenden Buchs durcharbeiten:

• Howard Straubing: "Finite Automata, Formal Logic, and Circuit Complexity" (Birkhäuser, 1994)

Vortragsthemen

1. Monadische Logik zweiter Stufe, reguläre Sprachen und reguläre numerische Prädikate.
   Material: Kapitel III.1 und III.2 (Seiten 21-28), Exercises 1 und 2 (Seite 35) und Chapter Notes bzgl. III.1-III.2 (Seite 37)
2. Unendliche Worte und entscheidbare Theorien.
   Material: Kapitel III.3 (Seiten 28-35), Exercises 4 und 5 (Seite 36) und Chapter Notes bzgl. III.3 (Seite 37)
3. Das Ehrenfeucht-Fraïssé Spiel und seine Anwendung auf FO[<].
   Material: Kapitel IV.1 und IV.2 (Seiten 39-46), Exercises 1 und 3 (Seite 51) und Chapter Notes bzgl. IV.1-IV.2 (Seite 52)
4. Eine Anwendung des Ehrenfeucht-Fraïssé Spiels auf FO[+1].
   Material: Kapitel IV.3 (Seiten 46-50), Exercises 2 und 4 (Seite 51) und Chapter Notes bzgl. IV.3 (Seite 52)
5. Das syntaktische Monoid und seine Berechnung.
   Material: Kapitel V.1 und V.2 (Seiten 53-59), Exercises 1 und 2 (Seite 76) und Chapter Notes bzgl. V.1-V.2 (Seiten 77-78)
6. Aperiodische endliche Monoide, FO[<] und semidirekte Produkte.
   Material: Kapitel V.3 und V.4 (Seiten 59-66), Exercises 3 und 6 (Seite 76) und Chapter Notes bzgl. V.3-V.4 (Seiten 77-78)
7. Kategorien und Pfad-Bedingungen.
   Material: Kapitel V.5 (Seiten 66-72), Exercise 7 (Seite 76) und Chapter Notes bzgl. V.5 (Seiten 77-78)
8. Pseudo-Varietäten.
   Material: Kapitel V.6 (Seiten 72-76), Exercises 4 und 5 (Seite 76) und Chapter Notes bzgl. V.6 (Seiten 77-78)
9. Eine Charakterisierung von FO[<] und eine Hierarchie in FO[<].
   Material: Kapitel VI.1 und VI.2 (Seiten 79-88), Exercise 3 (Seite 98) und Chapter Notes bzgl. VI.1-VI.2 (Seite 98)
10. Eine Charakterisierung von FO[+1] und Sätze mit regulären numerischen Prädikaten.
    Material: Kapitel VI.3 und VI.4 (Seiten 89-97), Exercise 1 und 2 (Seite 97) und Chapter Notes bzgl. VI.3-VI.4 (Seite 98)

Verbindliche Regeln zum Erwerb eines Scheins bzw. Bestehen des Moduls

Um das Modul zu bestehen bzw. einen Schein zu erwerben, sind nötig:

1. Einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 75 Minuten, plus 15 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
2. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas (abzugeben: spätestens 3 Wochen nach dem Halten des Vortrags; Layout: wie in der Layout-Vorlage angegeben) und
3. Anwesenheit bei mindestens 75% aller Termine.

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 3 Fälle eintritt, so ist die Gesamtnote eine 5.0 und es wird kein Seminarschein erteilt bzw. das Modul wird als "nicht bestanden" gewertet:
  1. Der Teilnehmer war an weniger als 75% der Termine 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.
• Falls keiner der obigen 3 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.

Termine

Die einzelnen Termine des Seminars Logik in Informatik finden Sie hier.

Literatur

[Straubing]	Howard Straubing: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, 1994.