FI:IA012 Complexity - Course Information
IA012 Complexity
Faculty of InformaticsAutumn 2024
- Extent and Intensity
- 2/0/1. 3 credit(s) (plus extra credits for completion). 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.
Supplier department: Department of Computer Science – Faculty of Informatics - Timetable
- Wed 18. 9. to Wed 11. 12. Wed 14:00–15:50 B411
- Prerequisites
- The course expands on course IB107 Computability and Complexity.
- 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
- Image Processing and Analysis (programme FI, N-VIZ)
- Bioinformatics and systems biology (programme FI, N-UIZD)
- Computer Games Development (programme FI, N-VIZ_A)
- Computer Graphics and Visualisation (programme FI, N-VIZ_A)
- Computer Networks and Communications (programme FI, N-PSKB_A)
- Cybersecurity Management (programme FI, N-RSSS_A)
- Discrete algorithms and models (programme FI, N-TEI)
- Formal analysis of computer systems (programme FI, N-TEI)
- Graphic design (programme FI, N-VIZ)
- Graphic Design (programme FI, N-VIZ_A)
- Hardware Systems (programme FI, N-PSKB_A)
- Hardware systems (programme FI, N-PSKB)
- Image Processing and Analysis (programme FI, N-VIZ_A)
- Information security (programme FI, N-PSKB)
- Information Security (programme FI, N-PSKB_A)
- Quantum and Other Nonclassical Computational Models (programme FI, N-TEI)
- Computer graphics and visualisation (programme FI, N-VIZ)
- Computer Networks and Communications (programme FI, N-PSKB)
- Principles of programming languages (programme FI, N-TEI)
- Cybersecurity management (programme FI, N-RSSS)
- Services development management (programme FI, N-RSSS)
- Software Systems Development Management (programme FI, N-RSSS)
- Services Development Management (programme FI, N-RSSS_A)
- Software Systems Development Management (programme FI, N-RSSS_A)
- Software systems (programme FI, N-PSKB)
- Machine learning and artificial intelligence (programme FI, N-UIZD)
- Computer Games Development (programme FI, N-VIZ)
- Processing and analysis of large-scale data (programme FI, N-UIZD)
- Natural language processing (programme FI, N-UIZD)
- Course objectives
- Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
- Learning outcomes
- After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms. - Syllabus
- The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
- The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
- Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
- Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
- Alternation and games. Interactive protocols and interactive proof systems.
- Lower bounds techniques. Kolmogorov complexity.
- Descriptive complexity.
- Literature
- required literature
- SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
- recommended literature
- ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
- SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
- PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
- Bookmarks
- https://is.muni.cz/ln/tag/FI:IA012!
- Teaching methods
- Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
- Assessment methods
- Lectures. Oral exam at the end of the term and individual project during the term.
- Language of instruction
- Czech
- Further Comments
- Study Materials
The course is taught annually. - Teacher's information
- https://is.muni.cz/auth/el/1433/podzim2024/IA012/index.qwarp
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/autumn2024/IA012