FI:I012 Complexity - Course Information

I012 Complexity

Faculty of Informatics
Autumn 1996

Extent and Intensity

3/0. 3 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Ivana Černá, CSc. (lecturer)

Guaranteed by

Contact Person: prof. RNDr. Ivana Černá, CSc.

Prerequisites

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.

Language of instruction

Czech

Teacher's information

http://www.fi.muni.cz/usr/cerna/i012.html