Блочно-симметричные модели и методы проектирования систем обработки данных

Казахский Национальный Технический Университет имени К.И.Сатпаева

УДК 658.512 519.87 004.83на правах рукописи

НАБИЕВА ГУЛНАЗ СОЦИАЛЕВНА

Блочно-симметричные модели и методы проектирования систем обработки данных

Республики Казахстан

Алматы, 2010

СОДЕРЖАНИЕ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ВЕДЕНИЕ

1. МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ

1.1 Обзор моделей анализа и синтеза модульных систем обработки данных

1.2 Модели и методы решения задач дискретного программирования при проектировании систем обработки данных

Постановка задачи исследования

Выводы по разделу

2. БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ

2.1 Общая постановка блочно-симметричных задач дискретного

программирования

2.2 Декомпозиция прикладных задач и исходных документов систем обработки данных на этапе технического проектирования

2.3 Проектирование модульных блок-схем систем обработки данных

2.4 Частные задачи проектирования модульных блок-схем систем обработки данных

Выводы по разделу 2

3. МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ БЛОЧНО-СИММЕТРИЧНЫХ

ЗАДАЧ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ. МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА СИНТЕЗА МОДУЛЬНЫХ БЛОК-СХЕМ ОБРАБОТКИ ДАННЫХ

3.1 Эффективный алгоритм решения блочно-симметричных задач проектирования модульных блок схем обработки данных

3.2 Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных

3.3 Программное обеспечение двухкритериальной задачи проектирования модульных систем обработки данных

3.3.1 Описание программного обеспечения решения задач проектирования модульной блок-схемы обработки данных

3.3.2 Описание логической структуры разработанной программы предназначеной для решения двухкритериальной задачи проектирования модульной блок-схемы обработки данных

3.3.4 Вызов и загрузка программы

Выводы по разделу 3

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

АИО - алгоритм итеративных отображений

БД – база данных

ВЗУ – внешняя запоминающая устройства

ВТ – вычислительная техника

ВС - вычислительная сеть

ВЦФ -
векторная целевая функция

ГЛС - граф локального сценария диалога

ДС - диалоговых систем

ДП - дискретного программирования

КТС - комплекса технических средств

МА - множествами альтернатив

ЛС - локальных сценариев

ТР – таблиц решений

ПМ - паретовское множество

ПМА - полного множества альтернатив

РБД - распределенных баз данных

РБнД - распределенных банков данных

СУБД – система управления базами данных

СОД – система обработки данных

СОД РВ - системах обработки данных реального времени

ТР - -таблиц решений

ЦЛП - задач целочисленного линейного программирования

ЦП - целочисленного программирования

ЧЦП - частичного целочисленного программирования

ЭВМ – электронно-вычислительная машина

ВВЕДЕНИЕ

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

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

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

Теоретической базой такого подхода является парадигма модульности, типизации и клонирования, а технической основой – современные технологии и системы автоматизированного проектирования СОД.

Принцип модульного построения систем общеизвестен и широко используется в самых различных областях, в том числе при разработке систем управления. Разработка формализованных моделей и методов оптимального синтеза программного и информационного обеспечения модульных систем обработки данных, автоматизация технического проектирования оптимальных по заданным критериям систем обработки данных значительно повышает эффективность и качество создаваемых систем, сокращает сроки разработки и внедрения систем в эксплуатацию на 30 – 50% по сравнению с традиционным индивидуальным проектированием.

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

При использовании современных технологий и методов разработки модульных СОД и автоматизации этой разработки процесс проектирования, по сути дела, заменяется процессам клонирования, т.е. созданием «генетически» подобной системы. При этом создаются функционально и структурно подобные СОД некоторого класса, соответствующие заданной предметной области и адаптированные на конкретный объект управления.

Общее время и затраты на разработку с использованием методов и средств анализа и синтеза модульных и типовых модульных СОД сокращаются в 10 – 100 раз в зависимости от особенностей создаваемых систем.

Проблемы анализа и синтеза модульных и типовых модульных систем весьма многообразны, в полном объеме не решены и в настоящее время интенсивно разрабатываются многими исследователями. Существующие методы синтеза модульных систем можно разделить на два класса. К первому относится методы [3-12], позволяющие по некоторым эвристическим правилам проектировать рациональные модульные системы и оценивать эффективность полученных систем по некоторым качественным показателям, ко второму – методы синтеза оптимальных модульных систем по заданным количественным критериям эффективности.

В рамках методов синтеза второго класса разрабатывается теоретические основы, формализованные модели и прикладные методы анализа и синтеза оптимальных и модульных СОД широкого класса и назначения, начиная с систем пакетной обработки и кончая системами реального времени и типовыми информационными системами общего назначения [13-33].

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

Традиционные технологии проектирования систем ориентированы на последовательную разработку, т.е. вначале проводится изучение и системный анализ организации, для которой создается СОД; формируются требования к автоматизированной системе; осуществляется ее декомпозиция, разрабатывается технический проект системы в целом и отдельных ее подсистем. Затем приступают к рабочему проектированию системы, т.е. разработка программного и информационного обеспечений, проводится отладка программного обеспечения, а также опытная эксплуатация и модификация созданной системы.

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

Одним из полходов проектирования эффективных и качественных систем обработки данных является разработка формализованных моделей и методов оптимального синтеза программного и информационного обеспечения модульных систем обработки данных. Автоматизация технического проектирования оптимальных по заданным критериям систем обработки данных значительно повышает эффективность и качество создаваемых систем, сокращает сроки разработки и внедрения систем в эксплуатацию на 30 – 50% по сравнению с традиционным индивидуальным проектированием.

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

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

Методы исследования.
В процессе постановки и решения задач исследования использованы методы системного анализа, теории графов, теории матриц, дискретного программирования.

Научная новизна результатов исследования
заключается:

- разработан комплекс взаимосвязанных моделей и методов проектирования систем обработки данных, сформулированных, в отличие от известных, как задачи нового класса - блочно-симметричные задачи;

- сформулирована общая блочно-симметричная дискретная задача проектирования систем обработки данных;

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

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

- впервые сформулирована и решена многокритериальная блочно-симметричная задача проектирования модульных блок-схем обработки данных.

- разработан эффективный алгоритм итеративных отображений решения блочно-симметричных задач.

Достоверность полученных результатов.
Научные положения, выводы и рекомендации обоснованы строгими математическими методами, результатами вычислительных экспериментов и внедрены на предприятиях и в организациях.

Практическая ценность.
Разработанные в диссертации комплекс моделей и методов, алгоритмов и программных средств использованы при проектировании систем обработки данных на Усть-Каменогорском свинцово-цинковом комбинате, в комитете по информатизации и связи, а также внедрены в учебный процесс.

Положения, выносимые на защиту.

На защиту выносятся следующие положения:

1. Новый подход и общая постановка блочно-симметричной дискретной задачи проектирования систем обработки данных.

2. Постановка задачи декомпозиции систем обработки данных на кластеры функциональных задач и информационных ресурсов.

3. Постановка задачи синтеза модульных блок-схем обработки данных, а также постановки частных задач проектирования модульных блок-схем.

4. Постановка многокритериальной блочно-симметричной задачи разработки модульной блок-схемы обработки данных.

5. Новые эффективные алгоритмы решения дискретных блочно-симметричных задач проектирования систем обработки данных.

Внедрение результатов диссертационного исследования.
Исследования, выполненные в работе, проводились в соответствии с планом госбюджетных работ кафедры «Вычислительная техника» КазНТУ им. К.И.Сатпаева, г. Алматы, – грантом программы фундаментальных исследований МОН РК: по теме 0100РК00633 - «Разработка и исследование блочно-симметричных моделей и методов проектирования модульных систем обработки» и по теме 0101РК00696 - «Разработка технического задания информационной системы «Введение государственного регистра информационно- телекоммуникационных систем» в части определения функциональных требований, состава сведений и их классификаций необходимые для ведения регистра».

Результаты работы внедрены в процессе проектирвания систем обработки данных в подразделениях Усть-Каменогорского свинцово-цинкового комбината и в Комитете связи и информатизации, а так же использованы при разработке лабораторных работ и лекционных занятий в КазНТУ имени К.И.Сатпаева.

Акты внедрения приведены в приложении.

Апробация работы.
Основные положения и результаты диссертационной работы были доложены и обсуждены на международных конференциях и конференциях Республики Казахстан: научная конференция магистрантов и аспирантов «Наука и творчество молодых: опыт, проблемы, перспективы» (Усть-Каменогорск, 2001г), международная конференция «Вычислительные и информационные технологии в науке, технике и образовании» (Алматы, 2003, часть II, IV), международная научно-практическая конференция «Состояние, проблемы и задачи информатизации в Казахстане» (Алматы, 2004), республиканская научно-практическая конференция «Молодежь и информационные технологии» (Актау, 2009), международная научно-методическая конференция «Актуальные проблемы естественно-научных дисциплин» (Алматы, 2010), а также научных семинарах кафедр «Техническая кибернетика» и «Вычислительная техника».

Публикации.
Научные результаты исследований опубликованы в 12 печатных работах, в том числе в изданиях, рекомендованных для публикации положений диссертации – 4 работы. В научных журналах опубликовано 4 работы, в материалах научных конференций – 8 работ.

Структура и объем диссертации.
Диссертационная работа состоит из введения, трех глав, заключения, списка использованных источников 147 наименований, 13 рисунков, 2 таблиц и двух приложений.

1.
МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ

В данном разделе проведен анализ формализованных моделей и методов проектирования модульных систем обработки данных (МСОД). Рассмотрены задачи предпроектного анализа предметной области, формирования исходных данных для проектирования систем обработки данных. Как правило, поставленные задачи сведены к задачам дискретного программирования, которые сложны и не часто позволяют решать задачи большой размерности. В разделе приведен краткий обзор методов решение задач дискретного программирования (ДП) [146].

На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.

1.1 Обзор моделей анализа и синтеза модульных систем обработки данных

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

В настоящее время разработаны формализованные методы проектирования прикладных программ и базы данных, системы автоматизации их проектирования, системы автоматизации процессов разработки программ.

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

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

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

Поэтому возникает необходимость разработки формализованных моделей и методов проектирования прикладного программного обеспечения и базы данных систем обработки данных. Одним из направлений такого подхода является разработка моделей и методов анализа и синтеза модульных и типовых модульных систем обработки данных.

