Исследование математических моделей и построение алгоритмов с оценками для векторных задач об остовных деревьях

• Автор: Зинченко, Ольга Алексеевна
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Черкесск
• Количество страниц: 123 с. : ил.

1.1. Содержательное описание задачи и соответствующая теоретикографовая модель.

1.2. Общая постановка векторной задачи об остовных деревьях

1.2.1. Представление топологических критериев, используемых в задаче об остовных деревьях

1.3. Оценка вычислительной сложности задачи об остовных деревьях.

1.3.1. Оценка мощности ПМА X для задач об остовных деревьях

1.3.2. ИРтрудная проблема нахождения ПМА для векторных задач об остовных деревьях

Глава 2. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЙ КЛАСС ЗАДАЧ ОБ

ОСТОВНЫХ ДЕРЕВЬЯХ

2.1. Полиномиальная разрешимость однокритериальных задач с топологическими критериями.
2.2. Полиномиальная разрешимость 2критериальных задач, в которых один из критериев является

топологически м.

Глава 3. ИСПОЛЬЗОВАНИЕ ПРЕДФРАКТАЛЬНОГО ДЕРЕВА
3.1. Определение фрактального графа
3.2. Операция замещения вершин затравкой ЗВЗ
3.3. Порождение Р адического дерева.
3.4. Фрактальное дерево
3.4.1. Регулярное дерево
3.4.2. Оценки диаметра предфрактального дерева
3.5. Остовное дерево предфрактального графа О
3.6. Алгоритм замещения висячей вершины затравкой
3.6.1. Индивидуальная задача выделения остовного дерева
степени 4.
Глава 4. ДЕКОМПОЗИЦИОННЫЙ СТАТИСТИЧЕСКИ ЭФФЕКТИВНЫЙ АЛГОРИТМ
4.1. Формулировка проблемы
4.2. Описание алгоритма А .
4.3. Обоснование статистической эффективности алгоритма
4.3.1 .Выделение минимального связного остовного дерева
со степенями вершин не более 3.
4.3.2. Выделение остовного дерева с ограничением на
степени вершин.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Обычно в каждом конкретном случае общая задача управления делится на части, что приводит к разделению информационной системы на подсистемы, которые по отношению ко всей ЭИС называются подсистемами первого уровня. Деление на подсистемы производится в каждом конкретном случае по своему принципу. Графическое разделение экономической информационной системы ЭИС на подсистемы ПС можно представить с помощью дерева. Рис. Система и подсистемы
На рис. ПС означает уровень подсистемы, второй ее порядковый номер в этом уровне. Чем сложнее исходная система, тем больше уровней подсистем она имеет. Задача о нахождении покрывающего дерева минимального веса имеет очевидную экономическую интерпретацию пгородов нужно соединить сетью шоссейных дорог. Г, можно было бы проехать в любой другой город Г,. Деревья представляют структуры, которые чрезвычайно часто используются в современном программировании. В частности, различные воплощения рекурсивных вычислений приводят естественным образом к деревьям. Новейшие языки программирования часто содержат средства для обработки списков. Список есть фактически корневое дерево, с висячими вершинами которого связаны элементарные единицы информации. Т.о. ЛИСП, ПЛЭННЕР и т. Необходимость в исследовании многокритериальных задач возникает в результате того, что при математическом моделировании достаточно сложных систем и объектов постановка скалярной однокритериальной задачи оптимизации не удовлетворяет потребностям лица, принимающего решение ЛПР, в связи с тем, что построение обобщенных функций полезности интегральной эффективности является проблемой весьма сложной, а иногда неразрешимой.