Контрольная работа: Структурное программирование

Отображение множества процедур на множество информационных элементов удобно представить в виде двудольного графа, дуги которого соединяют процедуры с соответствующими информационными элементами, причем дуги, инцидентные различным информационным элементам, могут быть помечены различными цветами (рис. 1).

Задача разбиения программного обеспечения на модули может быть сформулирована как задача разбиения заданного множества процедур обработки данных на непересекающиеся подмножества, имеющие минимальное число попарно общих информационных элементов. Наиболее наглядно такая постановка иллюстрируется с использованием графа, вершинами которого являются процедуры, а связывающие их дуги различного цвета соответствуют имеющимся информационным элементам. В этом случае в графовой интерпретации данная задача формулируется как задача разбиения раскрашенного графа на подграфы (модули), обеспечивающие минимум суммарного числа дуг различного цвета, связывающих выделенные подграфы, при ограничении на общее число выделяемых подграфов, число вершин и дуг в каждом подграфе, число связей между ними.

Для удобства постановки, описания методов и результатов решения задачи сведем информацию о связи процедур и данных (элементов записей), содержащуюся в графовой модели, в специальную табличную форму. По строкам таблицы расположим выполняемые системой функции или процедуры (запись, сортировка, контроль, обновление, выборка, печать и т.д.), а по столбцам - элементы множества идентификаторов исходных, промежуточных и выходных данных, связанных с выполнением этих процедур. На пересечении столбца и строки таблицы записывается "1" – признак зависимости или связи рассматриваемой функции и информационного элемента, если таковая существует.

Рис. 1

В этом случае критерий оптимального разбиения на модули информационного и программного обеспечения, содержание которого описано в табличной форме, формулируется следующим образом. Найти разбиение множества функций или процедур таблицы на непересекающиеся подмножества, минимизирующее суммарное число информационных связей между модулями при ограничениях: на число выделяемых модулей; на число информационных элементов, входящих в один модуль, определяющее сложность разработки блок-схемы подсистемы; на число процедур каждого модуля, определяющее, в основном, сложность кодирования блок-схемы; на число информационных связей между выделяемыми модулями; на совместимость отдельных процедур.

Введем необходимые обозначения:

D = {d₁ , d₂ , ..., d_l , ..., d_i }

-множество информационных элементов системы; - матрица взаимосвязи процедур и информационных элементов, где

Суммарное число S различн. информационных элементов, являющихся попарно общими для различных модулей, равно

При разработке программного обеспечения АСУ требуется минимизировать S при следующих основных технологических ограничениях: на число процедур в модулях

где М_v - мощность множества процедур в v-м модуле;

на число информационных элементов, используемых модулями,

где L_v - максимальное число информационных элементов, используемых v-м модулем;

на интерфейс между отдельным модулем и другими модулями системы

где S_{v '} - максимально возможное число информационных связей между модулем v' и остальными модулями системы;

на интерфейс между двумя заданными модулями системы

где S_{vv '} - максимально возможное число информационных связей между модулями v и v';

на разделение отдельных процедур системы по различным модулям

x_ry + x_{r ' v} ≤ 1,

где v = 1, 2, ..., V для заданных r и r'. Поставленная задача является задачей квадратичного целочисленного программирования и может быть сведена к линейной форме путем линеаризации выражений и введением связи между вспомогательными и основными переменными. В этом случае она может быть решена с использованием имеющихся пакетов прикладных программ.

В условиях, когда задано информационное обеспечение, т.е. определено содержание каждого информационного массива и его динамические характеристики, решаются динамические задачи разбиения системы программного обеспечения на модули. В качестве критерия оптимизации используются минимум общего времени обмена с внешней памятью и минимум межмодульного интерфейса.

Исходными данными для постановки и решения динамических задач синтеза системы модулей являются множество информационных массивов системы, для которых определены: входные, выходные и промежуточные данные; множество альтернативных процедур обработки данных, входящих в состав алгоритмов, обеспечивающих решение задач системы; возможные последовательности выполнения процедур в процессе обработки; способы обмена с внешней памятью модульной системы обработки данных; взаимосвязи процедур с информационными массивами; временные характеристики обращения к массивам.