Bachelor
2022/2023
Theory of Computation
Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'
Type:
Elective course (Applied Mathematics and Information Science)
Area of studies:
Applied Mathematics and Information Science
Delivered by:
Big Data and Information Retrieval School
Where:
Faculty of Computer Science
When:
3 year, 1, 2 module
Mode of studies:
offline
Open to:
students of one campus
Language:
English
ECTS credits:
5
Contact hours:
60
Course Syllabus
Abstract
This course teaches a mathematical theory that helps to invent better algorithms. With “better” we mean that the algorithms use fewer resources such as time or memory. We also consider parallel computation, distributed systems and learning problems. In these settings we might also optimize other types of resources. For example, in distributed systems we might want to minimize the amount of communication. We focuss on worst case guarantees. A large part of our time is devoted to the study of what is not possible. In other words, we study fundamental barriers for the existence of programs that use fewer resources than a given bound.
Learning Objectives
- understand the concepts of the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP
- be able to critically analyse resources used by a program (and optimize them at a high level)
- be able to recognize intractable problems and categorize their difficulty
- be able to recognize intractable problems and categorize their difficulty
- have deeper understanding and trained problem solving skills of known materials in: algebra, probability theory, discrete math, algorithms
