Course details

# Complexity

SLO Acad. year 2014/2015 Summer semester 5 credits

Guarantor

Language of instruction

Completion

Time span

Assessment points

Department

Lecturer

Instructor

Subject specific learning outcomes and competences

Learning objectives

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

Prerequisite kwnowledge and skills

Study literature

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

Fundamental literature

- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- 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.
- Final exam: max. 68 points

Exam prerequisites

Course inclusion in study plans