|
Lecturer:
Prof. Dr. Angelika Steger
|
|
|
Area:
4 lectures per week in
area III (Theoretical Computer Science)
core course
, topic complexity
|
|
|
Time and Place:
To be anounced.
|
|
|
Exercises:
2 hours per week exercises accompanying the lectures
Time and place to be announced.
Teaching Assistant: N.N.
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 Datastructures I advantagious, 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 Lectures:
|
|
|
Lecture Notes:
Not available.
|
|
|
References:
-
Balczar, Daz, Gabarr:
-
Structural Complexity I
EATCS Monographs, Springer-Verlag, begleitend
-
Rüdiger Reischuk:
-
Einführung in die Komplexitätstheorie
Teubner-Verlag, in Ausschnitten
|
|
|
Office Hours:
look here
|
