Бакалавриат
2022/2023
Методы теоретической информатики
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
4
Контактные часы:
44
Программа дисциплины
Аннотация
Основная цель освоения дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» обучить студентов основным понятиям и методам построения приближенных алгоритмов для задач комбинаторноий оптимизации, которые основаны на решении выпуклых релаксациий задачи.
Цель освоения дисциплины
- Освоить общие приемы построения приближенных алгоритмов: метод усреднения, ЛП релаксации, SDP релаксации.
- Изучить классические примеры использования метода усреднения, ЛП релаксаций и SDP релаксаций.
- Научиться анализировать сложность приближенных алгоритмов и их точность.
Планируемые результаты обучения
- Воспроизводит доказательства основных результатов о точности приближенных алгоритмов
- Оценивает точность приближения SDP релаксации
- Оценивает точность приближения в методе усреднения
- Оценивает точность приближения ЛП релаксации
Содержание учебной дисциплины
- Средние оценки и дерандомизация
- ЛП релаксации задач комбинаторной оптимизации
- SDP релаксации
- Знакомство с иерархией Лассера
Промежуточная аттестация
- 2022/2023 учебный год 3 модуль0.35 * Домашнее задание + 0.35 * Коллоквиум + 0.3 * Письменная работа
Список литературы
Рекомендуемая основная литература
- Комбинаторная оптимизация : теория и алгоритмы, Корте, Б., 2015
Рекомендуемая дополнительная литература
- A mathematical view of interior-point methods in convex optimization, Renegar, J., 2001
- Lectures on modern convex optimization : analysis, algorithms, and engineering applications, Ben-Tal, A., 2001
- Эффективные методы в нелинейном программировании, Нестеров, Ю. Е., 1989