PřF:M7140 Complexity - Course Information
M7140 Complexity
Faculty of ScienceAutumn 1999
- 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)
- Syllabus
- 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 is taught annually.
The course is taught: every week.
- Enrolment Statistics (Autumn 1999, recent)
- Permalink: https://is.muni.cz/course/sci/autumn1999/M7140