1. Цели и задачи дисциплины



Скачать 190.27 Kb.
Дата17.06.2015
Размер190.27 Kb.
ТипКраткое содержание

1. Цели и задачи дисциплины


В результате изучения и освоения дисциплины “Дискретная оптимизация“ дипломированный специалист должен:

  • иметь представление о месте и роли задач дискретной оптимизации;

  • иметь представление о теории сложности вычислений;

  • знать основные методы решения задач дискретной оптимизации, условия их применения;

  • иметь навыки в разработке программного обеспечения для решения задач дискретной оптимизации.

Краткое содержание дисциплины


Теоремы Форда – Фалкерсона, Холла, Кенига – Эгервари, Дилворта; Нахождение наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Венгерский алгоритм. Задача о назначениях на узкое место; Определения и примеры. Двойственность. Представимые матроиды. Ранговая функция. Жадный алгоритм. Задача планирования эксперимента. Общие трансверсали; Задача выбора. Варианты задачи оптимизации. Классы P NP. Полиномиальная сводимость. NP-полные задачи. Структура класса NP; Определения. Приближённый алгоритм Кристофидеса решения метрической задачи коммивояжёра.

2. Место дисциплины в структуре ООП


Дисциплина «дискретная оптимизация» включена в вариативную часть математического и естественнонаучного цикла основной образовательной программы (ООП).

Перечень предшествующих дисциплин, видов работ

Перечень последующих дисциплин,
видов работ

Дискретная математика

Высшая математика

исследование операций и теория игр

моделирование систем.



3. Компетенции обучающегося, формируемые в результате освоения дисциплины


1) умение логически верно, аргументировано и ясно строить устную и письменную речь (ОК-2);

2) готовность к кооперации с коллегами, работе в коллективе (ОК-3);

3) умение использовать нормативные правовые документы в своей деятельности  (ОК-5);

4) готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);

5) способность к формализации в своей предметной области с учетом ограничений

используемых методов исследования (ПК 2);

6) готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-3);

В результате освоения дисциплины студент должен:

а) знать:

- основы дискретной оптимизации;

б) уметь:



-применять математические методы и вычислительные алгоритмы для решения практических задач.

в) владеть:



- методами построения математической модели профессиональных задач и содержательной интерпретации полученных результатов.

4. Объем и виды учебной работы


Общая трудоемкость дисциплины составляет 4 зачетных единиц, 144 часа.


Вид учебной работы

Всего
часов

Распределение
по семестрам в часах

Номер семестра

6










Общая трудоемкость дисциплины

144

144










Аудиторные занятия

72

72










Лекции (Л)

36

36










Практические занятия, семинары и (или) другие виды аудиторных занятий (ПЗ)

36

36










Лабораторные работы (ЛР)
















Самостоятельная работа (СРС)

72

72










Подготовка к экзамену




+










Контроль самостоятельной работы студента (КСР)

7

7










Вид итогового контроля (зачет, экзамен)




Экз.












5. Содержание дисциплины



раздела

Наименование разделов дисциплины

Объем занятий по видам в часах

Всего

Л

ПЗ

ЛР

1

Минимаксные теоремы

14

7

7




2

Задача о назначениях и другие задачи о двудольных графах

14

7

7




3

Матроиды. Жадный алгоритм

16

8

8




4

Сложность задач

14

7

7




5

Приближенные алгоритмы

14

7

7



5.1. Лекции


№ лекции

№ раздела

Наименование или краткое содержание
лекционного занятия

Кол-во часов

1

1

Теорема Холла. Теорема Пуанкаре. Дополняемость латинских прямоугольников до латинских квадратов.

5

2

1

Теорема Кенига – Эгервари. Дважды стохастические матрицы. Рёберно-хроматическое число графа. Теорема Визинга.

5

3

1

Теорема Дилворта. Двойственная теорема. Их приложения к различным задачам.

5

4-6

2

Задачи о двудольных графах: нахождение наибольшего паросочетания и наименьшего вершинного покрытия; венгерский алгоритм решения задачи о назначениях; задача о назначениях на узкое место.

5

7-9

3

Матроиды: основные определения; двойственность; ранговая функция; жадный алгоритм; применение в задачах планирования эксперимента; трансверсальный матроид; общие трансверсали.

6

10-12

4

Сложность задач и алгоритмов: классы P и NP; полиномиальное сведение; NP-полные задачи: задача коммивояжера, Клика и другие.

5

6

5

Приближенные алгоритмы: основные понятия; алгоритм Кристофидеса решения задачи коммивояжера

5

5.2. Практические занятия, семинары


№ занятия

№ раздела

Наименование или краткое содержание
практического занятия, семинара

Кол-во часов

1

1

Теорема Холла. Теорема Пуанкаре. Дополняемость латинских прямоугольников до латинских квадратов.

5

2

1

Теорема Кенига – Эгервари. Дважды стохастические матрицы. Рёберно-хроматическое число графа. Теорема Визинга.

5

3

1

Теорема Дилворта. Двойственная теорема. Их приложения к различным задачам.

