inf451 - Complexity Theory (Complete module description)

inf451 - Complexity Theory (Complete module description)

Original version English PDF Download
Module label Complexity Theory
Modulkürzel inf451
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Verwendbarkeit des Moduls
  • Master's Programme Computing Science (Master) >
Zuständige Personen
  • Lehrenden, Die im Modul (Prüfungsberechtigt)
  • Lehrenden, Die im Modul (module responsibility)
Prerequisites
No participant requirements
Skills to be acquired in this module
This module covers the computational complexity of algorithms. Complexity considerations are concerned with the time, the memory, and the parallelism required or allowed, for solving an algorithmic problem. In particular, one is interested in lower and/or upper time and space bounds, and in approximative investigations providing information about entire classes of algorithms. For any concrete problem, complexity theory aims at being able to find out which class it belongs to, and thus estimating the cost of the most efficient methods of solving it. Methods taught in this module are general, not depending on any particular algorithmic model or chosen programming language.
Professional competence
  • use Turing machines and variants thereof
  • define time, memory, and processor requirements of algorithmic problems
  • specify the most relevant complexity classes
  • estimate the computational complexity of the most important problems
Methodological competence
The students:
  • analyse the complexity of algorithms
  • apply techniques of simulation, reduction, and diagonalisation
  • compare new problems in terms of complexity
Social competence
The students:
  • present proof sketches, proofs, and algorithmic solutions in front of an audience
Module contents
  • Mathematical foundations
  • Turing machines and register machines
  • Space and time hierarchies, equivalence and hierarchy theorems
  • Complexity classes: P, NP, NPC, PSPACE, and others
  • Alternating automata and polynomial time hierarchy
  • Circuit complexity
Literaturempfehlungen
  • Eike Best: Skript zur Vorlesung (2015)
  • Michael R. Garey, David S. Johnson: Computers and Intractability.Freeman, New York (2003).
  • Steven Homer, Alan L. Selman: Computability and Complexity Theory. Springer (2000).
  • John E. Hopcroft, Jeffrey D. Ullmann: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).
  • Rüdiger Reischuk: Komplexitätstheorie. 2. Auflage. Teubner, Stuttgart/Leipzig (1999).
  • Michael Sipser: Introduction to the Theory of Computation. Third Edition, Cengage (2005).
Links
Language of instruction German
Duration (semesters) 1 Semester
Module frequency irregular
Module capacity unlimited
Teaching/Learning method 1VL + 1Ü
Previous knowledge none
Form of instruction Comment SWS Frequency Workload of compulsory attendance
Lecture 2 SoSe 28
Exercises 2 SoSe 28
Präsenzzeit Modul insgesamt 56 h
Examination Prüfungszeiten Type of examination
Final exam of module
At the end of the lecture period
exercises and oral exam