Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений»
|
Скачать 30.13 Kb.
|
| Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» 4 курс, ММФ, НГУ часть 1 1. Алгоритмы сортировки и их характеристики. 2. Медианы и порядковые статистики, их нахождение за линейное время в среднем и худшем случаях. 3. Сбалансированные деревья, свойства и правила построения. 4. Динамическое программирование на примере распределительной задачи. Обратная задача и её свойства. 5. Модель размещения капитала, верхняя оценка оптимума, свойство оптимального решения линейной релаксации, алгоритм округления дробного решения. 6. Классическая задача о рюкзаке, теорема об алгоритмах с гарантированной абсолютной точностью. 7. Жадные алгоритмы для классической задачи о рюкзаке, свойства LP-релаксации 8. Приближенные алгоритмы с гарантированной относительной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и алгоритм с точностью ¾. 9. Аппроксимационные схемы, полиномиальные и полностью полиномиальные схемы для задачи о рюкзаке. 10. Замена оборудования. Алгоритм динамического программирования для конечного планового периода. 11. Задача упаковки в контейнеры. Алгоритмы NF, FF, BF, FFD и их свойства, отрицательный результат об аппроксимируемости. 12. Нижние оценки Martello и Toth. 13. Метод генерации столбцов для задачи упаковки в контейнеры. 14. Задача двумерной упаковки, кодировки решений. Алгоритм имитации отжига. 15. Задача календарного планирования. Критические работы, пути и критическое время проекта. 16. Постановка задачи календарного планирования с ограниченными ресурсами. 17. Т–поздние расписания. Алгоритм вычисления Т–поздних расписаний. 18. Доказательство оптимальности Т*–позднего расписания. Алгоритм Гимади. 19. Задачи календарного планирования с переменными длительностями работ. Сведение к линейному программированию. 20. Задача коммивояжера. Теорема о погрешности приближенных полиномиальных алгоритмов и алгоритмов локального спуска. 21. Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. Доказательство оценки и ее неулучшаемости. 22. Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья. 23. Алгоритм решения задачи о назначениях. 24. Метод ветвей и границ для задачи коммивояжера. часть 2 1. Вычислительная сложность алгоритмов. Определение задачи распознавания, задачи поиска, оптимизационной задачи. Асимптотический анализ алгоритмов. Определение недетерминированного алгоритма. Классы сложности задач. Дополнение задачи, класс co-NP. Теорема о совпадении классов NP и co-NP. 2. Вычислительная сложность алгоритмов. Сводимость задач по Карпу, по Тьюрингу. Сложность оптимизационной и соответствующей задачи распознавания. Классы PO, NPO. 3. Определение и примеры матроидов, жадный алгоритм для матроидов. 4. Теорема об эквивалентных определениях матроида. 5. Определение ранга, цикла, оболочки матроида. Теоремы о свойствах матроида (добавление элемента, единственность оболочки). Следствие из этих теорем. 6. Пересечение матроидов. Определения правильной, чередующейся последовательностей. Увеличивающийся путь. Лемма о том, что правильная последовательность является чередующейся. 7. Алгоритм для задачи о пересечении матроидов. 8. Задачи о покрытии. Математические модели вариантов задач о покрытии. Жадный алгоритм. Теорема Хватала. 9. Задачи о покрытии. Математические модели вариантов задач о покрытии. Вероятностный жадный алгоритм. Алгоритм муравьиной колонии. 10. Задачи размещения. Математические модели вариантов задач размещения. Генетический алгоритм. Основные операторы генетического алгоритма. 11. Двухуровневые задачи размещения. Задачи размещения в условиях конкуренции. Математические модели. Алгоритм локального спуска. 12. Задачи размещения в условиях конкуренции. Математические модели. Принятие решений в условиях голосования. «Безнадежный» пример. Задача о (r|p)-центроиде, математическая модель. 13. Рандомизированные алгоритмы. Классификация алгоритмов. Алгоритм Джонсона на примере задачи MAX SAT. 14. MAX-SAT в виде задачи целочисленного линейного программирования. LP-релаксация. Вероятностный алгоритм Джонсона. Оценка точности. 15. MAX-SAT в виде задачи целочисленного линейного программирования. Алгоритм Гойманса и Уильямсона для решения MAX-SAT. 16. Теория игр. Чистые стратегии. Лемма о минимаксе и максимине. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. 17. Теория игр. Смешанные стратегии. Теорема Фон-Неймана для смешанных стратегий. Что показывает «дилемма путешественников»? |
Похожие:
 | Программа курса «дискретные задачи принятия решений» Математические модели. Дискретные экстремальные задачи. Системы поддержки принятия решений | | Рабочая программа по курсу «теория принятия решения» Цель изучения дисциплины состоит в ознакомлении студентов с основными понятиями и методами теории принятия решений, с классами задач,... |
 | Инструменты менеджмента принятие управленческих решений Сначала разберем несколько упрощенный пример задачи принятия решений при управлении, потом введем основные понятия теории принятия... | | Вопросы к экзамену по курсу «Теория принятия инженерных решений» Основная математическая модель зпр в табличной, аналитической и графической формах |
| А. И. Орлов Теория принятия решений Моделирование как метод теории принятия решений и анализ ряда конкретных моделей предмет четвертой части. Приводятся методы принятия... | | 4. Теория принятия решений Издавна, в теории управления принятие решений (ПР) было важным разделом. Но по мере становления теория принятия решений тпр постепенно... |
| 2. Описание неопределенностей в теории принятия решений Одна из основных проблем в теории принятия решений – необходимость учета неопределенностей, оценки и управления рисками. Для описания... | | Вопросы к экзамену по курсу «теория вероятностей и математическая статистика» Известные дискретные распределения: Бернулли, биномиальное, геометрическое и Пуассона |
| Локальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта Ии позволяет решать многие прикладные задачи, такие, как задачи теории расписаний [9], задачи проектирования экспертных систем и... | | Вопросы к экзамену по курсу "Введение в акустику" Звуковые волны. Различные типы задач акустики (задачи о свободных волнах; задачи с начальными условиями; краевые задачи; задачи о... |