FI:I012 Complexity - Course Information
I012 Complexity
Faculty of InformaticsAutumn 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
- Informatics (programme FI, B-IN)
- Informatics (programme FI, M-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
- Information Technology (programme FI, B-IN)
- 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
- Enrolment Statistics (Autumn 1996, recent)
- Permalink: https://is.muni.cz/course/fi/autumn1996/I012