Přístupnostní navigace
E-application
Search Search Close
Course detail
FIT-SLOaAcad. year: 2024/2025
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 literature
Classification of course in study plans
specialization MGH , 0 year of study, summer semester, recommended course
specialization NGRI , 0 year of study, summer semester, electivespecialization NADE , 0 year of study, summer semester, electivespecialization NISD , 0 year of study, summer semester, electivespecialization NMAT , 0 year of study, summer semester, compulsoryspecialization NSEC , 0 year of study, summer semester, electivespecialization NISY up to 2020/21 , 0 year of study, summer semester, electivespecialization NNET , 0 year of study, summer semester, electivespecialization NMAL , 0 year of study, summer semester, electivespecialization NCPS , 0 year of study, summer semester, electivespecialization NHPC , 0 year of study, summer semester, electivespecialization NVER , 0 year of study, summer semester, electivespecialization NIDE , 0 year of study, summer semester, electivespecialization NISY , 0 year of study, summer semester, electivespecialization NEMB , 0 year of study, summer semester, electivespecialization NSPE , 0 year of study, summer semester, electivespecialization NEMB , 0 year of study, summer semester, electivespecialization NBIO , 0 year of study, summer semester, electivespecialization NSEN , 0 year of study, summer semester, electivespecialization NVIZ , 0 year of study, summer semester, elective
Lecture
Teacher / Lecturer
Syllabus
Project