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



Скачать 30.13 Kb.
Дата27.11.2012
Размер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. Теория игр. Смешанные стратегии. Теорема Фон-Неймана для смешанных стратегий. Что показывает «дилемма путешественников»?

Похожие:

Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconПрограмма курса «дискретные задачи принятия решений»
Математические модели. Дискретные экстремальные задачи. Системы поддержки принятия решений
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconРабочая программа по курсу «теория принятия решения»
Цель изучения дисциплины состоит в ознакомлении студентов с основными понятиями и методами теории принятия решений, с классами задач,...
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconИнструменты менеджмента принятие управленческих решений
Сначала разберем несколько упрощенный пример задачи принятия решений при управлении, потом введем основные понятия теории принятия...
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconВопросы к экзамену по курсу «Теория принятия инженерных решений»
Основная математическая модель зпр в табличной, аналитической и графической формах
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconА. И. Орлов Теория принятия решений
Моделирование как метод теории принятия решений и анализ ряда конкретных моделей предмет четвертой части. Приводятся методы принятия...
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» icon4. Теория принятия решений
Издавна, в теории управления принятие решений (ПР) было важным разделом. Но по мере становления теория принятия решений тпр постепенно...
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» icon2. Описание неопределенностей в теории принятия решений
Одна из основных проблем в теории принятия решений – необходимость учета неопределенностей, оценки и управления рисками. Для описания...
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconВопросы к экзамену по курсу «теория вероятностей и математическая статистика»
Известные дискретные распределения: Бернулли, биномиальное, геометрическое и Пуассона
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconЛокальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта
Ии позволяет решать многие прикладные задачи, такие, как задачи теории расписаний [9], задачи проектирования экспертных систем и...
Вопросы к экзамену по курсу «Дискретные задачи теории принятия решений» iconВопросы к экзамену по курсу "Введение в акустику"
Звуковые волны. Различные типы задач акустики (задачи о свободных волнах; задачи с начальными условиями; краевые задачи; задачи о...
Разместите кнопку на своём сайте:
ru.convdocs.org


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