В рамках этого направления рассмотрим известные подходы анализа и проектирование систем обработки данных.

Для разработки формализованных методов необходимо провести анализ предметной области, для которой разрабатываются системы обработки данных.

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

Уточним некоторые понятия.

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

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

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

Рассмотрим методы анализа систем обработки данных реального времени
(СОД РВ), которые могут быть использованы при анализе систем других классов.

Процедуры обслуживания заявок в системах обработки данных реального времени (СОД РВ) неоднозначно определяются требуемым множеством выходных информационных элементов и детерминированной технологией их получения, а зависят от времени поступлении заявки на обработку, состава и взаимосвязей необходимых для ее обслуживания задач и от текущего состояния информационной базы, определяющего альтернативные возможности обработки данных. Для исследование этих возможностей необходим совместный анализ множество требований, предъявляемых поступающими на обработку заявками, используемых для их обслуживания задач обработки данных, алгоритмов их решения и используемых массивов. Для анализа структур информационных потоков и технологии обработки данных в СОД РВ используется совокупность взаимосвязанных матричных и графовых моделей, обеспечивающих формальный анализ технологий обработки данных как отдельной задачи СОД РВ, так и множества задач в целом [25-30, 33,38]

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

Рассмотрим указанные процедуры анализа более подробно, так как они являются общими для модульных систем обработки данных любого класса.

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

Пусть задано множество задач СОД РВ . Технологии решения каждой задачи соответствует направленный граф , где множество вершин графа, отражающих информационные элементы задачи ; - множество отношений между информационными элементами . Каждому графу соответствует квадратная бинарная матрица смежности размера . Элемент матрицы равен 1, если элементы и графа связаны отношениями , и равен 0 в противном случае.

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

.

Затем определим на множестве декартово произведение . Пара элементов связано с процедурой , если она принадлежит отношению . Совокупность процедур задачи образует множество . Полное множество процедур анализируемого множества задач определяется путем объединения .

Для определения в задаче входных, промежуточных и выходных данных, последовательности их получения и контуров обратной связи, а также анализа взаимосвязей в системе введено понятие матрицы достижимости.

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

Матрица определяется на основе матрицы . При этом они связаны булевым уравнением

Анализ структур обработки данных для каждой задачи СОД и определение необходимой последовательности получение информационных элементов упрощается, если элементы построенной матрицы достижимости упорядочить по уровням (этапом) их обработки. Получение матрицы методом свертки циклов позволяет уменьшить ее размерность, облегчить анализ и синтез структуры решение как отдельных задач системы, так и функционирования всей СОД РВ.

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

Взаимосвязь между процедурами обработки данных при обслуживании каждой заявки СОД РВ, наборами входных и промежуточных данных удобно представлять с помощью таблицы инциденции обработки множеств запросов , которая представляет собой матрицу вида

В матрице каждая строка отображает процедуру обработки, а каждый столбец – использование всеми процедурами при решении задачи рассматриваемого информационного элемента. В строке содержится информация о множестве входных и выходных данных, связанных с анализируемой процедурой. Анализ столбцов позволяет выявить входные и выходные информационные элементы рассматриваемой задачи . Элементы являются входными при решении задачи, если столбец матрицы содержит единственную, отличную от нуля запись . Если -й столбец содержит запись , то соответствующий ему элемент является выходным. Технологической матрицей смежности при решении задачи назовем квадратную бинарную матрицу, проиндексированную по обеим осям множествами . Матрица имеет четыре подматрицы: с размерами .

Нулевые элементы подматрицы соответствует элементам, равным -1 в матрице , а не нулевые элементы подматрицы соответствует элементам, равным +1 в транспонированной матрице . Таким образом, элемент матрицы равен 1, если элемент является входным для процедуры , и элемент равен 1, если элемент является входным при решении задачи. В противном случае элементы в позициях и равны 0. Единичный элемент в позиции , подматрицы соответствует наличию единичных элементов в позиции подматрицы и в позиции подматрицы , , что равносильно существованию информационного элемента , который является входным для процедуры , и выходным для процедуры при решении задачи. Для удобство формального описания будет считать, что главная диагональ подматрицы заполнена единичными записями.

Используя матрицу , можно определить матрицу , которая содержит подматрицы , проиндексированы соответственно: .

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

.

Единичная запись в позиции подматрицы соответствует наличию направленного пути в графе технологии решения задачи от процедуры к процедуре .

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

.

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

В качестве моделей описания и анализа задач обработки данных при создании типовых модульных СОД также используется аналогичная совокупность графовых и матричных моделей. Методика анализа и структуризация исходной для синтеза системы типовых модулей СОД информации базируется на последовательном преобразовании матричных и графовых моделей алгоритмов решения задач обработки данных, содержащих всю необходимую информацию о взаимосвязях и отношениях между различными элементами отдельных задач. При формировании полного структурированного графа технологии решения задачи учитывается наличие в алгоритмах решения задач обработки данных циклических участков и альтернативных вариантов обработки, процедур обновления информационных элементов и процедур принятия решений. Полный структурированный граф и соответствующие ему матрицы смежности и достижимости позволяют описывать алгоритмы решения задач обработки данных в целом и отдельные их части с заданной степенью детализации [31,32,34,39,40]

Рост числа решаемых и диалоге задач в составе модульных СОД их сложности, повышение требований к своевременности, достоверности и полноте представляемой информации обусловливает необходимость дальнейшего усовершенствования методологии проектирования СОД которая должна учитывать не только особенности “человеческого фактора”, но и требование по обеспечению максимальной эффективности использования технического, программного и информационного обеспечения диалоговых систем
(ДС) и их типизации.

На стадии предпроектного анализа ДС необходимо выполнить комплекс работ, основной из которых также является анализ решаемых пользователями задач, технологии их решения, определения требований пользователей к эффективности и качеству решения задач [40]. На этой стадии определяется необходимый набор процедур реализации комплекса диалоговых задач и требуемой для их решения информации.

Для представления результатов изучения и анализа задач пользователей и технологии их решения используется модификации описанных выше формализованных методов представления результатов этого изучения.

Определение процедур обработки данных, анализ и структуризацию каждой диалоговой задачи целесообразно осуществлять с использованием дополнительной совокупности матричных и графовых моделей, обеспечивающих подготовку локальных сценариев (ЛС) диалога и других исходных данных, необходимых для технического проектирования оптимальных ДС [41].

Локальные сценарии диалога строятся на основе описанных пользователями (средствами языка описания задач – ЯОЗ) схем их решения, которые дополняют формами представления результатов проектирования систем. Схема решения каждой задачи представляется в виде совокупности взаимосвязанных таблиц решений (ТР), описывающих последовательность и содержание шагов диалога пользователя с ДС при решении задачи, используемую при этом информацию, а также требования пользователя к характеристикам процесса обработки запросов, выдаваемых на каждом шаге диалога. Совокупность таблиц решений однозначным образом отображается в граф локального сценария диалога (ГЛС). Каждая вершина ГЛС соответствует одной ТР, а направленные дуги – взаимосвязям между таблицами. Каждому ГЛС ставятся в соответствие матрица смежности и матрица достижимости, отражающие структуру и взаимосвязь узлов графа.

При помощи матриц для облегчения последующего анализа локальных сценариев диалога производиться упорядочение ГЛС, в ходе которого узлы графа распределяются по уровням их прохождения и процессе решения задача. При наличии контуров на уровнях ГЛС осущестиляется их свертка, что приводит к сокращению размерности и упрощению матриц смежности и достижимости графа. На основе упорядоченного таким образом ГЛС с помощью языка ГЕРТ сетей могут быть определны такие характеристики ГЛС диалога, как условная вероятность завершения решения задачи в заданном узле графа, обладающей свойством аддитивности на дугах графа.

С учетом результатов анализа требований пользователей и локальных сценариев диалога формируетсся сценарий ДС в целом путем операции «наложения» упорядоченных узлов на каждом уровне. Для формализации, упорядочения и анализа сценария диалога всей системы также используется совокупность взаимосвязанных матричных и графовых моделей и методы оценки ГЕРТ-сетей.

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

Качественные изменения в структуре современных модульных СОД связаны с широким внедрением сетей ЭВМ, систем управления локальными и распределенными базами данных, а также новейших систем передачи данных.

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

Анализ в процессе проектирования распределенных баз данных
(РБД) в модульных системах включает четыре взаимосвязанных этапа предпроектный анализ предметных областей пользователей, анализ предметных областей пользователей и построение внешних моделей, построение обобщенной внешней модели и построение канонической структуры РБД. Результатом анализа предметных областей пользователей является построение канонической структуры РБД, которая отражает наиболее существенные характеристики и устойчивые свойства данных и отношений между ними и является инвариантной по отношению к аппаратным и программным средствам ее реализации [35, 36, 37].

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

Целесообразность применения методов типизации при проектировании РБД определяется уровнем информационной и процедурной общности внешних моделей предметной области пользователей.

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

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

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

В процессе анализа модульных СОД широко используется аппарат сетей Петри
[42]. Задачи анализа систем обработки данных, решаемых при помощи временных сетей Петри с разноцветными маркерами, включают задачи определения возможности и корректности реализацим любой функциональной задачи пользователя или заданного множества таких задач, возможности многократного использования процедур обработки данных выявления тупиковых ситуаций при совместной обработке информационных элементов. С использованием сетей Петри проводитсятакже анализ механизмов защиты в системах обработки данных [42, 43].

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

Рассмотрим методы синтеза модульных систем обработки данных разного назначения.

Информационно-справочные системы.
Синтез модульных СОД на этапе технического проектирования включает оптимальной выбор состава модулей програмного обеспечения и информационных массивов, содержания межмодульного интерфейса, структуры системы обработки данных в целом, формализуемой в виде фунциональной блок-схемы, с учетом заданных технико-экономических характеристик фунционирования разрабатываемой системы.

Для оптимизации процесса проектирования системы мспользуетя критерий минимума сложности межмодульного интерфейса. Оптимизация эксплуатационных характеристик может быть осуществлена в зависимости от конкретных обстоятельств по одному из следующих критеров: минумум времени обмена между оперативной и внешней памятью, снижение технологической сложности алгоритмов обработки данных, что является обобщением показателя «транспортного фактора» при реализации алгоритмов решения функциональных задач, предложенного Лангефорсом. Кроме того, для информационных систем существенным является максимум инфармационной производительности и обеспечение достоверности обработки данных [14-21, 30, 31, 44-60].

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

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

