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

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

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

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

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

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

Дата и время Занятие Место Материалы
14 сентября
22:30–23:50
Лекция 1. О доказательствах в теоретической информатике, Лекция Конференция в zoom, Онлайн видео,  другое
15 сентября
00:00–01:30
Семинар 1, Семинар Конференция в zoom, Онлайн файлы
21 сентября
22:30–23:50
Лекция 2. Короткие доказательства и класс NP, Лекция Конференция в zoom, Онлайн видео,  другое
22 сентября
00:00–01:20
Семинар 2, Семинар Конференция в zoom, Онлайн файлы
28 сентября
22:30–23:50
Лекция 3. Машины Тьюринга, Лекция Конференция в zoom, Онлайн видео,  другое
29 сентября
00:00–01:20
Семинар 3, Семинар Конференция в zoom, Онлайн файлы
05 октября
22:30–23:50
Лекция 4. Конечные автоматы., Лекция Конференция в zoom, Онлайн видео,  другое
06 октября
00:00–01:20
Семинар 4, Лекция Конференция в zoom, Онлайн файлы
12 октября
22:30–23:50
Лекция 5. Вычисления с малой памятью., Лекция Конференция в zoom, Онлайн видео,  другое
13 октября
00:00–01:20
Семинар 5, Семинар Конференция в zoom, Онлайн файлы
19 октября
22:30–23:50
Лекция 6. Вероятностный алгоритм достижимости. Параллельные вычисления, Лекция Конференция в zoom, Онлайн видео,  другое
20 октября
00:00–01:20
Семинар 6, Семинар Конференция в zoom, Онлайн файлы
26 октября
22:30–23:50
Лекция 7. Параллельное умножение и сложение. Коммуникационная сложность., Лекция Конференция в zoom, Онлайн видео,  другое
27 октября
00:00–01:20
Семинар 7, Семинар Конференция в zoom, Онлайн файлы
02 ноября
22:30–23:50
Лекция 8. Игры Карчмера-Вигдерсона. Код Хемминга., Лекция Конференция в zoom, Онлайн видео,  другое
03 ноября
00:00–01:20
Семинар 8, Семинар Конференция в zoom, Онлайн файлы
09 ноября
22:30–23:50
Лекция 9. Коды Уолша-Адамара и Рида-Соломона, Лекция Конференция в zoom, Онлайн видео,  другое
10 ноября
00:00–01:20
Семинар 9, Семинар Конференция в zoom, Онлайн файлы
16 ноября
22:30–23:50
Лекция 10. Энтропия. Колмогоровская сложность (начало), Лекция Конференция в zoom, Онлайн видео,  другое
17 ноября
00:00–01:20
Семинар 10, Семинар Конференция в zoom, Онлайн Нет
23 ноября
22:30–23:50
Лекция 11. Колмогоровская сложность (продолжение). Приближенные алгоритмы для MaxSAT, Лекция Конференция в zoom, Онлайн видео,  другое
24 ноября
00:00–01:20
Семинар 11, Семинар Конференция в zoom, Онлайн Нет
30 ноября
22:30–23:50
Лекция 12. Вероятностно-проверяемые доказательства. Маленькие k-невависимые множества., Лекция Конференция в zoom, Онлайн видео,  другое
01 декабря
00:00–01:20
Семинар 12, Семинар Конференция в zoom, Онлайн Нет
07 декабря
22:30–23:50
Лекция 13. Теорема о матричных играх и принцип Яо, Лекция Конференция в zoom, Онлайн видео,  файлыдругое
08 декабря
00:00–01:20
Семинар 13, Семинар Конференция в zoom, Онлайн Нет
15 декабря
00:00–01:20
Семинар 14, Семинар Конференция в zoom, Онлайн Нет