Главная | Обратная связь
МегаЛекции

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




  1. Выделяем подмножество 0го уровня N0, которое содержит вершины, у которых множество левых инциденций G-1(i)=0. Пусть их будет l0 штук
  2. Нумеруем эти вершины от 1 до l0.
  3. Выделяем подмножество N1, которое содержит те вершины i, у которых множество

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

  1. Нумеруем эти вершины от l0+1 до l0+ l1
  2. Выделяем подмножество N2 тех вершин i, для которого множество левых инциденций включено в объединение множеств N0 и N1

Таких вершин l2

  1. Нумеруем эти вершины от l0+l1+1 до l0+l1+l2 и так далее, пока не будет пронумерованы все вершины.

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

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

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

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

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

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

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

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

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

Отношение вхождения Xj=Xj1, Xj2,…,Xjn означает, что документы Xj образуются непосредственно из множества документов Xj1, Xj2,…,Xj.

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

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

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

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

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

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

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

Пример:

 

 

П1=0 П23=1 П4=2 П5=3

 

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

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

Свойство: AN=0 AN+1=0

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

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

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

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

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

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

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

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

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) из графа выбрасываем все вершины принадлежащие V1.

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)

V2 = 3

 

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

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

V3 = 4,7,9

 

R(8) = (8,10)

Q(8) = (8,10)

V4 = (8,10)

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

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

 





©2015- 2017 megalektsii.ru Права всех материалов защищены законодательством РФ.