Матричные методы исследования информационных сетей и потоков

Основными направлениями экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года", утвержденными ХХУТ съездом КПСС, запланирован качественный подъем уровня хозяйствования во всех звеньях экономики страны [56]. Успешное решение данной задачи во многом зависит от развития методов планирования и управления [2,7,9,10,16,23,30,55,57,63,70,80,81,101], которое идет по пути создания комплексных интегрированных автоматизированных систем управления [59,85,103]. В этом свете особую значимость приобрела автоматизация проектирования информационных сетей [11,22,42,45,69,76,98,115,116,117] и потоков [3,5,15,28,29,36,40, 48−50,64,72,73,88,98,99,118,119]. Однако каждый из этих методов, взятых в отдельности, ориентирован на решение лишь ограниченного круга задач по анализу и синтезу потоков информации и сетей, что является одним из серьезных препятствий на пути к созданию САПР информационных систем (ИС).

В последние годы появились новые методы исследования больших систем управления, основанные на информационном подходе, базирующиеся на составлении теоретико-цепных моделей систем [18,21]. Методической основой для разработки методов исследования систем в данном аспекте служит теория энергетических (электрических) цепей и систем [62,79,86].

К сегодняшнему дню появился ряд работ [11,22,42,45,75,115 117], посвященных разработке различных аспектов теории информационных сетей, но до сих пор не создана обобщающая теория информационных сетей [61].

Характерной особенностью известных методов и алгоритмов исследования потоков информации, информационных цепей и информационннх сетей является использование большого разнообразия математических аппаратов и алгебр для решения задач. Это объясняется с одной стороны спецификой задач в рассмотренных аспектах (поток, цепь, сеть) представления моделей ИС, с другой стороны — отсутствием универсальных моделей и математических аппаратов. ориентированных на решение совокупностей задач, относящихся к исследованию и потоков информации, и информационных цепей, и информационных сетей. Наличие таких моделей и аппаратов позволит улучшить математическое и специальное программное обеспечение САПР интегрированных АСУ и их информационных подсистем.

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

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

В диссертационной работе ставятся и решаются следующие задачи:

1. Определение класса задач из теории ИС, имеющих аналогичную постановку в области электро-энергетических систем.

2. Разработка математического аппарата, ориентированного на создание математического и программного обеспечения подсистем анализа САПР информационных цепей, сетей и схем потоков.

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

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

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

В диссертации получены следующие научные результаты и обоснованы положения, выносимые на защиту:

— класс задач теории ИС, эффективно решаемых методами и алгоритмами символьного анализа теории энергетических (электрических) цепей и сетей;

— модели ИС, отвечающие различным аспектам исследования ИС, выявленные на основе абстрактной модели;

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

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

— методы и алгоритмы нахождения всех покрывающих подграфов для трех разновидностей локальных структур («шина» ," кольцо" - «звезда») информационных сетей, разработанные на основе теории ИМ;

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

— методы, основанные на бинарных операциях и преобразованиях ИМ для исследования потоков информации большой размерности;

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

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

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

Выводы по пятой главе.

1. Задачи, разрешимые в алгебре информационных матриц, абстрактно представляются точками 6-мерного пространства задач.

П^ = (Mm х М} *МА *Мп х Q'*у*'}, где М (Т) — множество типов информационно-матричных моделей, — множество требуемых результатов задач, t Ma — множество алгоритмов, Мп) ju! — подмножества степенных множеств процедур, алгоритмов и типов многочленов соответственно.

2. Подпакеты прикладных подпрограмм исследования и структур

— 126 ной оптимизации информационных цепей, сетей и потоков на основе алгебры ИМ и теории многочленов от элементов ИМ можно построить в 4-" вариантах, в зависимости от круга решаемых задач, как это следует из принятого в работе формального представления пространства задач.

3. Для решения ряда задач символьного анализа и синтеза информационных цепей и сетей целесообразно использовать разработанный комплекс подпрограмм INFMA Т, составленный на алгоритмическом языке Ф0РТРАН-1У, обеспечивающий сокращение объема памяти и вычислительных затрат по сравнению с другими программами аналогичного назначения, что подтверждается результатами анализа ряда4схем информационных цепей и сетей на ЭВМ ЕС 1022.

— 127 -ЗАКЛЮЧЕНИЕ.

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

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

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

4. Анализ графика соответствия Г между теориями матриц и диаматриц позволил выявить новые теоремы и понятия теорий ИМ. В частности, такие виды многочленов от элементов информационных матриц, как «зависимый минор», «суммарный минор», «О — минор», и «^ - минор», получены на основе графика соответствия между понятиями теорий матриц и диаматриц.

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

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

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