Теория вычислений

Магистратура 2022/2023

Статус: Курс по выбору (Современные компьютерные науки)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 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

Элементы контроля

Colloquium
Exam
HW

Промежуточная аттестация

2022/2023 учебный год 2 модуль
0.35 * Colloquium + 0.3 * Exam + 0.35 * HW

Программа дисциплины