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

 Устные вопросы "до билета" на экзамене

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17. Классификация задач теории расписаний: задачи  1| prec | f_max,    1| prec, pmtn, r_i | f_max

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

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

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

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

Редакция 21.05.2009