Course detail
Complexity
FIT-SLOAcad. year: 2014/2015
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.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Learning outcomes of the course unit
Prerequisites
Co-requisites
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
The minimal total score of 15 points gained out of the projects.
Course curriculum
- 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.
- Project on Mathematical models of computation.
- Project on Complexity.
Syllabus - others, projects and individual work of students:
Work placements
Aims
Specification of controlled education, way of implementation and compensation for absences
- Projects: max. 32 points
- Final exam: max. 68 points
Recommended optional programme components
Prerequisites and corequisites
Basic literature
Recommended reading
Classification of course in study plans
- Programme IT-MSC-2 Master's
branch MBI , 0 year of study, summer semester, elective
branch MBS , 0 year of study, summer semester, elective
branch MIN , 0 year of study, summer semester, compulsory-optional
branch MIS , 1 year of study, summer semester, elective
branch MMI , 0 year of study, summer semester, elective
branch MMM , 0 year of study, summer semester, compulsory-optional
branch MPV , 0 year of study, summer semester, elective
branch MSK , 0 year of study, summer semester, elective
branch MGM , 0 year of study, summer semester, elective