5

4-6

2

Задачи о двудольных графах: нахождение наибольшего паросочетания и наименьшего вершинного покрытия; венгерский алгоритм решения задачи о назначениях; задача о назначениях на узкое место.

5

7-9

3

Матроиды: основные определения; двойственность; ранговая функция; жадный алгоритм; применение в задачах планирования эксперимента; трансверсальный матроид; общие трансверсали.

6

10-12

4

Сложность задач и алгоритмов: классы P и NP; полиномиальное сведение; NP-полные задачи: задача коммивояжера, Клика и другие.

5

6

5

Приближенные алгоритмы: основные понятия; алгоритм Кристофидеса решения задачи коммивояжера

5

5.3. Лабораторные работы


№ работы

№ раздела

Наименование или краткое содержание
лабораторной работы

Кол-во часов







Лабораторные работы не предусмотрены



5.4. Самостоятельная работа студента и ее контроль


Выполнение СРС

Контроль СРС

Вид работы и содержание задания

Список литературы (с указанием разделов, глав, страниц)

Кол-во часов

Форма контроля

Содержание контроля

Кол-во часов






















































6. Образовательные технологии, используемые в учебном процессе данной дисциплины

6.1. Интерактивные формы обучения


Интерактивные
формы обучения

Вид
работы
(Л, ПЗ, ЛР)

Краткое описание

Кол-во ауд.
часов

Компьютерная симуляция










Деловая или ролевая игра










Разбор конкретных ситуаций










Тренинг










Мастер-классы экспертов
и специалистов




















6.2. Встречи с представителями российских и зарубежных компаний, государственных и общественных организаций


Должность и место работы

Вид
работы
(Л, ПЗ)

Тема встречи

Кол-во ауд.
часов




































6.3. Инновационные способы и методы, используемые в образовательном процессе


Наименование

Краткое описание и примеры использования в темах и разделах

Использование информационных ресурсов и баз данных




Применение электронных мультимедийных учебников и учебных пособий




Ориентация содержания на лучшие отечественные аналоги образовательных программ




Применение предпринимательских идей в содержании курса




Использование проблемно-ориентированного междисциплинарного подхода к изучению наук




Применение активных методов обучения, «контекстного» и «на основе опыта»




Использование методов, основанных на изучении практики (case studies)




Использование проектно-организованных технологий обучения работе в команде над комплексным решением практических задач








7. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов


Темы эссе, рефератов, курсовых работ и пр.




Контрольные вопросы и задания для проведения текущего контроля

  1. Сформулируйте теорему Холла.

  2. С помощью теоремы Холла докажите существование совершенного паросочетания

  3. Что такое рёберно-хроматическое число графа?

  4. в непустом регулярном графе.

  5. Что такое латинский прямоугольник? Докажите, что он дополняем до латинского квадрата.

  6. Сформулируйте теорему Кёнига-Эгервари. В чём её смысл применительно к двудольным графам?

  7. Каково соотношение между рёберно-хроматическим числом графа и наибольшей степенью вершины?

  8. Как найти рёберно-хроматическое число двудольного графа?

  9. Что такое цепь и антицепь в частично упорядоченном множестве?

  10. Сформулируйте теорему Дилворта и двойственную к ней.

  11. Что такое увеличивающая цепь? Докажите теорему Бёржа (критерий наибольшего паросочетания).

  12. Опишите алгоритм нахождения наибольшего паросочетания в двудольном графе.

  13. Как найти наименьшее вершинное покрытие в двудольном графе?

  14. Как формулируется задача о назначениях? Опишите венгерский метод решения этой задачи. Какова его трудоёмкость?

  15. Как формулируется и решается задача о назначениях на узкое место? Какова её трудоёмкость?

  16. Дайте определение матроида, его базиса и ранга.

  17. Докажите, что независимое множество матроида дополняется до базиса.

  18. Дайте определения однородного, векторного, матричного матроидов, матроида циклов графа.

  19. Что такое изоморфные матроиды? Приведите примеры.

  20. Что такое графические и кографические матроиды?

  21. Что такое ранговая функция матроида и каковы её свойства?

  22. Что такое жадный алгоритм?

  23. Докажите оптимальность жадного алгоритма на матроиде. Сформулируйте и докажите обратную теорему.

  24. Приведите пример задачи планирования эксперимента, в которой возникает структура матроида.

  25. Что такое трансверсаль совокупности множеств? В чём состоит критерий существования трансверсали?

  26. Что такое трансверсальный матроид? Докажите теорему Радо (критерий существования независимой трансверсали).

  27. В чём состоит критерий существования общей трансверсали двух матроидов? Как свести нахождение общей трансверсали к нахождению максимального потока в транспортной сети?

  28. Сформулируйте задачу выбора в слабом и сильном смысле. Дайте понятие индивидуальной и массовой задачи выбора. Покажите, что задача дискретной оптимизации является частным случаем задачи выбора.

  29. Опишите оптимизационный, вычислительный и распознавательный варианты задачи оптимизации. Приведите примеры их сведения друг к другу.

  30. Дайте определение классам P и NP. Приведите примеры соответствующих задач.

  31. Как определяется понятие полиномиальной сводимости одной задачи к другой?

  32. Что такое NP-полная задача?

  33. Докажите NP-полноту задачи 3-КНФ сведением к ней задачи ВЫПОЛНИМОСТЬ.

  34. Докажите NP-полноту задачи КЛИКА сведением к ней задачи 3-КНФ.

  35. Докажите NP-полноту задачи 3-РАСКРАСКА сведением к ней задачи 3-КНФ.

  36. Докажите NP-полноту задачи ГАМИЛЬТОНОВОСТЬ сведением к ней задачи 3-КНФ.

  37. Докажите NP-полноту задачи ПОЛУГАМИЛЬТОНОВОСТЬ сведением к ней задачи ГАМИЛЬТОНОВОСТЬ.

  38. Докажите, что задача 2-КНФ входит в класс P.

  39. Какова структура класса NP?

  40. Что такое приближённый алгоритм?

  41. Опишите приближённый алгоритм Кристофидеса решения метрической задачи коммивояжёра. Оцените его трудоёмкость.


