Seminar Komplexitätstheorie
Veranstalter: Prof. Carsten Lutz
S2, Modulbereich Theorie
Vorbesprechung: Mittwoch, 21.10., 14:00-16:00 MZH 3150
Ohne Teilnahme an der Vorbesprechung kann das Seminar nicht belegt werden.
Wer Interesse an dem Seminar hat, aber nicht zur Vorbesprechung kommen kann, meldet sich bitte bis 20.10.09 per email.
Kurzbeschreibung
Die Komplexitätstheorie beschäftigt sich mit der inhärenten
Komplexität von Berechnungsproblemen: wieviel Zeit (oder andere
Ressourcen) benötigt man, um ein gegebenes Problem zu
lösen--unabhängig davon, wie clever der Algorithmus ist, den man
verwendet? Es geht also um die Grenzen der Berechenbarkeit unter
beschränkten Ressourcen. Damit stellt die Komplexitätstheorie eine
wichtige Grundlage für den Entwurf und das Verständnis von
effizienten Algorithmen dar und versucht, die natürliche
Neugier nach dem in der Informatik prinzipiell machbaren zu
befriedigen.
Dieser Seminar baut auf der Vorlesung
Komplexitätstheorie im SS09 auf und gibt den Teilnehmern die
Möglichkeit, sich intensiver mit Themen auseinanderzusetzen, die
in der Vorlesung nicht oder nur sehr kurz besprochen wurden, wie z.B.
probabilistische Komplexitätsklassen, auf alternierenden
Turingmaschinen basierende Komplexitätsklassen, und
nicht-uniforme Modelle von Turingmaschinen sowie deren Zusammenhang zu
Schaltkreisen.
Voraussetzungen / Vorkenntnisse
Der Besuch der Vorlesung
Komplexitätstheorie im SS09 ist keine formale Voraussetzung.
Grundlegende Vorkenntnisse in Komplexitätstheorie, wie sie z.B.
in der Grundvorlesung Theoretische Informatik II vermittelt werden, werden jedoch
erwartet.
Organisation
Die Teilnehmer wählen während der Vorbesprechung ein Thema,
dass sie in einer 2er Gruppe bearbeiten. Zu
jedem Thema gibt es einen oder mehrere (englische) Aufsätze, die
von den bearbeitenden Teilnehmern zunächst gelesen und verstanden
werden sollen, wobei ihnen ein Betreuer zur Seite steht. Jede Gruppe
fertigt eine ca. 15-seitige, lesbare Ausarbeitung an, deren Form den
Standards wissenschaftlichen Arbeitens genügt. Am Ende des
Semesters stellt jede Gruppe ihr Thema in einem Vortrag den anderen
Teilnehmern in verständlicher Weise dar. Die Vorträge werden
in Form eines Blockseminares gehalten. Die Zeitplanung, Vereinbarung
von Terminen und das Stellen von Fragen an den Betreuer gehört zu
den Aufgaben der Teilnehmer.
Bei großer Teilnehmerzahl muss ein Teil der Betreuung auf
Englisch stattfinden (und auch die Ausarbeitung muss dann in
englischer Sprache angefertigt werden).
Terminplan
| bis 6.11. |
Erstes Treffen mit dem Betreuer |
6.11.-1.12. |
Literatur lesen und verstehen, Unklarheiten mit dem Betreuer
diskutieren |
|
spätestens 1.12. |
Beginnen, an der Hausarbeit zu schreiben |
| 4.1. |
Abgabe der fertigen Hausarbeit |
| 11.12. |
Rückgabe der korrigierten Hausarbeit durch den Betreuer |
| 22.1. |
Abgabe der endgültigen Hausarbeit und Vorlage der ersten Version der
Folien für den Vortrag
|
| 3.2. | Vortrag |
AG Theorie der künstlichen Intelligenz