Лекции по дисциплине Комбинаторные алгоритмы

Description

Уфа: УГАТУ, 2010 г., 85 стр.Содержание:ВведениеОсновные определения комбинаторикиСеть. Кратчайшие пути. Алгоритм ДейкстрыКратчайшие пути между всеми парами узлов. Алгоритм с тройственными операциямиПоиск остовного дерева в ширину и поиск в глубину. Алгоритмы Прима и Краскала (жадный) для поиска минимального остовного дереваПроблема коммивояжера. Алгоритмы "ближайшего соседа" и "самой близкой вставки"Сетевое планирование. Задача о кратчайшем сроке. Задача о критическом путиМаксимальные потоки. Теорема Форда и ФалкерсонаМетод нахождения максимального потока. Теорема о максимальных разрезахАлгоритмы для нахождения максимального потока и минимального разрезаПотоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-методНепересекающиеся цепи и разделяющие множества. Теорема МенгераМаксимальные и наибольшие паросочетания. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графаЗадачи о назначении. Венгерский алгоритмКлассы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачиКонтрольные вопросыЛитература