Vorlesung "Algorithmen und Komplexitätstheorie"

LV-Leiter:

Termin:

Di 10:00-12:00, HS-C

Ablauf:

Aktuelles:

Zugangscodes werden in der 1. VO-Einheit bekannt gegeben.
Zusatztermin: 14.10.2010, 12-14 Uhr, HS-3 (Ersatztermin für den 26.10.2010)
Zusatztermin: 04.11.2010, 12-14 Uhr, HS-3 (Ersatztermin für den 02.11.2010)
Details zum Beweis von Satz 4.3
Artikel: On P, NP, and Computational Complexity (Communications of the ACM)
Artikel: A short History of Computational Complexity
Zwischenklausur (Muster), Endklausur (Muster)

Kapitel	Ausgabe	Update	Folien
Organisatorisches	29.09.2010	--.--.----
Literatur	12.10.2010	--.--.----
1 Einführung und Überblick	05.10.2010	--.--.----
2 Fundamentalsatz und Lösen von Rekursionen	05.10.2010	--.--.----
3 Zahlen- und Matrizenmultiplikation	12.10.2010	--.--.----
4 Deterministische Komplexitätsklassen	12.10.2010	--.--.----
5 Nichtdeterministische Komplexitätsklassen	02.11.2010	--.--.----
6 NP-vollständige Probleme	02.11.2010	--.--.----
7 Orakel-Turingmaschinen und polynomiale Hierarchie	09.11.2010	19.11.2010
8 Probabilistische Algorithmen und Komplexitätsklassen	19.11.2010	15.12.2010
9 Zero-Knowledge Proofs und die Klasse IP	30.11.2010	01.12.2010
10 Ausgewählte Problemlösungen	10.01.2011	--.--.----
X Approximationsalgorithmen	02.12.2010	07.12.2010

Praktikum "Algorithmen und Komplexitätstheorie"

LV-Leiter	DDI Dr. Stefan Rass
Termine:	Di 14:00-16:00, E.1.42 (Vorbesprechung am 05.10.2010)
Ausweichtermine:	Mo 25.10.2010 14:00-16:00, HS 11
Ablauf:	Klausurtermine, LV-Modalitäten