ConvAppr24

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Экзамен 29.03.2024

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

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

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

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

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

Лекции будут по понедельникам, первая 15 января, начало 14:40, ауд. S301 (в дальнейшем аудитории будут меняться - смотрите распсиание или РУЗ). Семинары будут по субботам, более точная информация появится позже.

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

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

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

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


Контакты

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

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

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


Литература

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

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

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

Лекции

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

  1. (15.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
  2. (22.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии и выполнимости КНФ. (2.3, 3.3, 3.4, 3.5)
  3. (29.01) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2)
  4. (05.02) Метод эллипсоидов. Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (3.2, подробное изложение метода эллипсоидов см. в Корте, Фиген)
  5. (12.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3)
  6. (19.02) SDP релаксация для MAX2SAT. Оценки точности. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5)
  7. (26.02) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3)
  8. (04.03) SDP релаксация для задачи MAX-QP. Неравенство Гротендика. (7.1, 7.2, 5.6.1, 5.6.2)
  9. (11.03) SDP релаксации для задачи MAX-IND (7.3)
  10. (18.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.4, 10.5)

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

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

Ссылка на классрума для сдачи домашних заданий: ссылка.

Ссылка на гугл-диск с записями доски с семинаров: ссылка

  • Бонусное задание (на тему задачи 4.2б), правила получения бонусов см. в файле по ссылке.

Бонусную задачу решил Никита Звонков, он получает +1 балл к оценке за курс.

Вторая бонусная задача: 5.7. Условия выдачи бонусов те же. Условие даже разрешается ослабить: заменить 1/3 на какое-нибудь положительное число.

Третья бонусная задача: 6.6. Условия выдачи бонусов те же.

В задаче 6.7 ошибочно утверждалось, что релаксация неточна для 5-цикла (одновременно утверждалось, что SDP система совместна для 5-цикла, это верное утверждение). В качестве ещё одной бонусной задачи предлагается найти пример, когда SDP релаксация хроматического числа неточна.

Четвертая бонусная задача решена Федором Куяновым, он получает +1 к оценке за курс.

Источник — «http://wiki.cs.hse.ru/index.php?title=ConvAppr24&oldid=84315»