|
|
|
 |
|
|
held by: |
Prof. Dr. Markus Holzer
|
|
|
|
held in: |
SS 2007
|
|
|
|
schedule: |
Tuesday, 13:00 - 14:30 (MW 1801)
start date: 2007-04-17 / end date: 2007-07-20
Thursday, 08:30 - 10:00 (MI HS 3)
start date: 2007-04-26 / end date: 2007-07-20
|
|
|
|
news: |
Zur Vorlesung findet eine mündliche Prüfung statt. Interessenten melden sich bitte per Mail bei Herrn Holzer mit dem Subject "Prüfung Komplexitätstheorie" an.
|
|
|
|
sws: |
4
|
|
|
|
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet syntaktische und operationelle Beschreibungen
Informationen und Aufgabenblätter zur Übung finden Sie hier: Übung zur Vorlesung Komplexitätstheorie
Literatur
- J. L. Balcázar, J. Díaz, and
J. Gabarró.
Structural Complexity I, volume 11 of EATCS Monographs
on Theoretical Computer Science.
Springer, 1988.
- J. L. Balcázar, J. Díaz, and
J. Gabarró.
Structural Complexity II, volume 22 of EATCS Monographs
on Theoretical Computer Science.
Springer, 1990.
-
J. E. Hopcroft and J. D. Ullman.
Formal Languages and Their Relation to Automata.
Addison-Wesley, 1968.
-
J. E. Hopcroft and J. D. Ullman.
Introduction to Automata Theory, Languages and
Computation.
Addison-Wesley, 1979.
-
C. H. Papadimitriou.
Computational Complexity.
Addison-Wesley, 1994.
-
K. R. Reischuk.
Einführung in die Komplexitätstheorie.
Teubner, 1990
Weiterführende Literatur:
- L. A. Hemaspaandra and M. Ogihara.
The Complexity Theory Companion.
EATCS Monographs in Theoretical Computer Science. Springer, 2002.
-
K. Wagner and G. Wechsung.
Computational Complexity.
Mathematics and its applications (East Europeans series). VEB
Deutscher Verlag der Wissenschaften, Berlin, 1986.
|
|
|
|
downloadable material:
|
|
|
|
slides
|
|
title / description
|
download
|
|
Reduktion
|
click here...
|
|
|
Satz von Cook
|
click here...
|
|
|
 |
|
|
 |
Contact
Teaching
