|
Lecturer:
Prof. Dr. Ernst W. Mayr
|
|
|
Area:
4 lectures per week in
area III (Theoretical Computer Science)
core course
, topic complexity
|
|
|
Time and Place:
Tue 8:30 - 10:00, lecture hall N1070
Fri 8:30 - 10:00, lecture hall N1070
Start: 16. October
|
|
|
Exercises:
2 hours per week exercises accompanying the lectures
Tue 16h s.t. - 17:30, lecture hall 2705
Start: 30. October
Teaching Assistant: Ulrich Rührmair
Course Certificate: To get a course certificate students must
get at least 40% on the homework assignments and
pass the final exam.
|
|
|
Audience:
graduate students of computer science
students with computer science as minor
|
|
|
Prerequisites:
1st and 2nd year courses
Course Efficient Algorithms and Data Structures I advantageous, but not necessary
|
|
|
Recommended for:
In-depth knowledge in topic Complexity
|
|
|
Contents:
- Basics and Models of Computation
- Time and Space restricted Computations
- Important Complexity Classes (P, NP, PSPACE,EXPSPACE)
- Time Restricted reductions
- Circuits, Nonuniform Complexity
- Probabilistic Machines
- Polynomial Hierarchy
|
|
|
Related and Advanced Courses:
Efficient Algorithms and Data Structures
|
|
|
Lecture Notes:
Not available.
|
|
|
References:
-
J.L. Balcázar, J. Díaz, J. Gabarró:
-
Structural Complexity I (and II)
EATCS Monographs, Springer-Verlag, accompanying
-
K.R. Reischuk:
-
Einführung in die Komplexitätstheorie
Teubner-Verlag, excerpts
-
Ch. Papadimitriou:
-
Computational Complexity
Addison-Wesley
-
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
-
Complexity and Approximation --- Combinatorial optimization problems and their approximability properties
Springer-Verlag
|
|
|
Office Hours:
look here
|
