Přístupnostní navigace
E-application
Search Search Close
Course detail
FIT-SLOaAcad. year: 2023/2024
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
Entry knowledge
Rules for evaluation and completion of the course
Final exam is performed in written form. The maximal amount of points one can get is 70 points
Aims
Study aids
Prerequisites and corequisites
Basic literature
Recommended reading
eLearning
Classification of course in study plans
branch MBI , any year of study, summer semester, electivebranch MPV , any year of study, summer semester, electivebranch MGM , any year of study, summer semester, elective
branch MGMe , any year of study, summer semester, compulsory-optional
branch MSK , any year of study, summer semester, elective
specialization MGH , any year of study, summer semester, recommended
branch MBS , any year of study, summer semester, electivebranch MIN , any year of study, summer semester, compulsory-optionalbranch MMM , any year of study, summer semester, compulsory-optional
specialization NADE , any year of study, summer semester, electivespecialization NBIO , any year of study, summer semester, electivespecialization NGRI , any year of study, summer semester, electivespecialization NNET , any year of study, summer semester, electivespecialization NVIZ , any year of study, summer semester, electivespecialization NCPS , any year of study, summer semester, electivespecialization NSEC , any year of study, summer semester, electivespecialization NEMB do 2021/22 , any year of study, summer semester, electivespecialization NEMB , any year of study, summer semester, electivespecialization NHPC , any year of study, summer semester, electivespecialization NISD , any year of study, summer semester, electivespecialization NIDE , any year of study, summer semester, electivespecialization NISY , any year of study, summer semester, electivespecialization NISY do 2020/21 , any year of study, summer semester, electivespecialization NMAL , any year of study, summer semester, electivespecialization NMAT , any year of study, summer semester, compulsoryspecialization NSEN , any year of study, summer semester, electivespecialization NVER , any year of study, summer semester, electivespecialization NSPE , any year of study, summer semester, elective
branch MIS , 1. year of study, summer semester, elective
Lecture
Teacher / Lecturer
Syllabus
Project