автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Матричные методы исследования информационных сетей и потоков

ВВЕДЕНИЕ

ГЛАВА I. МОДШ И ЗАДАЧИ ИССЛЕДОВАНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ

1.1. Задачи проектирования информационных систем.

1.2. График соответствия между понятиями теорий информационных и энергетических систем.

1.3. Модели информационных систем.

1.4^ Алгебра информационных матриц

1.4.1. Операции над элементами информационных матриц

1.4.2. Операции над информационными матрицами.

Выводы по первой главе

ГЛАВА 2. ОСНОВЫ СИМВОЛЬНОГО АНАЛИЗА ИНФОРМАЦИОННЫХ ЦЕПЕЙ

МЕТОДОМ ИНФОРМАЦИОННЫХ МАТРИЦ.

2.1. Информационно-матричная, модель информационной

2.2. График соответствия мевд теориями матриц и информационных матриц.

2.3. Основные понятия и объекты

2.4. Свойства диаопределителей и операции над информационными матрицами

2.5. Диаопределители информационных матриц,специальной структуры.

2.6. Анализ и синтез информационных цепей методом информационных матриц.

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

ГЛАВА 3. МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ СТРУКТУРНЫХ ЗАДАЧ ИНФОРМАЦИОННЫХ СЕТЕЙ

3.1. Информационные сети и их локальные структуры.

3.2. Разновидности многочленов от элементов информационных матриц

3.3. Методы разложения диаопределителей информационных матриц.

3.4. Матричные методы нахождения всех покрывающих локальных структур информационных сетей.

3.5. Свойства локальных структур информационных сетей и исследование их количественных характеристик.

3.6. Минимизация локальных структур информационных сетей.

3.7. Минимизация структур типа "ориентированное дерево" и "шина"

Выводы по третьей главе

ГЛАВА 4. МЕТОДЫ ИССЛЕДОВАНИЯ ПОТОКОВ ИНФОРМАЦИИ.

4.1. Потоки информации.

4.2. График соответствия между информационными графами и матрицами.

4.3. Основные задачи исследования потоков информации

4.4. Метод,основанный на использовании бинарных операций

4.4.1. Алгоритмы анализа методом бинарных операций.

4.5. Метод, основанный на преобразованиях матриц.

4.6. Решение частичных задач потоков информации.

4.6.1. Алгоритмы анализа потоков информации.

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

Выводы по четвертой главе

ГЛАВА 5. СТРУКТУРА ПРИКЛАДНОГО АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ЗАДАЧ ИССЛЕДОВАНИЯ ИНФОРМАЦИОННЫХ СЕТЕЙ И ПОТОКОВ . III

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

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

5.3. Программная реализация разработанных алгоритмов

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