Автоматизированные системы, в которых обеспечивается данное требование, получили название автоматированных систем обработки данных реального времени (СОД РВ).

Рассмотрим методы синтеза оптимальных модульных систем обработки данных реального времени [25-30, 38, 54-66].

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

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

Можно выделить следующие основные задачи модулного построения программного и информационного обеспечения СОД РВ: синтез оптимальных модульных СОД РВ с бесприоритетным обслуживанием заявок в режиме разделения времени на однопроцессорных ЭВМ, синтез систем РВ с приоритетным обслуживанием заявок в ОС реального времени на однопроцессорных ЭВМ, синтез оптимальных модульных СОД РВ на многопроцессорных ЭВМ.

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

При синтезе СОД РВ с приоритетным обслуживанием заявок необходимо учитывать разнообразие входных заявок различных типов, характеризующихся различной интенсивностью поступления, приоритетностью обслуживания [31, 67]. Требования пользователей на время обслуживания заявок значительно жестче по сравнению с задачами бесприорететного обслуживания, что требует размещения в оперативной памяти ряда программных процедур и данных, необходимых для обслуживания отдельных заявок. Взаимосвязи между заявками по составу решаемых задач в таких системах, как правило, весьма существенны. Повышение эффективности решения данных задач осуществляется в основном за счет сокращения числа и времени обмена между уровнями памяти обслуживании заявок [55, 67, 68].

Решение задач синтеза оптимальных СОД РВ с мультипроцессорным обслуживанием предполагает сокращение не только времени обмена между уровнями памяти , но и среднего процессорного времени решения задач за счет параллельной реализации процедур, модулей или заявок в целом [58, 59, 61, 65, 66].

Задачи синтеза модульных СОД РВ этапе технического проектирования включают также оптимальный выбор состава модулей программного обеспечения и информационных массивов, содержания межмодульного интерфейса, структуры СОД РВ в целом, формализуемой в виде функционнальной блок-схемы с учётом заданных технико-экономических характеристик функционирования разрабатываемой системы.

Основным требованием к результатам синтеза системы является максимально высокий уровень обслуживания требований пользователей за счет оптимального использования вычислительных ресурсов.

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

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

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

,

при ограничениях на: время обслуживание -й заявки для заданного алгоритма организации очереди

;

устойчивость режима функционирования системы

;

общее число дублируемых процедур

;

число процедур в составе модуля

;

число информационных элементов в составе массива базы данных

,

дублирование информационных элементов в массивах

;

однородность включения процедур в программные модули

;

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

.

Переменные и обозначения в данной постановке определены следующим образом:

где - булевая матрица взаимосвязей задач и процедур обработки данных, и - матрицы взаимосвязей информационных элементов с процедурами обработки данных соответственно при считывании и записи:

Переменные и определяют взаимосвязи системы разрабатываемых модулей задачи с отдельными информационными элементами и массивами информационной базы соответственно при считывании и записи данных в процессе обмена с внешней памятью ЭВМ, а переменная - взаимосвязи задач с программными модулями.

Среднее время решения -й задачи СОД РВ определяется следующим образом:

,

Где - среднее процессорное время решения задачи; - среднее время поиска и перезаписи -го модуля из внешней памяти в оперативную память; - среднее время считывания -го массива из внешней памяти; - среднее время записи результатов обработки данных в -й массив. Среднее время решения всех задач обработки данных в СОД РВ определяется в соответствии с соотношением

.

Среднее время обслуживания заявки для алгоритма кругового циклического обслуживания с послеприбытием имеет вид

,

где - среднее время нахождения заявок в системе; – квант времени обслуживания заявки; - случайное положительное число, имеющее геометрическое распределение; - интенсивность поступления заявок -го типа; - интенсивность потока заявок.

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

Задачи синтеза решены при ряде технологических и эксплуатационных ограничений, основными из которых являются ограничения на устойчивость режима функционирования системы, на среднее время ожидания заявок на решения задач, сложность интерфейса. Поставленные задачи синтеза модульных СОД РВ сведены к моделям целочисленного нелинейного программирования, для решения которых предложены алгоритмы, основанные на схеме «ветвей и границ».

Диалоговые системы.
Современный уровень развития вычислительной техники и особенно персональных ЭВМ обусловил резкое расширение числа и возможностей диалоговых систем в модульных СОД, а также круга их пользователей.

Разработка эффективных диалоговых систем представляет собой комплексную проблему, включающую в себе анализ и типизацию информационных требований пользователей, синтез типовой модели диалога для заданного множества пользователей, информационные запросы которых принадлежат одной предметной области, синтез информационного и модульного программного обеспечения диалоговых систем (ДС) [130].

При синтезе оптимальных модульных ДС используется следующие системные и технические характеристики: затраты на разработку и внедрение системы в целом и ее подсистемы, время разработки и внедрения, эксплуатационные расходы, потери в системе от несвоевременного представления информации пользователю, конфигурация, качество и загрузка технических средств, используемых при решении задач пользователей, достоверность обрабатываемой информации, информационная производительность системы, надежность программного и технического обеспечения ДС, релевантность выполняемых системой запросов, время реакции ДС при выполнении запросов пользователей по заданным сценариям, время и удобство формирования пользователем запросов, степень приближения к работе в реальном масштабе времени (так режиме формирования запроса так и при реализации интерфейса ДС-БД) [131], объем оперативной памяти для размещения программных модулей и информационных массивов системы, быстродействие, время обращения к периферийному оборудованию, стоимость комплекса технических средств (КТС) и его комплектация с учетом эргономических требований, степень распределенности КТС в случае сетевой его архитектуры [56-57].

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

Наиболее общей задачей синтеза ДС является определение по заданным критериям эффективности сценарии (С), программного обеспечения (Р), информационного обеспечения (I) и комплекса технических средств (Г) диалоговой системы на основе анализа характеристик пользователей (П), решаемых ими задач (Ф) и требований пользователей к основным характеристикам решаемых задач.

К частным задачам синтеза ДС относятся определение оптимального сценария С диалоговой системы на основе локальных сценариев, выбор КТС из множества возможных, синтез Р и I на основе информации о сценарии С и характеристиках выбранного КТС.

Критерии эффективности при синтезе ДС целесообразно разбить на несколько уровней: ДС в целом, процесс диалога, обеспечивающие подсистемы ДС (программное, информационное и техническое обеспечение ДС),

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

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

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

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

При выборе технического обеспечения ДС целесообразно использовать в основном экономические показатели.

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

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

Поставлены и решены задачи синтеза программных модулей ДС при заданных сценариях диалога, известной структуре и характеристиках информационного обеспечения системы с учетом временных характеристик обслуживания запросов пользователей. Диалоговые системы при этом предложено моделировать в виде стохастической замкнутой сети системы массового обслуживания (СМО), что позволяет исследовать эффективность модульных ДС, реализуемых на базе вычислительных систем. Показатели эффективности ДС и ее компонент определяется как показатели эффективности отдельных СМО и сети в целом.

Решены также задачи синтеза оптимальной модульной структуры программного обеспечения ДС при условии, что запросы пользователей обслуживаются в соответствии с различными (бесприоритетными и приоритетными) дисциплинами обслуживания.

Функционирование ДС при этом моделируется в виде СМО с простейшими входящими потоками заявок и произвольными потокам обслуживания. Определены аналитически зависимости показателей эффективности рассматриваемой системы и зависимости от длительности обслуживания заявок каждого типа и интенсивности их поступления, а так же необходимые условия существования установившегося режима в ДС.

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

Задачи синтеза струтуры праграммного обеспечения ДС сведены к задачам нелинейного целочисленного программирование, для решения каторых используются метод «ветвей и границ» и другие методи [72].

Типизация разработки. Под тепизацией при разработке СОД понимается процесс анализа требований и харектеристик заданного множества обьектов автоматизации и выбора методов сведения многообразия индивидуальных проектных решений к огрониченному множеству решений, достаточно эффективно выполняющих требования объектов автоматизаций [31, 73, 74].

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

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

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

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

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

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

При синтезе типовых модульных СОД могут быть использованы общесистемные, минимаксные и сложные критерии проектирования теории активных систем. Первые экстремизируют суммарные показатели качества синтеза для множества пользователей или задач обработки данных, вторые-показатели гарантированного качества синтеза для пользователей обработки данных.Критерии третьего типа используются для выбора типовых проектных решений в случаях несовпадения целевых функций или точек экстремума центра и элементов системы. К числу общесистемных критериев относятся: минимум приведенной стоимости разработки отладки и эксплуатации проектируемой типовой модульной СОД, минимум общего времени разработки и отладки типовой модульной системы, минимум среднего значения межмодульного интерфейса, максимум среднего по множеству показателей информационной производительности проектируемой системы, максимум среднего коэффициента загрузки технических средств. Конкретный выбор степени централизации механизма проектирования, критерия эффективности и согласованной системы ограничений, определяющих постановку задачи синтеза типовых модульных СОД, базируется на использовании результатов анализа технологий решения множества задач обработки данных.

Задачи синтеза типовых модульных СОД сведены к задачам нелинейного и линейного целочисленного программирования и решаются с использованием известных стандартных пакетов и специальных методов, основанных на схеме «ветвей и границ».

Синтез структур баз данных.
Создание модульных СОД нового поколения тесно связано с широким внедрением сетей ЭВМ, локальных и распределенных баз данных (РБД) и систем передачи информации [75-81].

Синтез логической структуры РБД рассматривается как процесс поиска оптимального варианта отображения канонической структуры РБД в логическую, которая обеспечивает оптимальную значение заданного критерия эффективности функционирования РБД и удовлетворяет основным требованиям и ограничениям, накладываемым на логическую структуру на этапе разработки технического задания. Для отображения канонической структуры в логическую используются метод объединения групп канонической структуры РБД в типы логических записей с одновременным распределением их по узлам вычислительной сети.

Исходной информацией для этапа синтеза оптимальных компонент логического уровня представления информации в РБД являются характеристики канонической структуры, полученные на этапе анализа и нормализации внешних моделей предметных областей пользователей.

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

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

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

