Линейное программирование
Курс М.А. Бабенко из 10 лекций в рамках Computer Science клуба при ПОМИ РАН.
Настоящий курс преследует несколько целей. Во-первых, слушатели познакомятся с основными понятиями ЛП, изучат теоремы отделимости, линейной двойственности и обсудят полиномиальную разрешимость задачи ЛП с помощью метода эллипсоидов. Во-вторых, с самого начала большое внимание будет уделяться связи ЛП с теорией целочисленного программирования, комбинаторикой и оптимизацией.
В курсе также предполагается дать обзор современных направлений полиэдральной комбинаторики. Наконец, будут кратко изложены основные элементы полуопределенного программирования (SDP) и его приложений к приближенным алгоритмам (например, задаче о максимальном разрезе).
Расписание:
16.04.2011 – 17:20 – 20:50
17.04.2011 – 11:15 – 17:10
23.04.2011 – 17:20 – 20:50
24.04.2011 – 11:15 – 17:10