Дипломная работа: Блочно-симметричные модели и методы проектирования систем обработки данных
Для реализации программных
модулей используются исходные информационные элементы, которые представлены в
виде множества . Взаимосвязи
между множествам программных модулей и информационными элементами отображаются
в виде матрицы , , , где , если -й информационный элемент
используется -ым модулем, , в противном случае.
Необходимо объединить
информационные элементы в массивы базы данных, чтобы минимизировать число
взаимосвязей между программными модулями и массивами базы данных системы (число
обращений к базе данных).
Для постановки задачи введем
следующие переменные и обозначение:
Тогда, задача примет вид:
.(2.4.1)
При ограничениях на:
- число информационных
элементов в записи массива
, ,(2.4.1)
где -допустимое число
информационных элементов в записи массива;
- дублирование информационных
элементов в массивах базы данных
, .(2.4.2)
Данная задача относится к
классу блочно-симметричных задач, что следует из матричного представления
.(2.4.3)
При проектировании модульных
систем обработки данных возможен случай, когда база данных уже разработана и
сформулирована для решения приложений [132,133].
При возникновении новых
приложений, которые используют заданную базу данных, модернизации и изменения
состава и содержания прикладных задач, программных модулей, путем добавления и
исключения процедур обработки данных, формирования новых запросов и других
модификации необходимо синтезировать программные модули, удовлетворяющим
предъявленным требованиям.
В этом случае, задача
проектирования программных модулей (приложений) при заданной базе данных
формулируется следующим образом.
Пусть, задана база данных в
виде множества массивов , а
также множество процедур обработки данных ,
реализация которых приводит к решению прикладных задач. Процедуры обработки
данных используют элементы базы данных, что отражается взаимосвязи между
процедурами и таблицами базы данных , , . Необходимо объеденить
процедуры в программные модули приложений таким образом, чтобы минимизировать
число взаимосвязей программных модулей с базой данных. Для математической
постановки задачи введем следующие переменные ,
, , где , если -ая процедура включена в
состав -го программного модуля и , в противном случае. В
качестве критерия используется минимум взаимосвязей проектируемых программных
модулей к массивам базы данных.
Задача формулируется следующим
образом.
.(2.4.5)
при ограничениях на:
- число процедур в составе
модуля
, ;(2.4.6)
- дублирования процедур в
модуле
, .(2.4.7)
Сформулированная задача также
сводится к блочно-симметричной задаче. Матричное представление целевой функции
имеет вид:
.(2.4.8)
Таким образом,
сформулированные выше задачи (2.4.1)-(2.4.3) и (2.4.5)-(2.4.7) являются
частными блочно-симметричными задачами ДП. Для их решения разработан и
предложен эффективный алгоритм, приведенный в разделе 3.
Выводы к разделу 2
-
Разработана и
предложена общая модель проектирования систем обработки данных. Задача
сформулирована как блочно-симметричная задача дискретного программирования. Определены
свойства и особенности данного класса задач. Предложена схема решения задачи.
-
Сформулирована
задача декомпозиции сложной системы обработки данных на кластерах прикладных
задач и исходных документов, позволяющая минимизировать взаимосвязи между ними.
Задача решается на этапе технического проектирования систем обработки данных.
-
Сформулирована
блочно-симметричная задача синтеза модульной блок схемы систем обработки
данных. В качестве критерия в постановке задачи используется минимум информационных
взаимосвязей между программными модулями и массивами базы данных при ряде
технологические ограничений при проектировании систем обработки данных на этапе
рабочего проектирования.
-
Поставленные
частные задачи проектирование массивов базы данных при заданном множестве
прикладных программных модулей, а также разработаны системы программных модулей
при заданных массивах базы данных. Задачи сведены к блочно-симметричным задачам
дискретного программирования.
3. МЕТОДЫ И
АЛГОРИТМЫ РЕШЕНИЯ БЛОЧНО-СИММЕТРИЧНЫХ ЗАДАЧ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ
ДАННЫХ. МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА СИНТЕЗА МОДУЛЬНЫХ БЛОК-СХЕМ ОБРАБОТКИ ДАННЫХ
В данном разделе
рассматриваются алгоритмы решения блочно-симметирчных задач. Разработан и
предложен эффективный алгоритм решения синтеза модульных блок-схем систем
обработки данных. Произведена оценка вычислительной сложности алгоритма. Сформулирована
двухкритериальная задача разработки модульных блок-схем систем обработки
данных. Обоснованы и предложены критерии эффективности проектирования модульных
блок-схем. Разработан алгоритм решения двухкритериальной задачи. Приведены
численные примеры реализации алгоритмов.
3.1
Эффективный алгоритм решения блочно-симметричных задач проектирования модульных
блок-схем обработки данных
Анализ методов и
алгоритмов решения задач дискретного программирования показал, что они, в
основном, являются NP-полными и имеют
экспоненциальную вычислительную сложность. Следовательно, не могут быть решены
задачи большой размерности в различных приложениях [134-137].
В отличие от известных
методов и алгоритмов путем анализа и исследования постановки, свойств и
особенностей блочно-симметричных задач разработан и предложен эффективный
алгоритм решения задач этого класса.
Рассмотрим алгоритм
решения блочно-симметричных задач вида (2.2.1)-(2.2.5), (3.2.1)-(3.2.7), а
также частных задач [138].
Для описания алгоритма
введем следующие понятия.
В случае, если в процессе
проектирования модульных блок-схем не заданы число разрабатываемых модулей и массивов базы данных , они могуть быть
определены и следующих соотношений , , где и соответственно
максимальное число процедур в модуле и максимальное число информационных
элементов в массивах базы данных. Определим понятие базиса решения задачи.
Определение 3.1.1. Подматрицу , где ; ; ; , определенную на исходной
матрице , назовем исходным базисом
решения задачи.
В качестве базиса
используются ключевые информационные элементы и используемые ими процедуры
обработки данных. Если ключевые информационные элементы не определены, то
элементы (строки и столбцы матрицы ) задаются
исходя из технологических требований проекта.
Определение 3.1.2. Величины
(3.1.1)
и
(3.1.2)
назовём расстоянием между
строками (столбцами) не вошедшими в базис и строками (столбцами), которые вошли
в базис.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 |