Контрольные вопросы и задания для проведения промежуточной аттестации по итогам освоения дисциплины




Вопросы и задания самопроверки обучающегося по отдельным разделам дисциплины


8. Учебно-методическое и информационное обеспечение дисциплины

Печатная учебно-методическая документация


а) основная литература:

  1. Краснов, М. Л. Вся высшая математика: учебник. Т.7 / М. Л. Краснов,

А. И. Киселёв, Г. И. Макаренко и др.- М.: КомКнига, 2006. – 208 с.

  1. Эвнин А.Ю. Дискретная математика: задачник.  —  Челябинск: ЮУрГУ,

2009. – 265 с.

  1. Эвнин А.Ю. Вокруг теоремы Холла. – Челябинск, изд-во ЮУрГУ, 2004.

  2. Эвнин А.Ю. Элементарное введение в матроиды. – Челябинск, изд-во ЮУрГУ, 2004.

  3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. – М.: Мир, 1985.


б) дополнительная литература:

  1. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

  2. Липский В. Комбинаторика для программистов. - М.: Мир, 1988

  3. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Спб: Лань, 2010.


в) отечественные и зарубежные журналы по дисциплине, имеющиеся в библиотеке:




г) методические пособия для самостоятельной работы студента, для преподавателя:





Электронная учебно-методическая документация


Вид учебно-методической документации

Наименование
разработки

Ссылка на информационный ресурс

Наименование ресурса в электронной форме

Доступность
(сеть Интернет / локальная сеть; авторизованный / свободный доступ)













































9. Материально-техническое обеспечение дисциплины


Вид занятий

№ ауд.

Основное оборудование, стенды, макеты, компьютерная техника, предустановленное программное обеспечение, обеспечивающие проведение всех видов занятий




























Похожие:

1. Цели и задачи дисциплины icon1. Цели и задачи дисциплины
Цель, задачи дисциплины, ее место в подготовке бакалавра, специалиста
1. Цели и задачи дисциплины iconПрограмма дисциплины сд. 08. 8 Банки и банковское дело Цели и задачи дисциплины
Цели: изу­чение и практическое освоение студентами особенностей построения банковской системы, структуры и функций Центрального банка...
1. Цели и задачи дисциплины iconПрограмма дисциплины дпп. 02 История древнерусского языка цели и задачи дисциплины

1. Цели и задачи дисциплины iconДисциплины «История» Общая трудоемкость изучения дисциплины составляет 3 зач ед. ( 108 часов). Цели и задачи дисциплины
Целью изучения дисциплины является формирование у студентов представления об историческом прошлом России в контексте общемировых...
1. Цели и задачи дисциплины iconПрограмма дисциплины сдм. В. 04. Лингвистическая типология и сопоставительное изучение языков цели и задачи дисциплины

1. Цели и задачи дисциплины icon1. Цели и задачи дисциплины
Изучение дисциплины «Финансы» базируется на сумме знаний, полученных студентами в процессе изучения базовых дисциплин профессионального...
1. Цели и задачи дисциплины iconРабочая программа учебной дисциплины дпп. Ф. 06 Математика Томск 2012 Цели и задачи дисциплины
Преподавание курса математики должно быть направлено на достижение следующих взаимосвязанных целей
1. Цели и задачи дисциплины iconОД. А. 05. 01 Алгебраическая геометрия Цели и задачи дисциплины
Целью изучения дисциплины является: ознакомление студентов с наукой, в которой удивительно эффективным образом сочетаются методы...
1. Цели и задачи дисциплины iconПрограмма дисциплины дпп. Ф. 04 Органическая химия цели и задачи дисциплины
Целью курса является приобретение студентами знаний, отражающих с химической точки зрения картину мира, развивающих их способности...
1. Цели и задачи дисциплины iconПрограмма дополнительного образования по дисциплине
Цели и задачи дисциплины, её место в учебном процессе
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com