Title:

# Complexity (in English)

Code:SLOa
Ac.Year:2018/2019
Sem:Summer
Curriculums:
ProgrammeField/
Specialization
YearDuty
IT-MSC-2MBI-Elective
IT-MSC-2MBS-Elective
IT-MSC-2MGM-Elective
IT-MSC-2MGMe-Compulsory-Elective - group M
IT-MSC-2MIN-Compulsory-Elective - group B
IT-MSC-2MIS1stElective
IT-MSC-2MMM-Compulsory-Elective - group L
IT-MSC-2MPV-Elective
IT-MSC-2MSK-Elective
Language of Instruction:English
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 or Czech according to the individual preferences.

Private info:http://www.fit.vutbr.cz/study/courses/SLOa/private/
Credits:5
Completion:examination (written&oral)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:2600026
ExamsTestsExercisesLaboratoriesOther
Points:6800032
Guarantor:Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
Lecturer:Rogalewicz Adam, doc. Mgr., Ph.D. (DITS)
Instructor:Rogalewicz Adam, doc. Mgr., Ph.D. (DITS)
Faculty:Faculty of Information Technology BUT
Department:Department of Intelligent Systems FIT BUT
Prerequisites:
 Theoretical Computer Science (TIN), DITS
Follow-ups:
 Cryptography (KRY), DITS Parallel and Distributed Algorithms (PRL), DITS Static Analysis and Verification (FAV), DITS
Substitute for:
 Computability and Complexity (VSL), DITS

Learning objectives:
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.
Description:
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.
Knowledge and skills required for the course:
Formal language theory and theory of computability on master level.
Learning outcomes and competencies:
Understanding theoretical and practical limits of arbitrary computational systems. Ability to use a selected methods for computationally hard problems.
Syllabus of lectures:

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.
Syllabus - others, projects and individual work of students:
4 projects dedicated on different aspects of the complexity theory.
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
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
Progress assessment:

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