Модели и методы дискретной оптимизации. Модули 1 и 2

Модели и методы дискретной оптимизации. Модули 1 и 2
В.А. Овчинников
  • Год:
    2019
  • Тип издания:
    Учебник
  • Объем:
    278 стр. / 0 п.л
  • Формат:
    60x90/16
  • ISBN:
    978-5-7038-5105-0
  • Читать Online

Ключевые слова: адекватность модели, гиперграф, глубинное дерево (d-дерево), двоичная свертка, декомпозиция, дерево просмотра в ширину (Ь-дерево), дерево решений, дискретная оптимизация, задачи дискретной оптимизации, изоморфизм, информационно-логическая модель алгоритма, класс сложности задачи, композиция, корректность трансформации, максимальное паросочетание, максимальный поток, математическая модель, метод Дейкстры, метод Форда — Фалкерсона, метод ветвей и границ, метод динамического программирования, метод жадного выбора, методы дискретной оптимизации, модель вектора, модель сети, модель списка, неориентированный граф, операция добавления вершины (ребра), операция подразбиения ребра, операция свертки (факторизации) вершин, операция стягивания ребер, операция удаления вершины (ребра), оптимальное решение, оптимизирующие преобразования, ориентированный граф, особые графы, отсекающая оценка, оценка перспективности, парная свертка, поиск в глубину с возвращением, поиск в ширину, свойство оптимальности, структурный синтез, структуры данных, теория графов, ультраграф, формальная постановка задачи, целевая функция, эквивалентность алгоритмов

Изложен ряд основных разделов теории графов, необходимых для разработки моделей объектов и задач дискретной оптимизации. Рассмотрены модели структур сложных систем в виде различного вида графов: ультра-, гипер-, ориентированных и неориентированных, а также формальные постановки задач комбинаторной оптимизации на графах. Описаны особенности и сущность точных методов дискретной оптимизации, таких как жадный выбор, поиск в ширину и в глубину с возвращением, ветвей и границ, Дейкстры, Форда — Фалкерсона и динамического программирования.
Для студентов, обучающихся по направлению подготовки «Информатика и вычислительная техника» (уровень магистратуры), а также для преподавателей и аспирантов. Может быть полезен для научных работников, инженеров, аспирантов и студентов специальностей, связанных с проектированием сложных систем.

 

ОГЛАВЛЕНИЕ

Предисловие
Условные обозначения
Введение
Модуль 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.5. Представление схем соединения подсистем ориентированным графом
3.6. Модель структуры системы в виде гиперграфа
3.7. Представление схем неориентированным и смешанным графами
3.8. Модели монтажной области
3.9. Информационно-логическая модель алгоритма
3.10. Структуры данных и их модели
3.11. Модель сети
Контрольные вопросы и задания
Глава 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 Оптимизирующие преобразования алгоритмов на графах и множествах
7.1. Основные способы снижения вычислительной сложности алгоритмов 246
7.2. Снижение вычислительной сложности алгоритмов за счет
корректности формальной постановки задачи, выбора метода ее решения и снижения размерности входа
7.3. Преобразования, вытекающие из принципа формирования решения
7.4. Преобразования, определяемые способами задания множеств и графов
7.5. Преобразования, связанные со свойствами и характеристиками графов исходного описания объекта и результата проектирования
7.6. Преобразования, использующие свойства множеств, предикатов и операций над ними
Контрольные вопросы и задания
Литература
Предметный указатель

Авторы работы: Овчинников В.А.