Вопросы к экзамену

4 курс, ММФ НГУ, зимняя сессия

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

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

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

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

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

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

7. Замена оборудования. Алгоритм динамического программирования для конечного планового периода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24. Алгоритм решения задачи  1| prec, pmtn, r_i | f_max

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

26. Алгоритм решения задачи  P | pmtn, r_i |L_max

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

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

29. Задачи о покрытии, алгоритм Чватала, оценка его погрешности и экстремальный пример.

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

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

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

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

34. Бескоалиционные игры, равновесие по Нэшу, пример игры без равновесий.

35. Многокритериальная оптимизация. Эффективные решения по Парето и Джеоффриону. Линейные свертки и их свойства. Метод уступок.

 

Список вопросов в pdf