Программа курса «Дискретные экстремальные задачи»
| Вид материала | Программа курса |
СодержаниеИтоговый контроль Экстремальные задачи на графах. II. Задачи целочисленного линейного программирования. III. Полиномиальная сводимость и NP-трудные задачи. IV. Приближенные алгоритмы. |
- 1 Аналого-цифровое и цифро-аналоговое преобразование. Параметры типичных ацп и цап, 512.11kb.
- Семинар "нелинейный анализ и экстремальные задачи", 47.15kb.
- Программа дисциплины «Дискретные математические модели», 224.89kb.
- Программа дисциплины «Дискретные математические модели», 241.81kb.
- Аннотация курса “Дискретные модели и методы принятия решений, 92.89kb.
- Н. Г. Чернышевского кафедра радиофизики и нелинейной динамики рабочая программа, 145.34kb.
- Программа курса (цели, задачи, место курса; требования; разделы учебной программы), 233.99kb.
- Экстремальные формы политического процесса и журналистика, 85.78kb.
- Рабочая программа дисциплины Дискретные задачи принятия решений Направление подготовки, 115.31kb.
- Программа курса Конспект лекций > Тесты Задачи > Вопросы к экзамену Методические рекомендации, 1693.2kb.
Программа курса
«Дискретные экстремальные задачи»
Организационно-методический раздел.
0.1Название курса.
Дискретные экстремальные задачи.
Направление - математика
Раздел - “специальные дисциплины” вузовской компоненты.
Семестр(ы) - 7,8
0.2Цели и задачи курса.
Дисциплина “ Дискретные экстремальные задачи ” предназначена для студентов и магистрантов механико-математического факультета.
Основной целью освоения дисциплины является овладение студентами современными методами решения задач дискретной оптимизации. Курс отражает современное состояние теории дискретных экстремальных задач; его актуальность обусловлена широкими возможностями применения рассматриваемых методов при решении практических задач из производственной и научно-технической сферы.
Для достижения поставленной цели выделяются задачи курса:
1) изучение теоретической части курса в соответствии с программой
2) сдача экзамена в соответствии с учебным планом.
0.3Требования к уровню освоения содержания курса.
По окончании изучения указанной дисциплины студент должен
- иметь представление о задачах дискретной оптимизации;
- знать основные методы решения дискретных оптимизационных задач;
- уметь использовать освоенные методы при проведении теоретических и прикладных исследований.
0.4Формы контроля
Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен.
Текущий контроль. Не предусмотрен.
1Содержание дисциплины.
1.1Новизна.
Курс отражает современное состояние теории дискретных экстремальных задач; его актуальность обусловлена широкими возможностями применения рассматриваемых методов при решении практических задач из производственной и научно-технической сферы.
1.2Тематический план курса.
| Наименование разделов и тем | К о л и ч е с т в о ч а с о в | ||||
| Лекции | Семинары | Лабора- торные работы | Самосто- ятельная работа | Всего часов | |
| Экстремальные задачи на графах | 34 | | | | 34 |
| Задачи целочисленного линейного программирования | 8 | | | | 8 |
| Полиномиальная сводимость и NP-трудные задачи | 18 | | | | 18 |
| Приближенные алгоритмы | 8 | | | | 8 |
| Итого по курсу | 68 | | | | 68 |
1.3Содержание отдельных разделов и тем.
- Экстремальные задачи на графах.
Формулировки некоторых экстремальных задач на графах. Задача о минимальном остове (кратчайшей связывающей сети). Алгоритмы Краскала и Прима. Динамическая задача о кратчайшем пути. Алгоритм Дейкстры. Прямо-двойственный метод. Алгоритм Дейкстры с позиций прямо-двойственного метода.
Задача о назначениях: условия оптимальности, описание алгоритма. Алгоритм решения задачи о назначениях с позиций прямо-двойственного метода.
Задача нахождения паросочетания максимального веса. Теорема Бержа. Подход к решению задачи, основанный на теории двойственности, формулировка вспомогательной задачи, описание алгоритма ее решения и доказательство его конечности.
Упрощения в алгоритме в случае единичных весов ребер.
Задачи китайского почтальона и покрытия графа ребрами; их сводимость к задаче отыскания паросочетания максимального веса.
II. Задачи целочисленного линейного программирования.
Идея методов отсечения. Схема построения отсечений (дополнительных ограничений) в алгоритмах Гомори. LD-метод. Первый (циклический) алгоритм Гомори и доказательство его конечности. Третий (полностью целочисленный алгоритм) Гомори.
Целочисленные многогранные множества. Целочисленность многогранника допустимых решений транспортной задачи.
III. Полиномиальная сводимость и NP-трудные задачи.
Алгоритмы и оценки временной сложности. Классы P и NP. Полиномиальная сводимость. NP-полные и NP-трудные задачи. Теорема Кука.
NP-полнота задач: 3-ВЫПОЛНИМОСТЬ, 3-СОЧЕТАНИЕ, ВЕРШИННОЕ ПОКРЫТИЕ, КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ГАМИЛЬТОНОВ ЦИКЛ, 0-1 РЮКЗАК, РАЗБИЕНИЕ, МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ.
IV. Приближенные алгоритмы.
Полиномиальные алгоритмы построения приближенных решений с оценками точности. Приближенные алгоритмы с оценками для задачи коммивояжера и задачи k--центр. Полиномиальные аппроксимационные схемы.
2Учебно-методическое обеспечение дисциплины
2.1Темы рефератов (курсовых работ).
Не предусмотрено.
2.2Образцы вопросов для подготовки к экзамену.
а) Динамическая задача о кратчайшем пути; алгоритм Дейкстры.
б) Целочисленные многогранные множества (основная теорема).
в) NP-полнота задачи ГАМИЛЬТОНОВ ЦИКЛ.
2.3Список основной и дополнительной литературы.
1. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. - Новосибирск: НГУ, 1991.
2. "Исследования по дискретной оптимизации". - М.: Наука, 1976.
3. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. - М.: Наука, 1969.
4. Ху Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1974.
5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.
6. Пападимитриу Х, Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. --- М.: Мир, 1985.
7. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. Сб."Проблемы кибернетики", вып.31. --- М.: Наука, 1975.
2.4Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.
Не предусмотрено.
Отв. проф. Глебов Н.И.
доц. Плясунов А.В.