|
|
(не показаны 24 промежуточных версий 2 участников) |
Строка 1: |
Строка 1: |
| Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" | | Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" |
| | | |
− | Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров | + | Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров |
| | | |
| Лектор: [[Бухман Антон Владимирович]] | | Лектор: [[Бухман Антон Владимирович]] |
− |
| |
− | = Программа курса =
| |
− |
| |
− | == Часть 1. Теоретические основы ==
| |
− |
| |
− | '''Лекция 1.''' Основные определения. Простейшие свойства графов. Деревья. Теоремы о свойствах деревьев. Остовные деревья.
| |
− |
| |
− | '''Лекция 2.''' Число остовных деревьев. Остовные деревья с наибольшим числом висячих вершин. Коды Прюфера. Теорема Кэли.
| |
− |
| |
− | '''Лекция 3.''' Вершинная раскраска графов. Теорема Брукса.
| |
− |
| |
− | '''Лекция 4.''' Реберная раскраска мультиграфов. Оптимальные раскраски. Теорема Визинга.
| |
− |
| |
− | '''Лекция 5.''' Числа Рамсея, введение в теорию Рамсея. Задача о многоугольниках.
| |
− |
| |
− | '''Лекция 6.''' Критрий Эйлеровости. Достаточные условия Гамильтоновости.
| |
− |
| |
− | '''Лекция 7.''' Теорема Форда-Фалкерсона и оптимальные потоки в сетях. О паросочетаниях и их связи с потоками.
| |
− |
| |
− | '''Лекция 8.''' Теорема Менгера(формулировка). Основные элементы теории k-связности графов.
| |
− |
| |
− | == Часть 2. Алгоритмы ==
| |
− |
| |
− | '''Лекция 9.''' Представления графа, оценка сложности, сложность простейших операций в разных моделях. Поиск в глубину, ширину. Обоснование сложности и корректности.
| |
− |
| |
− | '''Лекция 10.''' Построение множества фундаментальных циклов. Построение компонент двусвязности.
| |
− |
| |
− | '''Лекция 11.''' Построение минимальных остовов. Алгоритм Краскала, алгоритм Прима.
| |
− |
| |
− | '''Лекция 12.''' Задача Коммивояжера. Её вариации. Сложность решения. Понятие приближённого алгоритма на примере задачи Коммивояжёра.
| |
− |
| |
− | '''Лекция 13.''' Понятие переборного алгоритма. Как оценивать качество переборного алгоритма. Переборный алгоритм построения всех остовных деревьев данного графа. Граф остовов и его свойства.
| |
− |
| |
− | == Часть 3. Дополнительные вопросы теории графов ==
| |
− |
| |
− | '''Лекция 14.''' Теорема Турана. Наследственные свойства графов.
| |
− |
| |
− | '''Лекция 15.''' Сложность задачи раскраска графа.
| |
− |
| |
− | '''Лекция 16.''' Введение в теорию матроидов.
| |
− |
| |
− | = Программа семинарских занятий =
| |
− |
| |
− | '''Семинар 1.''' Остовные деревья. Коды Прюфера.
| |
− |
| |
− | '''Семинар 2.''' Раскраска графов.
| |
− |
| |
− | '''Семинар 3.''' Теори Рамсея, эйлеровы и гамильтоновы графы.
| |
− |
| |
− | '''Семинар 4.''' Теорема Форда-Фалкерсона.
| |
− |
| |
− | '''Семинар 5.''' Фундаментальные циклы и компоненты двусвязности.
| |
− |
| |
− | '''Семинар 6.''' Минимальные остовные деревья.
| |
− |
| |
− | '''Семинар 7.''' NP-полные задачи награфах.
| |
− |
| |
− | '''Семинар 8.''' Переборные алгоритмы на графах.
| |
− |
| |
− | = Литература =
| |
− | #Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
| |
− | #Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
| |
− | #Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
| |
− | #Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
| |
− | #Карпов Д.В. Теория графов.
| |
− | #Липский В. Комбинаторика для программистов. М.: Мир, 1988.
| |
− | #Оре О. Теория графов. М.: Наука, 1980.
| |
− | #Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
| |
− | #Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
| |
− | #Харари Ф. Теория графов. М.: Мир, 1973.
| |
− | #Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
| |
− |
| |
| | | |
| | | |