|
Hier finden Sie die Vorlesungsfolien.
| Teil |
Kapitel |
Zum Anschauen |
Zum Ausdrucken (bunt) |
Zum Ausdrucken (weniger bunt) |
Version von |
Bemerkungen |
|
0. Einleitung |
laden |
laden |
laden |
12.10.10
|
|
A: Klassische Klassen
|
1. Wiederholung GTI |
laden |
laden |
laden |
14.10.10
|
Ein paar Formulierungen verändert
|
|
2. Spiele und Speicherplatz
|
laden |
laden |
laden |
21.10.10
|
|
|
3. Mehr Zeit, mehr Platz |
laden |
laden |
laden |
25.10.10
|
Lücken- und Beschleunigungssatz ergänzt
|
|
4. Beziehungen zwischen Komplexitätsklassen
|
laden |
laden |
laden |
28.10.10
|
|
| B: Weitere klassische Komplexitätsklassen |
5. Effiziente Parallelisierbarkeit
|
laden |
laden |
laden |
10.11.10
|
|
|
6. Zwischen NP und PSPACE
|
laden |
laden |
laden |
10.12.10
|
|
|
7. Zufallsalgorithmen und Probabilistische Komplexitätsklassen |
laden |
laden |
laden |
10.12.10
|
|
| C: Umgang mit NP-schwierigen Problemen |
8. Optimierungsprobleme und Approximation |
laden |
laden |
laden |
7.12.10
|
|
|
9. Parametrisierte Komplexität
|
laden |
laden |
laden |
11.1.11
|
|
D: Fortgeschrittene zufallsbasierte Konzepte
|
10. Interaktive Beweissysteme
|
laden |
laden |
laden |
18.1.11
|
Definition von MA ergänzt
|
|
11. PCP-Satz und Grenzen der Approximierbarkeit
|
laden |
laden |
laden |
3.2.11
|
|
|
12. Kryptographie und Komplexitätstheorie
|
laden |
laden |
laden |
1.2.11
|
|
|
