Title:  Complexity 

Code:  SLO 

Ac.Year:  2014/2015 

Sem:  Summer 

Curriculums:  

Language of Instruction:  Czech 

Private info:  http://www.fit.vutbr.cz/study/courses/SLO/private/ 

Credits:  5 

Completion:  examination (written&oral) 

Type of instruction:  Hour/sem  Lectures  Seminar Exercises  Laboratory Exercises  Computer Exercises  Other 

Hours:  26  0  0  0  26 

 Exams  Tests  Exercises  Laboratories  Other 

Points:  68  0  0  0  32 



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:  

Followups:  

Substitute for:  


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
spaceconstructive functions, typical examples of complexity classes.
Properties of complexity classes: importance of determinism and
nondeterminism in the area of computational complexity, Savitch
theorem, relation between nondeterminism 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 NPcomplete 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: 

  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 nondeterminism 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. NPcomplete problems. SAT problem.
 Travelling salesman problem, Knapsack problem and other important NPcomplete problems
 NP optimization problems and their deterministic solution: pseudopolynomial algorithms, parametric complexity
 Approximation algorithms.
 Probabilistic algorithms, probabilistic complexity classes.
 Complexity and cryptography
 PSPACEcomplete 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 1850322430
 Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0201441241

Study literature: 


 Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1850322430
 Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0201441241

Progress assessment: 

   4 projects  8 points each.
 Final exam: max. 68 points

Exam prerequisites: 

  The minimal total score of 15 points gained out of the projects. 
