Наименование дисциплины: Дискретная оптимизация
Направление подготовки (специальность): 090301 Компьютерная безопасность
Специализация: Математические методы защиты информации
Квалификация (степень) выпускника: специалист
Форма обучения: очная
Автор: к. ф.-м. н., доцент, доцент кафедры компьютерной безопасности и математических методов обработки информации .
1. Основными целями и задачами изучения дисциплина «Дискрентная оптимизация» являются: изучение основ дискретного программирования (классических моделей, их особенностей, известных алгоритмов решения задач); ознакомление с современными комбинаторными алгоритмами для практического решения задач; изучение технологии решения задач указанного типа и ее реализация для типовых задач. Дискретная оптимизация - важнейший математический инструмент, широко используемый в химии, генетике, исследовании операций, лингвистике, проектировании и кодировании. Непосредственное и детальное представление практических систем, таких, как распределительные сети и системы связи, приводит к графам большого размера, успешный анализ которых зависит от существования "хороших" алгоритмов. Поэтому в рамках курса уделяется большое внимание разработке и описанию эффективных алгоритмов, решающих практические задачи. Работа по этой проблематике значительно обогащает алгоритмическую культуру студентов, совершенствует технику написания программ, так как алгоритмы являются неиссякаемым источником задач любого уровня сложности
2. Для изучения материала необходимы знания основ математического анализа, линейной алгебры, линейного программирования и основ теории графов. Знания и практические навыки, полученные из курса «Дискретная оптимизация», используются обучаемыми при изучении естественно-научных дисциплин, а также при разработке курсовых и дипломных работ.
Дисциплина относится к вариативной части блока С3.
3. В результате освоения дисциплины обучающийся должен:
Знать:
-постановку общей задачи дискретного программирования и ее особенности;
-наиболее часто встречающиеся в приложениях модели;
-основы комбинаторных методов - метода ветвей и границ и метода динамического программирования;
-приложения методов в экономике
-основные способы представления графов в памяти компьютера;
-основные алгоритмы решения задач с помощью аппарата теории графов;
-понятие NP - полных задач, различные алгоритмы апроксимации ;
Уметь:
-уметь использовать общие методы и схемы, рассмотренные в процессе обучения, к решению новых задач дискретного программирования
-использовать известные алгоритмы на графах для решения прикладных задач;
-применять полученные знания в различных предметных областях;
-представлять различные объекты с помощью графов.
иметь навыки:
-алгоритмического мышления;
-работы с компьютерами, с различными программными средами и оболочками;
-работы с документацией.
4. Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.
5.Содержание дисциплины:
№ п/п | Раздел дисциплины |
1 | Постановка и особенности задач дискретного программирования. Модели дискретного программирования. |
2 | Венгерский алгоритм решения задачи о назначении. Задачи транспортного типа. |
3 | Метод ветвей и границ. Применение метода ветвей и границ для симметричной задачи коммивояжера |
4 | Применение метода динамического программирования для решения некоторых аддитивных задач дискретного программирования |
5 | Приближенные методы и алгоритмы решения задач дискретного программирования. Задачи большой размерности. Применение метода динамического программирования для ре шения задачи о распределении ресурсов между проектами. |
6 | Алгоритмы на графах. |
6. Учебно-методическое и информационное обеспечение дисциплины:
а) основная литература:
1. , , Ухалов оптимизация. Яр-ль: ЯрГУ, 2008 г. 94 с.
2. Вентцель операций. Задачи, принципы, методология. - М.: Наука, 2004.
3. Исследование операций в экономике /Под ред. проф. . - М.: ЮНИТИ, 2004.
б) дополнительная литература:
1. Ху Т. Целочисленное программирование и потоки в сетях, М.: Издательство "Мир", 1974.
2. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
3. , Войтенко программирование в примерах и задачах. - М.: Высшая школа, 1979.
4. Ковалев оптимизация. - Минск: Изд-во БГУ, 1977.
5. , , Холод математика: математическое программирование. - Минск, Высшая школа, 2001.
6. , , Холод к решению задач по математическому программированию. - Минск, Высшая школа, 2001
7. Сергиенко модели и методы решения задач дискретной оптимизации. - Киев, Наукова думка, 1985.
8. Учебно-методические материалы для лабораторных и самостоятельных работ по курсу "Численные методы решения прикладных задач. Дискретное программирование. Комбинаторные методы" /Сост. . - Калинин, 1990.
9. , Иванова в прикладное дискретное программирование: модели и вычислительные алгоритмы. - М.: Физматлит, 2002.
10. Вычислительные машины и трудно-решаемые задачи. М.: Мир, 1982.
11. Искусство программирования на ЭВМ. М.: Мир, 1978. Т.3: Поиск и сортировка.
12. Комбинаторика для программистов. М.: Мир, 1988.
13. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
14. Графы, сети и алгоритмы. М.: Мир, 1984.
15. Гарсиа- Методы анализа сетей. М.: Мир, 1984.
16. . Теория графов. Алгоритмический подход. – М.: Мир, 1978.
в) программное обеспечение и Интернет-ресурсы:
На сайте математического факультета имеются электронные варианты текстов учебных пособий и методических указаний.
