Course detail
Complexity (in English)
FIT-SLOaAcad. year: 2022/2023
Turing machines as a basic computational model for computational complexity analysis, time and space complexity on Turing machines. Alternative models of computation, RAM and RASP machines and their relation to Turing machines in the context of complexity. Asymptotic complexity estimations, complexity classes based on time- and space-constructive functions, typical examples of complexity classes. Properties of complexity classes: importance of determinism and non-determinism in the area of computational complexity, Savitch theorem, relation between non-determinism and determinism, closure w.r.t. complement of complexity classes, proper inclusion between complexity classes. Selected advanced properties of complexity classes: Blum theorem, gap theorem. Reduction in the context of complexity and the notion of complete classes. Examples of complete problems for different complexity classes. Deeper discussion of P and NP classes with a special attention on NP-complete problems (SAT problem, etc.). Relationship between decision and optimization problems. Methods for computational solving of hard optimization problems: deterministic approaches, approximation, probabilistic algorithms. Relation between complexity and cryptography. Deeper discussion of PSPACE complete problems, complexity of formal verification methods.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Offered to foreign students
Learning outcomes of the course unit
Prerequisites
Co-requisites
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
- 3 projects - 10 points each (recommended minimal gain is 15 points)
Final exam is performed in written form. The maximal amount of points one can get is 70 points
Course curriculum
Work placements
Aims
Familiarize students with a selected methods for solving hard computational problems.
Specification of controlled education, way of implementation and compensation for absences
Recommended optional programme components
Prerequisites and corequisites
- recommended prerequisite
Theoretical Computer Science
Basic literature
Ding-Zhu Du, Ker-I Ko: Theory of Computational Complexity, 2nd Edition, Wiley 2014, ISBN: 978-1-118-30608-6 (EN)
Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0 (EN)
Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1 (EN)
Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821 (EN)
Recommended reading
Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X (EN)
Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7 (EN)
Elearning
Classification of course in study plans
- Programme IT-MGR-1H Master's
branch MGH , 1 year of study, summer semester, recommended course
- Programme IT-MSC-2 Master's
branch MGMe , 0 year of study, summer semester, compulsory-optional
- Programme IT-MSC-2 Master's
branch MBI , 0 year of study, summer semester, elective
branch MBS , 0 year of study, summer semester, elective
branch MGM , 0 year of study, summer semester, elective
branch MIS , 1 year of study, summer semester, elective
branch MPV , 0 year of study, summer semester, elective
branch MSK , 0 year of study, summer semester, elective - Programme MIT-EN Master's 0 year of study, summer semester, compulsory-optional
- Programme MITAI Master's
specialization NADE , 0 year of study, summer semester, elective
specialization NBIO , 0 year of study, summer semester, elective
specialization NCPS , 0 year of study, summer semester, elective
specialization NEMB , 0 year of study, summer semester, elective
specialization NGRI , 0 year of study, summer semester, elective
specialization NHPC , 0 year of study, summer semester, elective
specialization NIDE , 0 year of study, summer semester, elective
specialization NISD , 0 year of study, summer semester, elective
specialization NISY up to 2020/21 , 0 year of study, summer semester, elective
specialization NMAL , 0 year of study, summer semester, elective
specialization NMAT , 0 year of study, summer semester, compulsory
specialization NNET , 0 year of study, summer semester, elective
specialization NSEC , 0 year of study, summer semester, elective
specialization NSEN , 0 year of study, summer semester, elective
specialization NSPE , 0 year of study, summer semester, elective
specialization NVER , 0 year of study, summer semester, elective
specialization NVIZ , 0 year of study, summer semester, elective
specialization NISY , 0 year of study, summer semester, elective - Programme IT-MSC-2 Master's
branch MIN , 0 year of study, summer semester, compulsory-optional
branch MMM , 0 year of study, summer semester, compulsory-optional - Programme MITAI Master's
specialization NEMB up to 2021/22 , 0 year of study, summer semester, elective
Type of course unit
Lecture
Teacher / Lecturer
Syllabus
- Introduction. Complexity, time and space complexity.
- Matematical models of computation, RAM, RASP machines and their relation with Turing machines.
- Asymptotic estimations, complexity classes, determinism and non-determinism from the point of view of complexity.
- Relation between time and space, closure of complexity classes w.r.t. complementation, proper inclusion of complexity classes.
- Blum theorem. Gap theorem.
- Reduction, notion of complete problems, well known examples of complete problems.
- Classes P and NP. NP-complete problems. SAT problem.
- Travelling salesman problem, Knapsack problem and other important NP-complete problems
- NP optimization problems and their deterministic solution: pseudo-polynomial algorithms, parametric complexity
- Approximation algorithms.
- Probabilistic algorithms, probabilistic complexity classes.
- Complexity and cryptography
- PSPACE-complete problems. Complexity and formal verification.
Project
Teacher / Lecturer
Syllabus
Elearning