Модели и методы дискретной оптимизации. Модули 1 и 2 (1900,00 руб.)

Стр.3

Стр.277

Стр.278

УДК 004.02 + 519.1(075.8) ББК 22.176 О-35 Издание доступно в электронном виде по адресу ebooks.bmstu.press/catalog/255/book2061.html Овчинников, В. А. О-35 Модели и методы дискретной оптимизации. Модули 1 и 2 : учебник / В. А. Овчинников. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2019. — 277, [1] с. : ил. ISBN 978-5-7038-5105-0 Изложен ряд основных разделов теории графов, необходимых для разработки моделей объектов и задач дискретной оптимизации. Рассмотрены модели структур сложных систем в виде различного вида графов: ультра-, гипер-, ориентированных и неориентированных, а также формальные постановки задач комбинаторной оптимизации на графах. Описаны особенности и сущность точных методов дискретной оптимизации, таких как жадный выбор, поиск в ширину и в глубину с возвращением, ветвей и границ, Дейкстры, Форда — Фалкерсона и динамического программирования. Для студентов, обучающихся по направлению подготовки «Информатика и вычислительная техника» (уровень магистратуры), а также для преподавателей и аспирантов. Может быть полезен для научных работников, инженеров, аспирантов и студентов специальностей, связанных с проектированием сложных систем. УДК 004.02 + 519.1(075.8) ББК 22.176 ISBN 978-5-7038-5105-0 © Овчинников В.А., 2019 © Оформление. Издательство МГТУ им. Н.Э. Баумана, 2019

Стр.3

Оглавление Предисловие Условные обозначения Введение Модуль 1. Задачи дискретной оптимизации, модели их объектов и формальная постановка задач Глава 1 Оптимизационные задачи дискретной математики и классы их сложности 1 1 Примеры задач дискретной оптимизации 1 2 Общая характеристика задач структурного синтеза 1 3 Этапы решения прикладной задачи структурного синтеза 1 4 Классы сложности задач дискретной оптимизации Контрольные вопросы и задания Глава 2 Основные понятия теории графов 2 1 Общее определение графа 2 2 Ультраграф 2 3 Гиперграф 2 4 Ориентированный граф 2 5 Неориентированный граф 2 6 Графы смешанные, с кратными ребрами, весами и сортированными вершинами в гиперребрах 2 7 Некоторые особые графы, блоки и части графов 2 8 Особые множества вершин и ребер графов 2 9 Изоморфизм и планарность графов Контрольные вопросы и задания Глава 3 Математические модели объектов структурного анализа и синтеза 3 1 Требования к математическим моделям объектов проектирования 3 2 Разработка моделей объекта и результата проектирования 3 3 Информация о структуре системы и ее монтажной области 3 4 Модель структуры системы в виде ультраграфа 3 7 Представление схем неориентированным и смешанным графами 3 8 Модели монтажной области 3 9 Информационно-логическая модель алгоритма 3 10 Структуры данных и их модели 3 10 1 Основные операции над структурами данных 3 10 2 Двухуровневые структуры данных 3 10 3 Комбинированные структуры данных 3 10 4 Отношения на элементах записи множеств и их модели 3 10 5 Модели одноуровневых структур данных 3 10 6 Модели двухуровневой и комбинированной структур данных 3 11 Модель сети Контрольные вопросы и задания 3 5 7 9 10 10 12 13 16 20 21 21 25 41 50 58 64 69 89 96 102 104 104 105 106 108 3 5 Представление схем соединения подсистем ориентированным графом 112 3 6 Модель структуры системы в виде гиперграфа 115 118 120 123 131 131 132 134 137 145 153 158 159

Стр.277

Оглавление Глава 4 Математические модели задач дискретной оптимизации 4 1 Общая формальная постановка задачи дискретной оптимизации 4 2 Формальная постановка задачи позиционирования 4 3 Модели коммутационных задач 4 4 Модели задач декомпозиции структур 4 5 Формальная постановка задачи установления идентичности структур 4 6 Модели задач выделения подмножеств особых компонентов 4 7 Модель задачи о максимальном потоке Контрольные вопросы и задания Модуль 2. Точные методы дискретной оптимизации и способы снижения вычислительной сложности алгоритмов Глава 5 Точные методы решения комбинаторных задач 5 1 Стратегии поиска решений задач дискретной оптимизации 5 2 Отсечение и выбор вариантов 5 3 Жадный выбор 5 4 Поиск в ширину и в глубину с возвращением 5 5 Метод ветвей и границ 5 6 Метод Дейкстры 5 7 Метод Форда — Фалкерсона 5 8 Динамическое программирование 5 9 Композиция методов дискретной оптимизации Контрольные вопросы и задания Глава 6 Операции преобразования моделей объектов структурного синтеза 6 1 Операции над графами 6 2 Добавление вершин и ребер 6 3 Удаление вершин и ребер 6 4 Свертка подмножества вершин 6 5 Стягивание ребер и подразбиение ребра 6 6 Объединение ультраграфов, гиперграфов и их кусков Контрольные вопросы и задания Глава 7 Оптимизирующие преобразования алгоритмов на графах и множествах 277 161 161 162 163 168 170 172 174 174 175 176 176 181 183 184 192 198 201 208 214 218 220 220 221 227 234 237 243 245 246 7 1 Основные способы снижения вычислительной сложности алгоритмов 246 7 2 Снижение вычислительной сложности алгоритмов за счет корректности формальной постановки задачи, выбора метода ее решения и снижения размерности входа 7 3 Преобразования, вытекающие из принципа формирования решения 7 4 Преобразования, определяемые способами задания множеств и графов 7 5 Преобразования, связанные со свойствами и характеристиками графов исходного описания объекта и результата проектирования 7 6 Преобразования, использующие свойства множеств, предикатов и операций над ними Контрольные вопросы и задания Литература Предметный указатель 249 249 252 255 258 268 269 271

Стр.278