1. Динамическое программирование на примере распределительной задачи.
   Обратная задача и её свойства.

2. Модель размещения капитала, верхняя оценка оптимума, свойство оптимального решения линейной релаксации, алгоритм округления дробного решения.

3. Классическая задача о рюкзаке, теорема об алгоритмах с гарантированной
   абсолютной точностью.

4. Жадные алгоритмы для классической задачи о рюкзаке, свойства
   LP-релаксации

5. Приближенные алгоритмы с гарантированной относительной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и алгоритм с точностью ¾.

6. Аппроксимационные схемы, полиномиальные и полностью полиномиальные схемы для задачи о рюкзаке.

7. Задача упаковки в контейнеры. Алгоритмы NF, FF, BF, FFD и их свойства,
   отрицательный результат об аппроксимируемости.

8. Нижние оценки Martello и Toth.

9. Метод генерации столбцов для задачи упаковки в контейнеры.

10. Задача двумерной упаковки, кодировки решений. Алгоритм имитации отжига.

11. Задача календарного планирования. Критические работы, пути и критическое время проекта.

12. Постановка задачи календарного планирования с ограниченными ресурсами.

13. Т–поздние расписания. Алгоритм вычисления Т–поздних расписаний.

14. Доказательство оптимальности Т*–позднего расписания. Алгоритм Гимади.

15. Задачи календарного планирования с переменными длительностями работ. Сведение к линейному программированию.

16. Задача коммивояжера. Теорема о погрешности приближенных полиномиальных алгоритмов и алгоритмов локального спуска.

17. Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. Доказательство оценки и ее неулучшаемости.

18. Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья.

19. Алгоритм решения задачи о назначениях.

20. Метод ветвей и границ для задачи коммивояжера.

21. Классификация задач теории расписаний. Примеры.

22. Алгоритм Лаулера для задачи 1| prec| fmax

23. Алгоритм решения задачи 1| prec, pmtn, ri | fmax

24. Алгоритм решения задачи P | pmtn |Cmax

25. Алгоритм решения задачи P | pmtn, ri |Lmax

26. Алгоритм решения задачи Q | pmtn |Cmax

27. Алгоритм решения задачи F2 || Cmax

28. Задачи размещения. Генетический алгоритм для задачи размещения производства.

29. Задачи размещения в условиях конкуренции, их связь с принятием решений голосованием, «безнадежный» пример.

30. Матричные игры. Определение седловой точки.

31. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон-Неймана. Дилемма заключенных.

Вопросы к экзамену ФИТ 2013.pdf

 

Лекции  ●  Вопросы к экзамену ●  Устные вопросы до экзамена