В процесс проектирования РБД выделяются следующие взаимосвязанные этапы: синтез оптимальных логической структуры РБД, проектирование структуры сетевого каталога и проектирование логических структур локальных баз данных (БД). Синтезируемые оптимальная по заданному критерию эффективности логическая структура РБД, сетевой каталог и логические структуры локальных БД должны обеспечивать сохранение семантических свойств информационных элементов и связей между ними, зафиксированных в канонической структуре РБД с учетом ограничений, накладываемых параметрами локальных СУБД и аппаратных средств передачи данных, топологией ВС и требованиями различных режимов функционирования распределенных банков данных (РБнД).

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

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

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

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

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

Логическая структура сетевого каталога фиксирована, так как количество уровней иерархии соответствующее количеству уровней отображения информации в РБнД и другие параметры логической организации являются детерминированными и не зависят от специфики предметных областей пользователей. Поэтому основной задачей проектирования сетевого каталога является выбор типа его структуры который определяет наличие и характер взаимодействия между главными и локальными каталогами в процесс реализации функции управления выполнением процедур обработки информации в РБнД

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

Поставлены и решены задачи синтеза оптимальных по заданным критериям эффективности логических и физических структур локальных баз данных. При проектировании оптимальных логических структур локальных баз данных возможны два подхода, каждый из которых детально исследован [69, 76, 79, 80].

Первый подход основывается на синтезе логических структур локальных баз данных, эффективность которых определяется единым критерием оптимальности функционирования РБД. Исходной информацией, используемой в этом случае при проектировании логических структур локальных БД являются характеристики логической структуры РБД и сетевого каталога. Проектирование осуществляется путем нормализации графа логической структуры отдельного узла ВС, формируемого в результате синтеза оптимальной логической структуры РБД и определения в графе несвязных и слабо связных подграфов, являющихся основой логических структур локальных БД, поддерживаемых конкретными СУБД.

Результатом данного этапа являются оптимальные логические структуры локальных БД спроектированные с учетом характеристик оптимальной логической структуры РБД, ограничений конкретных СУБД и операционной среды.

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

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

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

Основными критериями эффективности, используемыми при синтезе логической структуры локальной БД, являются минимум суммарного времени ввода информации и обслуживания заданного множества запросов, минимум суммарного числа связей между записями, минимум суммарной длины путей доступа к искомым информационным элементом, а также критерии, коррелируемые с достоверностью информации в локальной БД.

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

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

Синтез логической структуры локальной БД обеспечивает оптимальное распределение массивов по типам памяти и экземпляров логических записей по страницам памяти , выбор оптимальных методов организации записей и связей по страницам памяти, выбор оптимальных методов организации записей и связей пределах каждого массива или станицы памяти.

Разработанные методы, модели, алгоритмы и комплексы программ нашли широкое практическое использование при проектировании модульных СОД различного класса и назначения.

С использованием полученных результатов сформулированы принципы построения и рассмотрены основные элементы, структура и алгоритмическое обеспечение автоматизированной системы проектирования оптимальных модульных СОД, а также имитационные модели для анализа технологии обработки информации на системном уровне. На этой основе разработаны системы автоматизированного проектирования СОД семейства “Модуль”.

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

1.2 Модели и методы решения задач дискретного программирования при проектировании систем обработки данных

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

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

Большое число вышеуказанных прикладных задач, как правило, сводится к задачам дискретного программирования, постановка и решение которых в свою очередь взывают значительных сложности. Прежде всего имеется в виду вычислительная сложность (NP-полные задачи), размерность решаемых прикладных задач, точность и эффективность разработанных алгоритмов для практических приложений.

Как показал анализ проектирования модульных системы обработки данных в подавляющем большинстве задач анализа и синтеза СОД сводится к задачам дискретного программирования.

Приведем краткий обзор моделей и методов задач дискретного программирования (ДП), используемых в процессе проектирования систем обработки данных.

Определим задачу дискретного программирования следующим образом. [83]

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

, (1.2.1)

где - -мерный вектор; - скалярный функция; -некоторое множество в , .

Если - конечное (или счетное) множество или декартово произведение конечного (счетного) множества на множество мощности континиума, то будет иметь место задача ДП. В этом случае условие принадлежности некоторому множеству может быть записано в виде:

, ;

, ; ; . (1.2.2)

При - задача частично дискретного программирования.

Если - множество всех целочисленных векторов, то при - имеем задачу целочисленного программирования (ЦП). А при - задачу частичного целочисленного программирования (ЧЦП).

В наибольшей степени изучены методы решения задач целочисленного линейного программирования (ЦЛП):

;(1.2.3)

Здесь - множество всех неотрицательных целых чисел, частный случай задач ЦЛП задачи с булевыми переменными, где в (1.2.3):

, ;

В ряде задач ЦП требование целочисленности накладывается и на целевую функцию.

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

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

Обычно эффективное решение задачи тесно связанно с математической моделью задачи, со структурой модели и ее особенностями.

Рассмотрим некоторые математические модели дискретного программирования и методы их решения.

Модели задач ДП
. Классическим примером моделей этого класса являются модели целочисленного линейного программирования, в которых переменными являются неделимые величины. Модели этого класса в свою очередь генерировали различные варианты постановки прикладных задач и определены как модели с неделимостями.

В процессе развития теории дискретного программирования выделился класс комбинаторных моделей. [83]

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

Одним из типичных примеров комбинаторной модели является задача о коммивояжере. [84]

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

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

Постановка различных комбинаторных задач может часто формулироваться в виде модели с булевыми переменными, которые принимают только два значения 0 или 1.

К булевым моделям сводятся большое число прикладных задач, что свидетельствует о перспективности моделей этого класса. [85]

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

где

Эти модели образуют класс моделей с неоднородной разрывной целевой функцией.

Модели нахождения экстремума на области, задаваемой не только линейными неравенствам (ограничениями) но и логическими условиями. Такие области оказываются невыпуклыми либо несвязными. Эти задачи образуют модели на не классических областях. [84]

Особый интерес исследователей вызывают многоэкстремальные модели, в которых необходимо определить оптимальные значения более одной целевой функции при наличии (либо отсутствии) систем ограничений. Как правило, модели этого класса сложны в вычислительном отношении. Вместе с тем, постановки целого ряда прикладных задач сводятся к моделям данного класса. Решение указанных задач является актуальным. [103, 105, 107]

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

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

Методы решения задач дискретного программирования
(ДП). В задачах ДП методы их решения зачастую связаны с их математической постановкой и особенностями. Имеется большое число методов для решения этих задач. В этой связи целесообразно выделить следующие методы решения задач ДП: точные и приближенные. Среди точных методов наиболее распространены комбинаторные методы и методы отсечения.

Типичным примером комбинаторных методов является метод ветвей и границ [115]. Суть данного метода заключается в направленном переборе допустимых решений на основе вычисления оценок. Основное этапы подхода заключается в следующем:

1. Исходное множество решений разбиваются не подмножества (процесс ветвления);

2. Для каждого из подмножеств вычисляется значения оценок (нижние или верхние границы);

3. На основе выбранного значения оценок вычисляются допустимые решения;

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

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

Примерами успешной реализации методов отсечения являются алгоритмы Гомори [83] .

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

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

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

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

В ряде случаев при проектировании систем обработки данных необходимо учитывать вектор критериев, которые могут противоречить друг другу. Такие постановки задач сводятся к многокритериальным задачам дискретного программирования.

Математическая постановка – критериальной задачи предпологает, что задано множество допустимых решений , на котором определена векторная целевая функция (ВЦФ) [98,99].

,(1.2.4)

Причем критерии ВЦФ считаем минимизируемыми:

Fv
(
x
)→
min
,
v
=1,2,…,
N
.
(1.2.5)

Элемент называется Парето-оптимальным, если не существует такого допустимого решения , что выполняются неравенства , v=1, 2,…, N, среди которых хотя бы одно является строгим.

Через обозначаем паретовское множество (ПМ), состоящее из всех Парето-оптимальных элементов рассматриваемой задачи с ВЦФ (1) на множестве . Эта задача называется дискретной
, если мощность множества ее допустимых решений конечна.

Первоначальная формулировка проблемы многокритериальной (векторной) оптимизации восходит к [98, 99] и состоит в нахождении одного или всех элементов ПМ . Заметим, что в однокритериальном случае () ПМ представляет собой множество всех оптимумов данной оптимизационной задачи. Для последней, однако, более естественной является проблема нахождения какого-либо («первого попавшегося») оптимума. Как обобщение этой проблемы для многокритериального случая в настоящей работе в качестве основной рассматриваем проблему нахождения полного множества альтернатив (ПМА). Подмножество назовем ПМА, если оно удовлетворяет двум условиям: его мощность минимально и выполняется , где , где

.

Множество и будем называть множествами альтернатив (МА). В литературе наряду с МА изучается и другие подмножество паретовского множества.

В системном моделировании, в частности, в теорий выбора и принятия решений наиболее распространенными способами нахождения МА являются следующие.

1. Построение (определение) детерминированного формального механизма, позволяющего генерировать альтернативы с помощью параметров алгоритма или с помощью параметров формулы . [100-103]

2. Представление МА в неявном виде с помощью системы соотношений (ограничений ). [104-105]

3. Перечисление всех элементов МА, т.е. представление каждого элемента МА в явном виде. [108, 109]

В работе [121], именно в контексте алгоритмической проблемы, относящейся к последнему из указанных выше трех способов, осуществляется обоснование оценок мощности МА для таких многокритериальных дискретных задач, как задачи о совершенных паросочетаниях, о коммивояжере, о цепях между парой вершин и другие при этом нахождение МА понимается как перечисления с предъявлением всех его элементов [110, 100]. При определенных условиях нижние оценки мощности ПМ и ПМА перечисленных задач оказывается экспоненциальным. Последнее означает, что для рассматриваемых задач проблема нахождения МА является труднорешаемой [110,111]. Или (в терминологии [112,113]) она имеет экспоненциальную вычислительную сложность.

Следуя, [112], рассматриваемую - критериальную задачу назовем индивидуальной, если все ее параметры имеют фиксированные значения. Говорим о массовой - критериальной задаче или, коротко, о задаче, если для некоторых параметров заданы не фиксированные значения, а диапазоны их изменения.

