49743 (588672), страница 10
Текст из файла (страница 10)
Пусть, - множество прикладных задач обработки данных, подлежащие автоматизации;
- множество исходных документов, используемое для решения прикладных задач. Задана, матрица
,
,
, где
, если
-й исходный документ используется для решения
-ой прикладной задачи системы и
, в противном случае.
Необходимо разбить систему на подмножества прикладных задач и используемых ими документов таким образом, чтобы минимизировать взаимосвязи между кластерами прикладных задач и документов в процессе проектирования СОД (рис 2.2.1).
Определим дополнительные переменные следующим образом:
Данная переменная отражает использование -го документа для решения задач
-го кластера.
Переменная отражает использование в процессе решения
-ой задачи
-го кластера документов.
Взаимосвязи между кластерами прикладных задач и документов определяется из выражения:
Задачу декомпозиции СОД сформулируем следующим образом.
Необходимо минимизировать функцию вида
.(2.2.1)
При ограничениях на:
-
включение каждой прикладной задачи только в один кластер
,
;(2.2.2)
-
включение документа только в один кластер документов
,
;(2.2.3)
-
время разработки каждого кластера задач
,
;(2.2.4)
-
стоимость проектирования каждого кластера задач
,
;(2.2.5)
-
число прикладных задач в кластере
,
;(2.2.6)
-
число исходных документов в кластере
,
.(2.2.7)
Поставленная задача относится к блочно-симметричным задачам дискретного программирования. Для её решения разработан и предложен эффективный алгоритм позволяющий решать задачи большой размерности.
2.3 Проектирование модульных блок-схем систем обработки данных
В результатах декомпозиции сложных систем обработки данных на кластеры на этапе технического проектирования необходимо для каждого кластера разработать модульную блок-схему прикладного программного обеспечения и базы данных. Каждый кластер СОД и входящие в его состав прикладные задачи могут быть представлены в виде направлении графа процедур обработки данных, а кластер исходных документов – в виде совокупности информационных элементов. Эти данные являются исходными для проектирования прикладных программ и базы данных. Известно, что любой разветвленный граф отображения прикладной задачи можно представить в виде последовательного графа – цели отражающий последовательность реализации процедур [126]. Поэтому каждый кластер и задачу можно отобразить в виде линейной последовательности процедур.
Определение 2.3.1. Модульной блок-схемой обработки данных будем называть совокупность процедур, объединенных в модули и множество информационных элементов, объединенных в массивы (таблица) данных с отображением ингрированных связей между модулями и массивами.
Модульная блок-схема позволяет автоматизировать процесс программирования прикладных задач и создания базы данных и сократить затраты и длительность разрабатываемых систем.
На этапе рабочего проектирования наиболее общим критерием синтеза оптимальных блок-схем модульных СОД является их сложность, которая на логическом уровне измеряется числом информационных взаимосвязей между программными модулями и массивами базы данных. При синтезе блок-схемы должны быть учтены основные характеристики и ограничения систем управления базами данных и вычислительных средств, на которых предполагается эксплуатация создаваемого программного и информационного обеспечения.
Рассмотрим задачу синтеза модульной блок-схемы системы обработки данных, минимизирующей общее число связей между модулями и массивами базы данных.
Для постановки задачи введем следующие обозначения. Пусть, - множество процедур обработки данных для решения прикладных задач системы;
- множество информационных элементов, необходимых для реализации процедур из множеств
. На множестве
введем отношение
, определяемое матрицей
, где
Необходимо синтезировать модульную блок-схему СОД путем распределения множества процедур по модулям обработки данных, множества информационных элементов – в логическую структуру базы данных и установить оптимальные взаимосвязи между модулями и логической структурой базы данных, минимизирующих число взаимосвязей между компонентами блок-схемы.
Введем следующие переменные:
Введем вспомогательные переменные:
Переменная отражает использование -го информационного элемента
-м модулем, т.е. если хотя бы один информационный элемент обрабатывается
-ой процедурой, включенный в состав
-го модуля, то данный элемент также обрабатывается этим модулем.
Переменная отражает использование -го массива данных
-ой процедурой, т.е. если процедура использует хотя бы один информационный элемент, включенной в состав
-го массива данных, то данная процедура использует этот массив.
Переменную отражающую взаимосвязь между модулями блок-схемы и массивами базы данных можно определить следующим образом:
,
либо,
Определение указанных переменных вытекает из свойства симметричности блочно-симметричных задач.
Задача проектирования модульных блок-схем систем обработки данных (МСОД) формулируется следующим образом.
Необходимо синтезировать модульную блок схему путем распределения множества процедур по модулям обработки данных, множества информационных элементов – в логическую структуру базы данных и установить оптимальные взаимосвязи между модулями и логической структурой базы данных, минимизирующих число взаимосвязей между компонентами блок-схем.
При этом должны быть учтены такие требования, как ограниченность размеров модулей и логических массивов базы данных, отсутствие дублирования процедур в модулях и информационных элементов в логических массивах.
Математическая постановка задачи имеет вид:
(2.3.1)
при ограничениях:
-
число процедур в составе каждого модуля блок-схемы
,
,(2.3.2)
где -допустимое число процедур в
-ом модуле;
-
включение отдельных процедур обработкиданных в состав одного модуля
,
,(2.3.3)
для заданных и
;
-
дублирование процедур в модулях блок-схемы
,
,(2.3.4)
-
размер записи массива базы данных
;
, (2.3.5)
где - допустимое число информационных элементов в записи
-го массива данных;
-
дублирование информационных элементов в массивах базы данных
,
;(2.3.6)
-
число информационных элементов, обрабатываемых каждым модулем
,
.(2.3.7)
Сформулированная задача относится к новому классу задач дискретного программирования - блочно-симметричным задачам с булевыми двухиндексными переменными.
Целевую функцию (2.3.1) блочно-симметричной задачи разработки модульной блок-схемы удобно представить в матричной форме.
(2.3.8)
или
.(2.3.9)
Решением задач (2.3.1)-(2.3.7) являются множества булевых матриц , в котором
- состав модулей блок-схемы,
- состав массивов базы данных блок-схемы,
- взаимосвязи между модулями и массивами базы данных блок-схемы, а также оптимальные значение целевой функции
. Для решения данной задачи разработан и предложен эффективный алгоритм итеративных отображений (раздел 3).
2.4 Частные задачи проектирования модульных блок-схем систем обработки данных
Многоэтапный процесс разработки базы данных, который включает последовательное создание её концептуальной, логической и физической модели с последующей эксплуатацией с использованием возможностей выбранной системы управления базой данных (СУБД). При этом наиболее трудоемким этапом является проектирование концептуальной и логической модели данных в процессе которого необходимо провести анализ предметной области, определить сущности (объекты) и их взаимосвязи, выделить ключевые элементы и т.д.
Работы по проектированию базы данных на этом этапе слабо формализованы и в большой мере основаны на опыте и интуиции разработчиков.
В процессе проектирование базы данных необходимо также обеспечить эффективность её анализа, структуризации и обработкию. Поэтому структуризация проектируемой базы данных, то есть выделение массивов и взаимосвязей между ними и обеспечение её эффективности является актуальной задачей.
В процессе проектирование систем обработки данных на различных объектах могут возникнут ситуации, связанные с условиями и особенностями данных объектов. К примеру, определен состав прикладных задач, которые имеют модульную структуру программ и для реализации указанных задач необходимо сформулировать базу данных.