Сложность вычислений (спецкурс, весна 2021)
Весенний семестр 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 балла.
Список задач с указанием сроков сдачи.
Результаты проверки домашних заданий здесь.
Конспект лекции про теорему о иерархии Pdf, Postscript.
Конспект лекций о сложности в среднем (обновлено 24-Mar-2009): PDF, PS.
Конспект лекции о PSPACE-полноте задачи об универсальности регулярных выражений: TeX, Pdf, Postscript.
Конспект лекции о #P-полноте задачи о перманенте (обновлено 9-Dec-2008): Pdf, Postscript.