Структурный анализ системы

Структура – совокупность элементов системы и связей между ними.

Модель структуры системы должна отображать отношение элементов как между собой, так и с внешней средой. Система часто является многоуровневой:

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

Различают 3 уровня описания связей между элементами в системе:

1. определяет наличие связей в системе

2. изучение направленности связей

3. изучение вида и направления сигналов, определяющих взаимодействие между элементами

С помощью графов

1. Неориентированные графы системы, где вершины – это элементы, ребра – связи между элементами. На этом этапе возникают следующие задачи:

1. определение целостности системы( связности).

Если система не связана, то выделение изолированных подсистем

2. выделение циклов

3. определение минимальной и максимальной последовательности элементов, которые соответствует заданной задаче.

2. Ориентированный граф, где направление дуг соответствует направлению связей.

Основные задачи:

1. определение связности системы

2. топологическая декомпозиция системы с выделением сильно связанных подсистем

3. перечисление входных и выходных полюсов, определение углов, приема выдачи информации

4. определение уровней в структуре и определение их взаимосвязей

5. определение минимальных и максимальных путей

6. определение топологических характеристик значимости элементов

7. получение информации о слабых местах структуры

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

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

«1» в матрице смежности А говорит о наличии путей между i-той и j-той вершинами длины пути = 1. Если возвести матрицу А в квадрат, то наличие единиц в позиции i,j означает путь между этими вершинами длиной 2.

2-2 разные пути длиной 3

2-2 разные пути длиной 4

Элемент i,j определяет число путей длиной к от i к j.

Таким образом можно определить вершины входящие в контур и его дину. Но для определения конкретного вида контура необходим дополнительный алгоритм.

«–» низкое быстродействие

«+» просто и наглядно

Порядковая функция на графе

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

Алгоритм упорядочивания системы.

1. Выделяем подмножество 0го уровня N₀, которое содержит вершины, у которых множество левых инциденций G^-1(i)=0. Пусть их будет l₀ штук

2. Нумеруем эти вершины от 1 до l₀.

3. Выделяем подмножество N₁, которое содержит те вершины i, у которых множество

G^-1(i) включает подмножество N₀. Пусть их будет l₁ штук.

4. Нумеруем эти вершины от l₀+1 до l₀+ l₁

5. Выделяем подмножество N₂ тех вершин i, для которого множество левых инциденций включено в объединение множеств N₀ и N₁

Таких вершин l₂

6. Нумеруем эти вершины от l₀+l₁+1 до l₀+l₁+l₂ и так далее, пока не будет пронумерованы все вершины.

В результате получим тот же самый граф, но с переставленными номерами вершин. В ру этой матрицы смежности будет иметь треугольный вид такой что a_ij=0, если i>j.

Пример: Рассмотрим неупорядоченный граф.

После упорядочивания получаем:

Для описания анализа структуры системы и потоков информации в ней будем рассматривать для простоты движение документов в ИС:

Источники – документы, которые внутри системы формируются на основании других документов. Следовательно, все документы делятся на 3 класса.

1. исходные – те, которые поступают в систему

2. внешние – которые являются результатом работы системы

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

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

Отношение вхождения X_j=X_j1, X_j2,…,X_jn означает, что документы X_j образуются непосредственно из множества документов X_j1, X_j2,…,X_j.

Отношения порядка X_ji означает, что документы X_j следуют за документами X_i следуют X_j, может быть образован только после образования X_i.

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

Введем понятие порядка элемента.

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

1. Порядком Пj: элементами j называется длина наибольшего пути из элементов i в элемент j для любого i=1,2…,n,i≠j.

Функциональный смысл Пj означает номер такта, к которому готовы все документы, формирующие j-ый документ. Формально Пj вычисляется как:

, тогда: . В матрице «К» к j-ому элементу есть поступление информации, а в матрице «к+1» к j-ому элементу поступления нет.

Пример:

П₁=0 П₂=П₃=1 П₄=2 П₅=3

2. Число N=max П₁ для любого j называется порядком информационного графа.

N- тактный граф:

Свойство: A^N=0 A^N+1=0

3. Признаком контура служит появление ненулевое элементов на главной диагонали любой из матриц А^к. Появление контура – ошибка информационного графа.

4. – j-ый документ является исходным

– j-ый документ получен на основе элементов

– сумма элементов i-ой строки матрицы А^к

5. Если – j-ый документ является конечным/входящим.

Если – число документов, в которые входит i-ый документ

6. Если i=j и , то i-ый документ является изолированным в нашей системе.

7. Число путей от документа i к документу j определяется элементом a_ij, матрицы А^к.

8. Введем c элементами

Элемент матрицы – число путей всевозможной длины от документа i к документу j.

9. Элементы матрицы определяет все документы, которые участвовали в формировании j-го документа.

