M7140 Complexity

Faculty of Science
Autumn 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.
The course is also listed under the following terms Autumn 2000.
  • Enrolment Statistics (Autumn 1999, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn1999/M7140