Title:

Complexity

Code:SLO
Ac.Year:2011/2012
Term:Summer
Study plans:
ProgramBranchYearDuty
IT-MSC-2MBI-Elective
IT-MSC-2MBS-Elective
IT-MSC-2MGM-Elective
IT-MSC-2MGM.-Elective
IT-MSC-2MIN-Compulsory-Elective - group B
IT-MSC-2MIN.2ndElective
IT-MSC-2MIS1stElective
IT-MSC-2MIS.1stElective
IT-MSC-2MMI-Elective
IT-MSC-2MMM-Compulsory-Elective - group L
IT-MSC-2MPS-Elective
IT-MSC-2MPV-Elective
IT-MSC-2MSK-Elective
IT-MSC-2EITE2ndElective
Language:Czech, English
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
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.