|
Allgemeines
|
- Betreuung:
Reinhard Bauer,
Martin Holzer,
Marcus Krug,
Dorothea Wagner
- Regelmäßiger Termin: Dienstag, 15:45–17:15 Uhr
- Ort: Seminarraum 301, Informatik-Hauptgebäude
- Anmeldung und weitere Fragen: Entweder per Email an Reinhard Bauer oder einfach im Büro vorbeikommen.
- Hinweis: Das Seminar ist mittlerweile vollständig belegt. Freie Seminarplätze im algorithmischen Bereich finden sich hier.
|
| |
|
Aktuelles
|
8. Mai: Die Terminzuteilung der Hauptvorträge findet sich hier (Änderungen vorbehalten). Die Reihenfolge der Zwischenvorträge lehnt sich – soweit möglich – an diese Einteilung an.
22. April: Die Einteilung für die kww-Schulung findet sich hier.
|
| |
|
Inhalt
|
Die P-ungleich-NP-Frage ist eines der größten ungelösten Probleme der Informatik.
Das Proseminar behandelt aktuelle Ansätze zur Lösung der P-ungleich-NP-Frage.
Ziel ist, dass sich jeder Teilnehmer einen dieser Ansätze erarbeitet und anschließend in einem Vortrag vorstellt. Außerdem wird ein kleines Training in Wissenschaftlichem Schreiben und Vortragen angeboten.
|
| |
|
Termine
|
| 22.04.2008 |
15:45–17:15 |
SR 301 |
Vorbesprechung |
| 29.04.2008 |
15:45–17:15 |
SR 301 |
Fachliches Präsentieren |
| 07.05.2008 |
16:00–19:00 |
SR 301 |
kww-Schulung |
| 08.05.2008 |
16:00–19:00 |
SR 131 |
kww-Schulung |
| 13.05.2008 |
15:45–18:00 |
SR 301 |
Zwischenvorträge |
| 20.05.2008 |
15:45–18:00 |
SR 301 |
Wiss. Schreiben + LaTeX |
| 27.05.2008 |
15:45–19:00 |
SR 301 |
Hauptvorträge |
| 04.06.2008 |
14:00–17:15 |
SR -109 |
Hauptvorträge |
|
| 15.06.2008 |
|
|
Gliederung Ausarbeitung |
| 29.06.2008 |
|
|
erste Fassung Ausarbeitung |
| 20.07.2008 |
|
|
Hauptfassung Ausarbeitung |
| 03.08.2008 |
|
|
endgültige Fassung Ausarbeitung |
|
| |
|
Einteilung kww-Termine
|
| 07.05.2008 |
| 08.05.2008 |
- Jan
- Felix
- Florian
- Christian
- Benjamin
|
|
- Stephan
- Nelli
- Simon
- Moritz
- Alexander
|
|
| |
|
|
| |
|
Vorträge
|
| Thema |
StudentIn |
Betreuer |
|
| Dienstag, 27. Mai: |
| On the Structure of Polynomial-Time Reducibility [3] |
Moritz |
Reinhard |
| Speicherplatzbasierte Komplexitätsklassen [7, Kap. 13.1–13.4] |
Benjamin |
Martin |
| Pebble Game [6, Kap. 24] |
Christian |
Reinhard |
| Interaktive Beweise [7, Kap. 11] |
Stephan |
Marcus |
| IP=PSPACE [5] |
Simon |
Marcus |
|
| Mittwoch, 4. Juni: |
| Das PCP-Theorem [1, Kap. 7] |
Jan |
Reinhard |
| Die Komplexität von nichtuniformen Problemen [7, Kap. 14.1–14.5] |
Felix |
Martin |
| Kommunikationskomplexität [7, Kap. 15.1–15.3] |
Nelli |
Reinhard |
| Das Äquivalenzproblem für LOOP(1)- und LOOP(2)-Progr. [6, Kap. 3] |
Florian |
Reinhard |
| Kolmogorov-Komplexität [2, Kap. 2.4/5.6] |
Alexander |
Marcus |
|
| |
|
Literatur
|
- Ausiello et al.: Complexity and Approximation, Springer 1999.
- Juraj Hromkovic: Theoretische Informatik, Teubner 2007.
- Richard Ladner: On the Structure of Polynomial Time Reducibility.
- Nash et al.: Universal Languages and the Power of Diagonalization.
- Adi Shamir: IP=PSPACE.
- Uwe Schöning: Perlen der Theoretischen Informatik, BI Wissenschaftsverlag 1995.
- Ingo Wegener: Komplexitätstheorie, Springer 2003.
- Avi Wigderson: P, NP and mathematics - a computational complexity perspective, 2006.
|
| |
|
Links
|
|
|
| |
