Course details

# Complexity (in English)

SLOa Acad. year 2019/2020 Summer semester 5 credits

Guarantor

Deputy Guarantor

Language of instruction

Completion

Time span

Assessment points

Department

Lecturer

Instructor

Course Web Pages

News

This course is instructed in English, and it is intended for incoming Erasmus+ students, too.Projects and final exam can be done in English as well as in Czech according to individual preferences. |

Subject specific learning outcomes and competences

Learning objectives

Familiarize students with a selected methods for solving hard computational problems.

Why is the course taught

Prerequisite kwnowledge and skills

Study literature

- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821
- Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN: 0521424267. Available online.
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
- Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X
- Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7

Fundamental literature

- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1

Syllabus of lectures

- 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.

Syllabus - others, projects and individual work of students

Progress assessment

- 4 projects - 8 points each (recommended minimal gain is 15 points).
- Final exam: max. 68 points

Schedule

Course inclusion in study plans

- Programme IT-MSC-2, field MBI, MBS, MGM, MPV, MSK, any year of study, Elective
- Programme IT-MSC-2, field MGMe, any year of study, Compulsory-Elective group M
- Programme IT-MSC-2, field MIN, any year of study, Compulsory-Elective group B
- Programme IT-MSC-2, field MIS, 1st year of study, Elective
- Programme IT-MSC-2, field MMM, any year of study, Compulsory-Elective group L
- Programme MITAI, specialisation NADE, NBIO, NCPS, NEMB, NGRI, NHPC, NIDE, NISD, NISY, NMAL, NNET, NSEC, NSEN, NSPE, NVER, NVIZ, any year of study, Elective
- Programme MITAI, specialisation NMAT, any year of study, Compulsory