Город: Санкт-Петербург Казань Язык: Русский 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. Колмогоровская сложность., лекция ПОМИ РАН Нет
02 декабря 2016

Экзамен

Вопросы к экзамену: http://compsciclub.ru/learning/attachments/824VhmjL/

Экзамен можно сдать 8-го или 15-го декабря. Желающим сдавать экзамен следует как минимум за 24 часа до экзамена записаться по ссылке: https://docs.google.com/forms/d/1psaORbCMloNN5sLyQ6bVfYnPMH4NWEz9jwSLOhR6t_Y/viewform