Дипломная работа: Блочно-симметричные модели и методы проектирования систем обработки данных
Одним из этапов проектирования
систем обработки данных является определение переченя и последовательности
решения функциональных (прикладных) задач
обработки данных и состава исходных документов, в которых содержится необходимая входная информация
(информационные элементы) и установленные взаимосвязи между ними.
При большом числе прикладных задач и требуемых для их решения исходных документов,
появляется необходимость декомпозиции этой структуры с целью разделения ее на
слабосвязанные фрагменты для облегчения процесса проектирования.
В последующем каждый фрагмент
представляется в виде множества процедур обработки данных и взаимосвязанным с
ними информационных элементов. На этом этапе необходимо сформулировать
структуру модульной системы обработки данных, представляющую собой совокупность
процедур обработки данных, объединенных в модули и совокупности информационных
элементов, объединены в массивы (таблицы) базы данных и установить между ними
оптимальные взаимосвязи.
Необходимо обосновать и
выбрать критерии оптимизации в процессе формализованного проектирования систем
обработки данных.
Большие размерности задач,
решаемые на каждом этапе проектирования обусловливают необходимость
исследования и разработки новых подходов, моделей, методов и алгоритмов
проектирования систем обработки данных.
Одним из новых направлении
постановки и решения задач эффективного проектирования СОД являются
блочно-симметричные модели и методы, которые позволяют решать задачи большой
размерности. Разработка и развитие этих методов является весьма актуальной проблемой.
В процессе проектирования СОД возникает
необходимость учета вектора критериев оптимизации, которые часто бывают
противоречивым.
В этом случае решается
многокритериальная задача дискретного программирования, алгоритмы решения
которых являются сложными и требуют новых подходов.
Анализ существующих методов
проектирования модульных систем обработки данных (МСОД), алгоритмов реализации
этих моделей и проведенные исследования показали необходимость разработки новых
подходов и классов моделей и методов проектирования систем обработки данных.
На основе проведенного анализа
моделей и методов проектирования СОД сформулированы задачи исследования.
Необходимо разработать
взаимосвязанный комплекс моделей и методов, алгоритмов и программ
формализованного проектирования систем обработки данных, включающий следующие
задачи:
-разработать общую
блочно-симметричную модель проектирования систем обработки данных;
- сформулировать и решить
задачу декомпозиции систем обработки данных на кластеры функциональных задач и
исходных документов;
- разработать методы синтеза
модульных блок-схем обработки данных;
- разработать
многокритериальные блочно-симметричные модели и методы проектирования модульных
блок-схем обработки данных;
- разработать подход,
эффективные методы и алгоритмы решения блочно-симметричных задач и программное
обеспечение.
Выводы к разделу 1
-
Приведен анализ
существующих моделей и методов проектирования модульных систем обработки
данных.
-
Приведен краткий
обзор методов и алгоритмов дискретного программирование для решения задач
проектирование систем обработки данных.
-
Сформулированы
задачи диссертационного исследования.
2.
БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ
В данном разделе
рассматриваются общая постановка блочно-симметричной задачи дискретного
программирования, её особенности и свойства. Разработан общий подход решения
задач данного класса.
Сформулирована постановка
задачи декомпозиции функциональных задач обработки данных и исходных документов
в виде блочно-симметричной задачи дискретного программирования.
Указанная задача решается
на этапе технического проектирования систем обработки данных. С использованием
результату этой задачи поставлена задача проектирования модульных блок-схем
обработки данных, обеспечиваем разработку прикладного программного обеспечения
и базы данных.
Сформулирован также
частные задачи проектирования модульных блок-схем обработки данных [142]
2.1 Общая
постановка блочно-симметричных задач дискретного программирования
Ряд прикладных задач:
проектирования модульного программного обеспечения и массивов базы данных
информационных систем, распределение программных модулей и массивов базы данных
по узлам вычислительных сетей, выбор проектов в условиях ограниченных ресурсов
можно сформулировать в виде нового класса задач – блочно-симметричных моделей
дискретного программирования. В отличие от традиционных моделей модели этого
класса позволяют формулировать задачи с несколькими типами переменных различной
природы, проводить декомпозицию сложных задач на блоки с единой целевой
функцией и разрабатывать эффективные алгоритмы, имеющие полиномиальную
вычислительную сложность.
Рассмотрим общую
постановку блочно-симметричных задач дискретного программирования [126, 127].
Постановка задачи. Пусть задано множество объектов и множество объектов с элементами различных
типов, а также взаимосвязи между элементам этих множеств, которые определяются
матрицей
, ,,
Элементы которой целочисленные
и булевы. Необходимо объединить элементы множество в
непересекающиеся подмножества , а
элементы множества -
непересекающейся подмножества , таким
образом, чтобы доставить экстремум целевой функции .
Для формализованной
постановки задачи введем следующие переменные. Пусть - булева матрица, где , если -й элемент распределяется в
-ю группу, в противном случае.
Аналогично , где , если -й элемент распределяется в
-ю группу и в противном случае. В общем
случае матрицы переменных и могут быть целочисленными
[136].
Определим на множестве функцию , зависящую от распределения
элементов множеств и по подмножествам и . Соответственно на
множестве - функции , а на множестве - функции , определяющие ограничения
на множествах и .
Блочно-симметричная
задача дискретного программирования формулируется следующим образом:
,(2.1.1)
при ограничениях
(2.1.2)
(2.1.3)
В множестве ограничений
(2.1.2) и (2.1.3) в зависимости от постановок задач знаки неравенств могут
меняться на противоположеные.
В общем случае
двухиндексные матрицы – переменных и и заданная матрица могут быть целочисленными.
Рассмотрим задачу при
условии, когда переменные , и - булевы матрицы. В
качестве функции часто используют
функцию вида , где
(2.1.4)
Рассмотрим выражение
(2.1.4), которое представляет собой произведение матриц переменных и и заданной матрицы , на которой определена
целевая функция. В отличие от традиционных постановок задач дискретного
программирования в данной постановке имеются два типа переменных и , переменные и симметричны относительно
заданной матрицы .
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 |