Рабочая программа дисциплины Дискретные задачи принятия решений Направление подготовки

Приложение 3

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Национальный исследовательский университет

Новосибирский государственный университет

Механико-математический факультет

УТВЕРЖДАЮ

_______________________

«_____»__________________201__ г.

Рабочая программа дисциплины

Дискретные задачи принятия решений

Направление подготовки

Error: Reference source not found

Профиль подготовки

Error: Reference source not found

Квалификация (степень) выпускника

Бакалавр

Форма обучения

Очная

Новосибирск 2010

Аннотация рабочей программы

Дисциплина «Дискретные задачи принятия решений» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found». Дисциплина реализуется на Механико-математическом факультете Национального исследовательского университета Новосибирский государственный университет кафедрой Теоретической кибернетики ММФ НИУ НГУ.

Содержание дисциплины охватывает круг вопросов, связанных с теорией принятия решений, математическими моделями целочисленного линейного программирования, вычислительной сложностью алгоритмов, а также точными и приближенными подходами к решению NP-трудных задач.

Дисциплина нацелена на формирование общекультурных компетенций ОК-6, ОК-8, ОК-11, ОК-12, профессиональных компетенций ПК-12, ПК-20, ПК-21, ПК-25, ПК-29 выпускника.

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

Программой дисциплины предусмотрены следующие виды контроля: текущий контроль успеваемости в форме контрольной работы, проверка домашних заданий промежуточный контроль в форме коллоквиума. Формы рубежного контроля определяются решениями Ученого совета, действующими в течение текущего учебного года.

Общая трудоемкость дисциплины составляет ?? зачетных единиц, 184 академических часа. Программой дисциплины предусмотрены 68 часов лекционных и 34 часа практических занятий, а также 68 часов самостоятельной работы студентов. Остальное время – контроль в форме контрольной, коллоквиума и экзамена.

1. Цели освоения дисциплины

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

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

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

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

Дисциплина «Дискретные задачи принятия решений» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found».

Дисциплина «Дискретные задачи принятия решений» опирается на следующие дисциплины данной ООП:

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

  • Методы оптимизации;

  • Теория алгоритмов (понятие временной сложности алгоритма);

  • Основы работы на ЭВМ;

  • Программирование (базовые навыки составления программ).

3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Error: Reference source not found»:

  • общекультурные компетенции: ОК-6, ОК-8, ОК-11, ОК-12;

  • профессиональные компетенции: ПК-12, ПК-20, ПК-21, ПК-25, ПК-29.

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

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

4. Структура и содержание дисциплины

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

№ п/п

Раздел дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и
трудоемкость

(в часах)

Формы текущего контроля успеваемости
(по неделям семестра)

Форма промежуточной аттестации
(по семестрам)

Лекция

Лабор. работа

Самост. работа

Контр. работа

экзамен

1.1

Алгоритмы и их сложность

7

1, 2

4

0

4

1.2

Алгоритмы сортировки и сбалансированные деревья

7

3, 4

4

0

4

1.3

Динамическое программирование

7

5, 6

4

0

4

1.4

Задачи о рюкзаке

7

7, 8

4

6

4

проверка семестрового задания

1.5

Задачи раскроя и упаковки

7

9, 10, 11

6

6

6

1.6

Метаэвристики

7

12, 13, 14

6

2

6

контрольная работа

1.7

Дискретные задачи размещения

7

15, 16, 17

6

2

6

1.8

Задачи календарного планирования

8

1, 2

4

4

4

1.9

Задача коммивояжера

8

3, 4

4

2

4

1.10

Задача о назначениях

8

5, 6

4

2

4

контрольная работа

1.11

Теория NP-полных задач

8

7, 8

4

6

4

1.12

Задачи двухуровневого программирования

8

9, 10

4

0

4

1.13

Задачи многокритериальной оптимизации

8

11, 12

4

0

4

1.14

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

8

13, 14, 15

6

4

6

1.15

Теория игр

8

16, 17

4

0

4

проверка семестрового задания

14

ИТОГО: 184

68

34

68

14

5. Образовательные технологии

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

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

Для контроля усвоения дисциплины в течение семестра проводится контрольная работа, а также в течение семестра студенты сдают семестровые задания. Они заключаются в решении задач с применением специализированного программного обеспечения, отражающих основное содержание дисциплины. Для самостоятельной работы предусмотрены домашние и семестровые задания по темам: дискретные задачи размещения, метаэвристики, задача коммивояжера, задачи раскроя и упаковки, календарное планирование. В конце года учебным планом предусмотрен экзамен. Образцы экзаменационных вопросов.

