Title:

Complexity

Code:SLO
Ac.Year:2012/2013
Term:Summer
Study plans:
ProgramBranchYearDuty
IT-MSC-2MBI-Elective
IT-MSC-2MBS-Elective
IT-MSC-2MGM-Elective
IT-MSC-2MIN-Compulsory-Elective - group B
IT-MSC-2MIS1stElective
IT-MSC-2MMI-Elective
IT-MSC-2MMM-Compulsory-Elective - group L
IT-MSC-2MPV-Elective
IT-MSC-2MSK-Elective
IT-MSC-2EITE2ndElective
Language:Czech
Private info:http://www.fit.vutbr.cz/study/courses/SLO/private/
Credits:5
Completion:examination (written&verbal)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:2600026
 ExaminationTestsExercisesLaboratoriesOther
Points:6800032
Guarantee:Vojnar Tomáš, prof. Ing., Ph.D., DITS
Lecturer:Rogalewicz Adam, Mgr., Ph.D., DITS
Instructor:Rogalewicz Adam, 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
Formal Analysis and Verification (FAV), DITS
Parallel and Distributed Algorithms (PRL), DITS
Substitute for:
Computability and Complexity (VSL), DITS
 
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, NP-completness, important NP-complete problems, satisfability problem and its variants, other NP-problems, NP and co-NP languages, space complexity, PS and NPS languages, PS-complete languages, language classes based on randomization, applications of computational complexity theory - cryptography and one-way functions.
Learning outcomes and competences:
Understanding theoretical and practical limits of arbitrary computational systems.
Syllabus of lectures:
  1. Introduction. Complexity, time and space complexity.
  2. Matematical models of computation. Skeleton language.
  3. RAM, RASP machines and their relation with Turing machines.
  4. Nondeterminism. Oracle machines. Reducibility.
  5. P and NP. Examples: Kruskal, Traveling Salesman.
  6. NP-completness. NP-complete problems.
  7. Satisfability problem and its variants.
  8. Other NP-problems.
  9. NP and co-NP languages.
  10. Space complexity, PS and NPS languages.
  11. PS-complete languages.
  12. Language classes based on randomization - classes RP and ZPP.
  13. Applications: Cryptography and one-way functions.
Syllabus - others, projects and individual work of students:
  1. Project on Mathematical models of computation.
  2. Project on Complexity.
Fundamental literature:
  1. Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  2. Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
Study literature:
  1. Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  2. Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
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.