Основными направлениями экономического и социального развития СССР на 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,115117], посвященных разработке различных аспектов теории информационных сетей, но до сих пор не создана обобщающая теория информационных сетей [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. На основе анализа системы множеств исходных данных, требуемых результатов и решений задач по исследованию информацион -ных цепей, сетей и потоков определен состав необходимых процедур и прикладных программ, который может быть включен вместе с алгеброй ИМ в состав математико-программного обеспечения САПР информационных систем. Единство алгебры для решения большого перечня задач наилучшим образом отвечает принципам интеграции обеспечивающих частей АСУ на стадиях создания и развития интегрированных АСУ.

1. Автоматизация проектирования систем управления. / Под ред. В.А.Трапезникова. - М.: Финансы и статистика, 1982, вып.4. -- 208 с.

2. Автоматизированные системы управления предприятиями ./Под ред.

3. B.Н.Четверикова М.: Высшая школа, 1979. - 303с.

4. Айламазян А.К. Информация и информационные системы. М.: Радио и связь, 1982. - 161 с.

5. Акофф Р., Сасиени М. Основы исследования операций. М.: Мир, 1971. - 534 с.

6. Аксютина О.П., Чирченко О.Н. Информационные системы и документация в экономических системах. М.: Наука, 1979. - 175 с.

7. Алгебра структурно-режимных схем и теория диаопределителей при расчете электронных цепей. / П.Ф.Хасанов, Ю.Р.Рашидов,

8. C.Х.Ирматов,А.А.Кадыров, З.К.Юсупов. В кн.: Автоматизация проектирования радиоэлектронной аппаратуры на промышленных предприятиях. - Киев: Общество "Знание" Украинской ССР, 1976, с.4-5.

9. Анисимов Б.В., Четвериков В.Н. Преобразование информации для ЭЦВМ. М.: Высшая школа, 1968. - 333 с.

10. Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978. - 368 с.

11. Белостоцкий А.А., Чухман В.Н. Исследование и организация производства при создании автоматизированных систем управления.- М.: Металлургия, 1971, 255 с.

12. Белоногов Г.Г., Новоселов А.П. Автоматизация процессов накопления, поиска и обобщения информации. М.: Наука, 1979.- 256 с.

13. Береговенко Г.Я., Цымбал В.П. О возможностях квазианалогово- 130 го моделирования коммуникационных сетей. В кн.: Научно-техническая информация. Серия 2. Информационные процессы и системы. - М.: ВИНИТИ, 1983, № II, с.13-15.

14. Блох Е.Л., Лошинский Л.И., Т^рин В.Я. Основы линейной алгебры и некоторые ее приложения. М.: Высшая школа, 1971. - 256с.

15. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. М.: Советское радио, 1973. - 440 с.

16. Веников В.А. Кибернетические модели электрических систем. --М.: Энергоиздат, 1982, 327 с.

17. Воробьев Г.Г. Документ: информационный анализ. М.: Наука, 1971. - 255 с.

18. Глушков В.М. Введение в АСУ. Киев: Техника, 1974. - 319 с.

19. Головина Л.И. Линейная алгебра и некоторые ее приложения. -- М.: Наука, 1971. 288 с.

20. Денисов А.А. Основы теории информационных цепей. Л.: ЛПИ, 1977. -49 с.

21. Денисов А.А. Информационные основы управления. Л.: Энерго-атомиздат, 1983. - 72 с.

22. Денисов А.А., Колесников Д.Н. Теория больших систем управления. Л.: Энергоиздат, 1982. - 288 с.

23. Денисов А.А. Теоретические основы кибернетики. Л.: ЛПИ, 1975. - 40 с.

24. Дэвис Д., Барбер Д. Сети связи для вычислительных машин. М.: Мир, 1976. - 680 с.

25. Теория систем с переменной структурой./ Пер.с анг. под ред. С.В.Емельянова. -М.: Наука, 1970. 592 с.

26. Ефимов Е.Н. Решатели интеллектуальных задач. М.: Наука, 1982. - 316 с.

27. Ефимов А.Н., Рубанов В.Г. Оптимизация процессов первичной обработки информации в АСУ. Киев: Техника, 1976. -144 с.- 131

28. Куков JI.А. Стратан Н.П. Установившиеся режимы сложных электронных сетей и систем. М.: Энергия, 1979. - 416 с.

29. Заманский М. Введение в современную алгебру./Пер.с франц.под ред.Е.И.Стечкиной.- М.: Наука, 1974. 488 с.

30. Зингер Н.С., Коротаев М.Ф., Модин А.А. Исследование и анализ потоков информации на промышленных предприятиях. -М.: Наука, 1970. 151 с.

31. Зингер Н.С, Моделирование информационных процессов в системах управления предприятиями. -М.: Статистика, 1974. 128 с.

32. Игнатов В.А. Теория информации и передачи сигналов. М.: Советское радио, 1979. - 280 с.

33. Идельчик В.Н. Расчеты установившихся режимов элекорических схем. М.: Энергия, 1977. - 192 с.

34. Ильин В.А., Позняк Э.Г. Линейная алгебра. М.: Наука, 1974.- 296 с.

35. Ильин В.Н. Основы автоматизации схемотехнического проектирования. М.: Энергия, 1979. - 392 с.

36. Ионкин П.А., Соколов А.А. Основы построения графов для расчета электрических цепей. Электричество,1964, № 5, с.67-73.

37. Кабулов В.К., Ирматов М. Методологические основы РАСУ. Ташкент: Фан, 1976. - 174 с.

38. Казаковцев B.C. Наука техника - управление. Интеграция науки, техники и технологии, организации и управления в США.- М.: Советское радио, 1966. 518 с.

39. Калниболотский Ю.М., Королев Ю.В. Синтез электронных схем.- Киев: Вища школа, 1979. 230 с.

40. Кафаров В.В., Мешалкин В.П.,Перов В.Л. Математические основы автоматизированного проектирования химических производств. -М.: Химия, 1979. 318 с.

41. Клист-Дашинский М.Н. Алгебра матриц и векторов. Л. Ленин40