Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Учебно-методическое пособие'
Методическое пособие подготовлено по государственному заказу Министерства индустрии и торговли РК в рамках республиканской бюджетной программы 001 «О...полностью>>
'Конкурс'
Приглашаем Вас принять участие во Всероссийском фестивале-конкурсе «Русская сказка». Фестиваль -конкурс будет проходить с 25 февраля по 1 марта 2010 ...полностью>>
'Документ'
В 1988 году Генеральная Ассамблея выразила свою глубокую обеспокоенность тем, что синдром приобретенного иммунодефицита (СПИД) приобрел масштабы панд...полностью>>
'Документ'
ПРОГРАММА ПРОФИЛАКТИКИ И ЛЕЧЕНИЯ АЛКОГОЛИЗМА, НАРКОМАНИИ И ТАБАКОКУРЕНИЯ, А ТАКЖЕ СНИЖЕНИЯ УРОВНЯ ПРЕСТУПНОСТИ В РОССИЙСКОЙ ФЕДЕРАЦИИ МЕТОДАМИ ТИБЕТС...полностью>>

Программа курса «Дискретные экстремальные задачи»

Главная > Программа курса
Сохрани ссылку в одной из сетей:

Программа курса

«Дискретные экстремальные задачи»

      1. Организационно-методический раздел.

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Содержание отдельных разделов и тем.

  1. Экстремальные задачи на графах.

Формулировки некоторых экстремальных задач на графах. Задача о минимальном остове (кратчайшей связывающей сети). Алгоритмы Краскала и Прима. Динамическая задача о кратчайшем пути. Алгоритм Дейкстры. Прямо-двойственный метод. Алгоритм Дейкстры с позиций прямо-двойственного метода.

Задача о назначениях: условия оптимальности, описание алгоритма. Алгоритм решения задачи о назначениях с позиций прямо-двойственного метода.

Задача нахождения паросочетания максимального веса. Теорема Бержа. Подход к решению задачи, основанный на теории двойственности, формулировка вспомогательной задачи, описание алгоритма ее решения и доказательство его конечности.

Упрощения в алгоритме в случае единичных весов ребер.

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

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Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.

Не предусмотрено.

Отв. проф. Глебов Н.И.

доц. Плясунов А.В.



Скачать документ

Похожие документы:

  1. Основная образовательная программа высшего профессионального образования Направление подготовки (10)

    Основная образовательная программа
    4. Документы, регламентирующие содержание и организацию образовательного процесса при реализации магистерской программы по профилю «Исследование операций и оптимизация» 7
  2. Наименование магистерской программы Методы анализа и синтеза проектных решений Направление подготовки

    Документ
    Целями дисциплины являются: ознакомление с современными языками программирования, их классификацией и областями их применения; освоение различных методов абстрагирования, обеспечения модульности и других аспектов проектирования программных
  3. Аннотация курса “Дискретные модели и методы принятия решений ”

    Документ
    Предлагаемая дисциплина “ Дискретные модели и методы принятия решений ”, с одной стороны, направлена на изучение математических постановок целого ряда типовых (массовых) моделей принятия целесообразных решений, имеющих дискретную структуру.
  4. Учебном процессе программного обеспечения для решения экстремальных задач

    Документ
    Различные типы экстремальных задач рассматриваются во многих математических, экономических курсах и курсах по различным прикладным дисциплинам. При изучении алгоритмов решения этих задач, как обучающим, так и обучаемым желательно
  5. Программа курса «Анализ риска аварий техногенных систем»

    Программа курса
    Количество аудиторных часов: 18 лекций по 2 аудиторных часа; 18 семинаров по 2 аудиторных часа. Всего: 72 аудиторных часа. Самостоятельная работа: 72 часа.

Другие похожие документы..