Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Структурная теория сложности
Осень 2008, посмотреть все семестры

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

Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область информатики содержит как "великие" нерешенные задачи (например, P vs NP — одна из семи задач, за решение которых Clay Mathematical Institute объявил призы по $1,000,000), так и красивые теоремы (теорема Шамира об интерактивных доказательствах, теорема Разборова о монотонных логических схемах…). Без знания теории сложности невозможно глубокого понимания криптографии и многих других областей теоретической информатики.

Конспекты лекций, читавшихся ранее: http://logic.pdmi.ras.ru/~hirsch/students/complexity1/

Видео лекций https://www.lektorium.tv/course/22750?id=22750

Дата и время Название Место Материалы
28 сентября
14:15–15:45
Лекции 1-2, лекция ПОМИ РАН слайды
12 октября
14:15–15:45
Лекции 3-4, лекция ПОМИ РАН слайды
26 октября
14:15–15:45
Лекции 5-6, лекция ПОМИ РАН слайды
09 ноября
14:25–15:55
Лекции 7-8, лекция ПОМИ РАН слайды
16 ноября
14:30–16:00
Лекции 9-10, лекция ПОМИ РАН слайды
23 ноября
14:30–16:00
Лекции 11-12, лекция ПОМИ РАН слайды