Seminar Highlights der Theoretischen Informatik
Veranstalter: Prof. Carsten Lutz
S2, Modulbereich Theorie
Vorbesprechung: Mittwoch, 2.11.2011, 14:00-16:00 MZH 3150
Ohne Teilnahme an der Vorbesprechung kann das Seminar nicht belegt
werden.
In diesem Leitfaden finden sich
eine Beschreibung des Ablaufs sowie Hinweise zur
erfolgreichen Teilnahme.
Kurzbeschreibung
In diesem Seminar werden aufbauend auf den
Einführungsveranstaltungen "Theoretische Informatik I + II"
ausgewählte Themen aus verschiedenen Teilgebieten der
Theoretischen Informatik behandelt, wie zum Beispiel der Theorie der
formalen Sprachen und der Komplexitätstheorie. Es handelt sich
dabei um klassische und weithin bekannte Resultate, die Meileinsteine
in ihrem jeweiligen Gebiet darstellen und oft besonders elegante und
innovative Beweise haben. Beispiele sind etwa
- Unentscheidbarkeit von Hilberts zehntem Problem, eines der bekanntesten Resultate der Theoretischen Informatik
- Die Isomorphievermutung von Berman-Hartmanis (in etwa: alle
NP-vollständigen Probleme sind in Wahrheit dasselbe Problem
in unterschiedlicher Verkleidung) und damit zusammenhängende Resultate
über spärliche Mengen
- Das Äquivalenzproblem für LOOP-Programme der
Schachtelungstiefen 1 und 2 und ihre überraschend unterschiedliche
Komplexität (NP-vollständig für Tiefe 1 und unentscheidbar für Tiefe 2)
Die Studierenden werden sich mit je einem Resultat näher
auseinandersetzen, es in seinen jeweiligen Kontext einordnen und die
dazugehörigen Beweistechniken kennenlernen.
Das Seminar stützt sich auf folgende Bücher. Elektronische
Versionen sind verfügbar (bitte auf Cover klicken).
Voraussetzungen / Vorkenntnisse
Theoretische Informatik I + II
Organisation
Die Teilnehmer wählen während der Vorbesprechung ein Thema,
das sie in einer Zweiergruppe bearbeiten. Zu jedem Thema gibt es ein
Kapitel in den oben genannten Büchern, das die Grundlage der
Seminararbeit darstellt. Zusätzlich kann es erforderlich sein,
einen oder mehrere Artikel der wissenschaftlichen Originalliteratur
hinzuzuziehen. Die relevante Literatur soll von den bearbeitenden
Teilnehmern zunächst gelesen und verstanden werden, wobei ihnen
ein Betreuer aus der AG zur Seite steht. Jede Gruppe fertigt dann eine
ca. 15-seitige Ausarbeitung über das gewählte Thema
an, deren Form den Standards wissenschaftlichen Arbeitens
genügt. Am Ende des Semesters findet ein Blockseminar statt, in
dem jede Gruppe ihr Thema in einem Vortrag den anderen Teilnehmern
vorstellt. Die Zeitplanung und das Vereinbaren von Terminen mit dem
Betreuer gehört zu den Aufgaben der Teilnehmer. Mehr Information
und Tipps zur erfolgreichen Teilnahme gibt es in
diesem Leitfaden.
Ein Teil der Betreuung wird auf englisch (oder türkisch oder spanisch) stattfinden.
Terminplan
| bis 17.11. |
Erstes Treffen mit dem Betreuer |
| 9.11.–7.12. |
Literatur lesen und verstehen, Unklarheiten mit dem Betreuer diskutieren |
| spätestens 8.12. |
Beginnen, an der Hausarbeit zu schreiben |
| 11.1. |
Abgabe der fertigen Hausarbeit |
| 18.1. |
Rückgabe der korrigierten Hausarbeit durch den Betreuer |
| 1.2. |
Abgabe der endgültigen Hausarbeit und Vorlage der ersten Version der Folien für den Vortrag |
| ca. 15.2. |
Vortrag |
AG Theorie der künstlichen Intelligenz