This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
IN2007 is a semester module in English language at Bachelor’s level and Master’s level which is offered in summer semester.
This Module is included in the following catalogues within the study programs in physics.
- Catalogue of non-physics elective courses
|Total workload||Contact hours||Credits (ECTS)|
|240 h||90 h||8 CP|
Content, Learning Outcome and Preconditions
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
|VU||6||Complexity Theory (IN2007)||
Thu, 10:00–12:00, MI HS3
Thu, 12:00–14:00, MI 03.11.018
Mon, 08:00–10:00, MI 00.13.009A
Learning and Teaching Methods
Giorgio Ausiello, Pierluigi Creszenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi: Complexity and approximation - Combinatorial optimization problems and their approximability properties. Springer-Verlag: Berlin-Heidelberg, 1999.
Jose L. Balcazar, Josep Diaz, Joaquim Gabarro: Structural Complexity I (and II). EATCS Monographs on Theoretical Computer Science, Springer-Verlag: Berlin-Heidelberg, 1995.
Christos H. Papadimitriou: Computational Complexity. Addison-Wesley Publishing Company: London-Amsterdam-New York, 1994.
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Englewood Clis, NJ, 1982.
Karl Rudiger Reischuk: Komplexitätstheorie - Band I: Grundlagen. B.G. Teubner: Stuttgart-Leipzig, 1999.
Michael Sipser: Introduction to the Theory of Computation. International Edition, Thomson Course Technology: Australia-Canada-Mexico-Singapore-Spain-United Kingdom-United States, 2006.
Ingo Wegener: The complexity of Boolean functions. Wiley-Teubner Series in Computer Science: Stuttgart-Chichester-New York, 1987.
Description of exams and course work
The exam may be repeated at the end of the semester.