Введение
Глава 1. Обзор способов представления распределенных структур и методов их обработки 32
1.1. Ориентированные, взвешенные графы и деревья 33
1.2. Матричные алгоритмы на графах 43
1.3. Технологии обработки разреженных матриц 44
1.4. Методы определения трудоемкости алгоритмов 51
1.5. Оптимизация вычислений за счет распараллеливания алгоритмов 57
Выводы 61
Глава 2. Методы преобразования разреженных прямоугольных матриц с сохранением первоначальных значений 64
2.1. Примеры задач, сводимых к разреженным матрицам 64
2.2. Приведение разреженной матрицы к односторонне окаймляющей блочной диагональной форме 67
2.3. Приведение разреженной матрицы к треугольной форме 70
2.3.1. Метод ненулевой диагонали 71
2.3.2. Метод уплотнения вниз 77
Выводы 83
Глава 3. Организация последовательных и параллельных вычислений 84
3.1. Матричный метод перебора путей в графе 87
3.2. Построение параллельного алгоритма на основе его последовательного аналога с последующей оптимизацией по числу процессоров 88
3.2.1. Матричное преобразование алгоритмов и их оптимизация по числу процессоров 88
3.2.2. Оптимизация алгоритмов по ширине с применением списков смежности 99
3.2.3. Оптимизация алгоритмов по ширине с применением списков следования 104
3.3. Оптимизация параллельных алгоритмов по времени выполнения 109
3.3.1. Матричное преобразование алгоритма с целью
оптимизации по времени выполнения 111
3.3.2. Оптимизация алгоритма по времени выполнения с
применением списков следования 117
3.4. Оптимизация алгоритмов по нескольким параметрам 132
Выводы 138
Глава 4. Методы конструирования реляционных схем на основе метаданных функциональных зависимостей 140
4.1. Проблемы аномалии избыточности в различных моделях данных 140
4.2. Функциональные зависимости реляционных отношений 141
4.2.1. Представление функциональных зависимостей с помощью графов 141
4.3. Построение реляционной модели на основе орграфа функциональных зависимостей 150
4.4. Декомпозиция отношения на основе орграфа простых функциональных зависимостей 157
4.5. Метод получения новых функциональных зависимостей на основе декларированных 164
4.6. Определение ключей по орграфу функциональных зависимостей 170
4.7. Декомпозиция отношения на основе орграфа составных функциональных зависимостей 176
Выводы 179
Глава 5. Применение разработанных методов на различных прикладных задачах 181
5.1. Задача 1. Распараллеливание алгоритма конструирования реляционных схем 181
5.1.1. Построение информационного графа алгоритма 181
5.1.2. Оптимизация информационного графа алгоритма нормализации реляционных отношений 194
Выводы 208
5.2. Задача 2. Организация преобразований в системах, основанных на расписании 210
5.2.1. Выполнение параллельных процессов в системе 210
5.2.2. Графовый метод распределения задач на кластере 213
5.2.3. Матричный метод распределение задач 225
5.2.4. Применение онтологии при организации процесса распределения задач на кластере
Выводы 243
5.3. Задача 3. Тестирование разработанных методов на модели управления процессом электролиза алюминия 245
5.3.1. Структурная идентификация процесса получения алюминия 245
5.3.2. Выбор метода решения системы линейных уравнений 249
5.3.3. Применение методов распараллеливания к алгоритму по приведению разреженной матрицы к форме BDF на модели управления процессом электролиза алюминия 260
Выводы 271
5.4. Задача 4. Применение матричных методов в теории принятия решений 273
5.4.1. Особенности алгоритмов построения дерева решений 273
5.4.2. Применение методов распараллеливания к алгоритму ID3 276
5.4.3. Матричный метод построения дерева решений 286
Выводы 293
Заключение 294
Список литературы
