WiSe 2010/2011 » Komplexitätstheorie
Ziegler
Aktuelles
| 21.12.2010 | Aus dienstlichen Gründen muss die Veranstaltung am 2.2. und am 4.2. leider ausfallen. |
| 12.11.2010 | Übungsaufgabe 10 (Blatt 3) aktualisiert |
| 27.09.2010 | Am 29.10. muss die Veranstaltung wegen einer Dienstreise leider ausfallen; dafür finden bereits in der ersten Vorlesungswoche beide Termine statt. |
Veranstalter
| Name |
Raum |
Tel. |
| Martin Ziegler | | |
Vorlesung
| Tag | Uhrzeit | in Raum |
|---|
| Mittwochs | 11:40 - 13:20 | S2|15-201 |
Literatur
- Papadimitriou: Computational Complexity (HeBIS, Amazon)
Übung
| Nr. | Zeit | in Raum |
|---|
| 1 | Freitags, 9:50 - 11:30 | S2|15-201 |
Formalien
Für Bachelor im dritten Studienjahr
V2Ü2, 6 ECTS Punkte
auch geeignet für den Studiengang Informatik,
vgl.
MHB 432
Inhalt
- Asymptotik, Rechenmodelle, Ressourcen
- Turingmaschinen und ihre Programmierung
- polynomielle Zeit und Platz
- Beispielprobleme SAT, 3SAT, IS, Clique
- Beziehungen zwischen ihnen, Reduktion
- Klasse NP, Satz von Cook-Levin
- weitere NP-vollständige Probleme
- Approximationsalgorithmen und Güte
- Beispiele: VC, metr. TSP, Knapsack
- Nichtapproximierbarkeit
- PSPACE und QBF
- Gewinnstrategie auf Graphen
- Satz von Savitch
- Erreichbarkeit und NL
- Immerman-Szelepcsényi
- parallele Komplexität und Schaltkreise
- P-Vollständigkeit
- Kryptographie und UP
- randomisierte Komplexität
- polynomielle Hierarchie
- Sipser-Gács-Lautemann
Skript
von Prof. Blömer
Impressum | Datenschutzerklärung