2023/2024
Методы анализа и оптимизации в дискретных задачах
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Дисциплина общефакультетского пула
Кто читает:
Департамент прикладной математики
Когда читается:
3 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Славнов Сергей Андреевич
Язык:
русский
Кредиты:
4
Контактные часы:
40
Программа дисциплины
Аннотация
Целями дисциплины является ознакомление студентов с основными методами анализа и оптимизации в дискретных задачах. Обсуждается понятия сложности и приближенной разрешимости. В качестве модельного примера рассматривается базовая задача "об укладке рюкзака". Рассматриваются различные приложения.
Цель освоения дисциплины
- Целями освоения дисциплины «Методы анализа и оптимизации в дискретных задачах» являются ознакомление студентов с основными методами и алгоритмами решения задач оптимизации в дискретных системах.
Планируемые результаты обучения
- Знать теоретические основы и основные алгоритмы дискретной оптимизации, в том числе – в моделях, используемых при проектировании и анализе функционирования вычислительных систем.
- Иметь навыки практической программной реализации известных алгоритмов решения задач дискретной оптимизации.
- Уметь давать математическую постановку прикладных задач дискретной оптимизации, выбирать адекватный метод их решения, определять его параметры, использовать стандартные программы для решения задач дискретной оптимизации.
Содержание учебной дисциплины
- Эффективно решаемые задачи дискретной оптимизации
- Задача линейного программирования и двойственность
- Венгерский алгоритм и прямо-двойственные алгоритмы
- Симплекс-алгоритм
- Целочисленное линейное программирование: подходы к решению задач.
- Метод ветвей и границ
Список литературы
Рекомендуемая основная литература
- Дискретная математика: комбинаторная оптимизация на графах : учеб. пособие для вузов, Галкина, В. А., 2003
- Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач: Учебное пособие / Струченков В.И. - М.:СОЛОН-Пр., 2016. - 192 с.: ISBN 978-5-91359-181-4
- Комбинаторная оптимизация. Алгоритмы и сложность, Пападимитриу, Х., 1985
- Лунгу, К. Н. Линейное программирование. Руководство к решению задач : учебное пособие / К. Н. Лунгу. — 2-е изд., испр. и доп. — Москва : ФИЗМАТЛИТ, 2009. — 132 с. — ISBN 978-5-9221-1029-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2253 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Динамическое программирование в примерах и задачах : уч. пособие, Калихман, И. Л., 1979
- Линейное программирование. Транспортная задача: Учебное пособие / Литвин Д.Б., Мелешко С.В., Мамаев И.И. - Ставрополь:Сервисшкола, 2017. - 84 с.: ISBN - Режим доступа: http://znanium.com/catalog/product/976430