Course detail
Complexity (in English)
FIT-SLOaAcad. year: 2020/2021
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.
Guarantor
Department
Offered to foreign students
Of all faculties
Learning outcomes of the course unit
Understanding theoretical and practical limits of arbitrary computational systems. Ability to use a selected methods for computationally hard problems.
Prerequisites
Formal language theory and theory of computability on master level.
- recommended prerequisite
Co-requisites
Not applicable.
Recommended optional programme components
Not applicable.
Literature
Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7 (EN)
Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2 (EN)
Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X (EN)
Planned learning activities and teaching methods
Not applicable.
Assesment methods and criteria linked to learning outcomes
- 3 projects - 10 points each (recommended minimal gain is 15 points).
- Final exam: max. 70 points
Language of instruction
English
Work placements
Not applicable.
Aims
Familiarize students with the complexity theory, which is necessary to understand practical limits of algorithmic problem solving on physical computational systems.
Familiarize students with a selected methods for solving hard computational problems.
Classification of course in study plans
- Programme IT-MGR-2 Master's
branch MBI , any year of study, summer semester, 5 credits, elective
branch MPV , any year of study, summer semester, 5 credits, elective
branch MGM , any year of study, summer semester, 5 credits, elective - Programme IT-MGR-2 Master's
branch MGMe , any year of study, summer semester, 5 credits, compulsory-optional
- Programme IT-MGR-2 Master's
branch MSK , any year of study, summer semester, 5 credits, elective
branch MBS , any year of study, summer semester, 5 credits, elective
branch MIN , any year of study, summer semester, 5 credits, compulsory-optional
branch MMM , any year of study, summer semester, 5 credits, compulsory-optional - Programme MITAI Master's
specialization NADE , any year of study, summer semester, 5 credits, elective
specialization NBIO , any year of study, summer semester, 5 credits, elective
specialization NGRI , any year of study, summer semester, 5 credits, elective
specialization NNET , any year of study, summer semester, 5 credits, elective
specialization NVIZ , any year of study, summer semester, 5 credits, elective
specialization NCPS , any year of study, summer semester, 5 credits, elective
specialization NSEC , any year of study, summer semester, 5 credits, elective
specialization NEMB , any year of study, summer semester, 5 credits, elective
specialization NHPC , any year of study, summer semester, 5 credits, elective
specialization NISD , any year of study, summer semester, 5 credits, elective
specialization NIDE , any year of study, summer semester, 5 credits, elective
specialization NISY , any year of study, summer semester, 5 credits, elective
specialization NMAL , any year of study, summer semester, 5 credits, elective
specialization NMAT , any year of study, summer semester, 5 credits, compulsory
specialization NSEN , any year of study, summer semester, 5 credits, elective
specialization NVER , any year of study, summer semester, 5 credits, elective
specialization NSPE , any year of study, summer semester, 5 credits, elective - Programme IT-MGR-1H Master's
branch MGH , any year of study, summer semester, 5 credits, recommended
- Programme IT-MGR-2 Master's
branch MIS , 1. year of study, summer semester, 5 credits, elective
Type of course unit
Lecture
26 hours, optionally
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
26 hours, compulsory
Teacher / Lecturer
Syllabus
3 projects dedicated on different aspects of the complexity theory.
eLearning
eLearning: opened course