Предмет и метод исследования операций. Процесс решения управленческой задачи методом исследования операций. Динамическое программирование. Распределительная задача. Задача о ближайшем соседе. Модели календарного планирования. Параметры сетевой модели. Алгоритм Форда для вычисления рангов событий, ранних и поздних моментов наступления событий. Критические события, работы и пути. Правильная нумерация событий и правильное упорядочивание работ. Задачи с директивными сроками и ресурсными ограничениями. Складируемые и нескладируемые ресурсы. Алгоритм вычисления Т-поздних расписаний. Задачи маршрутизации. Сложность построения приближенных решений с гарантированной оценкой точности для задачи коммивояжера. Алгоритм перестройки остовного дерева и оценка его погрешности. Алгоритм ветвей и границ. Задача о назначениях и алгоритм ее решения. Задачи раскроя и упаковки. Приближенные алгоритмы с оценками для задачи упаковки в контейнеры. Понятие аппроксимационной схемы, полиномиальные и вполне полиномиальные аппроксимационные схемы. Примеры аппроксимационных схем. Алгоритм имитации отжига. Задачи о покрытии и метод Лагранжевых релаксаций. Дискретные задачи размещения. Генетический алгоритм для дискретных задач размещения. Теория матричных игр. Чистые и смешанные стратегии. Теорема Фон-Неймана. NP-трудные задачи. Сбалансированные деревья.

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

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

  1. Т. Кормен. Алгоритмы построение и анализ. Второе издание. – М.: Издательский дом «Вильямс», 2009.

  2. Э. Гимади. Математические модели и методы исследования операций. – Учебное пособие. СибГУТИ.: Новосибирск, 2009.

  3. А. И. Ерзин. Введение в исследование операций. – Новосибирск. НГУ, 2006.

  4. А. И. Ерзин, Е. Н. Гончаров, В. Залюбовский. Исследование операций: примеры и задачи. – Новосибирск. Изд-во ММФ НГУ, 2005.

  5. В. Л. Береснев. Дискретные задачи размещения и полиномы от булевых переменных. – Новосибирск. Изд-во ИМ СО РАН. 2005.

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

  1. Ausiello G. and others. Complexityandapproximation. Combinatorial optimization problems and their approximability properties – Springer, 1999.

в) программное обеспечение и Интернет-ресурсы:

  1. General Algebraic Modeling System. – .

  2. примеры задачи коммивояжера

g.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html.

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

  • Ноутбук, медиа-проектор, экран.

  • Программное обеспечение для демонстрации слайд-презентаций.

  • Программное обеспечение для решения оптимизационных задач GAMS.

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению «Error: Reference source not found» и профилю подготовки «Error: Reference source not found».

Авторы:

д.ф.-м.н., профессор НГУ, с.н.с. ИМ СО РАН

Кочетов Юрий Андреевич,

к.ф.-м.н., доцент НГУ, н.с. ИМ СО РАН

Алексеева Екатерина Вячеславовна

Рецензент (ы)

Программа одобрена на заседании

(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)

от ___________ года, протокол № ________

  1. Рабочая программа дисциплины «дискретная математика» Рекомендуется для направления подготовки

    Рабочая программа
    Накопление необходимого запаса сведений по математике (основные определения, теоремы, правила), а также освоение математического аппарата, помогающего моделировать, анализировать и решать задачи, связанные с информатикой, помощь в усвоении математических
  2. Рабочая программа дисциплины «эконометрическое моделирование» Рекомендуется для направления подготовки

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

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

    Рабочая программа
    Дать студентам представление о современных промышленных технологиях и инновационных направлениях их развития, способствовать приобретению теоретических знаний, необходимых для выполнения функций менеджера по экономическому сопровождению
  5. Рабочая программа дисциплины "Теоретические основы автоматизированного управления" Направление подготовки (1)

    Рабочая программа
    в том числе: 1,41 51 Лекции (ЛК) 0,94 34 34 Лабораторные работы (ЛР) - - Практические занятия: (ПЗ) 0,47 17 17 Семинарские занятия (СЗ) Текущий контроль (тестирование – т/ коллоквиум - к) (ТК) Консультации (К) 0,09 3 % интерактивных
  6. Рабочая программа дисциплины "Теоретические основы автоматизированного управления" Направление подготовки (2)

    Рабочая программа
    в том числе: 1,41 51 Лекции (ЛК) 0,94 34 34 Лабораторные работы (ЛР) - - Практические занятия: (ПЗ) 0,47 17 17 Семинарские занятия (СЗ) Текущий контроль (тестирование – т/ коллоквиум - к) (ТК) Консультации (К) 0,09 3 % интерактивных
  7. Программам дисциплин (модулей) Аннотация к рабочей программе дисциплины «Иностранный язык» (2)

    Программа
    Дисциплина «Иностранный язык» включена в базовую часть гуманитарного, социального и экономического цикла ООП. К исходным требованиям, необходимым для изучения дисциплины «Иностранный язык», относятся знания, умения и виды деятельности,
  8. Рабочая программа дисциплины Для студентов, обучающихся по направлению 010400. 62 «Прикладная математика и информатика»

    Рабочая программа
    цукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъфывапролджэячсмитьбюйцукенгшщзхъчсмитьбюйцукенгшщзхъфывапролджэячсукенгшщзхъфывапролджэячс
  9. Рабочая программа дисциплины Дискретные Экстремальные Задачи Направление подготовки

    Рабочая программа
    Дисциплина «Error: Reference source not found» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found».

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