Эффективные алгоритмы и программные средства реализации линейных диофантовых моделей сетей ЭВМ

• Автор: Кулаков, Кирилл Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Петрозаводск
• Количество страниц: 170 с. : ил.

Оглавление

Перечень сокращений и условных обозначений

Введение
1. Системы однородных неотрицательных линейных ди-офантовых уравнений, ассоциированные с контекстно-свободными грамматиками

1.1 Основные свойства систем одАНЛДУ

1.2 Сложность задачи нахождения базиса Гильберта

1.3 Частные случаи систем одАНЛДУ

1.4 Преобразования произвольной системы одАНЛДУ

1.5 Сравнение предложенных преобразований с общим методом

последовательного исключения

1.6 Моделирование сетей ЭВМ на основе систем одАНЛДУ и базисов Гильберта
Выводы
2. Линейные диофантовы модели сети MPLS
2.1 Обзор технологии и размерность реальных сетей MPLS
2.2 Задача восстановления соединений в сети MPLS
2.3 Обзор алгоритмов восстановления соединений
2.4 Модель топологии

2.5 Модель с фиксированным соединением
2.6 Модель с характеристиками линии связи
2.7 Кумулятивная характеристика маршрута
2.8 Модель с множественной пересылкой
2.9 Вопросы применения моделей
Выводы
3. Алгоритмы нахождения базиса Гильберта и генерации систем одАНЛДУ
3.1 Постановка задач решения и генерации
3.2 Построение оценок вычислительной сложности
3.3 Алгоритм ТгапзЗої нахождения базиса Гильберта системы
одАНЛДУ
3.3.1 Алгоритм преобразования к трапециевидной форме
3.3.2 Алгоритм НБГ системы 5
3.3.3 Алгоритм подстановки базиса для системы (1.9)
3.3.4 Модификация алгоритма ТгапвЗоІ для нахождения части базиса
3.4 Алгоритм ЛогбапСеп генерации систем одАНЛДУ с единичным базисом Гильберта
3.5 Алгоритм СаиБвСеп генерации систем одАНЛДУ с частично
единичным базисом Гильберта
3.6 Алгоритм ЕхіДаивзДеп генерации систем одАНЛДУ с частично единичным базисом Гильберта. Общий случай
3.7 Алгоритм ЭутОеп генерации систем содАНЛДУ
3.8 Алгоритм ExtSymGen генерации систем одАНЛДУ, сводящихся к симметричным
3.9 Применение алгоритмов НБГ и генерации для моделирования сети MPLS
3.9.1 Генерация и реализация модели топологии
3.9.2 Генерация и реализация модели с фиксированным соединением
3.9.3 Генерация и реализация модели с характеристиками линии связи
3.9.4 Генерация и реализация модели с множественной пересылкой
3.10 Сводная информация по разработанным алгоритмам
Выводы
Комплекс программ и экспериментальное исследование алгоритмов
4.1 Постановка задач экспериментального исследования
4.2 Измерение вычислительных ресурсов
4.3 Комплекс программ для поддержки экспериментов
4.3.1 Реализация алгоритмов НБГ и генерации
4.3.2 Программная система alg_analyser
4.3.3 Программная система Web-SynDic
4.4 Экспериментальное исследование алгоритмов
4.4.1 Схема организации экспериментов
4.4.2 Тестирование алгоритма Syntactic

В преобразовании к трапециевидной форме итераций может быть меньше (?' п). При г < п исходная система сводится не к одному уравнению, а к некоторой системе содАНЛДУ, для которой известны линейные по числу базисных решений алгоритмы НБГ [71]. На каждой итерации обратной подстановки решается 1одАНЛДУ, для которого также известен линейный по числу базисных решений алгоритм (свойство 1.3 на с. 28).
2. В общем методе исключения уравнений на каждой итерации получается система одНЛДУ с меньшим числом уравнений, но, возможно, с экспоненциальным числом неизвестных и большими абсолютными значениями коэффициентов в сравнении с исходной системой.
В предложенных преобразованиях промежуточная система S всегда является подсистемой исходной системы, поскольку получена исключе-

нием уравнений и неизвестных. Она содержит неизвестные [Д. = Nm [J Lj.

3. Общий метод исключения неизвестных ориентирован на исключение одной неизвестной на каждой итерации.
В преобразовании к трапециевидной форме на каждой итерации может исключаться несколько неизвестных (xi, i € Lfc), которые агрегируются в виде 1одАНЛДУ (1-14).
4. Общий метод исключения уравнений на каждой итерации требует трудоемкой операции отбора минимальных решений (1.2).
В обратной подстановке для произвольной системы одАНЛДУ нельзя полностью избавиться от выполнения этой операции. Однако, автором найден подкласс систем, для которых она не требуется (теорема 3.3 в гл. 3). Также автором разработаны алгоритмы генерации М-систем одАНЛДУ, для которых не требуется этой операции (гл. 3).