Stud.IP Uni Oldenburg
University of Oldenburg
09.12.2021 14:32:54
inf451 - Complexity Theory (Complete module description)
 Module label Complexity Theory Module code inf451 Credit points 6.0 KP Workload 180 h Institute directory Department of Computing Science Applicability of the module Master's Programme Computing Science (Master) > Theoretische Informatik Responsible persons Best, Eike (Authorized examiners) Lehrenden, Die im Modul (Authorized examiners) Prerequisites 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 competenceThe students:use Turing machines and variants thereofdefine time, memory, and processor requirements of algorithmic problemsspecify the most relevant complexity classesestimate the computational complexity of the most important problemsMethodological competenceThe students:analyse the complexity of algorithmsapply techniques of simulation, reduction, and diagonalisationcompare new problems in terms of complexitySocial competenceThe students:present proof sketches, proofs, and algorithmic solutions in front of an audience Module contents Mathematical foundationsTuring machines and register machines Space and time hierarchies, equivalence and hierarchy theoremsComplexity classes: P, NP, NPC, PSPACE, and othersAlternating automata and polynomial time hierarchyCircuit complexity Reader's advisory 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 unregelmäßig Module capacity unlimited Modullevel / module level AC (Aufbaucurriculum / Composition) Modulart / typ of module je nach Studiengang Pflicht oder Wahlpflicht Lehr-/Lernform / Teaching/Learning method Vorkenntnisse / Previous knowledge
Course type Comment SWS Frequency Workload of compulsory attendance
Lecture
2 SuSe 28
Exercises
2 SuSe 28
Total time of attendance for the module 56 h
Examination Time of examination Type of examination
Final exam of module
At the end of the lecture period
exercises and oral exam