Программа вступительных испытаний для поступающих в магистратуру (теория игр) (544672)
Текст из файла
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
ПРОГРАММА
ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ (СОБЕСЕДОВАНИЯ)
ДЛЯ ПОСТУПАЮЩИХ В МАГИСТРАТУРУ ПО НАПРАВЛЕНИЮ
010400 приКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА
профилирующая дисциплина
ТЕОРИЯ ИГР И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
«Утверждаю»
Директор института
АВТ Лунин В.П.
Зав. кафедрой
ПМ Еремеев А.П.
Часть I
УЧЕБНАЯ ПРОГРАММА ПРОФИЛИРУЮЩЕЙ ДИСЦИПЛИНЫ
"ТЕОРИЯ ИГР И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ"
-
Содержание теоретических разделов дисциплины
Введение (2 часа)
Основные понятия дисциплины. Игра - как модель конфликтной ситуации. Принятие решений как задача исследования операций. Общая схема процесса принятия решений. Задача принятия решений. Специфика принятия решений в условиях определенности, риска, неопределенности. Основные направления исследований. Классификация методов теории принятия решений. Строгие и эвристические методы. Границы применимости строгих методов. Специфика эвристических методов принятия решений.
Теоретико-игровые методы принятия решений (14 часов)
Теоретико-игровые методы принятия решений в конфликтных ситуациях. Классификация игровых моделей.
Парная антагонистическая игра. Понятие оптимальной стратегии игроков. Представление игры в виде дерева игры и матричное. Поиск решения на дереве игры: максиминный метод и метод альфа-бета отсечения. Оценка эффективности методов.
Методы решения матричных игр. Понятие чистых стратегий и седловой точки игры. Смешанные стратегии. Теоремы об оптимальном решении для случаев полной и неполной информации. Принцип "максимина". Точные и приближенные методы решений антагонистических игр: метод Лагранжа, симплекс-метод, итерационный метод. Эквивалентность игровой модели и модели линейного программирования.
Парная игра с произвольной суммой (биматричная игра). Методы решения биматричных игр. Метод Нэша. Ограниченность теории Нэша. Понятие рефлексивной игры. Игры с упорядоченными исходами при наличии многокритериальности.
Основы теории статистических решений (игры с "природой"). Методы поиска решения при известных и неизвестных вероятностях состояний природы. Критерии оптимальности (Вальда, Сэвиджа, Гурвица). Ограничения теоретико-игровых методов.
Основы теории ожидаемой полезности (5 часов)
Рациональное и иррациональное поведение лица, принимающего решения (ЛПР). Функция ожидаемой полезности. Лотереи. Поиск решения в условиях лотереи. Парадоксы рационального поведения.
Теория субъективной ожидаемой полезности. Поиск решения на основе проспектов. Функция субъективной ожидаемой полезности.
Коллективное принятие решений. Системы голосования. Методы поиска решения.
Специфика принятия решений в малых группах.
Теория принятия решений
1. Методы теории принятия решений (1 час)
Классификация методов теории принятия решений. Строгие и эвристические методы. Границы применимости строгих методов. Специфика эвристических (логико-лингвистических) методов принятия решений.
2. Методы поиска решения в пространстве состояний (10 часов)
Принятие решений в условиях неопределенности и риска на основе эвристических методов. Задача эвристического поиска как задача поиска в пространстве состояний. Методы поиска в пространстве состояний. Решающие деревья. Стратегии прямого, обратного и комбинированного поиска решения. Проблема сложности (комбинаторности) задачи поиска оптимального решения. Применение оценочных эвристических функций. Допустимый и оптимальный алгоритм поиска. Теорема о допустимости алгоритма поиска на основе эвристической функции. Универсальность и эффективность методов поиска. Ограниченность универсальных методов.
Параллельная продукционная модель принятия решений табличного типа. Организация параллельного поиска решения на основе функциональной сети. Использование стратегии "потока данных" и волнового алгоритма.
3. Методы поиска решения в пространстве целей (системе редукций) (8 часов)
Представление пространства целей посредством пропозициональных (И/ИЛИ) графов (деревьев). Редукции задачи на подзадачи. Метод уменьшения различий. Проблема взаимодействия подзадач (подцелей). Специфика параллельных методов поиска решения. Сравнение безвозвратных стратегий и стратегий с возвратами. Оценка трудоемкости (сложности) методов поиска.
4. Многокритериальные задачи принятия решений (5 часов)
Специфика многокритериальных задач принятия решений. Методы решения многокритериальных задач. Парето-оптимальные решения. Качественные методы принятия решений на основе упорядочения альтернатив, выделения и анализа множеств Парето.
Имитационное моделирование (6 часов)
Марковские и немарковские процессы принятия решений. Влияние различного рода неопредленности (нечеткости, неточности, неполноты, противоречивости и т.д. исходной информации) на процесс принятия решений. Представление временных и причинно-следственных зависимостей. Имитационные модели в исследовании операций и моделировании процессов принятия решений.
Системы принятия и поддержки принятия решений (Decision Making Systems and Decision Support Systems).
Имитационное моделирование процессов принятия решений: на основе аппарата таблиц решений; на основе системы динамических продукций типа «ресурсы-действия-операции».
-
Содержание практических занятий дисциплины
-
Поиск решения на дереве игры - метод максимина и метод на основе альфа-бета отсечения.
-
Методы решения антагонистических игр в матричной форме – методы Лагранжа, линейного программирования, приближенный (итерационный).
-
Методы решения биматричных игр.
-
Методы решения игр с упорядоченными исходами.
-
Поиск решения в пространстве состояний.
-
Поиск решения в пространстве целей.
-
Взаимодействие подцелей при параллельном поиске решения.
-
Метод таблиц решений.
-
Метод динамических продукций типа «ресурсы-действия-операции».
Лабораторные работы, выполняемые с применением компьютерных средств
№ 1. Методы решения антагонистических игр на базе системы MatrixGames (3 часа).
№ 2. Моделирование процесса принятия решений с использованием системы имитационного моделирования на основе таблиц решений СИМПР-WINDOWS (7 часов).
№ 3. Моделирование процесса принятия решений с использованием системы имитационного моделирования РДО - «Ресурсы-Действия-Операции» (7 часов).
-
Литература
-
Учебники
-
Ларичев О.И. Теория и методы принятия решений, а также хроника событий в Волшебных Странах: Учебник. Изд. второе, перераб. и доп. - М.: Логос, 2002. - 392 с.
-
Воробьев Н.Н. Теория игр для экономистов-кибернетиков. - Наука. Гл. ред. физ.-мат. лит. 1985. - 272 с.
-
-
Учебные пособия
-
Еремеев А.П. Теоретико-игровые методы принятия решений: учебное пособие. – М.: Изд. дом МЭИ, 2007. – 52 с.
-
Еремеев А.П. Экспертные модели и методы принятия решений/ Учебное пособие. -М.: Изд-во МЭИ, 1995. - 111 с.
-
Таха Х. Введение в исследование операций. В 2-х книгах. Пер. с англ. – М.: Мир, 1985.
-
Трахтенгерц Э.А. Компьютерная поддержка принятия решений: Научно-практическое издание. М.: СИНТЕГ, 1998. - 376 с.
-
Вагин В.Н. Дедукция и обобщение в системах принятия решений.- М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 384 с.
-
Борисов А.Н., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей: Примеры использования. Рига: Зинатне, 1990. - 184 с.
-
-
Методические указания
1. Еремеев А.П., Чибизова Н.В. Инструментальный комплекс проектирования систем поддержки принятия решений реального времени СИМПР-WINDOWS / Методич. пособие. - М.: Изд-во МЭИ, 1999. - 40 с
2. Еремеев А.П., Шутова П.В. Моделирование процессов принятия решений на основе системы интеллектуального имитационного моделирования РДО / Методич. пособие. - М.: Изд-во МЭИ, 2002. - 84 с.
3. Емельянов В.В., Ясиновский С.И. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. Язык РДО. - М.: АНВИК, 1998. - 427 с.
-
Технические и профессиональные справочники, обеспечивающие практическую деятельность по дисциплине
-
CD-носители информации по дисциплине
-
Система решения антагонистических игр GAME.
-
Система имитационного моделирования на основе таблиц решений СИМПР-WINDOWS.
-
Система имитационного моделирования процессов принятия решений РДО.
-
Адреса сайтов в Интернете, содержащие информацию по дисциплине
www.jair.org
www.raai.org
Программу составил
Зав. кафедрой ПМ
д.т.н., профессор Еремеев А.П.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.