Optimization: Advanced Level

2021/2022

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

2 year, 1, 2 module

Instructor

Gribanov, Dmitry

Программа дисциплины

Аннотация

Целями освоения дисциплины «дополнительные главы теории оптимизации» является подготовка в области основ математических и естественно-научных знаний, получение высшего профессионально профилированного (на уровне магистра) образования, позволяющего выпускнику успешно работать в избранной сфере деятельности, обладать универсальными и предметно-специализированными компетенциями, способствующими его социальной мобильности и устойчивости на рынке труда.

Цель освоения дисциплины

• Владеет навыками решения математических задач, возникающих в некоторых прикладных областях
• Знает основные методы дискретной оптимизации
• Знает основные методы линейного и целочисленного программирования
• Знает основные понятия и теоремы. Умеет решать задачи
• Умеет применять на практике методы дискретной оптимизации

Планируемые результаты обучения

• Знает основные понятия и теоремы. Умеет решать задачи

Содержание учебной дисциплины

• Введение в теорию линейной оптимизации.
• Введение в теорию полиэдров.
• Эвристические алгоритмы комбинаторной оптимизации
• Базовые алгоритмы для работы с графами.
• Использование средства непрерывной оптимизации для решения задач комбинаторной оптимизации.
• Primal-dual подход для решения задач комбинаторной оптимизации.
• Введение в теорию сложности.
• Матроиды, полиматроиды, субмодулярные функции

Элементы контроля

• Домашнее задание
• Домашнее задание
• Устный экзамен
• Домашнее задание
• Домашнее задание
• Устный экзамен

Промежуточная аттестация

• 2021/2022 учебный год 2 модуль
  0.3 * Домашнее задание + 0.4 * Устный экзамен + 0.3 * Домашнее задание

Список литературы

Рекомендуемая основная литература

• Верещагин, Н. К. Колмогоровская сложность и алгоритмическая случайность : учебное пособие / Н. К. Верещагин, В. А. Успенский, А. Шень. — Москва : МЦНМО, 2013. — 575 с. — ISBN 978-5-4439-2012-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/56395 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012
• Долбилин, Н. П. Жемчужины теории многогранников : учебное пособие / Н. П. Долбилин. — Москва : МЦНМО, 2000. — 40 с. — ISBN 5-900916-48-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9333 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Крупский В. Н. - ТЕОРИЯ АЛГОРИТМОВ. ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ 2-е изд., испр. и доп. Учебное пособие для бакалавриата и магистратуры - М.:Издательство Юрайт - 2019 - 117с. - ISBN: 978-5-534-04817-9 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-algoritmov-vvedenie-v-slozhnost-vychisleniy-444131
• Линейное программирование. Практикум : учеб. пособие / А.С. Шевченко. — М. : ИНФРА-М, 2018. — 297 с. - Режим доступа: http://znanium.com/catalog/product/1007387
• Линейное программирование. Транспортная задача: Учебное пособие / Литвин Д.Б., Мелешко С.В., Мамаев И.И. - Ставрополь:Сервисшкола, 2017. - 84 с.: ISBN - Режим доступа: http://znanium.com/catalog/product/976430
• Трухан А.А., Ковтуненко В.Г. - Линейная алгебра и линейное программирование: учебное пособие - Издательство "Лань" - 2018 - 316с. - ISBN: 978-5-8114-2744-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/99214

Рекомендуемая дополнительная литература

• Бирюкова Л. Г., Сагитов Р. В. ; Под общ. ред. Татарникова О.В. - ЛИНЕЙНАЯ АЛГЕБРА И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ПРАКТИКУМ. Учебное пособие для СПО - М.:Издательство Юрайт - 2019 - 53с. - ISBN: 978-5-9916-9981-5 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/lineynaya-algebra-i-lineynoe-programmirovanie-praktikum-437932
• Брандин, В. Н. Размерностная сложность. Интеллект : монография / В. Н. Брандин. — Москва : ФИЗМАТЛИТ, 2008. — 168 с. — ISBN 978-5-9221-0954-3. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/59512 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Палий И. А. - ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 175с. - ISBN: 978-5-534-04716-5 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/lineynoe-programmirovanie-438834
• Разборов, А. А. Алгебраическая сложность : брошюра / А. А. Разборов. — Москва : МЦНМО, 2016. — 31 с. — ISBN 978-5-4439-3032-9. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/80160 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Авторы

• Грибанов Дмитрий Владимирович