Přístupnostní navigace
E-application
Search Search Close
Course detail
FIT-SLOaAcad. year: 2019/2020
Turing machines as a basic computational model for computational complexity analysis, time and space complexity on Turing machines. Alternative models of computation, RAM and RASP machines and their relation to Turing machines in the context of complexity. Asymptotic complexity estimations, complexity classes based on time- and space-constructive functions, typical examples of complexity classes. Properties of complexity classes: importance of determinism and non-determinism in the area of computational complexity, Savitch theorem, relation between non-determinism and determinism, closure w.r.t. complement of complexity classes, proper inclusion between complexity classes. Selected advanced properties of complexity classes: Blum theorem, gap theorem. Reduction in the context of complexity and the notion of complete classes. Examples of complete problems for different complexity classes. Deeper discussion of P and NP classes with a special attention on NP-complete problems (SAT problem, etc.). Relationship between decision and optimization problems. Methods for computational solving of hard optimization problems: deterministic approaches, approximation, probabilistic algorithms. Relation between complexity and cryptography. Deeper discussion of PSPACE complete problems, complexity of formal verification methods.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Offered to foreign students
Learning outcomes of the course unit
Prerequisites
Co-requisites
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
Course curriculum
Work placements
Aims
Specification of controlled education, way of implementation and compensation for absences
Recommended optional programme components
Prerequisites and corequisites
Basic literature
Recommended reading
Classification of course in study plans
branch MBI , 0 year of study, summer semester, elective
branch MGH , 0 year of study, summer semester, recommended course
branch MSK , 0 year of study, summer semester, electivebranch MMM , 0 year of study, summer semester, compulsory-optionalbranch MBS , 0 year of study, summer semester, electivebranch MPV , 0 year of study, summer semester, electivebranch MIS , 1 year of study, summer semester, electivebranch MIN , 0 year of study, summer semester, compulsory-optionalbranch MGM , 0 year of study, summer semester, elective
branch MGMe , 0 year of study, summer semester, compulsory-optional
specialization NMAT , 0 year of study, summer semester, compulsoryspecialization NBIO , 0 year of study, summer semester, electivespecialization NSEN , 0 year of study, summer semester, electivespecialization NVIZ , 0 year of study, summer semester, electivespecialization NGRI , 0 year of study, summer semester, electivespecialization NISD , 0 year of study, summer semester, electivespecialization NSEC , 0 year of study, summer semester, electivespecialization NCPS , 0 year of study, summer semester, electivespecialization NHPC , 0 year of study, summer semester, electivespecialization NNET , 0 year of study, summer semester, electivespecialization NMAL , 0 year of study, summer semester, electivespecialization NVER , 0 year of study, summer semester, electivespecialization NIDE , 0 year of study, summer semester, electivespecialization NEMB , 0 year of study, summer semester, electivespecialization NSPE , 0 year of study, summer semester, electivespecialization NADE , 0 year of study, summer semester, electivespecialization NISY , 0 year of study, summer semester, elective
Lecture
Teacher / Lecturer
Syllabus
Project