ConvApprox26

Экзамен 27.03.2026

Аудитория D101. Время экзамена с 11 до 15. Чтобы всем не сидеть так долго, запишитесь в таблицу участия.

Экзамен устный. В билете два вопроса: один на знание определений и формулировок утверждений, второй - на знание доказательств. На подготовку ответа даётся около получаса. Использовать печатные или электронные материалы при подготовке нельзя. При ответе допустимы пропуски технически трудных моментов рассуждений. При необходимости экзаменатор может попросить восстановить пропуски, используя учебные материалы.

Программа экзамена.

Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы

Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи.

Лекции будут по понедельникам, первая 19 января, начало 11:10, аудитория S324.

Правила оценивания

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

Вес домашних заданий в итоговой оценке равен 0.4, вес экзамена равен 0.6. Округление арифметическое.

Ссылка на таблицу с оценками.

Контакты

Чат курса в telegram: https://t.me/+qnh5yDSxQhgxOTcy

Лектор: Вялый Михаил Николаевич, e-mail: vyalyi@gmail.com, telegram: @mnvyalyi.

Семинарист: Павел Александрович Захаров, telegram: @DuckBinLaden

Литература

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

Кроме того, полезными могут оказаться следующие книги:

Approximation algorithms, V. Vazirani, 2001.
Комбинаторная оптимизация: теория и алгоритмы, Корте, Б., Фиген, Й., 2015.
Методы выпуклой оптимизации, Нестеров, Ю. Е.
Н.В.Верещагин, М.Н.Вялый Записки о линейном программировании (учебные материалы для курса ДМ2 2017 года)

Лекции

В конце описания лекции указаны ссылки на соответствующие разделы черновика электронного учебника.

(19.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
(26.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии. (2.3, 3.3, 3.4)
(02.02) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2)
(09.02) Метод эллипсоидов. Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (3.2 (подробное изложение метода эллипсоидов см. в Корте, Фиген), 3.6)
(16.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Задачи SDP программирования, полиномиальные приближенные алгоритмы их решения. (5.1, 5.2, 5.3)
(25.02) SDP релаксация для MAX2SAT. Оценки точности. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5)
(02.03) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3)
(11.03) SDP релаксация для задачи MAX-QP. Неравенство Гротендика. (7.1, 7.2, 5.6.1, 5.6.2)
(16.03) SDP релаксации для задачи MAX-IND (7.3)
(23.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.4)

Материалы для семинаров и домашние задания

Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара.

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