Графы и их применения — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
(Добавлен апрограмма)
Строка 5: Строка 5:
 
Лектор: [[Бухман Антон Владимирович]]
 
Лектор: [[Бухман Антон Владимирович]]
  
 +
 +
== Программа курса Графы и их применения. ==
 +
 +
 +
'''Занятие 1.
 +
1. Введение. Обзор курса. - 20 минут
 +
2. Семинар. Задачи на повторение курса по графам.
 +
 +
'''Занятие 2.
 +
1. Семинар. Задачи на повторение продолжение.
 +
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.
 +
 +
'''Занятие 3.
 +
1. Обходы графов.
 +
2. Поиск компонент вершинной двусвязности.
 +
3. Разбор задач на двусвязность.
 +
 +
'''Занятие 4.
 +
1. Поиск множества фундаментальных циклов
 +
2. Поиск компонент сильной связности.
 +
 +
'''Занятие 5.
 +
1. Матроиды и жадные алгоритмы.
 +
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.
 +
 +
'''Занятие 6.
 +
1. Переборные алгоритмы для построения всех остовных деревьев.
 +
2. Коды Прюфера. Число остовных деревьев для полного графа
 +
 +
'''Занятие 7.
 +
1. Числа Рамсея. Оценка чисел Рамсея.
 +
2. Обобщение чисел Рамсея. Применение чисел Рамсея.
 +
 +
'''Занятие 8.
 +
1. Паросочетания теорема Холла
 +
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
 +
 +
'''Занятие 9.
 +
1. Семинар по пройденным темам.
 +
 +
'''Занятие 10.
 +
1. Алгоритм Куна для поиска максимальных паросочетаний
 +
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
 +
3. Венгерский алгоритм.
 +
 +
'''Занятие 11.
 +
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
 +
2. Задача коммивояжёра. ЗКНТ.
 +
2. Эйлеров цикл. Задача китайского почтальона.
 +
 +
'''Занятие 12.
 +
1. Последовательности деБрёйна.
 +
2. Теорема о числе последовательностей.
 +
 +
'''Занятие 13.
 +
1. Некоторые NP полные задачи на графах.
 +
2. Обзор пройденного материала.
 +
 +
 +
'''Занятие 14.
 +
Семинар по пройденным темам.
 +
 +
'''Занятие 15.
 +
Итоговая контрольная работа по курсу
  
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]

Версия 13:37, 13 июня 2023

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: Бухман Антон Владимирович


Программа курса Графы и их применения.

Занятие 1. 1. Введение. Обзор курса. - 20 минут 2. Семинар. Задачи на повторение курса по графам.

Занятие 2. 1. Семинар. Задачи на повторение продолжение. 2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

Занятие 3. 1. Обходы графов. 2. Поиск компонент вершинной двусвязности. 3. Разбор задач на двусвязность.

Занятие 4. 1. Поиск множества фундаментальных циклов 2. Поиск компонент сильной связности.

Занятие 5. 1. Матроиды и жадные алгоритмы. 2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

Занятие 6. 1. Переборные алгоритмы для построения всех остовных деревьев. 2. Коды Прюфера. Число остовных деревьев для полного графа

Занятие 7. 1. Числа Рамсея. Оценка чисел Рамсея. 2. Обобщение чисел Рамсея. Применение чисел Рамсея.

Занятие 8. 1. Паросочетания теорема Холла 2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

Занятие 9. 1. Семинар по пройденным темам.

Занятие 10. 1. Алгоритм Куна для поиска максимальных паросочетаний 2. Вершинное покрытие двудольного графа. Взвешенные паросочетания. 3. Венгерский алгоритм.

Занятие 11. 1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа. 2. Задача коммивояжёра. ЗКНТ. 2. Эйлеров цикл. Задача китайского почтальона.

Занятие 12. 1. Последовательности деБрёйна. 2. Теорема о числе последовательностей.

Занятие 13. 1. Некоторые NP полные задачи на графах. 2. Обзор пройденного материала.


Занятие 14. Семинар по пройденным темам.

Занятие 15. Итоговая контрольная работа по курсу

Источник — «https://mk.cs.msu.ru/index.php?title=Графы_и_их_применения&oldid=10330»