Город: Санкт-Петербург Новосибирск Казань Язык: Русский 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, Лекция Конференция в 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, Онлайн Нет