| Разработка алгоритмов моделирования и построения информационных сетей методом структурных образований
Диссертация
Автор: Журавлев, Рихсибой
Название: Разработка алгоритмов моделирования и построения информационных сетей методом структурных образований
Справка: Журавлев, Рихсибой. Разработка алгоритмов моделирования и построения информационных сетей методом структурных образований : диссертация кандидата технических наук : 05.13.01 Ташкент, 1984 234 c. : 61 85-5/1654
Объем: 234 стр.
Информация: Ташкент, 1984
Содержание:
ВВЕДЕНИЕ
ГЛАВА I ТОПОЛОГИЧЕСКИЕ ЗАДАЧИ И МОДЕЛИ ОБЪЕКТОВ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ И ТЕОРИИ ИНФОРМАЦИИII
11 Топологические задачи технической кибернетики и теории информации II
12 Взаимосвязанность задач анализа и синтеза информационных сетей
13 Топологические методы исследования функциональной надежности РЭС
14Структурное образование - структура данных для машинного решения топологических задач
Выводы по первой главе
ГЛАВА 2 ОПРЕДЕЛИТЕЛИ СТРУКТУРНЫХ ОБРАЗОВАНИЙ
21 О двух разновидностях структурных образований
22 Операции над Д-образованиями
23 Д-определители структурных образований
231 Алгоритмы нахождения Д-миноров Д-определителей
232 Некоторые свойства Д-определителей
233 Способы вычисления Д-определителей
234 Алгоритмы уменьшения порядка Д-определителей 62 Выводы по второй главе
ГЛАВА 3 МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ТОПОЛОГИЧЕСКИХ ЗАДАЧ
С ПОМОЩЬЮ СТРУКТУРНЫХ ОБРАЗОВАНИИ
31 Нахождение всевозможных путей в графе
32 Функционально-условная запись структурных образований
33 Определение и перечисление путей, содержащих заданную приоритетную дугу
34 Определение всевозможных покрывающих деревьев в графах
341 Определение всевозможных покрывающих де ревьев в ориентированных графах
342 Определение всевозможных покрывающих де ревьев в неориентированных графах
343 Определение покрывающих деревьев, включающих приоритетную дугу
35 Определение оптимального покрывающего дерева в графе
Выводы по третьей главе
ГЛАВА 4 АЛГОРИТМЫ АНАЛИЗА И ПОСТРОЕНИЕ ИНФОРМАЦИОННЫХ СЕТЕЙ И ЦЕПЕЙ С ПРИМЕНЕНИЕМ СТРУКТУРНЫХ ОБРАЗОВАНИИ
41 Разработка методов и алгоритмов моделирования частных задач анализа и построения ИС
411 Определение всевозможных маршрутов между оконечными узлами ИС
412 Определение множества маршрутов между выб -ранными входным и выходным узлами ИС, про -ходящих через заданную линию связи
413 Построение минимальной структуры ИС типа "дерево"
42 Алгоритмы моделирования функциональной надеж -ности РЭС
43 Алгоритмы моделирования информационных цепей методом структурных образований
44 Методы и алгоритмы анализа цепей РЭС
Выводы по четвертой главе
Введение:
Решениями ХХУ1 съезда КПСС намечены серьезные и широкомасштабные задачи по развитию науки и ускорению технического прогресса, В частности, предусматривается на основе использования достижений науки и техники совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и сис -тем сбора, передачи и обработки информации, и продолжить формирование единой автоматизированной сети связи страны на базе новей -ших систем передачи информации /I/.
Основу современных информащонных и управляющих систем сос -тавляют электрические и радиоэлектронные схемы и структуры. Совершенствование этих систем сопровождается возрастанием уровня интеграции используемых в них микроэлектронных схем и структур, что приводит к увеличению оложности как самих цепей, структур, так и их функций. Это сильно усложняет моделирование таких схем и структур. фи анализе и синтезе их резко возрастает время модел!фова-ния (а следовательно, и время проектирования), время подготовки задачи к решению даже с применением систем (или подсистем) авто -матизированного проектирования.
Эффективность работы управляющих и информационных систем в равной степени зависит от надежного функционирования применяемых в них радиоэлектронных схем и структур, с одной стороны, выбора соответствующих алгоритмов процедур распределения управляющей информации и управления процессами в системе в целом, с другой стороны.
Решение вышеуказанных задач во многом зависит от уровня методов моделирования и проектирования как радиоэлектронных схем и структур, так и структур самих информащонных сетей и цепей, и требует разработки новых и постоянное совершенствование существующих подходов, методов и алгоритмов реализации задач моделирования и проектирования.
В нашей стране и за рубежом ведутся интенсивные исследования по созданию общей теории и методов автоматизированного проектирования, в частности рациональных методов описания, анализа и син -теза радиоэлектронных структур и схем, информационных сетей и цепей, и их элементов. R'современным моделям и математическим аппаратам, ориентированным на использование ЭВМ, предъявляются требования высокой степени формализации, минимальности количества ис -пользуемых математических символов и приспособленности операций алгебры к операторам языка или к выполняемым машинным операциям.
Решению таких задач посвящены работы Анисимова Б.В., Кални -болотского Ю.М., Петренко А.И., Сигорского В.П., Пухова Г.Е.Дро-хименко Я.К., Белова Б.И., Норенкова И.П., Нагорного Л.Я., ton -на В.Н., Гуревича И.В., Ланнэ A.A., Бондаренко В.М., Хасайова П.Ф., Королева Ю.В., Юрина О.Н., Баталова Б.В., Казеннова Г.Г., Абрайтиса Л.Б., Мелихова А.Н., Матюхина H.a., Кабулова В.К., Глу-шковаВ.М., Брюнина В.Н., Лазарева В.Г., Поспелова Д.А., Сифорова В.И., Толчан А.Й., Рогинского В.Н., Давыдова Г.Б., Харкевича А.Д., Бусленко М.П., Журавлева Ю.П., Ченцова В.М. и многих других ав -торов.
Несмотря на широкое распространение матричного аппарата, алгебр графов и различных теоретико-множественных моделей, они недостаточно учитывают особенности выполнения операций алгорит -мических языков и машинного представления данных. Как результат этого, программы решения многих задач в области технической кибернетики и теории информации получаются довольно сложными и требуют больших вычислительных затрат. Это особенно становится ощутимым при решении задач по синтезу и анализу топологических свойств объектов.
В этой связи актуальной является разработка новых моделей и аппаратов для решения топологических задач в области технической кибернетики и теории информации, равносильных матричным и графовым математическим аппаратам и достаточно приспособленных для машинной реализации. Одним из возможных путей решения этой задачи является разработка систем операций и цроцедур, применимых непосредственно к структурам данных о моделируемом объекте.
Целью настоящей работы является разработка методов и алгоритмов решения задач топологического анализа информационных сетей (ИС), цепей (ИЦ) и радиоэлектронных схем и структур (РЭС), основанных на использовании операций над структурами данных о моделируемом объекте.
В диссертации ставятся и решаются следующие задачи:
1. Разработка модели логической структуры данных и определение совокупностей операций и процедур над ними, ориентированных для решения задач топологического анализа сложных информационных сетей, цепей и РЭС.
2. Разработка регулярных алгоритмов определения всевозмок -ных путей между двумя заданными вершинами графов, множества пу -тей, проходящих через приоритетную дугу и всех маршрутов между заданными узлами ИС, содержащих выбранную линию связи.
3. Разработка регулярных алгоритмов составления списка всевозможных и минимальных (максимальных) покрывающих деревьев, включающих приоритетное ребро (или дугу).
Методы исследований. В работе применялись главным образом методы и основные положения общей теории математического модели -рования, линейной алгебры, теорий сетей, графов, множеств и структур данных.
Научные положения и результаты, выносимые на защиту:
1. Разработаны топологические модели информационных сетей и цепей РЭС, ИЦ и графов в виде структурных образований, представляющих собой разновидности файлов. Они позволяют в компактной и единой форме связать данные (или сведения) как о топологии, так и о параметрах состояний исследуемого объекта (ИС, их элементов, РЭС и т.п.).
2. Предложена система операций и процедур над структурными образованиями, которые могут быть использованы для целей исследования линейных систем различной природы.
3. Предложены методы и алгоритмы топологического анализа информационных сетей, цепей и РЭС, оперирующие непосредственно массивами данных об объекте.
4. Разработаны методы и алгоритмы определения оптимального покрывающего дерева неориентированного графа, использующие более цростые операции и процедуры по сравнению с известными. Предло -жены методики определения множества путей и деревьев, включающих заданную (приоритетную) дугу или ребро.
5. Составлены алгоритмы определения всевозможных маршрутов между оконечными узлами ИС, множества маршрутов, проходящих че -рез заданную линию связи, и построения минимальной по стоимости линий связи структуры ИС типа "дерева".
Научная новизна работы заключается в разработке системы операций и процедур над структурами данных о графах, методов решения топологических задач моделирования информационных сетей, цепей и РЭС, алгоритмов нахождения всевозможных путей'и деревьев в графах на основе преобразований над структурными образованиями.
Практическая значимость работы проявляется в возможности совершенствования известных и разработки новых инженерных методов анализа, цреобразования цепей РЭС и ИД, моделирования ИС и надежности Функционирования РЭС с неисправностями.
Научные результаты диссертационной работы наши црактическое применение в научно-исследовательских работах, проводимых в ТашПИ им.Абу Райхана Берунй, й внедрены в »лектромеханическом заводе г.Ташкента.
Результаты диссертации доложены на: Республиканской научно-технической конференции "Автоматизация с применением электротехнических устройств и автоматизированное управление производственными процессами в отраслях народного хозяйства" (г.Ташкент,1978); Республиканской конференции молодых ученых и специалистов (г.Самарканд ,1978); Республиканской научно-технической конференции молодых ученых и специалистов, посвященной 50-летию ТашПИ (г.Таш -кент,1980); П Всесоюзной межвузовской научно-технической конфе -ренции "Математическое, алгоритмическое и техническое обеспече -ние АСУ ТП"; П Всесоюзном семинаре "Методы синтеза и планирова -ния развития структур сложных систем" (г.Ташкент,1981); Ш Все -союзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (гг.Ташкент,Новосибирск, 1984); ежегодных научно-технических конференциях профессорско-преподавательского состава ТашПИ (г.Ташкент,1977-1984).
Диссертационная работа состоит из введения, четырех глав, заключения, приложений, списка использованной литературы и акта о внедрении результатов.
|