ConvApprox26: различия между версиями
Vyalyi (обсуждение | вклад) Нет описания правки |
Vyalyi (обсуждение | вклад) Нет описания правки |
||
| Строка 68: | Строка 68: | ||
# Н.В.Верещагин, М.Н.Вялый [https://www.dropbox.com/s/ga8ns2l680p1ici/main-ver.pdf?dl=0 Записки о линейном программировании] (учебные материалы для курса ДМ2 2017 года) | # Н.В.Верещагин, М.Н.Вялый [https://www.dropbox.com/s/ga8ns2l680p1ici/main-ver.pdf?dl=0 Записки о линейном программировании] (учебные материалы для курса ДМ2 2017 года) | ||
==Лекции == | ==Лекции == | ||
В конце описания лекции указаны ссылки на соответствующие разделы [https://drive.google.com/file/d/1_GGZi_9JKtSooFX-aTIoYr8nlkLtuYLl/view?usp=sharing черновика электронного учебника]. | В конце описания лекции указаны ссылки на соответствующие разделы [https://drive.google.com/file/d/1_GGZi_9JKtSooFX-aTIoYr8nlkLtuYLl/view?usp=sharing черновика электронного учебника]. | ||
# ( | # (19.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1) | ||
<!--- | |||
# (22.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии и выполнимости КНФ. (2.3, 3.3, 3.4, 3.5) | # (22.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии и выполнимости КНФ. (2.3, 3.3, 3.4, 3.5) | ||
# (29.01) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2) | # (29.01) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2) | ||
| Строка 83: | Строка 83: | ||
# (11.03) SDP релаксации для задачи MAX-IND (7.3) | # (11.03) SDP релаксации для задачи MAX-IND (7.3) | ||
# (18.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.4, 10.5) | # (18.03) Иерархия Лассера (10.1, 10.2, 10.3, 10.4, 10.5) | ||
!---> | |||
==Материалы для семинаров и домашние задания == | ==Материалы для семинаров и домашние задания == | ||
| Строка 88: | Строка 90: | ||
Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара. | Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара. | ||
Ссылка на | Ссылка на классрум для сдачи домашних заданий: [https://classroom.google.com/c/NjI4MjcwOTA5MjI2?cjc=ausyeyi ссылка]. Чтобы сдавать ДЗ нужно зарегистрироваться по ссылке. | ||
<!--- | |||
Ссылка на гугл-диск с записями доски с семинаров: [https://drive.google.com/drive/folders/1sh66ONtso_SGLfuGTTb9koGlTGW_eElQ?usp=sharing ссылка] | Ссылка на гугл-диск с записями доски с семинаров: [https://drive.google.com/drive/folders/1sh66ONtso_SGLfuGTTb9koGlTGW_eElQ?usp=sharing ссылка] | ||
!---> | |||
* [https:// | * [https://drive.google.com/file/d/1IHw5cuEegH-ec9Uhgjb8NzQtoHmN4ksV/view?usp=sharing Семинар 1 и домашнее задание 1] | ||
<!--- | |||
* [https://www.dropbox.com/scl/fi/gdjwim6epu6ul5xm5w1la/pr02CA.pdf?rlkey=777erncv2kn1dz1g9akkwd9g9&dl=0 Семинар 2 и домашнее задание 2] | * [https://www.dropbox.com/scl/fi/gdjwim6epu6ul5xm5w1la/pr02CA.pdf?rlkey=777erncv2kn1dz1g9akkwd9g9&dl=0 Семинар 2 и домашнее задание 2] | ||
Версия от 11:19, 21 января 2026
Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы
Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи.
Лекции будут по понедельникам, первая 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)
Материалы для семинаров и домашние задания
Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара.
Ссылка на классрум для сдачи домашних заданий: ссылка. Чтобы сдавать ДЗ нужно зарегистрироваться по ссылке.