УДК 519.682.1

ББК 22.18 (я7)

П 30

П 30 Филиппова А.С. Лекции по дисциплине «Комбинаторные алгоритмы»: Учеб. пособие / А.С.Филиппова; Уфимск. гос. авиац. техн. ун-т. – Уфа: УГАТУ, 2010.-85 с. ISBN 0-486-41962-2

Пособие соответствует государственному образовательному стандарту дисциплины «Комбинаторные алгоритмы» направления подготовки бакалавров 010300 – «Математика. Компьютерные науки». Дисциплина посвящена алгоритмам решения типовых задач комбинаторной оптимизации. В лекциях основное внимание уделено комбинаторным алгоритмам и задачам исследования операций: кратчайшие расстояния на графах, остовные деревья, сети, сетевое планирование, потоки в сетях, паросочетания, понятие NP-полных задач.

Учебное пособие предназначены для студентов 2-го и 3-го курса общенаучного факультета, изучающих дисциплину «Комбинаторные алгоритмы».

Ил. 37. Табл. 13. Библиогр.: 5 назв.

Рецензенты: д-р. физ.-мат. наук, проф. С.И. Спивак

…

ISBN

ББК 22.18 (я7)

ISBN 0-486-41962-2 © Уфимский государственный авиационный

технический университет, 2010

© А.С. Филиппова, 2010

Содержание

Предисловие………………………………………………………………………………..4

Введение…………………………………………………………………………………….4

Лекция 1. Основные определения комбинаторики……………………………………5

Лекция 2. Сеть. Кратчайшие пути. Алгоритм Дейкстры……………………………..9

Лекция 3. Кратчайшие пути между всеми парами узлов. Алгоритм

с тройственными операциями…………………………………………………………….16

Лекция 4. Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы.

Прима и Краскала (жадный) для поиска минимального остовного дерева…………….21

ЛЕКЦИЯ 5. Проблема коммивояжера. Алгоритмы «ближайшего соседа», «самой близкой вставки»……………………………………………………………………………26

ЛЕКЦИЯ 6. Сетевое планирование. Задача о кратчайшем сроке.

Задача о критическом пути…………………………………………………………………30

ЛЕКЦИЯ 7. Максимальные потоки. Теорема Форда и Фалкерсона……………………..35

Лекция 8. Метод нахождения максимального потока. Теорема о максимальных разрезах………………………………………………………………………………………40

ЛЕКЦИЯ 9. Алгоритмы для нахождения максимального потока и минимального разреза………………………………………………………………………………………..46

ЛЕКЦИЯ 10. Потоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-метод………………………………………………………………………………….51

Лекция 11. Непересекающиеся цепи и разделяющие множества

Теорема Менгера. …………………………………………………………………………...56

ЛЕКЦИЯ 12. Максимальные и наибольшие паросочетания. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графа.…………60

ЛЕКЦИЯ 13 Задачи о назначении. Венгерский алгоритм……………………………….59

ЛЕКЦИЯ 14. Классы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачи……………………………………………………………………………….74

Контрольные вопросы… …………………………………………………………………..82

Литература…………………………………………………………………………………..84

Предисловие

Учебное пособие содержит в себе курс лекций по дисциплине «Комбинаторные алгоритмы». Оно посвящено некоторым комбинаторным алгоритмам, которые встречаются в информатике, исследовании операций и дискретной математике. Особое внимание уделяется идеям, лежащим в основе алгоритмов, а так же детальному разбору численных примеров для каждого приведенного алгоритма. Каждый пример проиллюстрирован, что упрощает понимание сути изучаемых алгоритмов. Основу для материалов лекций составила книга Ху Т.Ч., Шинга М.Т. «Комбинаторные алгоритмы», перевод и научное редактирование которой выполнены в 2004 году на кафедре математической логики и высшей алгебры Нижегородского государственного университета им. Н.И.Лобачевского. Несмотря на то, что на русском языке имеются разного уровня и объема учебники, отражающие в разной степени рассматриваемую тематику, в основном они изданы в конце прошлого века и поэтому для студентов составляет трудность их изучение. Данное учебное пособие отличает простой стиль изложения с минимумом формализма (но не в ущерб математической строгости), отбор материала, сбалансированный объем.