Aktuelles | Inhalte | Vortragsthemen | Verbindliche Regeln zum Erwerb eines Scheins bzw. Bestehen des Moduls | Literatur  

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

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:

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:

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.