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