МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ
Модели и методы решения задач дискретного программирования при проектировании систем обработки данных
На основе выбранного значения оценок вычисляются допустимые решения;
Постановка задачи исследования
Общая постановка блочно-симметричных задач дискретного программирования
Декомпозиция прикладных задач и исходных документов систем обработки данных на этапе технического проектирования
Проектирование модульных блок-схем систем обработки данных
Частные задачи проектирования модульных блок-схем систем обработки данных
Эффективный алгоритм решения блочно-симметричных задач проектирования модульных блок-схем обработки данных
Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных
Кульба В.В., Мамиконов А.Г. Синтез оптимальных модульных СОД.М.:Наука, 1986
Навигация
Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных
Блочно-симметричные модели и методы проектирования систем обработки данных
158931
знак
0
таблиц
1
изображение
3.2 Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных
Как показал опыт проектирования систем обработки данных в ряде случаев к ним предъявляются различные технологические требования, часто противоречивые, которые необходимо учитывать. При этом одни требования имеют важное значение в качестве критериев эффективности, а другие – определяют технологические ограничения в процессе проектирования систем обработки данных.
В процессе анализа и синтеза систем обработки данных возникает необходимость одновременного учета нескольких показателей эффективности, которые определяют качество разрабатываемой ситемы в области заданных ограничений. Тогда задача сводится к тому, что необходимо использовать несколько критериев, чтобы наиболее адекватно отобразить их требуемую постановку. В этом случае необходимо формулировать и решать многокритериальные блочно-симметричные задачи.
Общая постановка многокритериальной задачи формулируется следующим образом [121-123,135,142,143].
Необходимо найти экстремум вектора функций, отражающего показатели эффективности разрабатываемых систем обработки данных в области заданных технологических ограничений.
Приведем математическую постановку общей многокритериальной задачи.
Пусть, 
- двухиндексная переменная, отражающая распределение элементов одного типа по группам, а 
- переменная, отражающая распределение элементов другого типа по соответствущим группам. Задана матрица 
взаимосвязи элементов различных типов между собой.
Определены критерии 
, 
эффективности, зависящие от переменных и 
, доставляющие экстремум функции вида , .
Многокритериальная блочно-симметричная задача дискретного программирования формулируется следующим образом:
,(3.2.1)
при ограничениях вида
, 
,(3.2.2)
, 
.(3.2.3)
Для решения однокритериальной блочно-симметричной задачи (
) разработан и предложен эффективный алгоритм, позволяющий определить оптимальные решения при определенных условиях. Используя разработанный алгоритм можно предложить следующую схему решения многокритериальной задачи.
1. Решается однокритериальная задача при ограничениях вида (3.2.2) - (3.2.3) с использованием заданного алгоритма. Определяются переменные и .
2. Определяются значение функций , 
.
3. Решается однокритериальная задача при ограничениях вида (3.2.2) - (3.2.3) с использованием заданного алгоритма. Определяются переменные и .
4. Определяются значение функций , 
.
5. Решается однокритериальная задача при ограничениях вида (3.2.2) - (3.2.3) с использованием заданного алгоритма. Определяются переменные и .
6. Экстремальные значения функций определяют область нахождения решения.
Таким образом, в результате решения многокритериальной задачи определяется область решения, в которой находится решение, удовлетворяющее всем критериям и соответствующим условиям [135].
Рассмотрим постановку и решение двухкритериальной задачи разработки модульной блок-схемы системы обработки данных.
В данной постановке необходимо множество процедур обработки данных 
распределить по программным модулям, а множество информационных элементов 
, необходимых для реализации заданных процедур, распределить по массивам базы данных таким образом, чтобы минимизировать связи между программными модулями.
В качестве критерия эффективности используем минимум взаимосвязей между модулями блок-схем и массивами базы данных. Данный критерий позволяет представить структуру блок-схемы в виде слабосвязанных компонент модулей и связанных с ними массивов базы данных, уменьшить число обращений модулей к массивам в процессе их обработки. При заданных числовых характеристиках: времени обработки процедуры информационных элементов, времени обращения модулей к массивам базы данных, объемов процедур и информационных элементов, формируется критерии минимума времени обработки блок-схем, минимума памяти при обработке блок-схем и т.д.
В матрчной форме данный критерий запишется в виде
.(3.2.4)
В процессе проектирования модульных блок-схем часто необходимо, определить межмодульный интерфейс,который представляет собой состав и число информационных элементов между модулями систем обработки данных. Данный критерий позволяет определить содержание межмодульного интерфейса и оптимальную структуру всей модульной блок-схемы.
Критерий минимума информационных элементов, используемых программными модулями (межмодульной интерфейс) блок-схемы обработки данных в матричной форме записывается следующим образом:
.(3.2.5)
В общем случае данные критерии противоречивы, для которых трудно определить точное решение.
В матричной форме двухкритериальная блочно-симметричная задача запишется в следующем виде:
(3.2.6)
(3.2.7)
при ограничениях вида (3.2.2) – (3.2.3).
- сумма единичных элементов результирующих булевых матриц (3.2.6) и (3.2.3);
, 
, 
- переменная распределения процедур обработки данных по модулям блок-схемы;
, 
, 
- переменная распределения информационных элементов по массивам базы данных;
- взаимосвязи между информационными элементами и процедурами обработки данных;
- транспонированная матрица.
Для решения поставленной задачи разработан и предложен алгортм, основанный на вышеуказанной схеме решения общей многокритериальной задачи.
Рассмотрим численный пример решения двухкритериальной задачи. На таблице 3.2.1 приведена исходная матрица. Используя предложенный алгоритм решения однокритериальных задач находим решение двухкритериальной задачи. На рис. 3.2.3 и 3.2.4 приведён численный пример решения двухкритериальной задачи. Значение целевой функции приведены на рис. 3.2.5. Полученное решение определяет область, ограниченную треугольником АВС (рис. 3.2.6).
Разработано программное обеспечение решения двухкритериальной задачи вида (3.2.6) – (3.2.7) и (3.2.2) – (3.2.3) при любом размере исходной матрицы (размер исходной матрицы генерируется случайным образом) в среде Delphi 7.0. Программное опеспечение описано в разделе 3.3.
3.3 Программное обеспечение решения двухкритериальной блочно-симметричной задачи проектирования модульных систем обработки данных
3.3.1 Описание программного обеспечения решения задач проектирования модульной блок-схемы обработки данных
Разработанная программа предназначена для решения двухкритериальной задачи проектирования модульной блок-схемы обработки данных [139-141,143,146].
Программа позволяет разработчикам СОД быстро и эффективно находить решение задачи проектирования модульной блок-схемы, удовлетворяющих заданным критериям.
Основными критериями выбора программной среды для создания данной программы являются:
1. Обеспечение максимальной простоты роботы в системе, для этого разработан удобный для пользователя интерфейс.
2. Обеспечение максимальной скорости работы программы.
3. Доступность всех шрифтов программы
На основе последовательных критериев и анализа современных программных сред была выбрана визуальная программная среда Borland Delphi 7.0. Программа разработано в среде Borland Delphi 9 [145].
Общая блок-схема программы приведена на рис.3.3.1.
Процедура Create_Mat cоздаем матрицу W случайным образом по заданным числам строк и столбцов матрицы и записывает его на файл. Процедура Rotate транспонирует заданную матрицу, используется для вычисления матрицы Y. Процедура Mat_D создает матрицу D (базис). который на каждой итераций определяет значение элементов. Процедура New_matrisa. Промежуточная матрица создается по значениям элементов матрицы D и формирует решения и Y с использованием алгоритма однокритериальной блочно-симметричной задачи. В программе используются функции SUM и SUM_UM, которые вычисляют элементы промежуточной матрицы по критериям (логическое сложение и умножение). Значение целевых функции по двум критериям соответственно записываются на два файла и строится их область решения.
3.3.2 Описание логической структуры разработанной программы предназначеной для решения двухкритериальной задачи проектирования модульной блок-схемы обработки данных
Логическая структура модуля Unit1 с привязкой к строкам текста имеет следующий вид:
1 – Присвоение имени Unit1 к Unit-у
2 – Открытый интерфейс модуля
3 – 5 – Список подключаемых модулей
6 – 7 – Объявление класса формы
8 – 13 – Объявление типов компонентов
14 – 15 – Объявление процедур
16 – 17 - Закрытая часть класса
18 – 19 – Открытая часть класса
20 – Конец объявления описании модуля
21 – 22 – Объявление типов переменных
23 – 25 – Подключение модулей
26 – 47 – Объявление типов переменных
48 – 54 – Функция сложения
55 – 61 – Функция произведения
62 – 120 – Функция создания матрицы
121 – 144 – Функция транспонирования матрицы
145 – 228 – Процедура решения Mat_D
229 – 824 – Процедура создания новой матрицы
825 – 828 – Закрытие формы Form1
829 – Конец модуля
Логическая структура модуля Unit2 с привязкой к строкам текста имеет следующий вид:
830 – Присвоение имени Unit2 к Unit-у
831 – Открытый интерфейс модуля
832 - 834 – Список подключаемых модулей
835 – 836 – Объявление класса формы
837 – 847 – Объявление типов компонентов
849 – 851 – Объявление процедур
852 – 853 - Закрытая часть класса
854 – 855 – Открытая часть класса
856 – Конец объявления описании модуля
857 – 858 – Объявление типов переменных
859 – 861 – Подключение модулей
862 – 867 – Процедура решения задачи по критерию сложения
868 – 873 - Процедура решения задачи по критерию умножения
874 – 877 – Закрытие формы Form2
878 – Конец модуля
Логическая структура модуля Unit3 с привязкой к строкам текста имеет следующий вид:
879 – Присвоение имени Unit3 к Unit-у
880 – Открытый интерфейс модуля
881 - 883 – Список подключаемых модулей
884 – 885 – Объявление класса формы
886 – 889 – Объявление типов компонентов
890 – Объявление процедур
891 – 892 - Закрытая часть класса
893 – 894 – Открытая часть класса
895 – Конец объявления описании модуля
896 – Объявление типов переменных
897 – 899 – Подключение модулей
900 – 903– Закрытие формы Form3
904 – Конец модуля
Логическая структура модуля Unit4 с привязкой к строкам текста имеет следующий вид:
905 – Присвоение имени Unit4 к Unit-у
906 – Открытый интерфейс модуля
907 - 909– Список подключаемых модулей
910 – 911 – Объявление класса формы
912 – 915 – Объявление типов компонентов
916 – Объявление процедур
917 – 918 - Закрытая часть класса
919 – 920 – Открытая часть класса
921 – Конец объявления описании модуля
922 – 923 - Объявление типов переменных
924 – 925 – Подключение модулей
926 – 929– Закрытие формы Form3
930 – Конец модуля
3.3.3 Вызов и загрузка программы
Для вызова программы необходимо запустить Пуск → Программы → Borland Delphi7 → Delphi7 и из каталога найти соответствующий . ехе файл.
Для компиляции программы нажать F9 или на вкладке Run→ Run соответственно.
Входные данные. Входные данные представлены на рисунке 3.3.2.
Выходные данные. При помощи различных процедур и функции получаем следующие данные, представленные на рисунках 3.3.3, 3.3.4, 3.3.5.
Выводы по разделу 3
- Разработан и предложен эффективный алгоритм решения блочно-симметричных задач проектирования модульных блок-схем обработки данных полиноминальной вычислительной сложности.
- Поставлена и решена многокритериальная задача синтеза модульных блок-схем обработки данных с использованием показателей эффективности: минимум взаимосвязей между модулями и массивами базы данных; минимум межмодульного интерфейса в проектируемых системах.
- Разработано программное обеспечение проектирования систем обработки данных.
ЗАКЛЮЧЕНИЕ
В диссертационной работе получены следующие результаты:
1. Разработан подход, взаимосвязанный комплекс моделей, методов, алгоритмов и программных средств формализованного проектирования систем обработки данных на основе нового класса задач – блочно-симметричных задач дискретного программирования.
2. Предложена общая постановка блочно-симметричных задач проектирования систем обработки данных. Разработана общая модель и схема её реализации, определены свойства и особенности задач данного класса.
3. Сформулирована и решена задача декомпозиции систем обработки данных на кластеры прикладных задач и исходных документов, решаемая на этапе технического проектирования систем.
4. Поставлена и решена задача синтеза оптимальных модульных блок-схем обработки данных, обеспечивающая минимум общих информационных взаимосвязей между модулями и массивами базы данных системы. Задача решается на этапе рабочего проектирования систем обработки данных и позволяет сократить затраты и время разработки прикладного программного обеспечения и базы данных.
5. Разработан новый эффективный алгоритм итеративных отображений решения блочно-симметричных задач проектирования систем обработки данных полиномиальной вычислительной сложности.
6. Сформулирована и решена многокритериальная задача проектирования модульных блок-схем обработки данных. Разработан алгоритм решения многокритериальной задачи при заданном векторе целевых функции.
7. Разработано программное обеспечение решения блочно-симметичных задач проектирования систем обработки данных.
Разработанные блочно-симметричные модели, методы, алгоритмы и программное обеспечение внедрены в Усть-Каменогорском свинцово-цинковом комбинате, Комитете информатизации и связи, а также в учебный процесс КазНТУ имени К.И.Сатпаева.
Результаты научных исследований позволили сократить длительность проектирования прикладного программного и информационного обеспечения систем обработки данных в 5-10 раз по сравнению с традиционными технологиями проектирования.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1.Трапезников В.А. Управление и научно-технический процесс. М: Наука, 1983. C.83-92.
2.Boehm B. Software engineering // IEEE Trans. Computers. Dec. 1976. V.25 №12 P.1226-1241.
3.Parnas D.L. On the criteria to be used in decomposing systems into moduls // CACM. Dec. 1978.P.1053-1058.
4.Boehm B. Software and its impact: A guantitative assessment // Datamation. May 1973. P. 48-59.
5.Phodes J. Mansgement by m=Moduls. pt. // Data systems. 1971 V.12. № 8. Pt 2; № 9.
6.Parnas D.L. The influence of software structure on reliability // Proc. Int. conf. Reliable Software. Apr. 1975. P. 358-362.
7.Липаев В.В., Филиппович В.В., Принципы и правила модульного построения сложных комплексов программ АСУ // Управляющие системы и машины. 1975. №1. C.43-52.
8.Куликов М.Я., Погребной В.К. О модульных принципах построения АСУ в условиях автоматизированного проектирования // Приборы и системы управления. 1978. №11 С. 10-14.
9.Boehm B. Structured programming: A guantitative assessment // Computer. June 1975.P. 38-54.
10.Parisi-Presicce F. A based approach to modular system design // 12th Int. Conf. Software Eng., Nice. Los Alamitos (Calif), 1990. P. 202-211.
11.George K.M. A multilevel programming paradigm // 9th Annu. Int. Phoenix conf. Comput. And Commun., Seottsdale Ariz, Los Alamitos (Calif), 1990, P.340-346.
12.Мамиконов А.Г., Косяченко С.А., Кульба В.В. Вопросы модульного построения сложных программ // Формализованные методы синтеза сложных систем. М.: Ин-т проблем управления. 1976.Выпю 13. С.-16-24.
13.Казиев Г.З., Косяченко С.А., Кульба В.В. Некоторые вопросы модульного проектирования АСУ. Научно-техническая пропаганда. М.:ЦНИИТЭИприборостроения, 1977.
14.Кульба В.В., Мамиконов А.Г. Методы анализа и синтеза оптимальных модульных систем обработки данных (обзор) // Аит. 1980. №11 С. 152-179.
Похожие работы
... также невысока и обычно составляет около 100 кбайт/с. НКМЛ могут использовать локальные интерфейсы SCSI. Лекция 3. Программное обеспечение ПЭВМ 3.1 Общая характеристика и состав программного обеспечения 3.1.1 Состав и назначение программного обеспечения Процесс взаимодействия человека с компьютером организуется устройством управления в соответствии с той программой, которую пользователь ...
... производительных сил, тем быстрее повышается Б. населения. В еще большей степени Б. связано с эффективностью социально-экономической политики в данном обществе. Информатика как наука. Предмет и объект прикладной информатики. Системы счисления Инфоpматика — это основанная на использовании компьютерной техники дисциплина, изучающая структуру и общие свойства информации, а также закономерности и ...
... . Особо стоит отметить наличие в СЗИ защиты загрузки операционной системы с гибких магнитных дисков и CD-ROM, которая обеспечивает защиту самих средств защиты от "взлома" с использованием специальных технологий. В различных СЗИ существуют программные и аппаратно-программные реализации этой защиты, однако практика показывает, что программная реализация не обеспечивает необходимой стойкости. ...
... разных этапах производства (потребления) электроэнергии. Основная цель создания таких систем – дальнейшеё повышение эффективности технических и программных средств автоматизации и диспетчеризации СЭС для улучшения технико-экономических показателей и повышения качества и надёжности электроснабжения ПП. Реформирование электроэнергетики России требует создания полномасштабных иерархических систем ...
0 комментариев