Анализируя приложения той или другой задачи, нетрудно убедиться, что состав критериев ВЦФ обычно меняется. Например, в системах автоматизированного проектирования электронной техники [114-118] возникает многокритериальные задачи на графах, в которых остовное дерево (связывающая сеть) может оценивается такими критериями, как вес, «узкое место» (минимаксный критерий), степень, диаметр и т.д. [119,120]. При этом по мере необходимости эти критерии входят в состав ВЦФ в разнообразных комбинациях, порождая различные варианты задач об остовных деревьях. Общим у этих задач является лишь множество допустимых решений , каждый элемент которого является связным остовным подграфом данного графа.

Используя понятие «задача» как переменное, употребляем для ее обозначения символ [120]. Конкретизируя рассматриваемую задачу, т.е. определяя для нее множество допустимых решений , присваиваем ей общепринятое наименование и собственное, отличающее её от других задач, обозначение .

Перечислим рассматриваемые здесь дискретные многокритериальные задачи:

1. - задача о совершенных паросочетаниях, в которой - совершенное паросочетание графа с четным числом вершин ;

2. - задача об остовных деревьях, - остовное дерево связного -вершинного графа;

3. - задача о цепях, - простая цепь между выделенной парой вершин графа ;

4. - задача о коммивояжере, - гамильтонов цикл в -вершинном графе;

5. - задача о покрытии -вершинного графа цепями, - остовной подграф, компо

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

6. - задача о назначениях, т.е. задача о совершенных паросочетаниях на двудольном графе , , - совершенное паросочетание на .

Таким образом, решение многокритериальных задач ДП весьма сложно в вычислительном отношении, о чем свидетельствует результаты исследований.

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

1.3 Постановка задачи исследования

Проектирование систем обработки данных многоэтапный и длительный процесс в зависимости от сложности проектируемой информационной системы.

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

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

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

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

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

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

Необходимо обосновать и выбрать критерии оптимизации в процессе формализованного проектирования систем обработки данных.

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

Одним из новых направлении постановки и решения задач эффективного проектирования СОД являются блочно-симметричные модели и методы, которые позволяют решать задачи большой размерности. Разработка и развитие этих методов является весьма актуальной проблемой.

В процессе проектирования СОД возникает необходимость учета вектора критериев оптимизации, которые часто бывают противоречивым.

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

Анализ существующих методов проектирования модульных систем обработки данных (МСОД), алгоритмов реализации этих моделей и проведенные исследования показали необходимость разработки новых подходов и классов моделей и методов проектирования систем обработки данных.

На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.

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

-разработать общую блочно-симметричную модель проектирования систем обработки данных;

- сформулировать и решить задачу декомпозиции систем обработки данных на кластеры функциональных задач и исходных документов;

- разработать методы синтеза модульных блок-схем обработки данных;

- разработать многокритериальные блочно-симметричные модели и методы проектирования модульных блок-схем обработки данных;

- разработать подход, эффективные методы и алгоритмы решения блочно-симметричных задач и программное обеспечение.

Выводы к разделу 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), которое представляет собой произведение матриц переменных и и заданной матрицы , на которой определена целевая функция. В отличие от традиционных постановок задач дискретного программирования в данной постановке имеются два типа переменных и , переменные и симметричны относительно заданной матрицы .

В задаче (2.1.1) -(2.1.3) можно выделить множество ограничений вида (2.1.2), которые зависят от переменной , и множество ограничений вида (2.1.3), которые зависят от переменной .

Функционал вида можно представить следующим образом:

(2.1.5)

(2.1.6)

(2.1.7)

(2.1.8)

(2.1.9)

В постановке задачи (2.1.5) - (2.1.9) выделим блок функции (2.1.6), (2.1.7), зависящий только от переменной , и блок функций (2.1.8), (2.1.9), зависящий только от переменной , объединенных единым функционалом вида (2.1.5). Заметим, что в ряде постановок задач может быть блок ограничений вида

(2.1.10)

зависящий от переменных и .

В этом случае можно выделить блок функционала цели вида (2.1.5), (2.1.10).

Отсюда следует.

Определение 2.1.
Блочно-симметричной задачей дискретного программирования назовем задачу вида (2.1.5) - (2.1.9), где переменные и и значения функций , , - целые, либо булевые

Рассмотрим выражение (2.1.4). из него следует что переменные и симметричны относительно заданной матрицы и функция (2.1.4) может быть определена как слева направо, так и наоборот, т.е.

(2.1.11)

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

Свойство 1.
В блочно-симметричной задаче имеется два типа переменных и различного содержания, определенных как целочисленные (булевы) матрицы на заданной матрице .

В общем случае переменных может быть и больше в зависимости от постановок задач.

Свойство 2.
Блочность задачи заключается в выделении в постановке отдельных блоков функций вида (2.1.5), (2.1.10); (2.1.6), (2.1.7) и (2.1.8), (2.1.9), которые соответственно зависят от переменных и .

Как видно из указанных соотношении каждый из блоков имеет свою целевую функцию и координируется общим функционалом вида (2.1.5).

Свойство 3.
Блочно-симметричную задачу в большинстве случаев можно представить в матричной форме вида (2.1.11).

Матричная форма постановки блочно-симметричных задач позволяет использовать аппарат теории матриц и разрабатывать эффективные алгоритмы решения задач этого класса.

Свойство 4.
Симметричность задачи заключается в возможности вычисления (2.1.11) как слева направо, так и обратном направлении.

Указанные свойства и особенности блочно-симметричных задач ДП позволяют синтезировать алгоритмы, обеспечивающих решение практических задач большой размерности.

В ряде постановок задач функционал (2.1.1) можно представить в виде вектора функций . В этом случае формулируется многокритериальная блочно-симметричная задача дискретного программирования.

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

Утверждение.
Распределение элементов множества по непересекающим подмножествам соответствует логическому сложению строк матриц , а распределение элементов множества по непересекающимся подмножествам - логическому сложению столбцов матрицы . [132, 133] Результаты данного утверждения позволяют просто вычислить оценки и направления поиска решения для разработки эффективных алгоритмов.

Введем понятие базиса решения задач. Под базисом понимается заранее заданный состав элементов подмножеств и .

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

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

1. В булевой матрице выделим подматрицу , , и определим её как базис решения задачи.

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

3. В соответствии с полученными оценками осуществим распределение элементов множества по множествам . В результате зафиксируем решение и промежуточную. Матрицу , , .

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

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

6. Следует отметить, что поиск решения задачи может осуществляться как в прямом направлении по схеме , так и в обратном направлении по схеме .

При заданном базисе решение данного класса задач имеет полиноминальную вычислительную сложность.

2.2 Декомпозиция прикладных задач и исходных документов систем
о
бработки данных на этапе технического проектирования

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

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

Рассмотрим постановку задачи декомпозиции сложных систем обработки данных на этапе технического проектирования.

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

При большом числе прикладных задач и сложном документообороте возникает необходимость декомпозиции системы на кластеры.

Под кластером прикладных задач
понимается объединение задач в подмножества, а кластерами документов объединение документов в подмножества и установление взаимосвязей между соответствующими подмножествами. Таким образом, разрабатываемая система может быть представлена в виде двудольного графа, вершинами верхнего уровня которого являются функциональные задачи, а вершинами нижнего уровня – документы используемые при реализации задач. Дуги двудольного графа отражают взаимосвязи между задачами и документами в процессе решения задач. Результатом декомпозиции системы является также двудольный граф, вершинами верхнего уровня которого являются кластеры функциональных задач, вершинами нижнего уровня кластеры исходных документов. Взаимосвязи между ними отражают интегрированные связимежду кластерами (рис 2.2.1). Опыт проектирования систем обработки данных и проведенные исследования показали, необходимость декомпозиции исходной системы, которая позволяет на этапе технического проектирования глубже проанализировать кластеры задач и документов, распараллелить объемы работ между проектировщиками, выделить процедуры обработки данных и информационные элементы для разработки прикладного программного обеспечения и базы данных СОД.

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

Аналогично введём переменную

, , ,
где

В ряде случаев на данном этапе определяются характеристики задач и документов.

Введем - время разработки -ой задачи, - объем -ого документа, - общая стоимость разработки -ой задачи и -го документа, - время разработки и подготовки -го документа, -стоимость разработки -ой задачи, - стоимость подготовки -го документа.

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

