WiSe 2011/2012 » Komplexitätstheorie
Ziegler
Aktuelles
| 01.02.2012 | krankheitshalber muß morgen (Donnerstag) die Vorlesung leider ausfallen |
| 06.12.2011 | Am 16.12. findet an Stelle der Übung im Raum 201 die Vorlesung im Raum 301 statt;
dafür ist am 22.12. Übung. |
| 27.10.2011 | Wegen einer Habilitationsprüfung beginnt die Vorlesung am 3.11. mit 30 Minuten Verspätung. |
| 24.10.2011 | Erste Übung am 27.Oktober (Donnerstag) um 14h25 im S2|15-201 |
| 17.10.2011 | The second lecture will take place on Tuesday, October 25.
Time (and place) for exercises and subsequent lectures will be agreed upon based on a doodle-poll; see the first exercise sheet.
No lecture on October 19 (Wednesday)! |
| 06.09.2011 | Initial session (Vorbesprechung) 18.10.2011 14h25 im S101/A2 |
Veranstalter
| Name |
Raum |
Tel. |
| Ziegler, Martin | | |
Vorlesung
| Tag | Uhrzeit | in Raum |
|---|
| Donnerstags | 14:25 - 16:05 | S2|15-201 |
Literatur
Übung
| Nr. | Zeit | in Raum | bei |
|---|
| 1 | Freitags, 11:40 - 13:20 | S2|15-201 | Carsten Rösnick |
Formalien
Für Bachelor im dritten Studienjahr
V2Ü2, 6 ECTS Punkte
auch anrechenbar für den Studiengang Informatik,
vgl.
MHB 432
Veranstaltungssprache: Englisch (default)
Contents
- asymptotics, models of computation, ressources
- Turingmachines and their progrogramming
- polynomial time and space
- exemplary problems SAT, 3SAT, IS, Clique
- relations among them, reduction
- class NP, Cook-Levin Theorem
- further NP-complete problems
- approximation algorithms and quality
- examples: VC, metr. TSP, Knapsack
- nonapproximability
- PSPACE and QBF
- winning strategies on graphs
- Savitch's Theorem
- reachability and NL
- Immerman-Szelepcsényi
- parallel complexity and circuits
- P-completeness
- cryptographie and UP
- randomized complexity
- polynomial hierarchy
- Sipser-Gács-Lautemann
Skript
von Prof. Blömer und
(auf english) von
Prof. Bläser
Impressum | Datenschutzerklärung