City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Introduction to Theoretical Computer Science
Saint Petersburg / autumn 2020, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

Date and time Class|Name Venue|short Materials
14 September
18:30–19:50
Лекция 1. О доказательствах в теоретической информатике, Lecture Конференция в zoom, Онлайн video,  other
14 September
20:00–21:30
Семинар 1, Seminar Конференция в zoom, Онлайн files
21 September
18:30–19:50
Лекция 2. Короткие доказательства и класс NP, Lecture Конференция в zoom, Онлайн video,  other
21 September
20:00–21:20
Семинар 2, Seminar Конференция в zoom, Онлайн files
28 September
18:30–19:50
Лекция 3. Машины Тьюринга, Lecture Конференция в zoom, Онлайн video,  other
28 September
20:00–21:20
Семинар 3, Seminar Конференция в zoom, Онлайн files
05 October
18:30–19:50
Лекция 4. Конечные автоматы., Lecture Конференция в zoom, Онлайн video,  other
05 October
20:00–21:20
Семинар 4, Lecture Конференция в zoom, Онлайн files
12 October
18:30–19:50
Лекция 5. Вычисления с малой памятью., Lecture Конференция в zoom, Онлайн video,  other
12 October
20:00–21:20
Семинар 5, Seminar Конференция в zoom, Онлайн files
19 October
18:30–19:50
Лекция 6. Вероятностный алгоритм достижимости. Параллельные вычисления, Lecture Конференция в zoom, Онлайн video,  other
19 October
20:00–21:20
Семинар 6, Seminar Конференция в zoom, Онлайн files
26 October
18:30–19:50
Лекция 7. Параллельное умножение и сложение. Коммуникационная сложность., Lecture Конференция в zoom, Онлайн video,  other
26 October
20:00–21:20
Семинар 7, Seminar Конференция в zoom, Онлайн files
02 November
18:30–19:50
Лекция 8. Игры Карчмера-Вигдерсона. Код Хемминга., Lecture Конференция в zoom, Онлайн video,  other
02 November
20:00–21:20
Семинар 8, Seminar Конференция в zoom, Онлайн files
09 November
18:30–19:50
Лекция 9. Коды Уолша-Адамара и Рида-Соломона, Lecture Конференция в zoom, Онлайн video,  other
09 November
20:00–21:20
Семинар 9, Seminar Конференция в zoom, Онлайн files
16 November
18:30–19:50
Лекция 10. Энтропия. Колмогоровская сложность (начало), Lecture Конференция в zoom, Онлайн video,  other
16 November
20:00–21:20
Семинар 10, Seminar Конференция в zoom, Онлайн No
23 November
18:30–19:50
Лекция 11. Колмогоровская сложность (продолжение). Приближенные алгоритмы для MaxSAT, Lecture Конференция в zoom, Онлайн video,  other
23 November
20:00–21:20
Семинар 11, Seminar Конференция в zoom, Онлайн No
30 November
18:30–19:50
Лекция 12. Вероятностно-проверяемые доказательства. Маленькие k-невависимые множества., Lecture Конференция в zoom, Онлайн video,  other
30 November
20:00–21:20
Семинар 12, Seminar Конференция в zoom, Онлайн No
07 December
18:30–19:50
Лекция 13. Теорема о матричных играх и принцип Яо, Lecture Конференция в zoom, Онлайн video,  filesother
07 December
20:00–21:20
Семинар 13, Seminar Конференция в zoom, Онлайн No
14 December
20:00–21:20
Семинар 14, Seminar Конференция в zoom, Онлайн No