Программа курса «дискретные задачи принятия решений»




НазваниеПрограмма курса «дискретные задачи принятия решений»
Дата03.02.2016
Размер3.97 Kb.
ТипПрограмма курса
ПРОГРАММА

КУРСА «ДИСКРЕТНЫЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ»
ММФ, НГУ, 4 курс



  1. Математические модели. Дискретные экстремальные задачи. Системы поддержки принятия решений.

  2. Алгоритмы и оценки временной сложности. Классы P и NP. Полиномиальная сводимость. NP-полные и NP-трудные задачи. Теорема Кука.

  3. NP-полнота задач: 3-ВЫПОЛНИМОСТЬ, 3-СОЧЕТАНИЕ, ВЕРШИННОЕ ПОКРЫТИЕ, КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ГАМИЛЬТОНОВ ЦИКЛ, 0-1 РЮКЗАК, РАЗБИЕНИЕ, МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ.

  4. Приближенные алгоритмы. Полиномиальные алгоритмы построения приближенных решений с оценками точности. Асимптотически точные алгоритмы на детерминированных и случайных входах. Полиномиальные вполне и полиномиальные аппроксимационные схемы. Примеры аппроксимационных схем.

  5. Задачи маршрутизации. Сложность построения приближенных решений с гарантированной оценкой точности для задачи коммивояжера. Алгоритмы локального
    поиска и их свойства. Алгоритм локального поиска с чередующимися окрестностями. Нижние оценки для задачи коммивояжера. Задача о назначениях и алгоритм ее решения. Задача коммивояжера с временными окнами.

  6. Модели календарного планирования. Алгоритмы вычисления параметров сетевой модели. Задачи с директивными сроками и ресурсными ограничениями. Т-поздние расписания. Полиномиальный алгоритм задачи со складируемыми ресурсами. Стохастическая постановка задачи и вероятность завершения проекта к заданному сроку.

  7. Задачи о покрытии и метод Лагранжевых релаксаций. Дискретные задачи
    размещения. Алгоритм Хватала и его погрешность. Алгоритм Хошбаум. Генетический алгоритм для дискретных задач размещения.

  8. Задачи раскроя и упаковки. Приближенные алгоритмы с оценками и аппроксимационные схемы для задачи упаковки в контейнеры..Алгоритм имитации отжига на примере задачи двумерной упаковки прямоугольников. Математические модели гильотинного раскроя, раскроя кругов и прямоугольников в угол и полосу минимальной длины.

  9. Игровые задачи размещения. Равновесия по Нэшу. Сложность нахождения равновесных решений. Трудоемкость алгоритмов локального улучшения. Цена анархии и цена стабильности.

  10. Задачи двухуровневого программирования и равновесия Штаккельберга. Задача о центроиде. NP-трудность частных случаев. Задачи на цепи и деревьях. Метод генерации столбцов. Вероятностные алгоритмы поиска с запретами.



ЛИТЕРАТУРА

  1. Гимади Э.Х., Глебов. Н.И. Математические модели и методы принятия решений. Учебное пособие, НГУ, 2008 .

  2. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. Сб."Проблемы кибернетики", вып.31. --- М.: Наука, 1975

  3. Гимади Э.Х.. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации. Труды Института математики. Новосибирск. Наука. Сиб. Отд–ние. 1988. с. 89–115. 

  4. Гэри М., Джонсон Д.. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. с. 154–191.

  5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.

  6. Косточка А. В. Дискретная математика. Часть 2 // Новосибирск: НГУ, 2001.

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

  8. Coffman E.G., Garey M.R., Johnson. D.S. Approximation algorithms for bin packing: A survey. (pdf-file  503 Кb)

  9. Matello S.,.Toth P. Knapsack Problems.  Algorithms and Computer Implementations.-John Wiley & Sons. 1990. 296 p. (pdf-file   23 Mb)



Составили

д.ф.-м.н., профессор Э.Х.Гимади
к.ф.-м.н., профессор Ю.А. Кочетов

19.03.2009

Похожие:

Программа курса «дискретные задачи принятия решений» iconРазработка управленческих решений (Планы семинарских занятий)
Теоретические основы принятия управленческих решений. Методологические основы теории принятия решений. Наука и практика (искусство)...
Программа курса «дискретные задачи принятия решений» icon"Математические методы принятия решений в условиях неопределенности"
Постановка задачи принятия решений; альтернативы, критерии, оценки; неопределенность первого и второго рода
Программа курса «дискретные задачи принятия решений» iconВопросы к экзамену для ба 4 (озо) модели и методы принятия решений
Основные понятия теории принятия решений. Современный этап развития теории принятия решений
Программа курса «дискретные задачи принятия решений» icon1. Теория принятия решений в организации
Система управления как система принятия решений, роль принятия решений в системе управления
Программа курса «дискретные задачи принятия решений» iconРабочая программа дисциплины модели и методы принятия решений фд. А. 01 Специальность 05. 13. 01 «Системный анализ, управление и обработка информации»
Целью дисциплины является углубленное изучение принципов принятия управленческих решений на основе математического моделирования...
Программа курса «дискретные задачи принятия решений» iconВо Введении мы сформулировали две основные задачи этого исследования. Первая состояла в реконструкции процесса принятия властями решений по украинскому
Первая состояла в реконструкции процесса принятия властями решений по "украинскому вопросу" и реакции русского общественного мнения...
Программа курса «дискретные задачи принятия решений» iconРабочая программа дисциплины «Методы принятия управленческих решений»
Рабочая программа дисциплины «Методы принятия управленческих решений». Программа для студентов, обучающихся по направлению 080200...
Программа курса «дискретные задачи принятия решений» iconРабочая программа дисциплины основы теории принятия экономических решений
Речь идет, прежде всего, о таких фундаментальных для математического образования понятиях и методах как задачи линейного программирования,...
Программа курса «дискретные задачи принятия решений» iconМетоды принятия управленческих решений: теоретический аспект
«Методы принятия управленческих решений» одна из спорных и актуальных тем в теории управления
Программа курса «дискретные задачи принятия решений» iconПоддержка принятия решений по управлению структурой иерархических пространственных систем*
Ов (ппк) с целью принятия решений по изменению их структуры предложена открытая модель ппк, состоящая из концептуальной модели предметной...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница