2022/2023
Теория вычислений
Статус:
Маго-лего
Кто читает:
Базовая кафедра Яндекс
Когда читается:
1, 2 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Контактные часы:
56
Программа дисциплины
Аннотация
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.
Цель освоения дисциплины
- 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
Планируемые результаты обучения
- To know algorithms for prime testing and cryptography
- To know circuit complexity, the classes NC_k and AC_k, and P-completeness
- To know problems that are complete for NP and PSPACE
- To know several classes in communication complexity
- To know the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP; relations among these classes (including separations through the hierarchy theorems); famous open problems
Содержание учебной дисциплины
- Complexity classes P and NP, reductions, NP-completeness and hierarchy theorems
- L, NL, PSPACE, EXPSPACE, and PSPACE-completeness of some games
- Oracle computations and oracles the P vs NP problem relative to specific oracles
- Randomized computation and prime testing
- Communication complexity, property testing, PCP-theorems and inapproximability of NP-hard problems
- Cryptography
- Circuit complexity and parallel algorithms
Список литературы
Рекомендуемая основная литература
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
Рекомендуемая дополнительная литература
- Du, D., & Ko, K.-I. (2014). Theory of Computational Complexity (Vol. Second edition). Hoboken, New Jersey: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=784130
- Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography (Vol. Second edition). Boca Raton, FL: Chapman and Hall/CRC. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=1766746
- Roughgarden, T. (2015). Communication Complexity (for Algorithm Designers). Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1509.06257