Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Спецкурс «Сложность вычислений (полугодовой)»

Весенний семестр 2021 года

Спецкурс читается он-лайн по вторникам с 18:30 до 20:05. Первая лекция 17 февраля. Подключение по ссылке: https://us02web.zoom.us/j/89713098732?pwd=MHVBQ0lDaWhlbU1pN2tKeWU0WFo1UT09 Идентификатор конференции: 897 1309 8732, Код доступа: 546543

Новости

  • Во вторник 23 февраля лекция состоится (в обычное время)!

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

Видеозаписи лекций

Записи на доске во время лекций

Дневник лекций

Для сдачи спецкурса нужно каждую неделю решить две задачи. За задачи выставляются баллы, равные доле правильно решенных задач. Оценки за курс (при условии посещения лекций): отлично — 80% от максимального количества баллов, хорошо — 65%, удовлетворительно — 50%. Зачет — 60%. Для студентов ФКН ВШЭ: 93% — 10 баллов, 86% — 9 баллов, 80% — 8 баллов, 72% — 7 баллов, 65% — 6 баллов, 57% — 5 баллов, 50% — 4 балла, менее 50% — 3 балла.

Список задач с указанием сроков сдачи.

Результаты проверки домашних заданий здесь.

Конспект лекции про теорему о иерархии PdfPostscript.

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

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

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