Laajuus: 5
Aikataulu: 07.01.2019 - 09.04.2019
Opetusperiodi (voimassa 01.08.2018-31.07.2020):
III - IV (Spring)
Osaamistavoitteet (voimassa 01.08.2018-31.07.2020):
Once you have taken the course, you master the central concepts of computational complexity theory and are able to use these concepts to analyse the complexity of computational problems. You can formulate a concrete real-world computational task as a formal computational problem and formally reason about its computational complexity in comparison with well-known problems and complexity classes. You can use reductions and other complexity-theoretic concepts to identify which algorithmic tools — such as randomisation, approximation, parameterisation and parallelism – can and cannot help with the efficient solution of a given problem.
Sisältö (voimassa 01.08.2018-31.07.2020):
Basic concepts of complexity theory: models of computation, complexity measures including time and space, reductions, complexity classes and completeness. Complexity classes: P, NP and coNP; PSPACE, LOGSPACE, EXPTIME. Advanced topics such as the polynomial hierarchy, approximation, randomised computation, circuits and parallel computation, fine-grained complexity, and relativisations.
Toteutus, työmuodot ja arvosteluperusteet (voimassa 01.08.2018-31.07.2020):
Exams and exercises.
Oppimateriaali (voimassa 01.08.2018-31.07.2020):
Lecture slides and exercises.
S. Arora and B. Barak: Computational Complexity – A Modern Approach, Cambridge U.P. 2009.
C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
Korvaavuudet (voimassa 01.08.2018-31.07.2020):
T-79.5103 Computational Complexity Theory
Esitiedot (voimassa 01.08.2018-31.07.2020):
Automata and formal languages. Deterministic and nondeterministic Turing machines. Decidable and undecidable problems (e.g. CS-C2150 / ICS-C2000 Theoretical Computer Science). Basics of discrete mathematics.
Arvosteluasteikko (voimassa 01.08.2018-31.07.2020):
0-5
- Opettaja: Hirvonen Juho
- Opettaja: Jindal Gorav
- Opettaja: Orponen Pekka