Komplexitätstheorie

PD Dr. rer.nat. habil. Karl-Heinz Niggl

Vorlesung: Dienstag, 11.00 - 12.30 Uhr
Raum: Audimax

Sprechstunde K.-H. Niggl: Mi 15-17 Uhr

Die Klausur findet am 23.02.2006, 12.30 Uhr im Audimax statt!

Übungen

Dienstag	15.00 - 16.30 Uhr	H 1527	H. Wunderlich	(Sprechstunde: Mi 15-17 Uhr)
Mittwoch	13.00 - 14.30 Uhr	HU 129	H. Wunderlich	(Sprechstunde: Mi 15-17 Uhr)
Donnerstag	9.00 - 10.30 Uhr	H 2507	U. Schellbach	(Sprechstunde: Do 15-17 Uhr)
Freitag	13.00 - 14.30 Uhr	H 1527	U. Schellbach	(Sprechstunde: Do 15-17 Uhr)
Montag	11.00 - 12.30 Uhr	HU 117	U. Schellbach	(Sprechstunde: Do 15-17 Uhr)

Dokumente zur Vorlesung

Beginn der Übungen in der 2. Vorlesungswoche (ab 17.10.05): Besprechung der "Stunde 0"

Verwendete Folien zur Vorlesung vom 24.01.2006

Verwendete Folien zur Vorlesung vom 17.01.2006

Verwendete Folien zur Vorlesung vom 10.01.2006

Vorlesungsskript Kapitel 1, 2 und 3

Verwendete Folien zur Vorlesung vom 20.12.2005

Reduktionsbaum Anmoderation von Kapitel 4

Verwendete Folien zur Vorlesung vom 13.12.05

Verwendete Folien zur Vorlesung vom 06.12.05

Verwendete Folien zur Vorlesung vom 29.11.05

Beispiel zur Polynomialzeitreduktion von 3-SAT auf RUCKSACK*

Der Satz von Cook

Turingreduzierbarkeit und Polynomialzeitreduzierbarkeit

P, NP und NP-Vollständigkeit

Reelle RAM
(Definition und Beispiel eines RRAM-Programms)

Literatur

Anmoderation
(Worum geht's ?, Themen im Überblick, Übungsbetrieb)

Übungsaufgaben

Lösungen von Übungsaufgaben sollten 14 Tage nach Ausgabe in der Vorlesung abgegeben werden (mit Name(n), Übungsgruppe, Tag). Möglich ist auch die Abgabe via Briefkasten KTEA/AFS bis spätestens Freitag 12:00 Uhr.