ConvApprox26

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

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

Расписание курса пока не определено, более точная информация появится позже. Лекции будут по понедельникам, первая 19 января, начало 11:10.

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

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

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

Контакты

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

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

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

Литература

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

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

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