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

Обзорный курс по теоретической информатике
Санкт-Петербург / осень 2020, посмотреть все семестры

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

Это содержательный курс, который даст слушателям представление не только о различных областях теоретической информатики, но также и об основных методах и идеях. Мы поговорим про такие области: алгоритмическая неразрешимость, сложность вычислений, понятие доказательств в информатике (классические, интерактивные, вероятностно проверяемые, доказательства с нулевым разглашением), линейное программирование и принцип двойственности, вычисления с малой памятью, параллельные вычисления, вероятностные алгоритмы, теория информации (классическая и алгоритмическая), коммуникационная сложность, тестирование свойств и пр.

Курс не требует никаких предварительных знаний, выходящих за программу первых двух курсов ВУЗов, но существенно проще будет тем, кто уже прослушал курсы по дискретной математике, алгоритмам и структурам данных и теории вероятностей.

Похожий курс читался в 2013 и 2016 годах.

Дата и время Занятие Место Материалы
14 сентября
18:30–19:50
Лекция 1. О доказательствах в теоретической информатике, Лекция Конференция в zoom, Онлайн видео,  другое
14 сентября
20:00–21:30
Семинар 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, Онлайн файлы
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. Колмогоровская сложность (продолжение). Приближенные алгоритмы для MaxSAT, Лекция Конференция в zoom, Онлайн видео,  другое
23 ноября
20:00–21:20
Семинар 11, Семинар Конференция в zoom, Онлайн Нет
30 ноября
18:30–19:50
Лекция 12. Вероятностно-проверяемые доказательства. Маленькие k-невависимые множества., Лекция Конференция в zoom, Онлайн видео,  другое
30 ноября
20:00–21:20
Семинар 12, Семинар Конференция в zoom, Онлайн Нет
07 декабря
18:30–19:50
Лекция 13. Теорема о матричных играх и принцип Яо, Лекция Конференция в zoom, Онлайн видео,  файлыдругое
07 декабря
20:00–21:20
Семинар 13, Семинар Конференция в zoom, Онлайн Нет
14 декабря
20:00–21:20
Семинар 14, Семинар Конференция в zoom, Онлайн Нет