| studiehandbok@lith | |
|
|
|
|
|
| TDDB41 | Computability and Complexity Theory, 3 p (sw) /Komplexitetsteori/ Advancement level: D | |
| Aim: The aim of this course is to present some of the most significant results obtained in complexity theory.Prerequisites: Basic knowledge of formal languages, automata theory, design and analysis of algorithms, and discrete mathematics. Probability theory and optimizationSupplementary courses: TDDA 32 Design and analysis of algorithms.Course organization: The content of the course is presented during the lectures by the course leader and the participants. Course content: Elements of computability theory, complexity classes, the classes P and NP, complexity of optimization problems, beyond NP, space-complexity classes, probabilistic algorithms and complexity classes.Course literature: Bovet, D.P., Crescenzi, P., Introduction to the Theory of Complexity. First edition | ||
| |
|
|
 |
|||||
|
|
||||||
