I012 Complexity

Faculty of Informatics
Autumn 2001
Extent and Intensity
3/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Tue 9:00–11:50 D1
Prerequisites
I005 Formal Languages and Automata I
Before enrolling this course the students should go through I005 Formal Languages and Automata I.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
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
Assessment methods (in Czech)
Závěrečné hodnocení je založeno na výsledcích písemné zkoušky.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i012.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Autumn 1999, Autumn 2000, Autumn 2002, Autumn 2003.
  • Enrolment Statistics (Autumn 2001, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2001/I012