• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2020/2021

Дополнительные главы методов оптимизации

Лучший по критерию «Новизна полученных знаний»
Статус: Курс обязательный (Интеллектуальный анализ данных)
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 2-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Прогр. обучения: Интеллектуальный анализ данных
Язык: русский
Кредиты: 6

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

Аннотация

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

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

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

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

  • Знает основные понятия и теоремы. Умеет решать задачи
Содержание учебной дисциплины

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

  • Введение в теорию линейной оптимизации.
    Понятие линейной программы. Виды линейных программ: стандартная, каноническая, общая. Симплекс метод, метод искусственного базиса. Зацикливание, виды защиты от зацикливания: лексикографический метод, правило Бленда. Жадная стратегия. Матричное представление симплекс метода. Теория двойственности. Теорема двойственности, теорема дополняющий нежесткости. Метод эллипсоидов.
  • Введение в теорию полиэдров.
    Понятие многогранного конуса. Способы зданий многогранных конусов: конечно порожденный конус, конечно определенный конус. Понятие аффинной оболочки и размерности. Теорема Минковского-Фаркаша-Вейля об эквивалентности представлений. Алгоритм построения двойственного описания. Понятие полиэдра. Понятия вершины, фасеты, грани размерности k. Оптимизация линейной функции на полиэдре. Связь с симплекс методом.
  • Эвристические алгоритмы комбинаторной оптимизации
    Метод отсечений Гомори. Теорема Шрайвера и ранг Хватала. Метод brunch and bound. Метод brunch and cut, отсечения для задачи TSP. Метод k-OPT для задачи TCP. Локальный поиск. Метод лагранжевой релаксации. Получение нижних и верхних оценок. Применение этих методов на примерах задач TCP и KNAPSACK.
  • Базовые алгоритмы для работы с графами.
    Алгоритмы BFS и DFS. Задачи, решаемые BFS: связные компоненты, реберные кратчайшие пути. Задачи решаемые DFS: сильные компоненты связности, Эйлеров обход дерева, эйлеров цикл, поиск мостов, поиск циклов, поиск точек сочленения, топологическая сортировка. Рандомизированный алгоритм поиска мостов и 2-мостов. Задача построения остова минимального веса, упоминание матроидов. Задача о кратчайшем пути. Алгоритмы Форда-Беллмана, Дейкстры, Флойда, Джонсона. Приложение: 3/2-приближенный алгоритм Кристофидеса для решения метрической задачи TSP.
  • Использование средства непрерывной оптимизации для решения задач комбинаторной оптимизации.
    Понятие TDI системы. Теорема Эдмондса-Джаилса. Теорема о том, что любая система линеных неравенств может быть преобразована в TDI систему. Критерий целочисленности полиэдра, заданного системой неравенств. Доказательства свойства TDI для полиэдров цепей и антицепей. Свойство TDI для полиэдра задачи о максимальном паросочетании. Полуопределенное программирование. Получение приближенного алгоритма для задачи MAX-SAT на основе полуопределенной релаксации, решаемой методом эллипсоидов.
  • Primal-dual подход для решения задач комбинаторной оптимизации.
    Взгляд на задачи комбинаторной оптимизации со стороны теории линейного программирования. Понятие тотальной унимодулярности. Критерий и достаточное условие тотальной унимодулярности. Примеры тотально унимодулярных матриц: матрица инцидентности двудольного графа, матрица инцидентсноти орграфа. Задачи о максимальном двудольном паросочетании и минимальном двудольном совершенном паросочетании. Полиэдры этих задач, доказательство целочисленноссти полиэдров. Понятие primal-dual алгоритма. Получение полиномиального primal-dual алгоритма для данных задач. Задача о максимальном паросочетании (невзвешенном) в графе общего вида. Формула Татта-Бержа. Алгоритм построения максимального паросочетания. Разработка primal-dual алгоритма для задачи построения минимального совершенного паросочетания в взвешенном графе общего вида. Эквивалентность данной задачи задаче о максимальном взвешенном паросочетании.
  • Введение в теорию сложности.
    Понятия машины Тьюринга, многоленточной машины Тьюринга, машины RAM. Полиномиальная эквивалентность этих моделей. Тезис Черча. Понятия сводимостей по Карпу и по Тьюрингу. Определение классов P, NP, PSPACE, EXP, примеры задач. Теорема о иерархии. Определение классов NP-hard и NP-complete. Доказательства NP-completeness основных задач комбинаторной оптимизации: SAT, CIRCUIT-SAT, 3-CNF, IS, CLIQUE, VC, ISOMORPHISM, HAMILTONIAN CIRCUIT, TSP, 3-COLORING и др. Классы NP-SEARCH, NP-OPT и их полиномиальная эквивалентность классу NP.
  • Матроиды, полиматроиды, субмодулярные функции
    Понятие матроида и жадного алгоритма. Примеры матроидов: равномерный матроид, линейный матроид, циклический матроид и др. Доказательство свойства TDI для полиэдра матроида и полиэдра пересечения двух матроидов. Примеры задач, представляемых в виде пересечения двух матроидов. Алгоритм оптимизации на пересечении двух матроидов. NP-трудность задачи оптимизации на пересечении 3-х матроидов. Полиматроиды и субмодулярные функции. Алгоритм оптимизации субмодулярных функций.
Элементы контроля

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

  • неблокирующий Домашнее задание
  • неблокирующий Домашнее задание
  • неблокирующий Устный экзамен
  • неблокирующий Домашнее задание
  • неблокирующий Домашнее задание
  • неблокирующий Устный экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.3 * Домашнее задание + 0.3 * Домашнее задание + 0.4 * Устный экзамен
Список литературы

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

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

  • Верещагин Н.К., Успенский В.А., Шень А. - Колмогоровская сложность и алгоритмическая случайность - Московский центр непрерывного математического образования - 2013 - 575с. - ISBN: 978-5-4439-2012-2 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/56395
  • Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012
  • Долбилин Н.П. - Жемчужины теории многогранников - Московский центр непрерывного математического образования - 2000 - 40с. - ISBN: 5-900916-48-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9333
  • Крупский В. Н. - ТЕОРИЯ АЛГОРИТМОВ. ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ 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
  • Палий И. А. - ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 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