Лектор: Лепин Виктор Васильевич

4-й курс, 7-й семестр 2001-2002 учебного года.

1. Понятия, принципы и средства ИО.
2. Путь с минимальным количеством промежуточных вершин.
3. Кратчайшие пути. Алгоритм Дейкстры.
4. Кратчайшие пути. Алгоритм Форда-Беллмана.
5. Построение кратчайшего остовного дерева.
6. Дерево кратчайших путей (критерий существования).
7. Кратчайшие пути с ограничениями на время проезда.
8. Кратчайшие пути в графе между всеми парами вершин.
9. Циклы минимальной средней стоимости. Алгоритм Карпа.
10. Диаграмма ПЕРТ.
11. Задача о потоке минимальной стоимости.
12. Вполне унимодулярные матрицы и матрицы с сетевым свойством.
13. Подзадачи о потоке минимальной стоимости.
14. Задача о максимальном потоке. Алгоритм Форда-Фалкерсона. Теорема об увеличивающем пути.
15. Теорема Холла.
16. Алгоритм пересчета пропускных способностей.
17. Алгоритм Диница нахождения максимального потока в сети.
18. Алгоритм Диница для сетей с единичными пропускными способностями.
19. Алгоритм Диница для простых сетей.
20. Алгоритм Карзанова нахождения максимального потока в сети. Алгоритмы Push и Pull.
21. Алгоритм Карзанова нахождения максимального потока в сети. Алгоритм насыщения и доказательство его трудоемкости.
22. Алгоритм Карзанова нахождения максимального потока в сети. Доказательство трудоемкости.
23. Минимальный разрез и максимальный поток в плоской сети.
24. Рёберная связность. Алгоритм Метьюла.
25. Максимальные паросочетания в произвольных графах.
26. Теоремы о максимальных паросочетаниях в произвольных графах. Модифицированный поиск в ширину.
27. Теоремы о максимальных паросочетаниях в произвольных графах. Модифицированный поиск в ширину. Перекрестные ребра. Цветок. Трудоемкость идентификации плохого перекрестного ребра и построения цветка.
28. Техника срезания цветка. Теорема Эдмонса. Алгоритм нахождения максимального паросочетания.
29. Задача о назначениях. Теорема Кана. Венгерский алгоритм.
30. Классы P, NP, co-NP, NP-полнота, NP-трудность.
31. NP-трудность ЦЛП.
32. NP-трудность Сумма подмножества, Ранец, С-процессорное расписание.
33. Алгоритм динамического программирования для Ранца.
34. Приближённый алгоритм для задачи о ранце.
35. Приближённый алгоритм для задачи с-процессорное расписание без прерываний.
36. Какие оптимизационные задачи имеют полностью полиномиальные приближённые схемы.
37. NP-трудность в сильном смысле.
38. Доказать, что задача коммивояжера является NP- трудной в сильном смысле.
39. Доказать, что задача о ранце не является NP- трудной в сильном смысле.
40. Абсолютное приближение. Раскраска планарного графа.
41. Абсолютное приближение. Задача о ранце.
42. Планарное независимое множество.
43. Псевдополиномиальные алгоритмы.
44. Задача коммивояжера с неравенством треугольника. Алгоритм использующий минимальное остовное дерево.
45. Задача коммивояжера с неравенством треугольника. Алгоритм Кристофидеса.
46. Задача бункерная упаковка. Алгоритм "первый подходящий" и его оценка.
47. Задача бункерная упаковка. Теорема о не существовании полиномиального алгоритма с отношением приближения < 1.5.
48. Приближенное решение задачи о вершинном покрытии.
49. 3-х мерное сочетание. Алгоритм с отношением приближения 3.
50. 3-х мерное сочетание. Алгоритм с отношением приближения 2.
51. Максимальная выполнимость. Max-2-Вып - NP-трудная.
52. Приближённый алгоритм для Максимальной выполнимости.
53. Вероятностно проверяемые доказательства.
54. Max-3-Вып не имеет ПВПС.
55. Независимое множество не имеет ПВПС.
56. Независимое множество не имеет ПА с константным приближением.
57. Вершинное покрытие не имеет ПВПС.
58. Целочисленность и нелинейность
59. Формулировка задачи коммивояжера как задачи ЦЛП.
60. ЦЛП. Метод ветвей и границ.
61. ЦЛП. Методы отсечений.