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

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


Смотрите также:
Общие положения теории принятия решений Глава Задачи принятия решений...
Рейтинг-план освоения дисциплины «Теория принятия решений» Недели...
Рабочая программа дисциплины Дискретные задачи принятия решений Направление подготовки...
Рабочая программа дисциплины «Алгоритм принятия уголовно-процессуальных решений» Направление...
Рабочая программа по курсу «теория принятия решения»...
«Системный анализ, управление и обработка информации»...
Программа учебного курса программа составлена в соответствии с государственным образовательным...
Методические указания к изучению курса «модели и методы принятия решений в анализе и аудите»...
Темы курсовых проектов по дисциплине «Теории принятия решений» Можаева Г. В...
1. Структура систем многокритериального принятия решений...
Задачами курса являются...
Учебная программа программы дополнительного профессионального образования повышения квалификации...



Загрузка...
скачать
ПРОГРАММА

КУРСА «ДИСКРЕТНЫЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ»
ММФ, НГУ, 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




Скачать 24,93 Kb.
оставить комментарий
Дата02.10.2011
Размер24,93 Kb.
ТипПрограмма курса, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх