Course detail

Complexity (in English)

FIT-SLOaAcad. year: 2019/2020

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.

Supervisor

doc. Mgr. Adam Rogalewicz, Ph.D.

Department

Department of Intelligent Systems (UITS)

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.

Co-requisites

Not applicable.

Recommended optional programme components

Not applicable.

Recommended or required reading

Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN: 0521424267. Dostupné 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
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
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

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

  • 4 projects - 8 points each (recommended minimal gain is 15 points).
  • Final exam: max. 68 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, optional
    branch MPV , any year of study, summer semester, 5 credits, optional
    branch MGM , any year of study, summer semester, 5 credits, optional

  • 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, optional
    branch MBS , any year of study, summer semester, 5 credits, optional
    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, optional
    specialization NBIO , any year of study, summer semester, 5 credits, optional
    specialization NGRI , any year of study, summer semester, 5 credits, optional
    specialization NNET , any year of study, summer semester, 5 credits, optional
    specialization NVIZ , any year of study, summer semester, 5 credits, optional
    specialization NCPS , any year of study, summer semester, 5 credits, optional
    specialization NSEC , any year of study, summer semester, 5 credits, optional
    specialization NEMB , any year of study, summer semester, 5 credits, optional
    specialization NHPC , any year of study, summer semester, 5 credits, optional
    specialization NISD , any year of study, summer semester, 5 credits, optional
    specialization NIDE , any year of study, summer semester, 5 credits, optional
    specialization NISY , any year of study, summer semester, 5 credits, optional
    specialization NMAL , any year of study, summer semester, 5 credits, optional
    specialization NMAT , any year of study, summer semester, 5 credits, compulsory
    specialization NSEN , any year of study, summer semester, 5 credits, optional
    specialization NVER , any year of study, summer semester, 5 credits, optional
    specialization NSPE , any year of study, summer semester, 5 credits, optional

  • 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, optional

Type of course unit

 

Lecture

26 hours, optionally

Teacher / Lecturer

doc. Mgr. Adam Rogalewicz, Ph.D.

Syllabus

  1. Introduction. Complexity, time and space complexity.
  2. Matematical models of computation, RAM, RASP machines and their relation with Turing machines.
  3. Asymptotic estimations, complexity classes, determinism and non-determinism from the point of view of complexity.
  4. Relation between time and space, closure of complexity classes w.r.t. complementation, proper inclusion of complexity classes.
  5. Blum theorem. Gap theorem.

  6. Reduction, notion of complete problems, well known examples of complete problems.
  7. Classes P and NP. NP-complete problems. SAT problem.
  8. Travelling salesman problem, Knapsack problem and other important NP-complete problems
  9. NP optimization problems and their deterministic solution: pseudo-polynomial algorithms, parametric complexity
  10. Approximation algorithms.
  11. Probabilistic algorithms, probabilistic complexity classes.
  12. Complexity and cryptography
  13. PSPACE-complete problems. Complexity and formal verification.

Projects

26 hours, compulsory

Teacher / Lecturer

doc. Mgr. Adam Rogalewicz, Ph.D.

Syllabus

4 projects dedicated on different aspects of the complexity theory.

eLearning

eLearning: currently opened course