Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Теория сложности вычислений
Санкт-Петербург / осень 2021, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Основная задача теории сложности вычислений --- выяснить, что можно, и что нельзя вычислить в рамках имеющихся ресурсов (обычно под ресурсами понимается время и память) при этом акцент делается на выяснения причины трудности вычислительных задач. В курсе мы изучим как классические вещи (классы P, NP, сводимость и NP-полнота), так и более продвинутые вещи: вычисления с ограниченной памятью, полиномиальную иерархию, булевы схемы, вероятностные алгоритмы, интерактивные протоколы и вероятностно проверяемые доказательства.

Курс будет излагаться на математическом уровне строгости, однако не требует специфических математических знаний, выходящих за рамки программ первых двух курсов технических специальностей (алгебра, математический анализ, основы дискретной математики, и основы теории вероятностей).

Список вопросов к экзамену

Краткий конспект лекций

Лекции будут читаться через Zoom. Ссылка для подключения будет опубликована в новостях курса (её получат те, кто запишется на курс).

Дата и время Занятие Место Материалы
14 сентября
18:30–19:50
Лекция 1. Машины Тьюринга и булевы схемы, Лекция Конференция в zoom, Онлайн слайды,  видео
14 сентября
20:00–21:20
Семинар 1, Семинар Конференция в zoom, Онлайн
21 сентября
18:30–19:50
Лекция 2. Класс NP, недетерминированные машины Тьюринга., Лекция Конференция в zoom, Онлайн слайды,  видео
21 сентября
20:00–21:20
Семинар 2, Лекция Конференция в zoom, Онлайн
28 сентября
18:30–19:50
Лекция 3. Теорема Кука-Левина, задачи поиска, Лекция Конференция в zoom, Онлайн слайды,  видео
28 сентября
20:00–21:20
Семинар 3, Лекция Конференция в zoom, Онлайн
05 октября
18:30–19:50
Лекция 4. Между P и NP., Лекция Конференция в zoom, Онлайн слайды,  видео
05 октября
20:00–21:20
Семинар 4, Лекция Конференция в zoom, Онлайн
12 октября
18:30–19:50
Лекция 5. Вычисления с ограничениями по памяти., Лекция Конференция в zoom, Онлайн слайды,  видео
12 октября
20:00–21:20
Семинар 5, Лекция Конференция в zoom, Онлайн
19 октября
18:30–19:50
Лекция 6. Логарифмическая память, Лекция Конференция в zoom, Онлайн слайды,  видео
19 октября
20:00–21:20
Семинар 6, Семинар Конференция в zoom, Онлайн
26 октября
18:30–19:50
Лекция 7. Полиномиальная иерархия, Лекция Конференция в zoom, Онлайн слайды,  видео
26 октября
20:00–21:20
Семинар 7, Семинар Конференция в zoom, Онлайн
02 ноября
18:30–19:50
Лекция 8. Вычисления с ограниченим и по времени, и по памяти. Схемная сложность., Лекция Конференция в zoom, Онлайн слайды,  видео
02 ноября
20:00–21:20
Семинар 8, Семинар Конференция в zoom, Онлайн
09 ноября
18:30–19:50
Лекция 9. Вероятностные классы сложности., Лекция Конференция в zoom, Онлайн слайды,  видео
09 ноября
20:00–21:20
Семинар 9, Семинар Конференция в zoom, Онлайн
16 ноября
18:30–19:50
Лекция 10. Интерактивные доказательства, Лекция Конференция в zoom, Онлайн слайды,  видео
16 ноября
20:00–21:20
Семинар 10, Семинар Конференция в zoom, Онлайн
23 ноября
18:30–19:50
Лекция 11. Вероятностно-проверяемые доказательства, Лекция Конференция в zoom, Онлайн слайды,  видео
23 ноября
20:00–21:20
Семинар 11, Семинар Конференция в zoom, Онлайн
30 ноября
18:30–19:50
Лекция 12. Вероятностно-проверяемые доказательства, окончание, Лекция Конференция в zoom, Онлайн слайды,  видео
30 ноября
20:00–21:20
Семинар 12, Семинар Конференция в zoom, Онлайн