Title:  Complexity 

Code:  SLO 

Ac.Year:  2010/2011 

Term:  Summer 

Curriculums:  

Language of Instruction:  Czech, English 

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

Credits:  5 

Completion:  examination (written&verbal) 

Type of instruction:  Hour/sem  Lectures  Sem. Exercises  Lab. exercises  Comp. exercises  Other 

Hours:  26  0  0  0  26 

 Examination  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: 

  To learn mathematical models of computation and complexity theory.  Description: 

  This course covers the following themes: Matematical models of computation ( skeleton language, RAM, RASP models and their connection with Turing machines), time complexity, complexity classes, P and NP, NPcompletness, important NPcomplete problems, satisfability problem and its variants, other NPproblems, NP and coNP languages, space complexity, PS and NPS languages, PScomplete languages, language classes based on randomization, applications of computational complexity theory  cryptography and oneway functions.
 Learning outcomes and competences: 

  Understanding theoretical and practical limits of arbitrary computational systems.  Syllabus of lectures: 


 Introduction. Complexity, time and space complexity.
 Matematical models of computation. Skeleton language.
 RAM, RASP machines and their relation with Turing machines.
 Nondeterminism. Oracle machines. Reducibility.
 P and NP. Examples: Kruskal, Traveling Salesman.
 NPcompletness. NPcomplete problems.
 Satisfability problem and its variants.
 Other NPproblems.
 NP and coNP languages.
 Space complexity, PS and NPS languages.
 PScomplete languages.
 Language classes based on randomization  classes RP and ZPP.
 Applications: Cryptography and oneway functions.
 Syllabus  others, projects and individual work of students: 


 Project on Mathematical models of computation.
 Project on Complexity.
 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: 

   Projects: max. 32 points
 Final exam: max. 68 points
 Exam prerequisites: 

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