Курс "Сложность вычислений (годовой)"

2015/2016 учебный год

Объявление: лекция 20 февраля отменяется! Следующая лекция - 29 февраля (вопреки сказанному на последней лекции).

Программа курса

Дневник лекций 2015/2016 учебного года

Для сдачи спецкурса нужно каждую неделю решить две задачи. Список задач с указанием сроков сдачи. Задачи дублируются на Гуглдиске здесь. Результаты проверки домашних заданий здесь.

2012/2013 учебный год

Программа курса

Дневник лекций 2012/2013 учебного года

2010/2011 учебный год

Экзамены

На экзамене можно пользоваться рукописными конспектами, но не книгами.

Первый экзамен состоится в среду 25 мая в 15:00, ауд. 1605

Второй экзамен состоится в понедельник 6 июня в 11:00, около ауд. 1306 или 1311 (совместно с Госэкзаменом)

Третий экзамен состоится в пятницу 10 июня в 10:00, ауд. 1605

Четвёртый экзамен состоится в понедельник 20 июня в 13:00, ауд. 1622

Программа курса 2010/2011 учебного года

Дневник лекций 2010/2011 учебного года

2008/2009 учебный год

Осенью 2008 и весной 2009 года лекции состоятся по понедельникам 18:30-20:05, ауд. 14-14.

Программа курса 2008/2009 учебного года

Дневник лекций 2008/2009 учебного года

Дневник лекций осенью 2006 года (полугодовой курс)

Программа экзамена по полугодовому курсу: TeX, Pdf, Postscript.

Задачи к экзамену по полугодовому курсу: TeX, Pdf, Postscript.

Конспекты лекций. Просьба посылать все замечания о конспектах о электронной почте на ver@mccme.ru.

Конспект лекции о теоремах о иерархии: TeX, Pdf, Postscript.

Конспект лекций о сложности в среднем (обновлено 24-Mar-2009): PDF, PS.

Конспект лекции о PSPACE-полноте задачи об универсальности регулярных выражений: TeX, Pdf, Postscript.

Конспект лекции о #P-полноте задачи о перманенте (обновлено 9-Dec-2008): Pdf, Postscript.