Proseminar: Theoretische Informatik

Leitung:	Prof. Dr. Peter Thiemann
Zeit und Ort:	Blockseminar: nach Vereinbarung		Vorbesprechung am Mo 22.10.2018, 18:00, Raum 00-010/14, Geb. 101		Themenvergabe am Mi 31.10.2018, 13:00, Raum 101-01-016		Vorträge des Blockseminars: am 07.02.2019, 09.00-16.00 Uhr in Raum SR 00-019 im Gebäude 079.

Prüfungsleistung

Aktive Teilnahme an der Proseminarsitzung
Einreichen der Ausarbeitung und Folien zu den angegebenen Terminen
Vorbereitung und Halten eines 30-minütigen Vortrags über das vereinbarte Thema
Schriftliche Ausarbeitung zum vereinbarten Thema (15 Seiten, 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.

Vorbesprechung (Treffen): Mi 22.10.2018, 17:00, Raum 079-00-019
Themenvergabe (Treffen) : Mi, 31.10.2018, 13:00, Raum 101-01-016
Erstes Treffen mit dem Betreuer: bis zum 16.11.2018
Abgabe erste Version der Ausarbeitung: 16.12.2018
Abgabe erste Version der Folien: 23.12.2018
Abgabe endgültige Version der Ausarbeitung: 27.01.2019
Abgabe endgültige Version der Folien: 03.02.2019
Präsentation: 07.02.2019, 09.00-16.00, jeweils in Raum SR 00-019 im Gebäude 079

Ausarbeitung

Die Ausarbeitung sollte ca. 15 Seiten umfassen und insbesondere Beweise nach Absprache mit dem Betreuer enthalten. Sie muss erstellt werden mit

LaTeX, document class llncs.cls

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 04.06.2018.

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
(4 Sternfreie Sprachen)
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

Zuordnung der Vorträge

Die Teilnahme an den Vorträgen ist verpflichtend.

1a Brzozowski Ableitungen (Mari Hernaes)
1b Antimirov Ableitungen (Katsiaryna Mironava)
2 Schwache Monadische Logik zweiter Stufe (Najji Hendo)
3 Alternierende endliche Automaten (Louis Ngo)
5 Automaten auf unendlichen Wörtern (Gerhard Seemann)
7 Weitere Akzeptanzbedingungen (Serge Zürcher)
11 Linearzeit-Temporale Logik (Daniel Witzke)
12 Automaten auf endlichen Bäumen (Paul Trappendreher)