ConvAppr24 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Vyalyi (обсуждение | вклад) |
Vyalyi (обсуждение | вклад) |
||
| (не показаны 33 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| + | ==Экзамен 29.03.2024 == | ||
| + | |||
| + | Аудитория D725. Время экзамена с 11 до 19. Чтобы всем не сидеть так долго, запишитесь в [https://docs.google.com/spreadsheets/d/1pWOAGfh21kzydhUTosmBUaqsbcReQCs-VIKZIwaLYn0/edit?usp=sharing таблицу участия]. | ||
| + | |||
| + | Экзамен устный. В билете два вопроса: один на знание определений и формулировок утверждений, второй - на знание доказательств. На подготовку ответа даётся около получаса. Использовать печатные или электронные материалы при подготовке нельзя. При ответе допустимы пропуски технически трудных моментов рассуждений. При необходимости экзаменатор может попросить восстановить пропуски, используя учебные материалы. | ||
| + | |||
| + | [https://www.dropbox.com/scl/fi/5aq6q6kq424623nofixa0/exam-program.pdf?rlkey=w5v73s6j200j36fzq1964svsl&dl=0 Программа экзамена]. | ||
| + | |||
== Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы== | == Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы== | ||
| Строка 11: | Строка 19: | ||
Вес домашних заданий в итоговой оценке равен 0.4, вес экзамена равен 0.6. Округление арифметическое. | Вес домашних заданий в итоговой оценке равен 0.4, вес экзамена равен 0.6. Округление арифметическое. | ||
| + | |||
| + | [https://docs.google.com/spreadsheets/d/1li4r9i9MjIKhK7Hw-zMv9WNWoXSD2Lj7/edit?usp=sharing&ouid=103234829628514842457&rtpof=true&sd=true Ссылка] на таблицу с оценками. | ||
<!--- | <!--- | ||
| Строка 44: | Строка 54: | ||
# Комбинаторная оптимизация: теория и алгоритмы, Корте, Б., Фиген, Й., 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 | + | # Н.В.Верещагин, М.Н.Вялый [https://www.dropbox.com/s/ga8ns2l680p1ici/main-ver.pdf?dl=0 Записки о линейном программировании] (учебные материалы для курса ДМ2 2017 года) |
==Лекции == | ==Лекции == | ||
| Строка 50: | Строка 60: | ||
В конце описания лекции указаны ссылки на соответствующие разделы [https://www.dropbox.com/s/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 черновика электронного учебника]. | В конце описания лекции указаны ссылки на соответствующие разделы [https://www.dropbox.com/s/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 черновика электронного учебника]. | ||
| − | # ( | + | # (15.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1) |
| − | + | # (22.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии и выполнимости КНФ. (2.3, 3.3, 3.4, 3.5) | |
| − | # ( | + | # (29.01) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2) |
| − | # ( | + | # (05.02) Метод эллипсоидов. Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (3.2, подробное изложение метода эллипсоидов см. в Корте, Фиген) |
| − | + | # (12.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3) | |
| − | # ( | + | # (19.02) SDP релаксация для MAX2SAT. Оценки точности. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5) |
| − | # ( | + | # (26.02) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3) |
| − | # ( | + | # (04.03) SDP релаксация для задачи MAX-QP. Неравенство Гротендика. (7.1, 7.2, 5.6.1, 5.6.2) |
| − | # ( | + | # (11.03) SDP релаксации для задачи MAX-IND (7.3) |
| − | # ( | + | # (18.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.4, 10.5) |
| − | # ( | + | |
| − | # ( | + | |
| − | + | ||
==Материалы для семинаров и домашние задания == | ==Материалы для семинаров и домашние задания == | ||
| Строка 68: | Строка 75: | ||
Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара. | Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара. | ||
| − | + | Ссылка на классрума для сдачи домашних заданий: [https://classroom.google.com/c/NjI4MjcwOTA5MjI2?cjc=ausyeyi ссылка]. | |
| + | |||
| + | Ссылка на гугл-диск с записями доски с семинаров: [https://drive.google.com/drive/folders/1sh66ONtso_SGLfuGTTb9koGlTGW_eElQ?usp=sharing ссылка] | ||
| + | |||
* [https://www.dropbox.com/scl/fi/2z362g36dxgmbzit61z3r/pr01CA.pdf?rlkey=7yxo9tsghru70fyozylk0kf7r&dl=0 Семинар 1 и домашнее задание 1] | * [https://www.dropbox.com/scl/fi/2z362g36dxgmbzit61z3r/pr01CA.pdf?rlkey=7yxo9tsghru70fyozylk0kf7r&dl=0 Семинар 1 и домашнее задание 1] | ||
| − | * [https://www.dropbox.com/ | + | * [https://www.dropbox.com/scl/fi/gdjwim6epu6ul5xm5w1la/pr02CA.pdf?rlkey=777erncv2kn1dz1g9akkwd9g9&dl=0 Семинар 2 и домашнее задание 2] |
| + | |||
| + | * [https://www.dropbox.com/scl/fi/5sqe1djnot72xwqn93fih/pr03CA.pdf?rlkey=ts1xyp76im8hkkma36c1el959&dl=0 Семинар 3 и домашнее задание 3] | ||
| + | |||
| + | * [https://www.dropbox.com/scl/fi/9xn07dvbkwnok1u42x5sf/pr04CA.pdf?rlkey=f874gl3ky4g47qx9d9rdibmni&dl=0 Семинар 4 и домашнее задание 4] | ||
| + | |||
| + | * [https://www.dropbox.com/scl/fi/0jmymnsle2r12glso9r23/bonus.pdf?rlkey=ukkcmbvl6gy8sbqdd3rafar5y&dl=0 Бонусное задание] (на тему задачи 4.2б), правила получения бонусов см. в файле по ссылке. | ||
| + | |||
| + | Бонусную задачу решил Никита Звонков, он получает +1 балл к оценке за курс. | ||
| − | * [https://www.dropbox.com/ | + | * [https://www.dropbox.com/scl/fi/zr8i9aphpyllmoo5nru33/pr05CA.pdf?rlkey=5o0stsoejqh9zxa9jcc4f90it&dl=0 Семинар 5 и домашнее задание 5] |
| − | + | Вторая бонусная задача: 5.7. Условия выдачи бонусов те же. Условие даже разрешается ослабить: заменить 1/3 на какое-нибудь положительное число. | |
| − | * [https://www.dropbox.com/ | + | * [https://www.dropbox.com/scl/fi/1qm2z8am8og8xxa6j50dm/pr06CA.pdf?rlkey=ufj4hbfaj68qzegncvbhzz450&dl=0 Семинар 6 и домашнее задание 6] |
| − | + | Третья бонусная задача: 6.6. Условия выдачи бонусов те же. | |
| − | + | В задаче 6.7 ошибочно утверждалось, что релаксация неточна для 5-цикла (одновременно утверждалось, что SDP система совместна для 5-цикла, это верное утверждение). | |
| + | В качестве ещё одной бонусной задачи предлагается [https://www.dropbox.com/scl/fi/vmvmb6pqlgztr0ys3amgn/bonus4.pdf?rlkey=uaq73dcnj6pn2t3xwzk13jxnm&dl=0 найти пример, когда SDP релаксация хроматического числа неточна]. | ||
| − | + | Четвертая бонусная задача решена Федором Куяновым, он получает +1 к оценке за курс. | |
| − | * [https://www.dropbox.com/ | + | * [https://www.dropbox.com/scl/fi/sx0brnr7wup3fjz7hvo94/pr07CA.pdf?rlkey=njg401smp112s9y9teb4wql0s&dl=0 Семинар 7 и домашнее задание 7] |
| − | * [https://www.dropbox.com/ | + | * [https://www.dropbox.com/scl/fi/kev76vnj9rgri7urfxoc7/pr08CA.pdf?rlkey=ukfm5fwl0y4v16chfd3yala8r&dl=0 Семинар 8 и домашнее задание 8] |
| − | * [https://www.dropbox.com/ | + | * [https://www.dropbox.com/scl/fi/n505r5hqc4lgszwrbnyjn/pr09CA.pdf?rlkey=cripx5isyy4hpbpysb8qductj&dl=0 Семинар 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/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 Видео] | ||
Текущая версия на 12:11, 21 марта 2024
Содержание
Экзамен 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
Литература
Рекомендуется использовать черновик электронного учебника, который полностью покрывает материал этого курса (и содержит много других сведений, в частности, раздел про трудность приближения, который в курсе не обсуждается). Этот файл, возможно, будет меняться во время курса, чтобы наиболее удобным образом покрыть его содержание.
Кроме того, полезными могут оказаться следующие книги:
- Approximation algorithms, V. Vazirani, 2001.
- Комбинаторная оптимизация: теория и алгоритмы, Корте, Б., Фиген, Й., 2015.
- Методы выпуклой оптимизации, Нестеров, Ю. Е.
- Н.В.Верещагин, М.Н.Вялый Записки о линейном программировании (учебные материалы для курса ДМ2 2017 года)
Лекции
В конце описания лекции указаны ссылки на соответствующие разделы черновика электронного учебника.
- (15.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
- (22.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии и выполнимости КНФ. (2.3, 3.3, 3.4, 3.5)
- (29.01) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2)
- (05.02) Метод эллипсоидов. Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (3.2, подробное изложение метода эллипсоидов см. в Корте, Фиген)
- (12.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3)
- (19.02) SDP релаксация для MAX2SAT. Оценки точности. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5)
- (26.02) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3)
- (04.03) SDP релаксация для задачи MAX-QP. Неравенство Гротендика. (7.1, 7.2, 5.6.1, 5.6.2)
- (11.03) SDP релаксации для задачи MAX-IND (7.3)
- (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 к оценке за курс.