Необходимо разбить систему на подмножества прикладных задач и используемых ими документов таким образом, чтобы минимизировать взаимосвязи между кластерами прикладных задач и документов в процессе проектирования СОД (рис 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 Частные задачи проектирования модульных блок-схем систем обработки данных

Многоэтапный процесс разработки базы данных, который включает последовательное создание её концептуальной, логической и физической модели с последующей эксплуатацией с использованием возможностей выбранной системы управления базой данных (СУБД). При этом наиболее трудоемким этапом является проектирование концептуальной и логической модели данных в процессе которого необходимо провести анализ предметной области, определить сущности (объекты) и их взаимосвязи, выделить ключевые элементы и т.д.

Работы по проектированию базы данных на этом этапе слабо формализованы и в большой мере основаны на опыте и интуиции разработчиков.

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

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

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

Аналогичные случаи возникает при заданном множестве запросов в СОД, которые испльзуют сформулированную базу данных, а при появлении новых запросов необходимо скорректировать базу данных.

Задача разработки логической структуры базы данных при заданном множестве программных модулей (запросов) формулируется следующим образом [124-131].

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

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

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

Для постановки задачи введем следующие переменные и обозначение:

Тогда, задача примет вид:

.(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.

2. Вычислить величины и составить матрицу . Зафиксировать состояние матрицы . Переход к 3.

3. -я итерация.

3.1. В матрице найти - й минимальный элемент . При наличии нескольких минимальных элементов, среди них выберем такой элемент, для которого значение суммы элементов по строке максимально. Таким образом, выбирая минимальный элемент, избавляемся от большого число связей. Если элементов такого свойства несколько, то среди этих минимальных элементов выберем элемент расположенный первым от начало отсчета строк. Переход к 3.2.

3.2. Определить элементы матрицы . Проверить ограничения на число процедур в составе каждого модуля. Если оно неудовлетворительно, то перейти к 3.3, иначе к 3.1.

3.3. Исключить из рассмотрения элемент . Установить . Переход к 3.1.

3.4. Вычислить состояние матрицы . Переход к 3.5.

3.5. Исключить из рассмотрения строку с номером . Пересчитать величины относительно столбца с учетом нового состояния . Переход к 3.6.

3.6. Проверить условие: все ли процедуры распределены? Если нет, то перейти к следующей итерации, приняв . Иначе переход к 4

4. Запомнить содержание матриц и . Переход к 5.

5. Вычислить относительно и составить матрицу . Переход к 6.

6. -я итерация.

6.1. В матрице найти -й минимальный элемент. При наличии нескольких минимальных элементов, среди них выберем такой элемент, для которого значение суммы по строкам минимально. Если элементов такого свойства несколько, то среди этих минимальных элементов выберем элемент расположенный первым от начало отсчета строк. Переход к 6.2.

6.2. Определить элементы матрицы . Проверить ограничения на число информационных элементов в логическом массиве. Если оно неудовлетворительно, то перейти к 6.3.

6.3. Исключить из рассмотрения элемент . Установить . Переход к 6.1.

6.4. Вычислить состояние матрицы . Переход к 6.5.

6.5. Исключить из рассмотрения строку с номером . Пересчитать величины относительно столбца с учетом нового состояния . Переход к 6.6.

6.6. Проверить условие: все ли информационные элементы распределены? Если нет, то перейти к следующей итерации, приняв . Иначе переход к 7.

7. Вывод решения задачи: матриц , , и значение целевой функции .

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

Необходимые количество шагов в процессе решения задачи с использованием алгоритма итеративных отображений равно

,(3.1.3)

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

.(3.1.4)

Сравнение соотношений (3.1.1), (3.1.2) показывает эффективность и полиномиальную сложность разработанных алгоритмов для решения поставленных задач большой размерности, в отличие от метода «ветвей и границ».

Блок-схема алгоритма итеративных отображений приведена на рис. 3.1.1.

Рассмотрим численный пример решения задачи. Необходимо синтезировать блок-схему модульной СОД, минимизирующую общее число обращений к логическим массивом базы данных.

Задача решается при следующих условиях: допустимое число процедур в составе модуля 3, допустимое число информационных элементов в составе логических массивов 4. Число модулей и логических массивов определяется по формулам: и , с округлением в большую строку.

В таблице 3.1.1 представлена исходная матрица с выделенным базисом в верхнем левом углу исходной матрицы. В базис вошли 1, 2, 3, 4, 5 и строки 1, 2, 3 матрицы . На рисунке 3.1.2 показан процесс формирования решения с использованием разработанного алгоритма. Матрица определена с использованием соотношения (3.1.1).

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

На рисунке 3.1.2 показан процесс формирования решения . Матрица определена с использованием соотношения (3.1.2) и матрицы . Процесс отображения представлен таблицей, в которой приведены номер итерации , минимальный элемент из в соответствии с которым номер информационного элемента отображается в номер файла . На рисунке 3.1.2 представлена матрица , которая сформирована до поиска оптимального решения и определена базисом, а также матрица, полученная в результате формирования решения . А также представлены матрица решения задачи , полученная с использоваием алгоритма итеративных отображений, и матрица , полученная в результате отображения. Матрица соответствует матрице целевой функции , отражающей взаимосвязи программных модулей и логических масивов базы данных модульной блок-схемы. Оптимальное значение целевой функции, полученное при этом базисе и ограничеиях, равно ==6.

С использованием алгоритма итеративных отображений решаются и частные задачи вида (2.4.1)-(2.4.4) и (2.4.5)-(2.4.8) как части блочно-симметричных задач.

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.

15. Кульба В.В., Мамиконов А.Г. Синтез оптимальных модульных СОД.М.:Наука, 1986

16.Мамиконов А.Г., Ашимов А.А., Кульба В.В. Оптимальные модульные системы обработки данных. Алма-ата: Наука, 1981.

17.Кульба В.В., Мамиконов А.Г. Задачи модульного построения ИСС // Тез. Докл.и Сообщений на Всесоюзной конференции по измерительным информационным системам (ИСС-77). Баку: АзиНЕФТЕХИМ,1977. С.10-11.

18.Кульба В.В., Мамиконов А.Г., Косяченко С.А., КуКазиев Г.З. Задачи формализации и автоматизации модульного роектирования систем обработки данных. М.: Ин-т проблем управления, 1978. Вып. 16. С. 5-18.

19.Мамиконов А.Г., Амишов А.А., Кульба В.В. и др. Синтез информационного обеспечения модульных систем обработки // Тр. 5-го Всесоюз. Совещания-семинара по управлению большими системами. Алма-ата: КазПТИ, 1978. С. 8-13.

20.Мамиконов А.Г., Амишов А.А., Кульба В.В. и др. Синтез информационного обеспечения модульных систем обработки // Тр. 5-го Всесоюз. Совещания-семинара по управлению большими системами. Алма-ата: КазПТИ, 1978. С.17-20.

21.Мамиконов А.Г., Амишов А.А., Кульба В.В. и др. Синтез оптимльных функциональных модулей обработки данных в АСУ. Препринт. М.: Ин-т проблем управления, 1979.

22.Алексеев О.Г., Бабаев А.А., Володость И.Ф. Комбинированный метод выбора модулей при разработке программ по критерию быстродействия // Программирование. 1978. № 3. С. 18-28.

23.Мамиконо А.Г., Ашимов А.А, Кульба В.В. и др. Автоматизация проектирования оптимальных модульных систем обработка данных // Методы анализа и синтеза автоматизированных систем управления. М.: Ин-т проблем управления, 1981. Вып. 25. С. 5-15.

24.Мамиконо А.Г., Ашимов А.А, Кульба В.В. и др. Модели и методы автоматизации проектирования модульных систем обработка данных // Автоматизация проектирования систем управления. М.: Финансы и статистика, 1981. С. 23-31.

25.Кротюк Ю.М., Федюшенко И.В. Вероятностные модели синтеза программного обеспечения модульных систем обработка данных РВ // Система программного обеспечения АСУ. Минск: ЦНИИТУ, 1976. Вып 4(38). С. 124-133.

26.Кротюк Ю.М. Формализованные модели и методы синтеза информационного и программного обеспечения модульных СОД РВ // Тез. Докл. Научно-технической конференции « Комплексная автоматизация и механизация-основа повышения эффективности производства и качества работы предприятий радиоэлектроники, связи и телевидения». Минск: БелНИИТИ, 1980. С. 19-20

27.28. Кротюк Ю.М. Формализация модели оптимальной декомпозиции и информационного обеспечения модульных СОД РВ // Автоматизация процессов проектирования. Минск: Ин-т технической кибернетики АН БССР, 1980. Вып. 3. С. 89-92.

28.Кошелев В.А. Некоторые задачи синтеза оптимальных модульных СОД РВ // Теоретические и прикладные задачи оптимизации. М.: Наука, 1985. С. 125-131.

29.Кротюк Ю.М., Кошелев В.А. Синтез оптимальных модульных СОД РВ с относительными приоритетами // Вопросы кибернетика. Автоматизация проектирования систем обработки данных. М.: Научный совет комплексной проблеме «Кибернетика», 1985. С. 45-55.

30.Кульба В.В., Кротюк Ю.М., Косяченко С.А. Задачи синтеза оптимальных модульных СОД РВ // Совершенствование технологии создания математического и программного обеспечения АСУ . Минск: ЦНИиПТИ организации и техники управления, 1982. С. 110-121.

31.Мамиконов А.Г., Кульба В.В., Косяченко С.А. и др. Типизация разработки модульных систем обработки данных. М.: Наука, 1989.

32.Мамиконов А.Г., Кульба В.В., Косяченко С.А. и др. Предпроектный анализ структуры информационных потоков и технологии обработки данных при разработке модульных СОД. Препринт. М.: Ин-т проблем управления, 1980.

33.Ефремова В.С., Кошелева В.А. Основные этапы анализа систем обработки данных реального масштаба времени // Всесоюзный семинар по методам синтеза типовых модульных СОД (Звенигород, 1985). Тез. Докл.и сообщений. М.: Ин-т проблем управления, 1985. С. 50.

34.Косяченко С.А., Сидоров Е.Н. Выделение типовых задач обработки данных на этапе предпроектного анализа // Всесоюзная конференция по автоматизации проектирования систем управления. Тез. Докл. М.: ВИНИТИ, 1984. С. 37.

35.Мамиконова А.Г., Кульба В.В., Ашимов А.А. и др. Анализ информационных потоков и построене канонической структуры базы данных (методические материалы и методика). Алма-Ата: КАЗНИИНТИ, 1984.

36.Мамиконова А.Г., Кульба В.В., Косяченко С.А., Ужастов И.А. Анализ предметных облстей пользователей и построение канонической структуры распределенных баз данных. Препринт. М.: Ин-т проблем управления, 1985.

37.Мамиконов А.Г., Кульба В.В., Лутровский Ю.П. Анализ предметной области банков данных и построение оптимальных структур баз данных с учетом требований к дотоверности информации. Препринт.М.: Ин-т проблем управления, 1988.

38.Белов Ю.В., Проценко В.С., Федоров В.В., Хижняк А.А. Индустриальные средства проектирования и оценки эффективности программных систем, работающих в реальном времени // Вычисл. системы и вопр. Принятия решений. М.,1991. С. 79-100.

39.Кесс Ю.Ю., Ревеко В.М. Типовые модули АСУП. М.: Энергия, 1977.

40.Мамиконов А.Г., Кульба В.В., Косяченко С.А. и др. Анализ диалоговых систем (модели и методы). Препринт. М.: Ин-т проблем управления.1986.

41.Калугин С.Э., Сомов С.К. Упорядочивание сценариев диалога пользователей с диалоговой системой // Разработка оптимальных модульных систем обработки данных. М.: Ин-т проблем управления, 1987.С. 24-28.

42.Мамиконов А.Г., Кульба В.В., Китапбаев Ш.Б., Швецов А.Р. Использование сетей Петри с разноцветными маркерами для анализа эффективности механизмов защиты данных в базах данных. Препринт. М.: Ин-т проблем управления, 1987.

43.Кульба В.В., Миронов Д.А., Соколова Е.Б. Отладка систем защиты с использованием сетей Петри. Препринт. М.: Ин-т проблем управления, 1990.

44.Мамиконов А.Г., Ккульба В.В., Ашимов А.А. Смнтез оптимальных модульных систем обработки данных // Вопросы кибернетики. Автоматизация проектирования систем обработки данных. М.: Научный совет по комплексной проблеме «Кибернетика». 1985. С.4-17.

45.Clemens M., Kaiser K.M., Mathony H.J. Integration der Module fur den Logiken twurf // Fortschr. Ber. VDJ. R.J. 1987.№ 65.S. 99-105.

46.Shafer Hartmut, Meller Klans. Inkrementelle Erweiterung von objektenein Ansatr rur Softwareintegration // Wiss. Z. Techn. Univ. Karl-Marx-Stadt. Chemitz. 1991. V. 33. № 5. S. 675-685.

47.Floyd Muchael. The evolution of component-based programming // Dr. Dobb’s J. 1991.V. 16. № 1. P. 96S, 96V.

48.Горбунов М.М. Изменяемые программы и однородные модули. Препринт № 202. М.: Ин-т прикладной математики. 1986.

49.Vulinovich Denis. The state transition table // Autom. And Contr. 1986. V. 17. № 5 P. 16-19.

50.Кулагин В.П. Анализ и синтез сложных структур как преобразование элементов линейного пространства // Вычислительная техника и автоматизированных системах контроля и управления. Пенза: Политехнический ин-т, 1991. С. 58-65.

51.Smith Brian T. Structured Software design // 77th Annu. Meet. Techn. Sec. Can. Puep. And Pap. Acsoc. Montreal, 1991. P. 115-120.

52.Лаврищева Е.М., Грищенко В.М. Сборочное программирование. Киев: Наук. думка, 1991.

53.Туяхов Л.С., Коваленко В.М. Организация интерфейса между модулями в составе ПО АСУ // Управляющие системы и машины. 1984. № 2.С. 72-74.

54.Кротюк Ю.М.Постановка и методы решения задач определения допустимой и оптимальной последовательности приоритетов при решении задач синтеза оптимальных модульных СОД в системах управления комплексно-автоматизированными участками и производствами. ЦНИИТУ, 1982. С.87-101.

55.Кротюк Ю.М.,Кошелев В.А.Определение оптимальной величины блоков обмена между различными уровнями памяти в модульных системах обработки данных реального времени//Анализ и синтез оптимальных модульных систем обработки данных:М.:Ин-т проблем управления ,1984.C.77-82.

56.Кошелев В.А.Об одной задаче автоматизации синтеза СОД РВ//Всесоюз. Коференция по автоматизации проектирования систем управления(Евреван ,1984)Тез.докл.М.: .:Ин-т проблем управления, 1984.C.84-86.

57.Кошелев В.А.,Мелодиев И.Е.Синтез оптимальной модульной СОДРВ для ИАСу строительством тоннелей БАМ//Роль молодых ученых и специалистов в развитии научно-технического прогресса на железнодорожном транспорте. Тез .докл. отраслевой научно-технической конференции.М.:Московчский ин-т железнодорожного транспорта,1984.С.73.

58.Доенкин О.Е., Кошелев В.А.Синтез оптимальных модульных СОД РВ с параллельным обслуживанием заявок//Всесоюз. конференция по автоматизации проектирования систем планирования и управления (Звенигород,1987) Тез.докл.М.: .:Ин-т проблем управления ,1987.C.46-47.

59.Доенкин О.Е., Кошелев В.А.Задачи синтеза оптимальной модульной СОД РВ, использующий мультипроцессорное обслуживание//Разработка оптимальных модульных систем обработки данных .М.: .:Ин-т проблем управления ,1987.C.37-41.

60.Кошелев В.А.,Шарикова М.П.Синтез оптимальных модульных СОД РВ по критерию максимума коэффициента готовности системы //Разработка оптимальных модульных систем обработки данных .М.: .:Ин-т проблем управления ,1987.C.41-46.

61.Косяченко С.А.,Кошелев В.А.,Доенкин О.Е.Синтез оптимальных модульных систем обработки данных , реализуемых на базе однородных вычислительных систем обработки данных . М.: .:Ин-т проблем управления ,1989.C22-28.

62.Hoistis Catherine E.Module allocation of real–time applications to distributed systems // IEEE Trans.Software Eng.1990.V.16.№7.P.699-709.

63.Гузик В.Ф. ,Золотовский В.Е., Туманский С.М.,Пуховский В.Н.Анализ производительности функционально распределенной вычислительной системе. // Многопроцессорные вычислительные структуры .Таганрог,1990. №12.С. 11-15.

64.Кальентов А.А,Сыгуров Ю.М.Распределение задач в однородной многомашинной вычислительной системе при наличие затрат на межмашинной обмен //Мат. Методы и модели В САПР.Самара:Авиац. Ин-т ,1991.С.11-15.

65.Мамедли Э.М., Слепченко А.Н.,Хусидман В.б.Модели организации диспетчеризации в мнногопроцессорных вычислительных системах реального времени //АиТ.1991.№ 117-129

66.Денисов С.Г. Турута Е.Н. Восстановление вычислительных процессов в многопроцессорной системе на основе их реактивизации // Упр. ресурсами и интегр сетях. М.: Ин-т проблем передачи информации, 1991. С. 117-129.

67.Казиев Г.З. Садвакосов Е.С. Структуры информационного обмена в модульных системах обработки данных // Тез.докл. Всесоюз.семинара по методом синтеза типовых модульных систем обработки данных. М.: Ин-т проблем управления, 1981. с. 49.

68. Казиев Г.З. Садвакосов Е.С. Оптимальное размещение файлов на внешней памяти в модульной СОД // Вопросы создания АСУТП и АСУП (Междувузовский сборник научных трудов). Алма-Ата: КазПТИ, 1983. с. 16-25.

69.Юрченко В.В. Процедурный и функциональный подход к описанию диалоговых систем // Сб.тр. ВНИИСИ. М., 1989. №13. с. 70-80.

70.Алеев В.Р. Формальная модель диалога программы с пользователем // Сб.тр. ВНИИСИ. М., 1989.№ 13. С.65-69.

71.Мамиконов А.Г., Кульба В.В., Сомов С.К., Калугин С.Э. Модель синтеза оптимальных модульных диалоговых систем // Автоматизация проектирования модульных систем обработки данных. М.: Ин-т проблем управления, 1989.С.5-12.

72.Емельянов С.В., Ларичев О.И. Многокритериальные методы приниятие решений. М.: Знание,1985.

73.Мамиконов А.Г., Кульба В.В., Косяченко С.А., Сидоров Е.Н. Некоторые задачи синтеза типовых модульных СОД с учетом активного поведения элементов системы проектирования. // Автоматизация проектирования систем обработки данных. М.: Ин-т проблем управления, 1989.С.13-22.

74.Преображенский А.А., Хохлов а.И., Курос Л.В. Задача анализа и синтеза типовых модулей системы обработки данных // Тез.докл.Всесоюз.конференции по автомтизации проектирования систем планирования и управления. М.: Ин-т проблем управления, 1987.С.48.

75.Косяченко С.А., Кульба В.В., Мамиконов А.Г., Ужастов И.А. Модели и методы проектирования распределенных баз данных (обзор) // АиТ.1989.№7.С.3-58.

76.Косяченко С.А., Кульба В.В., Мамиконов А.Г., Ужастов И.А. Оптимизация структур распределенных баз данных в АСУ. М.:Наука,1990.

77.Голинков Ю.П., Дарко Т.Г., Яструб В.И. Применение сетей на базе персональных компьютеров низовом звене АСУП// Анализ и проектирование прогр.обеспеч. и аппарат.средств вычисл.систем и сетей ЭВМ для ГАП, САПР и АСУ. М.: Моск.ин-т электрон.машиностр.,1991.С.11-14.

78.Прангишвили И.В. Микропроцессоры и локальные сети микро-ЭВМ в распределенных системах управления. М.: Энергоатомиздат,1985.

79.Глушков В.М. и др. Сети ЭВМ.М.: Наука, 1977.

80.Петухова Е.О., Томашевская Т.В. Математическая модель синтеза распределенной базы данных АСУ // изв.Ленингр.электротехн.ин-та.1991.№438.С.22-25.

81.Гудзенко Н.А., Дрянченко Н.И., Перова В.Б. Система автоматизированного проектирования распределенной базы данных // Использование мат.методов и ЭВМ в системах управления и проектирования. Киев: Ин-т кибернетики, 1991. С.134-144.

82.Казиев Г.З. Блочно-симметричные модели и методы постановки и решения задач дискретного программирования. // Вестник инженерной академии Республики Казахстан. №2(10). 2003. с. 55-59.

83.Корбут А.А, Филькейнштейн Ю.Ю. Дискретное программирование. - М.:Наука, 1969.

84.Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. М.: ФИЗМАТЛИТ, 2002.

85.Малюгин В.Д. Реализация булевых функций арифметическими полиномами //Автоматика и телемеханика. - 1982. - №4.- с.73

86.Дроздов Н.А. Алгоритмы дискретного программирования. – Тверь.: Наука, 2002.

87.Казиев Г.З. Синтез модульных блок-схем в автоматизированных системах управления// Автоматика и телемеханика. 1992. №11. с. 160-171.

88.Посыпкин М.А., Сигал И.Х., Галимьянова Н.Н. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. М.: ВЦ РАН, 2005.

89.Посыпкин М.А., Сигал И.Х., Галимьянова Н.Н. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. Сообщения по прикладной математике. М.: ВЦ РАН, 2005.

90.Сигал И.Х. Параметризация приближенных алгоритмов решения некоторых классов задач дискретной оптимизации большой размерности. // Известия РАН. Теория и системы управления. 2002. №6, С. 63-72.

91.Сигал И.Х. Параметризация и исследование некоторых задач дискретного программирования большой размерности. // Известия РАН. Теория и системы управления. 2001. №2, С. 60-69.

92.Сигал И.Х. Приближенные методы и алгоритмы в дискретной оптимизации. МГУПС (МИИТ), учебное пособие, 2000, Москва. 102 с.

93.Сигал И.Х. Алгоритмы решения задач коммивояжера большой размерности. В кн. “Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности”, гл.13. Москва, Наука, 2000, с. 295-317.

94.Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2007. - 304 с.

95.Сигал И.Х., (в соавторстве). Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности: М.: НАУКА, 2000.

96.Меламед И.И., Сигал И.Х. Вычислительное исследование трехкритериальных задач о деревьях и назначениях. // ЖВМ и МФ, 1998, т.38, №10, С. 1780-1787.

97.Меламед И.И., Сигал И.Х. Задачи комбинаторной оптимизации с двумя и тремя критериями. //ДАН, 1999, т.366, №2, С.170-173.

98.Kuhn H.W., T u c h e r A.W. Nonlinear Programming // Proc. Second Berkley Symp. on Math., Stat and Probab. / J. Neyman, Ed. - Berkley: Univ of California Press., 1951. - P. 272-301.

99.Гермейер Ю.Б. Игровые принципы в исследовании систем // Методы управления большими системами. - Иркутск: Сиб. энергетич. ин-т СО АН СССР, 1970. - Т, 1. - С. 4-24.

100.Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. - М.: Наука, 1982. - 287 с.

101.Поспелов Г.С, Ириков В.А., Курилов А.Е. Процедуры и алгоритмы формирования комплексных программ. - М.: Наука, 1985. - 424 с.

102.Краснощенко А.С., Федоров В.В., Морозов В.В. Декомпозиция в задачах проектирования // Изв. АН СССР. Техническая кибернетика. - 1979. - № 2. - С. 86-97.

103.Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. -М.: Знание, 1985. - 32 с.

104.Моисеев Н.Н. Математические задачи системного анализа. - М.: Наука, 1981. - 488 с.

105.Дубов Ю.А., Травкин С.И., Якимцев В.Н. Многокритериальные модели формирования и выбора вариантов систем. - М.: Наука, 1986. - 296 с.

106.Молодцов О.А., Федоров В.В. Устойчивость принципов оптимизации // Современное состояние теории исследования операций. - М.: Наука, 1979. - С. 236-263.

107.Подиновский В.В. Парето-оптимальные решения многокритериальных задач. - М.: Наука, 1982. - 256 с.

108.Сергненко И.В. Математические модели и методы решения задач дискретной оптимизации. - Киев: Наукова думка, 1988. - 472 с.

109.Емеличев В.А., Перепелица В.А. К вычислительной сложности многокритериальных задач // Изв. АН СССР. Техн. кибернетика. - 1988, № 1. - С. 78-85.

110.Гэри М,, Ддонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.-416 с.

111.Ахо А., Xопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

112.Пападимитриу X., Стайгиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.

113.Слисенко А.О. Сложностные задачи теории вычислений // Успехи мат. наук. - 1981. - Т. 36, вып. 6 (222). - С. 21-103.

114.Карапетиян A.M. Автоматизация оптимального конструирования ЭВМ. - М.: Сов. радио, 1973.-152 с.

115.Логическое проектирование БИС / Мищенко В.А., Аспидов А.И., Витер В.В и др. - М.: Радио и связь, 1984. - 322 с.

116.Мелихов А.Н., Берштейн Л.С, Курейчик В.М. Применение графов для проектирования дискретных устройств. - М.: Наука, 1974. – 307 с.

117.В.А. Емеличев, В. А. Перепелица 20. П е т р е н к о А.И, Основы автоматизированного проектирования. - Киев: Техника, 1982. - 295 с.

118.Се л ю г и н В. А. Машинное конструирование электронных устройств. - М.: Сов. радио, 1977. - 384 с.

119.Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.

120.Журавлев Ю.И, Дискретное программирование //Матем. энциклопедия. - М.: Сов.энциклопедия, 1979. - Т. 2. - С. 205-206.

121.Сергиенко И.В., Перепелица В.А. К проблеме нахождения множеств альтернатив в дискретных многокритериальных задачах // Кибернетика. - 1987. - № 5. - С. 85-93.

122.Емеличев В.А., Перепелица В.А. Полные задачи многокритериальной дискретной оптимизации // Сообщения АН ГССР. - 1988. - Т. 131, № 3. - С. 501-504.

123.Перепелица В.А. Многокритериальные задачи теории графов. Алгоритмический подход: Учебное пособие. - Киев: УМК ВО, 1989. - 67 с.

124.Мамиконов А.Г., Ашимов А.А., Кульба В.В. Синтез оптимальных функциональных модулей обработки данных в АСУ (препринт). Препринт. - Москва: ИПУ, 1979, с.1-74.

125.Казиев Г.З., Сиротюк В.О. Формализованные методы анализа модульных систем обработки данных. // Сб. «Вопросы создания АСУ технологическим процессами и предприятиями», Алма-Ата, КазПТИ, 1980.

126.Казиев Г.З., Мамиконов А.Г., Ашимов А.А., Косяченко С.А. Модели и методы автоматизации проектирования модульных систем обработки данных (статья). В кн.: Автоматизация проектирования систем управления, вып. 3, М.: Финансы и статистика, 1981, с. 63-79

127.Казиев Г.З., Мамиконов А.Г., Ашимов А.А., Косяченко С.А. Оптимальные модульные системы обработки данных (монография). Алма-Ата, Наука, КазССР, 1981, с.1-187

128.Казиев Г.З., Мамиконов А.Г., Ашимов А.А., Кульба В.В., Косяченко С.А. Автоматизация проектирования оптимальных систем обработки данных (статья) // Сб. трудов института проблем управления, вып.25, М.: Институт проблем управления, 1981,с.5-15

129.Казиев Г.З., Сиротюк В.О., Китапбаев Ж.Б. Модели и методы анализа и синтеза оптимальных структур баз данных в системах параллельной обработки запросов (тезисы). // Тезисы докладов Всесоюзной школы-семинара «Распараллеливание обработки информации», Львов, 1985, с. 114-115.

130.Казиев Г.З., Горбенко А.С., Касенкова О.А. Диалоговая система взаимодействия пользователей с базой данных (тезисы). // Тезисы докладов X Всесоюзного совещания по проблемам управления. Книга I. ИПУ, М., 1986, с. 444-445.

131.Казиев Г.З., Поликарпов О.Ю. Об одном подходе к анализу и структуризации проблемной области при разработке диалоговых баз данных (тезисы). // Тезисы докладов IV Всесоюзной конференции «Системы баз данных и знаний». Калинин, 1989, с.59-60.

132.Казиев Г.З. Метод автоматизированного проектирования логических структур баз данных (статья). // Сб. трудов «Динамика неоднородных систем». Вып. 13, ВНИИСИ . - М., 1990, с.45-52

133.Казиев Г.З., Кузнецов Н.А., Кульба В.В., Шелков А.Б. Модели, методы и средства анализа и синтеза модульных информационно- управляющих систем (статья). Журнал «Автоматика и телемеханика», N5, М.,1993,с.3-59.

134.Казиев Г.З., Айтчанова Ш.К., Мусина Р.Ж. Блочно-симметричные задачи дискретного программирования (тезисы). Тезисы докладов - 1 Съезда математиков Казахстан, Шымкент, Гылым, 1996, с. 288-289

135.Казиев Г.З., Набиева Г.С., Оспанова С.Б. Многокритериальные блочно – симметричные задачи дискретного программирования. // Труды международной научно-практической конференции «Состояние, проблемы и задачи информатизации в Казахстане», посвященной к 70-летию КазНТУ им.К.И.Сатпаева и 10-летию Международной Академии Информатизации (МАИН). – Алматы: РИО, 2004, С. 258-263.

136.Казиев Г.З., Набиева Г.С. Методы проектирования модульного прикладного программного обеспечения и массивов базы данных в информационных системах. // Совместный выпуск научных журналов «Вычислительные технологии» РАН и «Региональный вестник Востока» ВКГУ по итогам международной конференции «Вычислительные и информационные технологии в науке, технике и образовании», часть VI. - Новосибирск, Алматы, Усть – Каменогорск, 2003 г. С. 272-274.

137.Казиев Г.З. Блочно-симметричные модели и методы постановки и решения задач дискретного программирования. Вестник Инженерной академии РК N2 (10), Алматы, 2003,с. 55-59

138.Казиев Г.З., Сагимбекова А.О., Набиева Г.С., Оспанова С.Б. Эффективный алгоритм решения блочно-симметричных задач // Вестник КАЗ НТУ имени К.И. Сатпаева. - Алматы, 3/4 (37/38), 2003. С. 310-315.

139.Казиев Г.З., Набиева Г.С., Шукатаев А. Программная реализация многокритериальных блочно-симметричных задач дискретного программирования. // Научный журнал Министерства образования и науки «Поиск» , №4. – Алматы, 2006. с. 191-196.

140.Туенбаева А.Н., Набиева Г.С. Автоматизация приложений // Тезисы докладов научной конференции магистрантов и аспирантов «Наука и творчество молодых: опыт, проблемы, перспективы»: - Усть-Каменогорск: ВКГУ; 2001. С. 248-249.

141.Туенбаева А.Н., Набиева Г.С. Численное исследование математической модели сетей связи // Региональный Вестник ВКГТУ. - Усть-Каменогорск, 2001г. С. 119-123.

142.Набиева Г.С. Методы проектирования баз данных при заданном множестве программных модулей // Совместный выпуск научных журналов «Вычислительные технологии» РАН и «Региональный вестник Востока» ВКГУ по итогам международной конференции «Вычислительные и информационные технологии в науке, технике и образовании», часть II. - Новосибирск, Алматы, Усть – Каменогорск, 2003 г. С. 270-271.

143.Набиева Г.С. Берілген деректер базасы кезінде қосымшаларды жобалау әдісі. // Материалы Республиканской научно-практической конференции «Молодежь и информационные технологии». - Актау: КГУТиИ им.Ш.Есенова, 2009. С. 80-81.

144.Набиева Г.С., Ескендирова Д.М., Сыдыбаева М.А. Информационная безопосность в современных системах управление базами данных. // Материалы Республиканской научно-практической конференции «Молодежь и информационные технологии». - Актау: КГУТиИ им.Ш.Есенова, 2009. С. 242-249.

145.Ескендирова Д.М., Набиева Г.С., Тулегенова Б.А. Использование новых технологий в учебном процессе вузов. // Сборник материалов международной научно-методической конференции «Актуальные проблемы естественно-научных дисциплин». - Алматы: КазГАСА, 2010, С.140-142.

146.Г.С.Набиева. Дискретті программалаудың модельдері мен әдістерін зерттеу бойынша программалық қамтаманы өңдеу // Научный журнал Министерства Образовании и Науки «Поиск», №3(1), 2010г. С. 232-238.

147.Казиев Г.З., Набиева Г.С., Сатмагамбетова Ж.З., Абылхасенова Д.К. Модели и методы дискретного программирования. Блочно-симметричные модели - эффективный класс задач дискретного программирования. // «Вестник КБТУ», №3, 2010. С.