Proseminar: Theoretische Informatik

Prüfungsleistung

• Aktive Teilnahme an der Proseminarsitzung
• Hand-ins for the elaboration and the slides before the respective deadlines
• Preparation and presentation of a 30-minute talk about the assigned topic
• Preparation of a written elaboration of the assigned topic (15 pages, LaTeX, LNCS Style)

Ein Proseminar ist ausgerichtet auf die Präsenation von wissenschaftlichen Ergebnissen, aber es soll auch Kompetenzen für die wissenschaftliche Arbeit vermitteln. Insbesondere

• Literaturrecherche
• Lesen und Verstehen von wissenschaftlichen Texten
• Vorbereiten einer wissenschaftlichen Präsentation
• Halten einer Präsentation
• Anfertigen einer schriftlichen Ausarbeitung

Ablauf

Abgaben sollten jeweils am Morgen des folgenden Tages vorliegen. Sie sollten per Email an die verantwortliche Person geschickt werden.

1. Vorbesprechung (Treffen): Mo, 23.10.2017
2. Themenvergabe: Mo, 30.10.2017
3. Abgabe erste Version der Ausarbeitung: Mo, 27.11.2017
4. Abgabe erste Version der Folien: Mo, 04.12.2017
5. Abgabe endgültige Version der Ausarbeitung: Mo 12.02.2018
6. Abgabe endgültige Version der Folien: jeweils eine Woche vor Präsentation
7. Präsentation: je zwei Vorträge am 22.01.18 und am 05.02.2018, jeweils montags um 10ct

Ausarbeitung

Die Ausarbeitung sollte maximal 15 Seiten umfassen. Sie muss erstellt werden mit

Verwenden Sie diese Klasse gemäß des Musterdokuments, das auf der Webseite Information for Authors verfügbar ist. Verwenden Sie bibtex für Referenzen. Eine Anleitung finden Sie auf der o.g. Webseite unter Author Guidelines.

Die erste Version der Ausarbeitung ist fällig am 27.11.2017.

Themen

Grundlage des Proseminars ist das Buch "Automatentheorie und Logik" von Hofmann und Lange. Ein Vortrag entspricht in etwa einem Abschnitt im Buch vom Umfang etwa einer Vorlesungsstunde. Das Buch ist online und auch in der TF-Bibliothek verfügbar. Für Studenten, die gleichzeitig Informatik III hören, sind folgende Abschnitte als Grundlagen für einen Vortrag geeignet, wobei die Themen in Klammern einen etwas höheren Schwierigkeitsgrad haben:

• 2 Schwache Monadische Logik zweiter Stufe
• 3 Alternierende endliche Automaten
• 5 Automaten auf unendlichen Wörtern
• (6 Komplementierung von Büchiautomaten)
• 7 Weitere Akzeptanzbedingungen
• (10 Alternierende Automaten)
• (11 Linearzeit-Temporale Logik)
• 12 Automaten auf endlichen Bäumen

Presentation Schedule

Die Teilnahme ist verpflichtend.

• Mo 22.01.2018: Alternierende endliche Automaten, Automaten auf unendlichen Wörtern
• Mo 05.02.2018: Automaten auf endlichen Bäumen