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

Introduction to theoretical computer science
Saint Petersburg / autumn 2016, посмотреть все семестры

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

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

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

Похожий курс читался в 2013 году: http://compsciclub.ru/courses/cs-intro/2013-autumn/

Date and time Class|Name Venue|short Materials
08 September
18:30–19:50
Лекция 1. О понятии "доказательства" в теоретической информатике, Lecture ПОМИ РАН No
08 September
20:00–21:20
Практика 1., Seminar ПОМИ РАН No
15 September
18:30–19:50
Лекция 2. Короткие доказательства и класс NP, Lecture ПОМИ РАН No
15 September
20:00–21:20
Практика 2., Seminar ПОМИ РАН No
22 September
18:30–19:50
Лекция 3. Машины Тьюринга. Элементы сложности доказательств., Lecture ПОМИ РАН No
22 September
20:00–21:20
Практика 3., Seminar ПОМИ РАН No
29 September
18:30–19:50
Лекция 4. Решение оптимизационных задач: вероятностное округление, Lecture ПОМИ РАН No
29 September
20:00–21:20
Практика 4., Seminar ПОМИ РАН No
06 October
18:30–19:50
Лекция 5. Линейное программирование, Lecture ПОМИ РАН No
13 October
18:30–19:50
Лекция 6. Двойственность задач линейного программирования, матричные игры, Lecture ПОМИ РАН No
20 October
18:30–19:50
Лекция 7. Принцип Яо. PCP-теорема., Lecture ПОМИ РАН No
27 October
18:30–19:50
Лекция 8. Конечные автоматы и вычисления с константной памятью., Lecture ПОМИ РАН No
03 November
18:30–19:50
Лекция 9. Вычисления с (поли)логарифмической памятью, Lecture ПОМИ РАН No
10 November
18:30–19:50
Лекция 10. Параллельные вычисления. Коды, исправляющие ошибки, Lecture ПОМИ РАН No
17 November
18:30–19:50
Лекция 11. Коды, исправляющие ошибки. Коммуникационная сложность., Lecture ПОМИ РАН No
24 November
18:30–19:50
Лекция 12. Энтропия и однозначно-декодируемые коды, Lecture ПОМИ РАН No
01 December
18:30–19:50
Лекция 13. Колмогоровская сложность., Lecture ПОМИ РАН No