Дискретная математика. Комбинаторная оптимизация на графах

Автор(ы)

Галкина В.А

Год

2003

Язык

rus

ISBN

5-85438-069-2

Теги

Математика Программирование

Аннотация

Дискретная математика. Комбинаторная оптимизация на графах Год : 2003 Автор : Галкина В.А. Издательство : Гелиос АРБ ISBN : 5-85438-069-2 Язык : Русский Формат : DjVu Качество : Отсканированные страницы + слой распознанного текста Количество страниц : 221 Описание : В учебном пособии систематически излагается материал, входящий в федеральный компонент дисциплины «Дискретная математика» Государственных образовательных стандартов группы специальностей «Информационная безопасность». Рассмотрены основы теории графов, основные постановки и методы решения оптимизационных задач на графах, Особое внимание уделено вопросам построения алгоритмов приближенного решения оптимизационных задач и оценкам сложности. Для студентов и аспирантов, изучающих курсы дискретной математики в технических университетах, всех, интересующихся алгоритмами решения оптимизационных задач на графах. Примеры страниц Оглавление Глава 1. Основные свойства ориентированных графов § 1. Основные понятия ориентированных графов § 2. Эйлеровы и гамильтоновы контуры § 3. Сильно связные графы § 4. Порядковая функция и функция Гранди орграфа § 5. Внутренняя и внешняя устойчивость орграфа § 6. Теоремы о ядрах орграфа § 7. Задачи и упражнения Глава 2. Основные свойства неориентированных графов § 1. Основные понятия теории неориентированных графов § 2. Хроматическое число графа § 3. Цикломатическое число графа § 4. Эйлеровы графы § 5. Планарные графы § 6. Задачи и упражнения Глава 3. Деревья § 1. Основные свойства деревьев § 2. Построение остовного дерева минимального веса § 3. Задачи и упражнения Глава 4. Построение кратчайших путей в ориентированном графе § 1. Алгоритм поиска кратчайшего пути в орграфе с неотрицательными весами § 2. Алгоритм поиска кратчайших путей между всеми парами вершин орграфа для произвольной матрицы весов § 3. Задачи и упражнения Глава 5. Оптимальные потоки в орграфах § 1. Основные определения. Построение максимального потока и минимального разреза § 2. Построение заданного потока минимальной стоимости. Теорема о потоке минимальной стоимости § 3. Задачи и упражнения Глава 6. Задача коммивояжера § 1. Поиск с возвращением. Метод ветвей и границ § 2. Алгоритм решения задачи коммивояжера методом ветвей и границ § 3. Пример решения задачи коммивояжера алгоритмом Литтла § 4. Метод динамического программирования § 5. Задачи и упражнения Глава 7. Сложность алгоритмов оптимизации § 1. Алгоритмы и сложность § 2. Понятие о NP-полных задачах § 3. Задачи распознавания. Языки и кодирование § 4. Детерминированные машины Тьюринга и класс Р § 5. Недетерминированные машины Тьюринга и класс NP § 6. Соотношение между классами Р и NP § 7. Полиномиальная сводимость и NP-полные задачи § 8. Теорема Кука § 9. Метод сужения задачи для доказательства NP-полноты § 10. Задачи и упражнения Глава 8. Приближенные алгоритмы оптимизации § 1. Оценки погрешности приближенных алгоритмов § 2. Приближенный алгоритм решения задачи коммивояжера. Алгоритм дерева § 3. Приближенные алгоритм