Inhalt

Das Proseminar vertieft Inhalte aus den Grundvorlesungen der Arbeitsgruppe Theoretische Informatik. In diesem Fall werden weiterführende Themen aus der Berechenbarkeits- und Sprachentheorie behandelt (im Anschluss an "Grundlagen der theoretischen Informatik"). Mögliche Themen sind:

Anwendung endlicher Automaten (u.a.im Hardwareentwurf)

Anwendung kontextfreier Grammatiken (etwa im Compilerbau)

Einführung in die Komplexitätstheorie (2 Vorträge, u.a. P, NP, PSPACE)

Nichtentscheidbare Probleme

(Nicht-)Entscheidbarkeit logischer Theorien ( 2 Vorträge, u.a. Presburger-Arithmetik, Gödels Unvollständigkeitssätze)

Voraussetzungen

zwei abgeschlossene Fachsemester Informatik, Leistungsnachweis GTI

Literatur

u.a.

M. Sipser, Introduction to the Theory of Computation,

Aho, Ullman, Principles of Compiler Design

Nähere Informationen 

Die vorläufige Einteilung der Vorträge befindet sich unter "Resources".

Jeder Teilnehmer hält zwei Vorträge.

Die Vortragsdauer beträgt 60 Minuten; jeder Vortrag wird per Videokonferenz mit dem System Cisco Webex gehalten. Dabei können Folien,Tablet mit Eingabestift, Kombination von beiden, Videoübertragung einer beschrifteten Seite oder Tafel usw. benutzt werden. 

Eine ausführliche schriftliche Ausarbeitung eines  Vortrags ist nicht erforderlich, bitte fertigen Sie nur eine Zusammenfassung jedes Vortrags auf 4 DIN-A4 Seiten in PDF an und stellen Sie sie den Hörern vor dem Vortrag zur Verfügung. 

Die Vorträge sollten gut verständlich sein und technisch schwierige Teile des Themas (z.B. Beweise) nicht umgehen, sondern erklären. Die Literaturangaben zu den Themen dienen als Richtlinie. Sie dürfen und sollten, wenn Sie das Gefühl haben, dass die angegebene Literatur wichtige Aspekte des Themas nicht anspricht, auch noch andere Quellen heranziehen. Bitte besprechen Sie diese und andere Fragen bei einem Einzeltermin spätestens eine Woche vor dem Vortragstermin mit mir, den Sie bitte per E-Mail mit mir verabreden. Bitte bringen Sie schon ein Konzept für Ihren Vortrag mit.

Im Anschluss an jeden Vortrag wird ein Hörer zufällig ausgewählt, um den Inhalt kurz (etwa 5 Min.) mündlich zusammenzufassen.

"Aktive Teilnahme" ist durch zwei Vorträge und zugehörige schriftliche Zusammenfassungen erbracht, "regelmäßige Teilnahme" durch Anwesenheit bei 85% der Vorträge.