Title:

# Complexity

Code:SLO
Ac.Year:2010/2011
Sem:Summer
Curriculums:
ProgrammeField/
Specialization
YearDuty
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
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/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 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 competencies:
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.
• NP-completness. 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 - classes RP and ZPP.
• Applications: Cryptography and one-way 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 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:

• Projects: max. 32 points
• Final exam: max. 68 points

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