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

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

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

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

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

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

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