Комбинаторные алгоритмы

1
Аннотация
Курс включает изучение типичных задач дискретной оптимизации, основных методов
синтеза комбинаторных алгоритмов, а также оценки их сложностей.
Напоминание основных понятий, задач и алгоритмов, необходимых для изучения
данного курса. Временная сложность алгоритмов. Классы Р и NР. Полиномиальная
сводимость.
Цель и задачи дисциплины:
 Цель дисциплины:
Ознакомление с основными методами построения комбинаторных алгоритмов
После прохождения дисциплины студент должен:
 Знать:
Типичные алгоритмы для решения задач дискретной оптимизации и оценки их
сложностей
 Уметь:
Решение поставленных задач
 Владет :
Методами дискретной оптимизации
2
Объем дисциплины и виды учебной работы по рабочему учебному плану
Виды учебной работы
1
1. Общая трудоемкость изучения
дисциплины по семестрам , в т. ч.:
1.1. Аудиторные занятия, в т. ч.:
1.1.1. Лекции
1.2. Самостоятельная работа
2. Контрольные работы
3. Форма итогового контроля:
Экзамен/Зачет
Всег
о
часо
в
__I_
сем.
2
72
3
36
36
36
34
2
36
36
34
2
Количество часов по семестрам
___ ____ ____ ___ ___ ___ ___
_
сем. сем.
_
_
_
_
сем.
сем сем. сем. сем.
.
4
5
6
7
8
9
10
Заче
т
Содержание дисциплины:
Тематический план (Разделы дисциплины и виды занятий) по учебному плану:
Разделы и темы дисциплины
1
Всего
часов
2
Лекци
и,
часов
3
Практ.
Семин
заняти
а-ры,
я,
часов
часов
4
5
Другие
Лабор виды
,
заняти
часов й,
часов
6
7
Введение
Раздел 1
Алгоритмы и теоремы для типичных
задач дискретной оптимизации.
Задача
нахождения
максимального
потока в сетях. Алгоритм ФордаФалкерсона,
анализ
алгоритма.
Модификация Карпа—Эдмонса. Теорема
Кенига
и
алгоритм
построения
максимального
паросочетания
в
двудольных графах. Теорема Дилворта
и алгоритм раскраски графа интервалов.
Венгерский алгоритм для задачи о
назначениях.
Раздел 2
Матроиды.
Матроиы.
Примеры
матроидов.
Эквивалетные
системы
аксиом.
Оптимизационные задачи на матроидах.
Матроиды
и
жадный
алгоритм.
3
Пересечение двух матроидов.
Раздел 3
Арифметические алгоритмы.
Метод Крацубы для умножения целых
чисел. Алгоритм Штрасса для
умножения матриц. Задачи вычисления
xn и значения полинома. Задача
факторизации. Криптосистемы с
открытым ключом. Криптографические
протоколы. Протоколы с нулевым
разглашением.
Раздел 4
Геометрические алгоритмы.
Алгоритмы нахождения выпуклой
оболочки. Решение систем линейных
неравенств на плоскости. Задача
триангуляции и диаграммы Вороного.
Раздел 5
Приближенные полиноминальные
алгоритмы для NР -трудных задач.
Поведение жадного алгоритма для задач
покрытия множества и коммивояжера с
неравенством треугольника. Алгоритм
Кристофидеса для задач коммивояжера
с неравенством треугольника.
Приближенно полиномиальные схемы
для задач коммивояжера на плоскости и
о рюкзаке. Поведение жадного
алгоритма для задачи покрытия
множества в типичном случае.
ИТОГО
Рекомендуемая литература:
1. М. Айгнер. Комбинаторная теория. М., Мир, 1982.
2. М. Асанов, В. Баранский, В. Расин. Дискретная математика: графы, матроиды,
алгоритмы, РХД. Москва-Ижевск, 2001.
3. М. Гери, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.
Мир,1982
4. Кнут Д. Искусство программирования, Т.2, Получисленные алгоритмы. Москва.
Санкт-Петербург, Киев. 2007.
5. Коблиц Н. Курс теории чисел и криптографии. 2008.
6. Кормен Т., Лейзерсон И., Ривест Р., Штайн К. Алгоритмы построение и анализ.
Москва. Санкт-Петербург.Киев изд. ''Вильямс'', 2007.
7. Пападимитриу Н., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и
сложность. М. Мир, 1985.
8. Свами М., Тхуласирман К. Графы, сети и алгоритмы.М. Мир 1982.
9. Салома А. Криптография с открытым ключом. М.Мир 1995.
4
10. Berg M.,Cheong O.,Kreveld M.,Overmars M. Computational Geometry.
Algorithms and Applications. Springer.2008.
11. Schrijver A. A Course in Combinatorial Optimization. 2010.
5