Новосибирский государственный университет
Кафедра высшей математики

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

Дискретная математика

2 курс, ФФ, НГУ, Летняя сессия,  2009 г.
          

1. Проверка связности графа. Алгоритм Поиск и его трудоемкость.

2. Алгоритмы сортировки. Верхние и нижние оценки трудоемкости.

3. AVL-деревья, определение и назначение.

4. Задача о кратчайшем пути. Алгоритм Дейкстры.

5. Алгоритм Флойда-Уоршелла.

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

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

8. Задача коммивояжера с неравенством треугольника. Идея алгоритма с гарантированной оценкой точности 2.

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

10. Потоки в сетях. Разложение положительных потоков на элементарные.

11. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе.

12. Алгоритм Форда-Фалкерсона и его недостатки.

13. Алгоритм кратчайших путей для задачи о максимальном потоке

14. Теорема Менгера и теорема Уитни.

15. Теорема Кенига.

16. Симплекс-метод.

17. Критерий разрешимости задачи линейного программирования.

18. Метод искусственного базиса

19. Матроиды, теорема Радо-Эдмондса.

20. Алфавитные коды. Критерий однозначности декодирования.

21. Неравенство Макмиллана.

22. Коды с минимальной избыточностью.

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

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

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

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

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

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

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

Вернуться к лекциям

Редакция 21.05.2009