ConvAppr22 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Milovanov (обсуждение | вклад) |
Milovanov (обсуждение | вклад) |
||
| (не показано 39 промежуточных версии 2 участников) | |||
| Строка 2: | Строка 2: | ||
Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи. | Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи. | ||
| + | |||
| + | Курс начинается 10 января! | ||
| + | |||
| + | ===Экзамен=== | ||
| + | |||
| + | Экзамен по курсу пройдёт 30 марта (среда), начало 17:00, ауд. R408. | ||
| + | |||
| + | Экзамен устный. В билете два вопроса: один на знание определений и формулировок утверждений, второй - на знание доказательств. | ||
| + | |||
| + | На подготовку ответа даётся около получаса. Использовать печатные или электронные материалы при подготовке нельзя. При ответе допустимы пропуски технически трудных моментов рассуждений. При необходимости экзаменатор может попросить восстановить пропуски, используя учебные материалы. | ||
| + | |||
| + | [https://www.dropbox.com/s/z3l2r7sac3u1xs7/exam-program.pdf?dl=0 Программа экзамена] | ||
===Правила оценивания=== | ===Правила оценивания=== | ||
| Строка 15: | Строка 27: | ||
Семинарист: Алексей Милованов, e-mail: almas239@gmail.com, telegram: @AlexeySMilovanov. | Семинарист: Алексей Милованов, e-mail: almas239@gmail.com, telegram: @AlexeySMilovanov. | ||
| + | |||
| + | [https://docs.google.com/spreadsheets/d/1N5Dmtkt2MF0dhN-hx4LUGVTc_hQ_xVu62ZKt0Rke2vc/edit?usp=sharing Таблица с результатами] | ||
== Литература == | == Литература == | ||
| Строка 23: | Строка 37: | ||
# Approximation algorithms, V. Vazirani, 2001. | # Approximation algorithms, V. Vazirani, 2001. | ||
| − | # Комбинаторная оптимизация : теория и алгоритмы, Корте, Б., Фиген, Й., 2015. | + | # Комбинаторная оптимизация: теория и алгоритмы, Корте, Б., Фиген, Й., 2015. |
# [https://mipt.ru/dcam/upload/abb/nesterovfinal-arpgzk47dcy.pdf Методы выпуклой оптимизации, Нестеров, Ю. Е.] | # [https://mipt.ru/dcam/upload/abb/nesterovfinal-arpgzk47dcy.pdf Методы выпуклой оптимизации, Нестеров, Ю. Е.] | ||
| + | # Н.В.Верещагин, М.Н.Вялый [https://www.dropbox.com/s/ga8ns2l680p1ici/main-ver.pdf?dl=0 Записки о линейном программировании] (учебные материалы для курса ДМ2 2016 года) | ||
| + | |||
| + | ==Лекции == | ||
| + | |||
| + | В конце описания лекции указаны ссылки на соответствующие разделы [https://www.dropbox.com/s/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 черновик электронного учебника]. | ||
| + | |||
| + | # (10.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1) | ||
| + | # (17.01) Трудности при использовании метода усреднения. ЛП релаксации на примере задач о (вершинном) покрытии. (2.3, 3.3, 3.4) | ||
| + | # (24.01) Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. (3.1) | ||
| + | # (31.01) Метод эллипсоидов. ЛП реласкация для задачи MAX-SAT, алгоритм с точностью релаксации 3/4. (3.2, 3.5, подробное изложение метода эллипсоидов см. в Корте, Фиген, метод Штурма - в книге Прасолова "Многочлены") | ||
| + | # (07.02) Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (2.2.2, 3.6, приложение C.1) | ||
| + | # (14.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Оценки точности. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3) | ||
| + | # (21.02) Алгоритм, реализующий геометрическое округление Гёманса-Вильямсона. SDP релаксация для MAX2SAT. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5) | ||
| + | # (28.02) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3) | ||
| + | # (07.03) SDP релаксация для задачи MAX-QP. (7.1-7.2) | ||
| + | # (14.03) SDP релаксация для задачи MAX-IND (7.3) | ||
| + | # (21.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.5) | ||
==Материалы для семинаров и домашние задания == | ==Материалы для семинаров и домашние задания == | ||
| + | |||
| + | * [https://www.dropbox.com/s/augredi5u60k783/pr01CA.pdf?dl=0 Семинар 1 и домашнее задание 1] (обратите внимание, что условие задачи 1.8 изменено по сравнению с исходным вариантом) | ||
| + | |||
| + | * [https://www.dropbox.com/s/my855oyfjfs1df1/pr02CA.pdf?dl=0 Семинар 2 и домашнее задание 2] (обратите внимание, что в в задаче MAX-QP матрица считается симметрической, на лекции это условие было пропущено) | ||
| + | |||
| + | * [https://www.dropbox.com/s/10db9dzom1xy004/pr03CA.pdf?dl=0 Семинар 3 и домашнее задание 3] (обратите внимание, что в условии задачи 3.6 определение круга заменено на правильное) | ||
| + | |||
| + | * [https://www.dropbox.com/s/ziaopd6fmxc2n5m/pr04CA.pdf?dl=0 Семинар 4 и домашнее задание 4] (задача 4.5 снимается - в авторском решении обнаружена ошибка.) | ||
| + | |||
| + | * [https://www.dropbox.com/s/6hwslfkvhxlq51o/bonus.pdf?dl=0 Бонусное задание] (на тему задачи 4.5), правила получения бонусов см. в файле по ссылке. | ||
| + | |||
| + | '''Результаты выполнения бонусного задания''' (уточненные): Задача 1 засчитана как бонус Алексею Лямзину, Филлипу Грибову и Никите Калинину. Задача 5 засчитана как бонус Алексею Лямзину и Филлипу Грибову. Задачи 2-4 засчитаны как бонус Филиппу Грибову. | ||
| + | |||
| + | * [https://www.dropbox.com/s/ckyt3vtwq9hvr0a/pr05CA.pdf?dl=0 Семинар 5 и домашнее задание 5] | ||
| + | |||
| + | * [https://www.dropbox.com/s/h1bgb43bkj28xxz/pr06CA.pdf?dl=0 Семинар 6 и домашнее задание 6] | ||
| + | |||
| + | * [https://www.dropbox.com/s/3idffhjvnu0h9ok/pr07CA.pdf?dl=0 Семинар 7 и домашнее задание 7] | ||
| + | |||
| + | * [https://www.dropbox.com/s/fguy65hh7415aj2/pr08CA.pdf?dl=0 Семинар 8 и домашнее задание 8] (исправлена опечатка в условии задачи 8.8) | ||
| + | |||
| + | * [https://www.dropbox.com/s/w1ekwgzfv6du6e0/pr09CA.pdf?dl=0 Семинар 9 и домашнее задание 9] [https://jamboard.google.com/d/1U04v3KAKM5rBhrBK3t4n4hcvV_dHK6Ricnm_2LWZ7Sc/edit?usp=sharing Доска][https://drive.google.com/file/d/1IvQUka57O3G5syhUgaBxexjxd8THE90L/view?usp=sharing Видео] | ||
| + | |||
| + | * [https://www.dropbox.com/s/lbk93wb0976f55o/pr10CA.pdf?dl=0 Семинар 10 и домашнее задание 10] [https://jamboard.google.com/d/1zdNJRL_5MAnAEeNtfw8cEdFbzH_B1i7W2ZHdQtbkCX0/edit?usp=sharing Доска] [https://drive.google.com/file/d/14Ap03C1VAZtsMzekQcNyrS1nmwpH9rYu/view?usp=sharing Видео] | ||
| + | |||
| + | * [https://www.dropbox.com/s/kmuirn8w4qfhox4/pr11CA.pdf?dl=0 Семинар 11] [https://jamboard.google.com/d/1aUJ7OyUMrwLTw6xY0RFM3hriaz5PPAWR6taAD9twvqk/edit?usp=sharing Доска] [https://drive.google.com/file/d/1uJ0iKK05C7mvJEN1LcA7n7oISQxfVBJq/view?usp=sharing Видео] | ||
Текущая версия на 10:18, 24 марта 2022
Содержание
Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы
Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи.
Курс начинается 10 января!
Экзамен
Экзамен по курсу пройдёт 30 марта (среда), начало 17:00, ауд. R408.
Экзамен устный. В билете два вопроса: один на знание определений и формулировок утверждений, второй - на знание доказательств.
На подготовку ответа даётся около получаса. Использовать печатные или электронные материалы при подготовке нельзя. При ответе допустимы пропуски технически трудных моментов рассуждений. При необходимости экзаменатор может попросить восстановить пропуски, используя учебные материалы.
Правила оценивания
Оценка по курсу состоит из двух компонент: домашние задания (выдаются на неделю в течение модуля) и устный экзамен в сессию после 3го модуля.
Вес домашних заданий в итоговой оценке равен 0.4, вес экзамена равен 0.6. Округление арифметическое.
Контакты
Чат курса в telegram: https://t.me/+MVeYv06RlYlhYmMy
Лектор: Вялый Михаил Николаевич, e-mail: vyalyi@gmail.com, telegram: @mnvyalyi.
Семинарист: Алексей Милованов, e-mail: almas239@gmail.com, telegram: @AlexeySMilovanov.
Литература
Рекомендуется использовать черновик электронного учебника, который полностью покрывает материал этого курса (и содержит много других сведений, в частности, раздел про трудность приближения, который в курсе не обсуждается). Этот файл, возможно, будет меняться во время курса, чтобы наиболее удобным образом покрыть его содержание.
Кроме того, полезными могут оказаться следующие книги:
- Approximation algorithms, V. Vazirani, 2001.
- Комбинаторная оптимизация: теория и алгоритмы, Корте, Б., Фиген, Й., 2015.
- Методы выпуклой оптимизации, Нестеров, Ю. Е.
- Н.В.Верещагин, М.Н.Вялый Записки о линейном программировании (учебные материалы для курса ДМ2 2016 года)
Лекции
В конце описания лекции указаны ссылки на соответствующие разделы черновик электронного учебника.
- (10.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
- (17.01) Трудности при использовании метода усреднения. ЛП релаксации на примере задач о (вершинном) покрытии. (2.3, 3.3, 3.4)
- (24.01) Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. (3.1)
- (31.01) Метод эллипсоидов. ЛП реласкация для задачи MAX-SAT, алгоритм с точностью релаксации 3/4. (3.2, 3.5, подробное изложение метода эллипсоидов см. в Корте, Фиген, метод Штурма - в книге Прасолова "Многочлены")
- (07.02) Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (2.2.2, 3.6, приложение C.1)
- (14.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Оценки точности. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3)
- (21.02) Алгоритм, реализующий геометрическое округление Гёманса-Вильямсона. SDP релаксация для MAX2SAT. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5)
- (28.02) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3)
- (07.03) SDP релаксация для задачи MAX-QP. (7.1-7.2)
- (14.03) SDP релаксация для задачи MAX-IND (7.3)
- (21.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.5)
Материалы для семинаров и домашние задания
- Семинар 1 и домашнее задание 1 (обратите внимание, что условие задачи 1.8 изменено по сравнению с исходным вариантом)
- Семинар 2 и домашнее задание 2 (обратите внимание, что в в задаче MAX-QP матрица считается симметрической, на лекции это условие было пропущено)
- Семинар 3 и домашнее задание 3 (обратите внимание, что в условии задачи 3.6 определение круга заменено на правильное)
- Семинар 4 и домашнее задание 4 (задача 4.5 снимается - в авторском решении обнаружена ошибка.)
- Бонусное задание (на тему задачи 4.5), правила получения бонусов см. в файле по ссылке.
Результаты выполнения бонусного задания (уточненные): Задача 1 засчитана как бонус Алексею Лямзину, Филлипу Грибову и Никите Калинину. Задача 5 засчитана как бонус Алексею Лямзину и Филлипу Грибову. Задачи 2-4 засчитаны как бонус Филиппу Грибову.
- Семинар 8 и домашнее задание 8 (исправлена опечатка в условии задачи 8.8)
