ConvAppr22 — различия между версиями
Vyalyi (обсуждение | вклад) |
Vyalyi (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
# Комбинаторная оптимизация : теория и алгоритмы, Корте, Б., Фиген, Й., 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/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 черновик электронного учебника]. | ||
| + | |||
| + | # (10.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1) | ||
| + | # (17.01) Трудности при использовании метода усреднения. ЛП релаксации на примере задач о (вершинном) покрытии. (2.3, 3.3, 3.4) | ||
==Материалы для семинаров и домашние задания == | ==Материалы для семинаров и домашние задания == | ||
Версия 16:34, 23 января 2022
Содержание
[убрать]Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы
Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи.
Курс начинается 10 января!
Правила оценивания
Оценка по курсу состоит из двух компонент: домашние задания (выдаются на неделю в течение модуля) и устный экзамен в сессию после 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.
- Методы выпуклой оптимизации, Нестеров, Ю. Е.
Лекции
В конце описания лекции указаны ссылки на соответствующие разделы черновик электронного учебника.
- (10.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
- (17.01) Трудности при использовании метода усреднения. ЛП релаксации на примере задач о (вершинном) покрытии. (2.3, 3.3, 3.4)
Материалы для семинаров и домашние задания
- Семинар 1 и домашнее задание 1 (обратите внимание, что условие задачи 1.8 изменено по сравнению с исходным вариантом)
- Семинар 2 и домашнее задание 2 (обратите внимание, что в в задаче MAX-QP матрица считается симметрической, на лекции это условие было пропущено)
