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



Скачать 24.08 Kb.
Дата01.01.2013
Размер24.08 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Рабочая программа по курсу «теория принятия решения»
Цель изучения дисциплины состоит в ознакомлении студентов с основными понятиями и методами теории принятия решений, с классами задач,...
Программа курса «дискретные задачи принятия решений» iconА. И. Орлов Теория принятия решений
Моделирование как метод теории принятия решений и анализ ряда конкретных моделей предмет четвертой части. Приводятся методы принятия...
Программа курса «дискретные задачи принятия решений» icon3 Вероятностно-статистические методы принятия решений 3 Эконометрические методы принятия решений в контроллинге Эконометрика в контроллинге
Недаром специалисты по контроллингу большое внимание уделяют проблемам создания, развития и применения компьютерных систем поддержки...
Программа курса «дискретные задачи принятия решений» icon4. Теория принятия решений
Издавна, в теории управления принятие решений (ПР) было важным разделом. Но по мере становления теория принятия решений тпр постепенно...
Программа курса «дискретные задачи принятия решений» iconПрограмма «Повестка дня на XXI век»
«Информация для принятия решений» отмечено: «В целях создания надежной основы для процесса принятия решений на всех уровнях и содействия...
Программа курса «дискретные задачи принятия решений» iconАрутюнян Карен
Целью данной работы является разработка программного комплекса принятия решений на основе трех наиболее мощных и наглядно обосновывающих...
Программа курса «дискретные задачи принятия решений» iconЛокальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта
Ии позволяет решать многие прикладные задачи, такие, как задачи теории расписаний [9], задачи проектирования экспертных систем и...
Программа курса «дискретные задачи принятия решений» iconЗадача принятия решений : найти
Теория игр  математическая теория принятия решений в конфликтных ситуациях. Поясним, что такое конфликтная ситуация
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org