Сумма элементов j-го столбца определяет все документы, которые участвуют в формировании j-го документа. Аналогично, все элементы i-той строки определяют все документы, в формировании которых участвовал i-тый документ.

10. - максимальное значение порядков элементов не равных 0 , i-той строки. Определяют номер такта, после которого i-тый документ не используется в системе.

11. – число тактов, в течении которых, i-тый документ находился в системе:

Имея порядок элементов получим матрицу

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

R(i) – множество вершин достижимых из вершины i – достижимое множество.

– множество вершин, достижимых из вершины i по путям длиной k.

R(i) строится последовательно, начиная слева направо, до тех пор, пока текущей множество R не перестанет увеличиваться. Следовательно, получится полное достижимое множество. Число объединений зависит от графа, Р не должно превосходить число вершин.

Q(i) – контрдостижимое множество, это множество вершин из любой, из которых, можно достичь вершины i.

– контрдостижимое множество длиной 1, построенное на контрдостижимом множестве для одной вершины i.

Показатели степени означают длину пути, по которому можно попасть в i.

Это объединение множеств выполняется последовательно слева направо до тех пор, пока очередная операция объединения не перестанет изменять множество Q. q≤количества вершин.

Если рассмотреть – это означает множество вершин, каждая из которых принадлежит по крайней мере одному пути из вершины i в вершину j.

Эти вершины называются существенными относительно i к j.

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

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

0. упорядочивание вершин

1. берем первую вершину и для нее строим

2. определяем множество

3. из графа выбрасываем все вершины принадлежащие V₁.

4. Повторяем эту процедуру для оставшихся вершин с меньшими номерами.

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

R(1) = (1,2,4,5,6,7,8,9,10)

Q(1) = (1,2,3,5,6)

=(1,2,5,6)

R(3) = (3,4,7,9)

Q(1) = (3)

V₂ = 3

R(4) = (4,7,9)

Q(4) = (4,7,8,9,10)

V₃ = 4,7,9

R(8) = (8,10)

Q(8) = (8,10)

V₄ = (8,10)

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

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

Структурно-топологические характеристики системы.

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

1. Связанность структур

Позволяет выявить наличие обрыва в системе, висящей в изолированно вершине.

Для ориентированного графа: из

Все ненулевые элементы заменены на единицы

Из матрицы С определяется вершина, в которой нет входа или выхода.

Для неориентированного графа вычисляется коэффициент связности.

Структура связанная, если неравенство выполняется. (n-количество вершин).

Если K_s< (n-1), то структурная связка

2. Структурная избыточность

Коэффициент избыточности

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

Если R>0 – структура несвязна

Если R=0 – структура связно-минимальна

Если R<0 – структура связно-избыточна.

R используется для изучение экономичности и надежности системы.

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

Поэтому вводят следующую характеристику.

3. Равномерность распределения связей.

Для неориентированного графа, у которого m ребер и n вершин.

Тогда средняя степень вершин вычисляется как:

– степень i-ой вершины

– отклонение

Квадратное отклонение заданного распределения степени вершин.

Если , то структура равномерная

Если , то структура неравномерная

Чем больше , тем больше неравномерность связей.

Иногда называется недоиспользованием возможности структуры с достижением максимальной связности

4. Структура компактность

Этот параметр, который отражает близость элементов в системе между собой.

d_ij – отображает минимальную длину пути из элемента i в элемент j.

Для ориентированного графа – путь, для неориентированного – цепь.

Q – отображение общей структурной близости в системе.

, чем меньше Q ,тем структура компактнее.

Q определяется сложно, поэтому ввели Q_отн.

d=max d_ij

Если – абстрактная компактная структура

Если – абстрактная некомпактная структура

d – диаметр структуры, чем меньше d, тем структура компактнее.

Q и d выражают инерционность информационного процесса в системе.

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

5. Степень централизации в структуре

– индекс централизованности

– вешины

Абстрактная централизация =0

=1

6. Ранг элемента (для ориентированного графа)

к=3 или к=4

Используется при рассмотрении ресурсов в системе, так как от распределения элементов в порядки их значимости. Он определяется только количеством связей элементов системы длиной 3 или 4.

Чем выше ранг элемента, тем сильнее он связан с другими элементами и тем тяжелее последствия изменения элемента.

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

Основные виды структур.

1. Последовательная

2. Кольцевая

3. Радиальная

4. Древовидная

5. Полный

6. Несвязный

Сравнительная характеристика топологий систем:

№ структуры	R		Qотн	d
1	0	1.2	1	4	0.7
2	0,25	0	0.5	2	0
3	0	7.2	0.6	2	1
4	0	3.2	0.7	3	0.7
5	1,5	0	0	1	0
6	-0,25	-	-	-	-

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