PřF:M7140 Complexity - Course Information
M7140 Complexity
Faculty of ScienceAutumn 2000
- Extent and Intensity
- 3/0/0. 5 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- prof. RNDr. Ivana Černá, CSc. (lecturer)
- Guaranteed by
- prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc. - Course Enrolment Limitations
- The course is only offered to the students of the study fields the course is directly associated with.
- fields of study / plans the course is directly associated with
- Mathematics (programme PřF, M-MA, specialization Discrete Mathematics)
- Mathematics (programme PřF, N-MA, specialization Discrete Mathematics)
- Course objectives
- Problems and algorithms
Basic computational models and complexity measures.
Relations between complexity classes. Turing thesis.
Reductions and completeness. NP-complete problems.
coNP and function problems.
Lower bounds.
Randomized computation, randomized complexity classes.
Parallel computation. Parallel models of computation, the class NC. Parallel computation thesis.
Approximability. Approximation algorithms and their performance. Nonapproximability.
Applications: Cryptography and one-way functions. - Literature
- SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
- PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
- BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
The course is taught annually.
The course is taught: every week.
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/sci/autumn2000/M7140