ConvAppr24 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 65: Строка 65:
  
 
==Материалы для семинаров и домашние задания ==
 
==Материалы для семинаров и домашние задания ==
 +
 +
Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара.
  
 
<!---
 
<!---
* [https://www.dropbox.com/s/augredi5u60k783/pr01CA.pdf?dl=0 Семинар 1 и домашнее задание 1]  
+
* [https://www.dropbox.com/scl/fi/2z362g36dxgmbzit61z3r/pr01CA.pdf?rlkey=7yxo9tsghru70fyozylk0kf7r&dl=0 Семинар 1 и домашнее задание 1]  
  
 
* [https://www.dropbox.com/s/my855oyfjfs1df1/pr02CA.pdf?dl=0 Семинар 2 и домашнее задание 2]  
 
* [https://www.dropbox.com/s/my855oyfjfs1df1/pr02CA.pdf?dl=0 Семинар 2 и домашнее задание 2]  

Версия 12:41, 14 января 2024

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

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

Лекции будут по понедельникам, первая 15 января, начало 14:40, ауд. S301 (в дальнейшем аудитории будут меняться - смотрите распсиание или РУЗ). Семинары будут по субботам, более точная информация появится позже.

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

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

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


Контакты

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

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

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


Литература

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

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

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

Лекции

В конце описания лекции указаны ссылки на соответствующие разделы черновика электронного учебника.

  1. (10.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)

Материалы для семинаров и домашние задания

Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара.