1 2 Математические модели объектов дискретной оптимизации Формализованное решение задач структурного анализа и синтеза невозможно без наличия математических моделей объектов проектирования. Требования, предъявляемые к математической модели, определяются ее назначением. Так как модель является средством описания объекта проектирования, а само проектирование выполняется посредством ее преобразования и/или анализа, то возможность формальной постановки задачи зависит от степени формализации описания объекта и наличия математического аппарата, позволяющего выполнять преобразования модели.

2 2.1 Требования к математическим моделям С точки зрения возможности и эффективности выполнения формальных преобразований к математической модели объекта предъявляются следующие требования: высокая степень формализации отображаемого объекта; наличие математического аппарата, позволяющего выполнять формальные преобразования модели; адекватность модели, т.е. полнота и правильность отображение в модели всей информации об объекте, которая является существенной для решения данного класса задач. От адекватности математических моделей объекта и результата проектирования зависят точность и детерминированность формализованного решения задач структурного синтеза. Правильность отображения информации обеспечивается корректностью правил перехода от объекта к модели.

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

4 Математические модели объектов «В виде графов можно представлять блок-схемы программ (вершины – блоки, а дуги – разрешенные переходы от одного блока к другому), электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группам людей» – Судоплатов С.В., Овчинникова Е. В. Элементы дискретной математики: Учебник, «Занимаясь статистической механикой Уленбек обозначал точками (вершинами) молекулы, а смежность вершин толковал как взаимодействие наибольшей близости (соседства) некоторого физического типа, например магнитное притяжение или отталкивание» – Харари Ф. Теория графов, «Учение о цепях Маркова… связано с ориентированными графами в том смысле, что события представляются вершинами, а ориентированное ребро (дуга), идущее из одной вершины в другую, указывает на то, что вероятность прямого перехода от одного события к другому положительна» – Там же.

5 Пример. Модель алгоритма поиска максимального элемента массива

Графы: ультра-, гипер- и обыкновенные Общее определение графа. 1. Граф – множество вершин X, на элементах которого определены двуместные отношения смежности – (x j, x i ) F, где x j,x i X. Тогда пара вершин, находящихся в отношении смежности, рассматривается как ребро u k = (x j, x i ), u k U. 2. Граф – два непересекающиеся множества: X – вершин и U –ребер, на элементах которых x X, u U определён трёхместный предикат- инцидентов P(X,U,X). Предикат-инцидентов P(X,U,X) является конъюнкцией двуместных предикатов-отношений инцидентности Г 1 (X, U) –«вершинам множества X инцидентны ребра множества U» и Г 2 (U, X) – «ребрам множества U инцидентны вершины множества X»: Р(X, U, X) = Г 1 (X,U)& Г 2 (U,X), P(X,U,X)=«и»: Г 1 (x i,u j )=«и»&Г 2 (u j,x k ) )=«и»/ x j,x k X, u j U}.

7 Общее определение графа Положим, что при X={x 1,x 2,x 3 } и U={u 1,u 2,u 3,u 4 } предикаты Г 1 (X,U) и Г 2 (U,X) принимают значение «истина» на парах: Г 1 (X,U): (x 1,u 1 ), (x 1,u 2 ), (x 2,u 3 ), (x 3,u 4 ), Г 2 (U,X): (u 1,x 2 ), (u 1,x 3 ), (u 2,x 2 ), (u 2,x 3 ), (u 3,x 3 ), (u 4,x 1 ), (u 4,x 2 ). Тогда геометрическая интерпретация предикатов Г 1 (X,U), Г 2 (U,X) и их конъюнкции будет иметь вид, показанный на рис. а и б, а граф – на рис. в.

8 Общее определение графа Предикаты Г 1 (X,U) и Г 2 (U,X) таковы, что для всех графов при X и U : Г 1 (x i,u j )=«и» Г 2 (u j,x k )=«и» Г 1 (x i,u j )=«и» Г 2 (u j,x i ) = «и»). (1) Данное условие устанавливает возможность существования в графе петель. Геометрическая интерпретация выражения (1) при X={x 1,x 2 }, U={u 1 }, Г 1 (x 1,u 1 ) = «и», и Г 2 (u 1,x 2 ) = «и», Г 1 (x 1,u 1 )=«и», Г 2 (u 1,x 1 ) = «и» показана на рис. 1.

9 Виды графов Данная трактовка графов допускает существование в них петель и кратных ребер. Вид графа – обыкновенные неориентированный и ориентированный, гипер- и ультра граф – определяется свойствами предикатов инцидентности Г 1 (X,U) и Г 2 (U,X), которые порождают свойства предикатов смежности и соответствующих им отношений.

10 Отношения смежности На элементах множеств X и U определены также отношения смежности F 1 (X,X) и F 2 (U,U). Например, вершине x i смежна вершина x k, если существует ребро u j, инцидентное x i, такое, что x k инцидентно ему. Аналогично ребру u j смежно ребро u l, если существует вершина x i, инцидентная ребру u j, такая, что u l инцидентна этой вершине. Таким образом, понятие смежности вторично по отношению к понятию инцидентности.

11 Отношения смежности В соответствии с определением понятия «смежность» предикат смежности F 1 (X, X) является композицией предикатов Г 1 (X,U) и Г 2 (U,X): F 1 (X, X) = Г 1 (X, U) Г 2 (U, X), где F 1 (X, X) = {F 1 (x i, x t ) = «и»: u j (Г 1 (x i, u j ) = «и» Г 2 (u j, x t ) = «и») / x i, x t X, u j U}. Здесь – символ операции композиции. Предикат смежности F 1 (X, X), полученный композицией предикатов Г 1 (X, U) и Г 2 (U, X) изображён на рисунке г. Аналогично предикат смежности рёбер графа является композицией предикатов Г 2 (U, X) и Г 1 (X, U): F 2 (U, U) = Г 2 (U, X) Г 1 (X, U), где F 2 (U, U) = {F 2 (u j, u k )=«и»: x i (Г 2 (u j, x i )=«и» Г 1 (x i, u k ) = «и») / u j, u k U, x i X}.

Предикаты-свойства Определим одноместные предикаты-свойства, производные от предикатов Г 1, Г 2, F 1, F 2 (подстановка в двуместный предикат некоторого определенного элемента того или иного множества превращает его в одноместный): зафиксировав в Г 1 (X,U) некоторую вершину x i X, получим предикат-свойство Г 1 x i (U) – «вершине x i инцидентны ребра множества U», истинность которого задается i-й строкой матрицы предиката Г 1 (X,U), а подставив некоторое ребро u j U, получим предикат-свойство Г 1 u j (X) – «ребро u j инцидентно вершинам множества X». Истинность этого предиката определяет j-й столбец матрицы предиката Г 1 (X,U);

13 Предикаты-свойства зафиксировав в предикате Г 2 (U,X) ребро u j, придем к предикату-свойству Г 2 u j (X) – «ребру u j инцидентны вершины множества X», истинность которого задает j-я строка матрицы предиката Г 2 (U,X), а подставив вершину x i, получим предикат- свойство Г 2 x i (U) – «вершина x i инцидентна ребрам множества U». Истинность данного предиката задает i-й столбец матрицы предиката-отношения Г 2 (X,U).

14 Предикаты-свойства Характеристические множества рассмотренных предикатов- свойств будем обозначать через Г 1 x i, Г 1 u j, Г 2 u j, Г 2 x i, где: Г 1 x i =U 1i ={u j U : Г 1 x i (u j ) = «и» }, U 1i U – ребра, инцидентные вершине x i X; Г 1 u j = X 1j ={ x i X : Г 1 u j (x i ) = «и» }, X 1j X – вершины, которым инцидентно ребро u j U; Г 2 u j = X 2j ={x i X : Г 2 u j (x i ) = «и» }, X 2j X – вершины, инцидентные ребру u j U; Г 2 x i =U 2i ={u j U : Г 2 x i (u j ) = «и» }, U 2i U – ребра, которым инцидентна вершина x i X.

15 П р едикаты-свойства Зафиксировав в F 1 (X,X) некоторую вершину x i X, получим предикат-свойство F 1 x i (X) – «вершине x i смежныхе вершины множества X», истинность которого задается i-й строкой матрицы предиката F 1 (X,X), а подставив в F 2 (U,U) некоторое ребро u j U, – предикат-свойство F 2 u j (U) – «ребру u j смежныхе ребра множества U». Истинность этого предиката определяет i- я строка матрицы предиката F 2 (U,U). Характеристические множества рассмотренных предикатов- свойств будем обозначать через F 1 x i, F 2 u j, где: F 1 x i =X 1i ={x j X : F 1 x i (x j ) = «и» }, X 1i X –вершины, смежныхее вершине x i X; F 2 u j = U 2j ={ u i U : F 2 u j (u i ) = «и» }, U 2j U –ребра, смежныхее ребру u j U;

Ультраграфы Определенный выше граф называется ультра графом H U (X,U,Г 1,Г 2 ), если предикаты Г 1 (X,U) и Г 2 (U,X) обладают следующим свойством u j U (|Г 1 u j | + |Г 2 u j | ) >2, (2) т. е. в графе есть хотя бы одно ребро, суммарное количество вершин, которым оно инцидентно и которые инцидентны ему, больше двух.

17 Представление ультра графа матрицами инцидентности Полным и достаточно наглядным способом формального задания ультра графа является его представление через две матрицы инцидентности А 1 и A 2, где А 1 – матрица истинности предиката Г 1 (X,U) и А 2 – матрица истинности предиката Г 2 (U,X). Матрица инцидентности А 1, задающая связь между вершинами и ребрами, – это прямоугольная матрица размером n m, где n = |X|, m = |U|. Элементы этой матрицы определяются по правилу 1 – если Г 1 (x i,u j )= «и» a 1 i,j =, 0 – если Г 1 (x i,u j )= «л» где i = 1, n; j = 1, m.

18 Представление ультра графа матрицами инцидентности Матрица инцидентности А 2 задает связь между ребрами и вершинами. Ее строки соответствуют ребрам, а столбцы – вершинам (размер матрицы m n). Элементы матрицы А 2 определяются по правилу 1 – если Г 2 (u j,x i )= «и», a 2 j,i = 0 – если Г 2 (u j,x i )= «л».

19 Представление ультра графа матрицами инцидентности u 1 u 2 u 3 x x 1 x 2 x 3 x 4 x 5 x u А 1 = x , А 2 = u x u x

20 Аналитическое представление ультра графа Аналитически ультра граф полностью задается множествами X, U и образами этих множеств относительно предикатов Г 1 (X,U) и Г 2 (U,X). Образом множества A относительно предиката Q(A,B) является множество QA = {Qa i / a i A}, где Qa i = { b j B : Qa i (b j ) = «и»},– характеристическое подмножество предиката-свойства Qa i (B), т. е. образ элемента a i A относительно этого предиката. В ультра графе H u (X, U, Г 1 X, Г 2 U): Г 1 X={Г 1 x i /x i X}, Г 1 x i =U 1i U– образ вершины x i X (инцидентные ей ребра; Г 2 U={Г 2 u j /u j U}, Г 2 u j =X 2j X– образ ребра u j U, (инцидентные ему вершины).

21 Пример аналитического представления ультра графа Ультраграф данным способом будет задан, если заданы множества вершин X, ребер U и их образы. H u (X, U, Г 1 X, Г 2 U): X = {x 1, x 2, x 3, x 4, x 5 }, U = {u 1, u 2, u 3 }, Г 1 X = {Г 1 x i / i =1,5}, где: Г 1 x 1 = {u 1, u 2 }, Г 1 x 2 = Г 1 x 3 = Г 1 x 4 =, Г 1 x 5 = {u 1, u 3 }, Г 2 U = {Г 2 u j / j =1,3}, где: Г 2 u 1 = {x 2, x 3 }, Г 2 u 2 = {x 4 }, Г 2 u 3 = {x 5 }.

22 Аналитическое представление ультра графа образами и прообразами вершин и ребер Рассмотренное представление ультра графа, является полным, однако в ряде случаев затрудняет выполнение формальных преобразований и просмотр структуры ультра графа. Например, для того чтобы определить, каким вершинам инцидентно ребро u j U, необходимо проверить принадлежность этого ребра всем Г 1 x i и сформировать подмножество вершин согласно выражению: X j ={ x i X : u j Г 1 x i }. Аналогичное замечание справедливо и для определения множества ребер, которым инцидентна вершина x i X. Для задания таких множеств воспользуемся понятием «прообраз множества относительно предиката». По определению прообраз множества – это его образ относительно обратного предиката.

23 Аналитическое представление ультра графа образами и прообразами вершин и ребер Элементы обратных предикатов Г 2 -1 (X,U) и Г 1 -1 (U,X) определяются по правилам: u j U, x i X (Г 2 -1 (x i, u j ) = «и» : Г 2 (u j, x i ) = «и» ) и x i X, u j U (Г 1 -1 (u j, x i ) = «и» : Г 1 (x i, u j ) = «и») соответственно, т.е. таблицы истинности этих предикатов получаются транспонированием матриц истинности A 2 и A 1. Отсюда множество ребер U 2i, которым инцидентна вершина x i X – ее прообраз относительно предиката Г 2 (U,X), – это характеристическое множество i-го вектора строки матрицы истинности предиката Г 2 -1 (X,U) или i-го вектора-столбца матрицы А 2, т. е. предиката-свойства Г 2 x i (U): U 2i = Г 2 x i ={u j U : Г 2 x i (u j ) = «и» }, U 2i U. Прообразом множества X относительно предиката Г 2 (U,X) будет множество характеристических подмножеств предикатов- свойств Г 2 x i (U): Г 2 X= {Г 2 x i / x i X}.

24 Аналитическое представление ультра графа образами и прообразами вершин и ребер Аналогично множество вершин, которым инцидентно ребро u j U – его прообраз Г 1 u j относительно предиката Г 1 (X,U) –это характеристическое множество X 1j предиката-свойства Г 1 -1 u j (X), соответствующего j-у вектору-строке матрицы истинности предиката Г 1 -1 (U,X), или предиката-свойства Г 1 u j (X), задаваемого j-м вектором-столбцом матрицы А 1 : X 1j = Г 1 u j = { x i X : Г 1 u j (x i ) = «и» }, X 1j X. Прообразом множества U относительно предиката Г 1 (X,U) является множество характеристических подмножеств предикатов-свойств Г 1 u j (X): Г 1 U = {Г 1 u j / u j U }.

25 Аналитическое представление ультра графа образами и прообразами вершин и ребер Геометрическая интерпретация предикатов Г 1 -1 (U,X) и Г 2 -1 (X,U) показана на рисунке б. Г 2 X : Г 2 x 1 =, Г 2 x 2 ={u 1 }, Г 2 x 3 ={u 1 }, Г 2 x 4 ={u 2 }, Г 2 x 5 ={u 3 }, Г 1 U : Г 1 u 1 ={x 1, x 5 }, Г 1 u 2 ={x 1 }, Г 1 u 3 ={x 5 }. Для данного способа представления ультра граф будем обозначать H u (X, U, Г 1 X, Г 2 X, Г 1 U, Г 2 U).

26 Представление ультра графа матрицами смежности Предикат смежности вершин F 1 (X, X). Вершине x i смежна вершина x t, если существует ребро u j, инцидентное вершине x i, такое, что вершина x t инцидентна ему. Отсюда элементы матрицы смежности R 1 определяются по правилу: 1 – если a 1i,j =1 & a 2j,t =1, r 1i,t = 0 – в противном случае, где i, t =1, n; n = | X |, j =1, m; m = | U | R 1 =

27 Представление ультра графа матрицами смежности Предикат смежности ребер F 2 (U, U). Ребру u j смежно ребро u k, если существует вершина x i инцидентная ребру u j, такое, что ребро u k инцидентно ей. Отсюда элементы матрицы смежности R 2 определяются по правилу: 1 – если a 2j,i =1 a 1i,k =1, r 2j,k = 0 – в противном случае, где j,k =1,m; m = |U|, i =1,n; n = | X | R 2 = Совокупность предикатов F 1 (X, X) и F 2 (U, U) задает ультра граф не полностью

28 Образ и прообраз множества X относительно предиката смежности вершин F 1 (X, X) Образ и пробраз вершины x i – это характеристические множества предикатов-свойств F 1 x i (X), и F 1 -1 x i (X): F 1 x i =X 1i ={x j X : F 1 x i (x j ) = «и» }, X 1i X –вершины, смежныхее вершине x i X; F 1 -1 x i = X 1i -1 ={ x j X : F 1 -1 x i (x j ) = «и» }, X 1i -1 X –вершины, которым смежна вершина x i U. Они задаются i-ми вектором- строкой и вектором-столбцом матрицы R 1 соответственно: Для нашего ультра графа F 1 X = {F 1 x i / i =1,5}: F 1 -1 X = {F 1 -1 x i / i =1,5}: F 1 x 1 = {x 2, x 3, x 4 }, F 1 -1 x 1 =, F 1 -1 x 4 ={x 1 }, F 1 x 2 = F 1 x 3 = F 1 x 4 =, F 1 -1 x 2 ={x 1, x 5 }, F 1 -1 x 5 ={x 5 }. F 1 x 5 = {x 2, x 3, x 5 }, F 1 -1 x 3 ={x 1, x 5 }.

29 Образ и прообраз множества U относительно предиката смежности ребер F 2 (U, U). Образ и прообраз ребра u i – это характеристические множества предикатов-свойств F 2 u j (U) и F 2 -1 u j (U): F 2 u j = U 2j = { u i U : F 2 u j (u i ) = «и» }, U 2j U –ребра, смежныхее ребру u j U; F 2 -1 u j = U 2j -1 = { u i U : F 2 -1 u j (u i ) = «и» }, U 2j -1 U –ребра, которым смежно ребро u j U; Они задаются j-ми вектором-строкой и вектором-столбцом матрицы R 2 соответственно: Для рассматриваемого ультра графа F 2 U = {F 2 u j / j =1,3}: F 2 -1 U = {F 2 -1 u j / j =1,3}: F 2 u 1 = F 2 u 2 =, F 2 -1 u 1 ={u 3 }, F 2 u 3 ={u 1, u 3 }. F 2 -1 u 2 =, F 2 -1 u 3 ={u 3 }.

Гиперграфы Данный вид графа получим в соответствии со сформулированным выше определением при выполнении условий (1) в том случае, когда x i, x k X, u j U ((Г 1 (x i,u j )= «и» & Г 2 (u j,x i )= «и») (3, а) и u j U (|Г 2 u j | >2. (3, б) Условие (3) означает, что предикат-отношение Г 2 (U, X) является обратным к предикату-отношению Г 1 (X, U). Тогда гиперграф можно определить как два непересекающихся множества вершин X и ребер U, на элементах которых задана пара двуместных предикатов-отношений инцидентности Г 1 (X,U) и Г 2 (U,X) таких, что Г 2 (U, X)= Г 1 -1 (X, U).

31 Гиперграфы Вектор-строка таблицы истинности двуместного предиката- отношения Г 1 (X,U) – матрицы инцидентности вершины-ребра A 1 совпадает с вектором-столбцом таблицы истинности предиката Г 2 (U,X) – матрицы инцидентности ребра-вершины A 2. По определению предикаты эквивалентны, если их таблицы истинности совпадают. Отсюда следует, что: предикат-свойство Г 1 x i (U) – «вершине x i инцидентны ребра множества U» эквивалентен предикату-свойству Г 2 x i (U) – «вершина x i инцидентна ребрам множества U», предикат-свойство Г 2 u j (X) – «ребру u j инцидентны вершины множества X» эквивалентен предикату-свойству Г 1 u j (X) – «ребро u j инцидентно вершинам множества X».

32 Гиперграфы Отсюда, гиперграф будет полностью задан, если заданы множество вершин X, ребер U и один из предикатов Г 1 (X,U) или Г 2 (U,X). При геометрическом представлении гиперграфа в литературе вершины изображаются кружками, ребра – в виде контуров, а расположение вершины x i внутри ребра u j означает истинность Г 1 (x i,u j ), следовательно и Г 2 (u j,x i ).

33 Представление гиперграфов В качестве матрицы инцидентности A H будем использовать матрицу истинности предиката Г 1 (X,U). Аналитическое в форме H(X,U,Г 1 X,Г 2 U): u 1 u 2 u 3 X={x 1,x 2,x 3,x 4,x 5 }, U={u 1,u 2,u 3 }, x x Г 1 X ={ Г 1 x i / i=1,5}, где: Г 1 x 1 ={u 1,u 2 }, A H = x Г 1 x 2 =Г 1 x 3 ={u 1 }, Г 1 x 4 ={u 2 }, Г 1 x 5 ={u 1,u 3 }, x Г 2 U ={ Г 2 u j / j=1,3}, где: Г 2 u 1 ={x 1,x 2,x 3,x 5 }, x Г 2 u 2 ={x 1,x 4 }, Г 2 u 3 ={x 5 }.

34 Представление гиперграфа матрицами смежности Предикат смежности вершин F 1 (X, X). Элементы матрицы смежности R 1 гиперграфа по его матрице инцидентности определяются по правилу: 1 – если i k a i,j =1 a j,k =1, r 1i,k = 1 – если i=k a i,j =1 a j,k =1 f=1, 0 – в противном случае, где i,k =1,n; n=|X|, j =1,m; m=|U|, f= a j,k, a i,j и a j,k – элементы матрицы k=1,n инцидентности А H гиперграфа Условие i=k f=1 означает, что при вершине x i есть петля. R 1 =

35 Представление гиперграфа матрицами смежности Предикат смежности ребер F 2 (U, U). Элементы матрицы смежности R 2 гиперграфа по его матрице инцидентности определяются по правилу: 1 – если a j,i =1 a i,k =1, r 2j,k = 0 – в противном случае, где j,k =1,m; m=|U|, i =1,n; n=|X|, a j,i и a i,k – элементы матрицы инцидентности А H гиперграфа R 2 =

36 Образы вершин гиперграфа относительно предиката смежности F 1 Для каждой вершины x i X гиперграфа H(X, U) ее образ F 1 x i относительно предиката смежности F 1 (X, X) (множество смежныхех ей вершин X i ) определяется характеристическим множеством предиката-свойства F 1 x i ( X) X i = F 1 x i = {x k X : F 1 x i (x k ) = «и»}. Истинность предиката-свойства F 1 x i (X) задается i-м вектором- строкой матрицы R 1. Для рассматриваемого гиперграфа множество образов F 1 X ={ F 1 x i / x i X } его вершин будет: F 1 X = {F 1 x i / i =1,5}: F 1 x 1 = {x 2, x 3, x 4, x 5 }, F 1 x 2 ={x 1, x 3, x 5 }, F 1 x 3 = {x 1, x 2, x 5 }, F 1 x 4 = { x 1 }, F 1 x 5 = {x 1, x 2, x 3, x 5 }.

37 Образы ребер гиперграфа относительно предиката смежности F 2 Образ F 2 u j ребра u j U гиперграфа H(X, U) относительно предиката F 2 (U, U), т. е. множество U j смежныхех ему ребер, определяется характеристическим множеством предиката-свойства F 2 u j (U): U j = F 2 u j = { u k U: F 2 u j (u k ) = «и» }. Истинность предиката F 2 u j (U) задается j-м вектором-строкой матрицы R 2. Для нашего гиперграфа : F 2 U = {F 2 u j / j =1,3}: F 2 u 1 = {u 2, u 3 }, F 2 u 2 = {u 1 }, F 2 u 3 = {u 1, u 3 }. Так же как для ультра графа, совокупность матриц смежности, а также образов множеств вершин X и ребер U гиперграфа H(X,U) относительно предикатов смежности вершин F 1 (X,X) и ребер F 2 (U,U) задает гиперграф не полностью.

Обыкновенные ориентированные графы Этот вид графа получим в том случае, если предикаты Г 1 (X,U) и Г 2 (U,X) таковы, что u j U (|Г 1 u j | = |Г 2 u j |=1), (5) т. е. в графе нет ребер, суммарное количество вершин, которым оно инцидентно и которые инцидентны ему, больше двух. Данное условие допускает возможность существования в ориентированном графе петель. Из анализа (2) и (5) видно, что обыкновенный ориентированный граф является частным случаем ультра графа. Ребра ориентированного графа G(X,U) обычно в литературе называют дугами и изображают стрелками, соединяющими соответствующие пары вершин. С учетом (1) примем такое же изображение, имея в виду, что дуга u j идет из вершины x i в вершину x k, если Г 1 (x i,u j ) = «и» Г 2 (u j,x k ) = «и», и соединяет вершину x k с вершиной x i, если Г 1 (x k,u j ) = «и» Г 2 (u j,x i ) = «и».

39 Представление ориентированного графа Матрицы инцидентности A 1 и A 2 этого графа определяются так же как и ультра графа. Образы и прообразы вершин и ребер относительно предикатов Г 1 и Г 2 соответственно: X={x 1, x 2, x 3, x 4 }, U={u 1, u 2, u 3, u 4, u 5 }, Г 1 X ={Г 1 x i / i=1,4}, где: Г 1 x 1 = {u 1, u 2 }, Г 1 x 2 ={u 3 }, Г 1 x 3 ={u 4 }, Г 1 x 4 ={u 5 }, Г 2 U ={ Г 2 u j / j=1,5}, где: Г 2 u 1 = Г 2 u 4 = {x 2 }, Г 2 u 2 = {x 4 }, Г 2 u 3 = Г 2 u 5 = {x 4 }, Г 2 X ={Г 2 x i / i=1,4}, где: Г 2 x 1 = Г 2 x 3 =, Г 2 x 2 ={u 1, u 4 }, Г 2 x 4 = {u 2,u 3,u 5 }, Г 1 U ={ Г 1 u j /j=1,5}, где: Г 1 u 1 =Г 1 u 2 ={x 1 }, Г 1 u 3 ={x 2 }, Г 1 u 4 ={x 3 }, Г 1 u 5 ={x 4 }. Для данного способа представления ориентированный граф будем обозначать G(X, U, Г 1 X, Г 2 X, Г 1 U, Г 2 U).

40 Смежность вершин и ребер ориентированного графа Для ориентированного графа элементы матриц смежности вершин R 1 и ребер R 2, их образы и прообразы относительно предикатов смежности F 1 (X,X) и F 2 (U,U) определяются так же как и для ультра графа. X={x 1, x 2, x 3 }, U={u 1, u 2, u 3, u 4 }, F 1 X = {F 1 x i /i =1,3}: F 1 x 1 = {x 2, x 3 }, F 1 x 2 ={x 3 }, F 1 x 3 = {x 1 }, F 1 -1 X = {F 1 -1 x i /i =1,3}: F 1 -1 x 1 ={x 3 }, F 1 -1 x 2 ={x 1 }, F 1 -1 x 3 ={x 1, x 2 }. F 2 U = {F 2 u j / j =1,4}: F 2 u 1 = {u 4 }, F 2 u 2 = {u 3 }, F 2 u 3 = { u 1,u 2 }, F 2 u 4 ={u 3 }, F 2 -1 U = {F 2 -1 u j / j =1,4}: F 2 -1 u 1 = F 2 -1 u 2 ={u 3 }, F 2 -1 u 3 ={u 2, u 4 }, F 2 -1 u 4 ={u 1 }.

Обыкновенные неориентированные графы Неориентированный граф можно определить как два непересекающихся множества вершин X и ребер U, на элементах которых задана пара двуместных предикатов- отношений инцидентности Г 1 (X,U) и Г 2 (U,X), удовлетворяющих условиям (1), (3, а) и u j U (|Г 1 u j | = |Г 2 u j |=1). Таким образом ребра обыкновенного неориентированного графа соединяют вершины попарно, а предикат Г 2 (U,X) на основании (3, а) является обратным к предикату Г 1 (X,U). Из сказанного выше следует, что неориентированный граф является частным случаем гиперграфа. Обыкновенный неориентированный граф будет задан, если заданы множества X, U и один из этих предикатов. Ребра неориентированного графа изображают линиями, соединяющими вершины.

42 Представление неориентированного графа Образы вершин и ребер относительно предикатов Г 1 и Г 2 : X={x 1, x 2, x 3, x 4 }, U={u 1, u 2, u 3, u 4, u 5,u 6 }, Г 1 X ={Г 1 x i /i=1,4}, где: Г 1 x 1 = {u 1 }, Г 1 x 2 ={u 1,u 2,u 3,u 5 }, Г 1 x 3 = {u 1,u 4,u 5,u 6 }, Г 1 x 4 ={ u 2,u 4 }, Г 2 U={ Г 2 u j / j=1,6}, где: Г 2 u 1 = {x 1, x 2 }, Г 2 u 2 = {x 2, x 4 }, Г 2 u 3 = {x 2, x 3 }, Г 2 u 4 = { x 3, x 4 }, Г 2 u 5 = { x 2, x 3 }, Г 2 u 6 = {x 3 }. Аналитическое представление неориентированного графа, G(X, U, Г 1 X, Г 2 U), так же как и матричное, является полным В качестве матрицы инцидентности A H обычно используют матрицу истинности предиката Г 1 (X,U). АH=АH=

43 Смежность вершин и ребер неориентированного графа Для неориентированного графа элементы матриц смежности вершин R 1 и ребер R 2 и их образы относительно предикатов смежности F 1 (X,X) и F 2 (U,U) определяются так же как и для гиперграфа. X={x 1, x 2, x 3, x 4 }, U={u 1, u 2, u 3, u 4 }, F 1 X = {F 1 x i /i =1,4}: F 1 x 1 = {x 2 }, F 1 x 2 ={x 1,, x 3, x 4 }, F 1 x 3 ={x 2, x 4 }, F 1 x 4 = {x 2, x 3 }, F 2 U = {F 2 u j / j =1,4}: F 2 u 1 = {u 2, u 3 }, F 2 u 2 = {u 1,u 3, u 4 }, F 2 u 3 = { u 1,u 2, u 4 }, F 2 u 4 ={u 2, u 3 },

Характеристики вершин и ребер графов Характеристики вершин ультра- и ориентированного графа : + (x i ) – полустепень исхода, т. е. количество ребер, инцидентных вершине x i X: + (x i ) = | Г 1 x i | ; - (x i ) – полустепень захода, т. е. количество ребер, которым инцидентна вершина x i X: - (x i ) = | Г 2 x i | ; s + (x i ) – количество вершин, смежныхех вершине x i : s + (x i )= | F 1 x i | ; s - (x i ) – количество вершин, которым смежна вершина x i : s - (x i )= | F 1 -1 x i |. e(x i ) = |{ u j U : Г 1 u j = Г 2 u j = x i }| – количество петель при вершине x i. У ориентированного графа без кратных ребер s + (x i ) = + (x i ) и s - (x i ) = - (x i ).

45 Характеристики вершин и ребер графов Характеристики ребер ультра- и ориентированного графа : A + (u j ) – количество вершин, инцидентных ребру u j U : A + (u j )= | Г 2 u j | ; A - (u j ) – количество вершин, которым инцидентно ребро u j U : A - (u j )=| Г 1 u j | ; s + (u j ) – количество ребер, смежныхех ребру u i : s + (u j ) =| F 2 u j |; s - (u j )– количество ребер, которым смежно ребро u i : s - (u j ) =| F 2 -1 u j |;

46 Характеристики вершин и ребер графов Характеристики вершин гипер- и неориентированного графа : (x i ) –локальная степень вершины, т. е. количество ребер, инцидентных вершине x i X. (x i ) = | Г 1 x i | ; s(x i ) – количество вершин, смежныхех вершине x i X : s(x i )= |F 1 x i | ; e(x i ) – количество петель при вершине : e(x i )=|{u j Г 2 x i : | Г 2 u j |=1}|. Характеристики ребер гипер- и неориентированного графа: A(u j )– количество вершин множества X, инцидентных ребру u j : (u j ) = | Г 2 u j | (только для гиперграфа); s(u j ) – количество ребер, смежныхех ребру u j U : s(u j )= |F 2 u j |.

Некоторые особенные графы Конечный, пустой и смешанный графы. Граф G(X,U) называется конечным, если число его вершин |X|=n конечно. Граф G(X,U), у которого X = и U =, т. е. не содержащий ни вершин, ни ребер, называется пустым и обозначается G. Граф, на вершинах и ребрах которого заданы две пары двуместных предикатов-отношений инцидентности таких, что для первой пары справедливы (1) и (5), а для второй – (1), (3) и (5), называется смешанным. Смешанный Неориентированный Ориентированный

48 Полный и однородный неориентированный графы Количество ребер неориентированного графа определяется через локальные степени вершин как: n m =½ (x i ), где |X| = n. i=1 Неориентированный граф называется полным, если каждая из его вершин соединена ребрами с остальными, т. е. ( x i X) (F 1 x i =X \ x i ). У полного графа (x i ) = n-1, откуда число его ребер m= n(n-1)/2. Граф называется однородным степени К, если ( x i X) (x i )=К. Полный граф Однородный граф K=3

49 Полный ориентированный граф Количество ребер ориентированного графа n n r = (x i ) или r = (x i ). i=1 i=1 Ориентированный граф называется полным, если: ( x i, x j X) ( u k, u t U )(Г 1 u k = Г 2 u t = {x i } Г 2 u k = Г 1 u t ={x j } i j k t), т. е. у каждой пары вершин существует по две дуги, по одной в каждом направлении. Число ребер полного ориентированного графа – m = n(n-1). Полный ориентированный граф

50 Двудольный граф (граф Кенига) Граф называется двудольным или графом Кенига, если его множество вершин Х распадается на два непересекающихся подмножества Х 1 и Х 2, таких, что существуют отношения смежности между элементами этих множеств и не существует таких отношений между элементами каждого множества, т. е.: ( x i,x j X 1 ) x j F 1 x i, ( x k,x t X 2 ) x t F 1 x k - для неориентированных и ( x i,x j X 1 ) x j F 1 x i & x j F 1 -1 x i, ( x k,x t X 2 ) x t F 1 x k & x t F 1 -1 x k – для ориентированных. Смешанный Неориентированный Ориентированный

51 Мультиграф Граф, у которого хотя бы для двух ребер u j,u l U справедливо Г 2 u j = Г 2 u l Г 1 u j = Г 1 u l, называется мультиграфом, а максимальное количество кратных ребер – мультичислом. Мультичисло: неориентированных ребер r = 3, ориентированных – r = 2

52 Маршрут, цепь, цикл Последовательность смежныхех ребер неориентированного графа без петель и кратных ребер называется маршрутом. В общем случае ребра в маршруте могут встречаться неоднократно. Если все ребра маршрута различны, он называется цепью. Замкнутая цепь называется циклом. Маршрут х 1,х 2,х 3,х 5,х 2,x1,х 4 х 1,х 2,х 3,х 5,х 2,x1,х 4 Цепь х 1,х 2,х 3,х 4,x 2,х 5 Цикл х 1,х 2,х 3,х 5,х 2,х 4,х 1 Цепи и циклы будут простыми, если они не содержат повторяющихся вершин, например, х 1,х 2,х 3,х 4,х 5 – простая цепь, а х 1,х 2,х 3,х 4,х 1 – простой цикл.

53 Эйлеров и гамильтонов циклы Цикл, включающий все ребра графа, называется эйлеровым. Связный граф содержит эйлеров цикл, если локальные степени всех его вершин – четные, т. е. ( x i X) (x i ) 0. mod 2 Простой цикл, проходящий через все вершины графа, называется гамильтоновым. Это понятие используется при определении планарности графа. Граф G имеет гамильтонов цикл, если сумма локальных степеней любой пары вершин больше или равна числу его вершин, т. е. x i, x j X ( (x i ) + (x j )) n, i j, |X|=n, например, х 1, х 2, х 5, х 3, х 4, х 1.

54 Связность графа Две вершины x i, x j X называются связанными, если в графе G(X,U) существует маршрут S = S(x i,x j ). Граф G – связный, если любые две его вершины связаны, т. е. ( x i, x j X) S(x i,x j ). Ребро, удаление которого приводит к разбиению графа на две компоненты связности, называется перешейком. Вершина называется расщепляющейся, если в ней можно граф разделить на две или более компоненты связности путем ее дублирования. Перешеек Расщепляющаяся вершина

55 Деревья Связный граф, не имеющий циклов, называется деревом. Начальная вершина дерева называется корнем, выходящие из него ребра – ветвями. Дерево, имеющее n вершин, содержит m=n-1 ребер. На одних и тех же n вершинах можно построить t n = n n-2 различных деревьев. Дерево называется покрывающим граф или остовным, если оно содержит все его вершины. Звездное Последовательное

56 Части графа Граф G i (X i,U i ) называется частью графа G(X,U), если он находится в отношении включения к нему G i G, т. е. X i X и U i U. Часть графа G i (X i, U i ) называется куском, если X i X, U i U, причем в U i входят все ребра, инцидентные X i. Множество ребер куска таково, что U i = U i,i U i,j, где U i,i – множество ребер, оба конца которых инцидентны X i, а U i,j – множество ребер, один конец которых инцидентен X i, а второй – X j =X \ X i. Часть графа G i (X i, U i ) называется подграфом, если X i X, U i U, т. е. подграф образуется удалением из графа некоторых вершин и всех инцидентных им ребер. Часть графа G i (X i, U i ) называется суграфом, если X i = X, а U i U, т. е. суграф получается удалением из графа части ребер. Граф Кусок графа ПодграфСуграф

57 Минимальные массивы Множество X i вершин куска H i (X i,U i ) гиперграфа H(X,U) называется минимальным массивом, если удаление из него любой вершины приводит к увеличению количества внешних ребер, т. е. для любого куска H i(X i,U i), в котором X i X i, справедливо (X i ) > (X i ), где (X i ) и (X i ) – количество внешних ребер кусков H i и H i. Минимальный массив {x i,x j } Свертка минимального массива

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

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

Представление схемы ультра графом Ультраграф является универсальной (обобщенной) моделью, так как позволяет в общем случае отобразить всю информацию, необходимую для решения широкого класса задач.. Модель схемы в виде ультра графа необходима в тех случаях, когда: существенной является информация о принадлежности подсистем соединениям с указанием является подсистема источником сигнала для данной цепи или приемником из нее; количество подсистем проектируемого объекта, являющихся источниками/приемниками информации, более одного, т.е. в схеме есть цепи, соединяющие более двух подсистем. К числу таких задач можно отнести, например, задачи идентификации и покрытия, временного анализа топологической реализации схемы и др.

61 Представление схемы ультра графом Для этих задач адекватность математической модели объекту следует рассматривать в смысле полноты и правильности отображения той информации, которая характеризует ее функционирование. В частности для задач покрытия и идентификации – тех свойств схемы, которые определяют логику ее работы. Тогда в математической модели системы необходимо отобразить следующую информацию о ней: имена и функции подсистем, в том числе и монтажной логики; имена цепей и, возможно, передаваемых по ним сигналов; связанность подсистем как некоторой цепью, так и в системе в целом; принадлежность подсистем цепям с точностью до вывода с учетом направления распространения сигнала; допустимые значения времени распространения сигналов от подсистем -источников к подсистемам-приемникам.

62 Представление схемы ультра графом При разработке математической модели системы в общем случае будем рассматривать множества подсистем (компонентов) структуры сложной системы П, их типов ТП, контактов К, множество соединений C и имен сигналов V. В модели необходимо отобразить подключена ли связь к входу или выходу компонента. Свойства, которые определяют является ли компонент источником сигнала в цепь или наоборот, задаются высказываниями: – « к выходам подсистем П подключены соединения С» и – « соединения С подключены к входам подсистем П». Обозначим эти высказывания как Пр 1 (П, С) и Пр 2 (С, П) соответственно.

63 Представление схемы ультра графом Адекватность ультра графа как структурной модели в указанных выше условиях обеспечивается следующими правилами перехода: – множеству подсистем структуры П и множеству соединений С поставим во взаимно однозначное соответствие множества вершин ультра графа X и ребер U; – типы подсистем отобразим, задав однозначное (сюръективное), возможно взаимно однозначное, соответствие множеств X и ТЭ; – имена сигналов, передаваемых по соединениям С, отобразим, задав взаимно однозначное, возможно однозначное, соответствие множеств U и V; – свойства Пр 1 (П, С) и Пр 2 (С, П) формально зададим предикатами Г 1 (X, U) и Г 2 (U, X) соответственно.

64 Представление схемы ультра графом Формальная запись правил перехода от структуры системы к ее модели в виде ультра графа H U (,, Г 1, Г 2 ) имеет вид: П X, С U, X ТЭ (X ТЭ), U V (U V), S 1 (П, С) ~ Г 1 (X, U), S 2 (С, П) ~ Г 2 (U, X).

65 Представление схемы ультра графом Информации о номерах выводов подсистемы и времени распространения сигнала от подсистемы-источника до каждого из подсистем-приемников в данной цепи может быть задана присваиванием весов вершинам и/или ребрам ультра графа. Множества образов и прообразов рёбер показанного ультра графа будут: : = { x 3, {03,04}, x 4, 02 }, = { x 4, 03>}, = { x 3, 05>, x 4, 04>}; : = { x 1, 10>, x 2, 14>}, = { x 2, 16>}, = { x 2, 18>}. Такой ультра граф будем обозначать H U (, U, V >, Г 1 X, Г 2 X,, ).

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

Представление структуры объекта гиперграфом и неориентированным графом В соответствии с характерными особенностями задач декомпозиции/композиции, размещения, трассировки и др. математическая модель системы должна: задавать принадлежность подсистем соединениям; позволять точно оценивать число соединений между подсистемами и частями системы; не диктовать порядок соединения подсистем, т. е. отражать фактор неизвестности соединения в пределах одной цепи; нести информацию о метрических параметрах и топологических свойствах подсистем и, возможно, соединений. При этом: характер принадлежности связи (вход или выход) не существенен; Адекватной моделью системы, если в ней есть цепи, соединяющие более двух подсистем является гиперграф.

68 Представление структуры объекта гиперграфом и неориентированным графом Для решения указанных задач в математической модели системы должна быть отображена следующая информация: имена подсистем, их связанность с точностью до вывода; принадлежность подсистем цепям, которые определяются своими именами и, возможно, характеризуются типами; метрические параметры подсистем (их размеры и размеры полей контактов); координаты подсистем и полей контактов (после решения задачи размещения); топологические свойства подсистем, обусловливающие ограничения на построение соединений (порядок расположения выводов, допустимость прохода соединений между ними и под подсистемой); возможные варианты топологической реализации или ориентации подсистем и сведения об инвариантности выводов.

69 Представление схемы гиперграфом При переходе от схемы к гиперграфу: множеству элементов Э поставим во взаимнооднозначное соответствие множество вершин Х : Э X, множеству цепей С – множество ребер U: C U, где n = |Э| и m = |C| – количество элементов и цепей схемы. Принадлежность цепей элементам и наоборот задается предикатами инцидентности Г 1 (X,U) и Г 2 (U,X) соответственно: Пр 1 (Э,С) ~ Г 1 (X,U), Пр 2 (С,Э) ~ Г 2 (U, X). Отношение связанности элементов цепью с j задается предикатом- свойством Г 2 u j (X). Это - множество вершин X j = Г 2 u j. X = {x 1, x 2, x 3, x 4 }, U= {u 1, u 2, u 3 }, Г 1 x 1 = Г 1 x 3 = U 1 = U 3 = {u 1, u 2 }, Г 1 x 2 = Г 1 x 4 = U 2 = U 4 = {u 2, u 3 }, Г 2 u 1 =X 1 = {x 1, x 3 }, Г 2 u 2 =X 2 = {x 1, x 2, x 3, x 4 }, Г 2 u 3 =X 3 = {x 2, x 4 }.

70 Представление схемы гиперграфом с точностью до выводом элементов Типы элементов, а также имена или типы цепей в гиперграфе можно отобразить, задав однозначное соответствие множества Х в множества типов элементов TЭ: X TЭ и взаимно однозначное отображение множества U в множество типов цепей V: U V. Принадлежность элемента э i Э цепи с j C с точностью до вывода может быть определена следующим образом: для отображения Г 2 U каждой вершине x i Г 2 u j ставится в многозначное соответствие множество контактов элемента э i x i, принадлежащее цепи с j u j. для отображения Г 1 Х каждому ребру u j Г 1 x i ставится в многозначное соответствие множество контактов элемента э i x i входящих в цепь с j u j. В результате применения указанных правил получаем гиперграф в форме H(,,, ).

71 Представление схемы взвешенным гиперграфом Гиперграф в форме H(,U, Г 1 X, ). X = {,,, }, Г 2 u 1 = X 1 = {x 1, x 3 }, K 1 = {5,4}, Г 2 u 2 =X 2 = {x 1, x 2, x 3, x 4 }, K 2 = {11,8,5,2}, Г 2 u 3 = X 3 = {x 2, x 4 }, K 3 = {12,11} или : Г 2 u 1 = X 1Т = {, }, Г 2 u 2 = X 2Т = {,,, }, Г 2 u 3 = X 3Т = {, }.

72 Определение связности элементов по гиперграфу Для того, чтобы определить, соединены ли элементы э i и э k с цепью с j, достаточно проверить условие x i, x k X j. Так как один элемент схемы может принадлежать разным цепям, то в общем случае X t X j X t Гu t X j Гu j t, j M =1,m. Решающее правило определения множества С 1,2 и количества s 1,2 цепей, соединяющих две подсхемы, множества элементов которых Э 1 Э и Э 2 Э соответственно(Э 1 Э 2 = ) будет: U 1,2 = Г 1 (X 1 ) Г 1 (X 2 ), С 1,2 U 1,2 и s 1,2 = | U 1,2 |, где X 1 Э 1 и X 2 Э 2. Следовательно, по гиперграфу можно точно оценить количество электрических соединений между частями или элементами схемы. Так как множество X j =Г 2 u j неупорядоченно, то последовательность записи в нем вершин гиперграфа не диктует порядок соединения соответствующих им элементов схемы - гиперграф отражает фактор неизвестности порядка соединения элементов цепью.

73 Представление схемы неориентированным графом Такая модель, как правило, используется для задач коммутации. В ней необходимо отобразить: элементы объекта, их характеристики и координаты; возможно, функциональное назначение элементов объекта; связи между элементами и их характеристики. Ранее было указано, что обыкновенный неориентированный граф является частным случаем гиперграфа – в нем нет ребер с суммарным количеством инцидентных вершин большим двух. Следовательно, эта модель может быть корректной только для объектов, элементы которых связаны попарно и для решения задачи несущественно является элемент источником или приемником. В этом случае она позволяет правильно оценить количество связей между элементами и частями объекта.

74 Пример представления схемы неориентированным графом Правила перехода от объекта (схемы соединения элементов) к неориентированному графу такие же, что и для гиперграфа. Если функциональное назначение связей и/или их характеристики различны, необходимо функции и/или характеристики отразить в графе в виде весов ребер, так как отношение связанности на графе обладает свойством транзитивности. Тогда, чтобы обеспечить получение компоненты связности объекта, соответствующей определенной функции, отношение транзитивности в графе необходимо строить по ребрам, имеющим одинаковый вес.

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

Математические модели монтажного пространства Математические модели монтажного пространства используются для задач размещения и трассировки. Сущность этих задач – определение положения, которое будут занимать соединения и подсистемы (элементы) в монтажной области объекта. В математической модели монтажного пространства с учетом метрических параметров, характеристик и топологических свойств объекта, его компонентов и связей между ними, должны быть формальным образом заданы возможные позиции реализации фрагментов соединений или компонентов объекта. Нередко монтажное пространство объектов, в том числе конструктивных модулей средств ЭВТ имеет прямоугольную форму и регулярное расположение позиций. Это в наибольшей степени удовлетворяет требованию конструктивно-технологической унификации. Позиции установки подсистем (элементов) предыдущего ранга фиксированы и имеют, как правило, постоянный шаг. При разработке топологии ИС и БИС и проектировании субблока на разногабаритных элементах нельзя заранее зафиксировать позиции для размещения элементов. Монтажное пространство в этом случае является нерегулярным.

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

78 Модель монтажной плоскости фрагмента верхнего слоя печатной платы с ортогональным монтажом при запрещении проведения проводников под микросхемами Если проводники разрешается проводить под углом 45°, каждой вершине может быть инцидентно восемь ребер.

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

80 Математические модели монтажного пространства (4) Расстояние между i-м и j-м узлами графа решетки в общем случае будет d i,j = (|S i -S j | k +|t i -t j | k ) h ; i,j =1,m; k = (1; 2); h = (0,5; 1), где m число узлов графа решетки. При ортогональной трассировке k = h = 1, выражение принимает вид d i,j = |S i -S j | + |t i -t j |. Для регулярного монтажного пространства в качестве модели поля размещения может быть использован граф решетки, вершины которого сопоставлены установочным позициям типовых конструкций предыдущего уровня.

81 Приближенный подсчет суммарной длины соединений между модулями Пусть моделью схемы соединений является неориентированный мультиграф G с взвешенной матрицей смежности М F : Для графа G, отображенного в решетку G r, строится матри- ца расстояний D r : Dr =Dr = MF =MF = Матрица геометрии D y получается поэлементным умножением матриц M F и D r : D у = D r M F = Откуда суммарная длина ребер L(G) = 25.

Математические модели структур данных Отображение данных в память ЭВМ требует реализации содержа- тельных связей между их отдельными частями, т. е. организации упорядоченного представления информации в виде структур данных. Структуры данных для представления графов должны позволять выполнение формальных преобразований над ними и обеспечивать высокую эффективность этих преобразований и экономное использование памяти. Представление графа в памяти ЭВМ должно отображать в виде струк- тур данных отношения смежности и инцидентности, заданные на множествах Х и U, а также, возможно, дополнительные отношения, позволяющие снизить вычислительную сложность выполнения некоторой или совокупности операций. Различные структуры данных имеют свои достоинства и недостатки, которые поразному проявляются в алгоритмах решения конкретных задач. От используемого способа организации множеств и мультимножеств, задающих граф, и связей между ними в значительной степени зависит вычислительная сложность алгоритмов и память, требуемая для хранения данных. Базовыми структурами памяти для хранения множеств являются вектор и линейный односвязный список.

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

84 Требования к моделям структур данных Таким образом в модели необходимо отобразить следующую информацию о структуре данных: – адреса элементов памяти; – содержимое элементов памяти, которое может быть как данными об объекте проектирования, так и адресами-указателями элементов рассматриваемой или другой структуры; – достижимость элементов памяти извне и от других; – наличие данного (адреса-указателя) в элементе памяти; – вычислительную сложность операций над данными, обеспечиваемую этой структурой; – объем, необходимый для хранения содержимого элемента памяти.

85 Выбор или разработка структур данных Полный анализ применимости различных структур данных должен включать оценку вычислительной и емкостной сложности алгоритма. Точная оценка сложности реализации алгоритма для каждого представления графа очень трудоемка, поэтому для выбора структур данных целесообразно использовать оценки трудоемкости выполнения операций на графе, часто используемых в рассматриваемом алгоритме. Комбинированные одноуровневые структуры данных позволяют сочетать достоинства и избежать недостатков базовых и производных структур. Выбор базовых или разработка комбинированных структур данных должны основываться: на оценках вычислительной сложности учитываемых операций над структурами данных; количестве повторений этих операций, что, как правило, определяется размерностью представляемых множеств.

86 Вектор Векторное представление данных имеет следующие преимущества: непосредственный доступ к любому элементу массива, быстрая и эффективная обработка всех данных или выделенных подмножеств благодаря индексной адресации; минимальная потребность в отслеживании различных имен групп данных за счет представления этих групп в виде одного массива; эффективное использование памяти ЭВМ, так как для организации векторной структуры не требуется дополнительной памяти. Недостатком векторного представления является довольно высокая трудоемкость выполнения операций удаления/добавления элемен- тов векторов (если нельзя заменять последним и добавлять в конец) или некоторой их последовательности,. Вектором называют однородный линейный массив фиксированной длины. Это – одномерная после- довательность элементов данных одного типа и размера, которая отображается в последователь- ную память.

87 Односвязный и двусвязный списки Линейный односвязный список – это линейный массив перемен-ного размера, каждый элемент которого представляет собой пару, состоящую из информаци-онной части и указателя на следующий. Двусвязный список. В двусвязном списке существует указатель предыдущего i–1-го компонента и указатель конца списка, что обеспечивает дополнительный порядок обработки – от конца списка к его началу. Это устраняет необходимость операций поиска последнего и предыдущего элемента.

88 Односвязный и двусвязный списки Для списковых структур характерны следующие преимущества: - низкая трудоемкость выполнения операций удаления/добавления данных; - простота последовательного доступа к элементам данных, содержательные связи между которыми реализованы указателями списка. Однако списковые структуры не обеспечивают прямого доступа к данным и эффективного использования памяти, так как для указателей требуется дополнительный объем памяти, который может превышать память, хранящую данные.

89 Комбинированные одноуровневые структуры данных Такие структуры позволяют эффективно выполнять операции прямого доступа к элементам множества, являющегося подмножеством универсума, и операции удаления/ добавления его элементов, сохраняя порядок их следования. Прямой доступ обеспечивается вектором P, размер которого равен количеству элементов универсума, а i -м элементом является указатель на элемент списка, в котором хранятся x i и S i.

90 Модель вектора Основными компонентами вектора данных как непрерывной последовательности элементов памяти, являются множество адресов элементов – A Э, адрес базы – а Б и множество значений элементов – З Э. Непрерывное размещение элементов предполагает, что к любому из них можно обратиться непосредственно, определив его смещение относительно адреса базы вектора по номеру и длине элемента. Для элементов вектора определены понятия первый, последний, следующий и предыдущий, т.е. на них задано отношение порядка, при этом адрес каждого элемента может быть получен из адреса любого предыдущего или последующего.

91 Модель вектора Возможность непосредственного доступа к элементам памяти определяет свойство достижимости адресов множества A Э из адреса а Б – Д(а Б, A Э ). Такой непосредственный доступ описывается отношением Ra – «ключ – любой элемент записи множества», в котором ключом является адрес базы а Б, а множество координат K – множеством адресов A Э. Модель вектора элементов памяти GSa (Z, Fz Б ), отражающую их достижимость от базы, получим по следующим правилам: А Z, где А = {а Б, A Э }, Д(а Б, A Э ) F1(z Б, Z). Здесь Z = {z Б, Z Э }, Z Э A Э, z Б а Б, а F 1 (z Б, Z) – предикат смежности, такой, что F 1 z Б = Z Э F 1 -1 z Б =, z i Z Э (F 1 z i = ).

92 Модель вектора Модели достижимости адресов вектора: достижимость адресов из адреса базы (а), достижимость адреса из любого другого б) и их объединение (в)

93 Модель вектора Достижимость элемента памяти от любого другого Д(A Э, A Э ) реализуется отношением Rm «текущий – все предыдущие и следующие». Моделью вектора элементов памяти в данном аспекте будет полный ориентированный граф GSm (Z Э, FZ Э ), в котором Z Э – то же, что и выше, Д(A Э, A Э ) F 2 (Z Э, Z Э ) и z i Z Э (F 2 z i = Z Э \ z i ). Граф GSm (Z Э, F 2 Z Э ) изображён на рис. б. Следовательно, модель достижимости адресов векторной структуры памяти, показанная на рис. в, будет определяться как G A (Z Э, F A Z), = GSa (Z, F 1 z Б ) GSm (Z Э, F 2 Z Э ), где F A Z = {F 1 z Б, F 2 Z Э }.

94 Модель вектора Наличие значения зн i в элементе памяти с адреcом а i задает отношение достижимости Д(А Э, З Э ). Это отношение является вырожденным случаем отношения D «координата элемента в записи множества B соответствует координате ассоциированного с ним элемента в записи множества С». В данном аспекте его можно определить как «координате элемента в записи множества B соответствует элемент записи множества С». Модель вектора элементов памяти, отражающая тот факт, что значение элемента з Эi находится в элементе памяти с адреcом а i, получим по следующим правилам: A Э Z Э, З Э Y и Д(А Э, З Э ) F 3 (Z Э, Y). Для предиката F 3 (Z Э, Y) справедливо: z i Z Э (F 3 z i = y i ), y i Y(F 3 y j = ) и y i = F 3 z i y i = F 3 z k z i = z k.

95 Модель вектора Тогда моделью достижимости значений данных будет граф G З ({Z Э, Y}, F 3 Z Э ), в котором Z Э Y = (см. рис а на следующем слайде). Этот граф представляет собой двудольный ориентированный граф, состоящий из n компонент связности: G З = {g зi ({z i, y i }, F 3 z i ) / i = 1, n }, где n = |Z Э |. Окончательно моделью вектора данных, отображающую как достижимость элементов памяти, так и принадлежность значения данного этому элементу, будет граф G V ({Z, Y}, FZ) = G A (Z, F A Z) G З ({Z э, Y}, F 3 Z э ), в котором FZ Э = {F 1 z Б, F 2 Z Э, F 3 Z Э }. Эта модель показана на рис. б следующего слайда.

96 Модель вектора Модели достижимости значений данных (а), вектора данных (б) и вектора упорядоченных данных (в)

97 Модель двусвязного списка Переход от списковой структуры к его модели в виде ориентированного графа проиллюстрируем на примере двусвязного списка. В моделях указателей начала и конца списка необходимо отобразить их адреса а у.н и а у.к, адреса первого а 1 и последнего а m элементов списка и достижимости Д(а у.н, а 1 ) и Д(а у.к, а m ). Это отношения Rf «ключ – первый элемент» и Rl «ключ – последний элемент» записи множества. В списке ключам доступа к элементам записи множества kf и kl соответствуют адреса указателей начала и конца списка а у.н и а у.к. Модель списка получим по следующим правилам. Поставим во взаимно однозначное соответствие адресам указателей начала и конца списка A у = {а у.н, а у.к } вершины множества Z у = {z у.н, z у.к }: а у.н z у.н, а у.к z у.к,

98 Модель двусвязного списка адресам элементов списка A Э – вершины множества Z ЭD, значениям элементов данных З Э – вершины множества Y D : A Э Z ЭD, З Э Y D. Отношения достижимости первого и последнего элементов списка сопоставим предикатам смежности, определённым на вершинах {z у.н, z 1 } и {z у.к, z m }: Д(а у.н, а 1 ) F(z у.н, z 1 ) и Д(а у.к, а m }) F(z у.к, z m ). Тогда моделями указателей начала и конца списка будут соответственно следующие ориентированные графы (см. рис. а на следующем слайде): g у.н ({z у.н, z 1 }, F{z у.н, z 1 }), где Fz у.н = {z 1 }, Fz 1 =, z 1 Z ЭD или g у.н ({z у.н, z 1 }, Fz у.н ) и g у.к ({z у.к, z m }, F{z у.к, z m }), где Fz у.к = {z m }, Fz m =, z m Z ЭD или g у.к ({z у.к, z 1 }, Fz у.к ).

99 Модель двусвязного списка

100 Модель двусвязного списка В моделях элементов списка необходимо отобразить их адреса а i A Э, рассмотренные выше кортежи и отношение достижимости из текущего элемента следующего и предыдущего (это отношения R и R ). Правила перехода к моделям элементов списка будут иметь вид: а i z i Z ЭD, з Э1,, а 2 y 1,, z 2, з Эi, а i-1, а i+1 y i, z i-1, z i+1 и з Эm, а m-1, y m, z m-1, для первого, i-го (1 i m) и последнего элементов соответственно. С учётом рассмотренного выше отношения достижимости значения элемента моделью i-го элемента списка будет следующий ориентированный граф(см. рис. б предыдущего слайда): g Di ({Z i, y i }, Fz i ),

101 Модель двусвязного списка Этот граф является объединением графов g i (Z i, Fz i ), g i (Z i, Fz i ) и графа g Зi ({z i, y i }, Fz i ), определённого при получении модели вектора данных. Моделями первого и последнего элементов списка будут соответственно следующие ориентированные графы: g 1 ({Z 1, y 1 }, Fz 1 ), где Z 1 = {z 1, z 2 }, Fz 1 = y 1,, z 2 (Fy 1 = Fz 2 = ) и g m ({Z m, y m }, Fz m ), где Z m = {z m-1, z m }, Fz m = ym, z m-1, (Fy m = Fz m-1 = ). Модель двусвязного списка (см. рис. в) получим объединением моделей его элементов и указателей его начала и конца: G D ({Z у, Z ЭD, Y D }, F{Z у, Z ЭD }) = g у.н g у.к { g Di / i=1,m}, где для двусвязного списка Z у = {z у.н, z у.к }, Z ЭD A Э, Y D З Э.

102 Модель комбинированной одноуровневой структуры Рассматриваемая структура предназначена для обеспечения вычислительной сложности равной 1 операции добавления/удаления и поиска элемента по номеру при сохранении порядка следования элементов подмножества R. Каждый элемент подмножества R – пара, состоящая из вершины графа x j X к X и значения локального критерия целесообразности ее выбора s j : R = {r j / j = 1, X к }, r j = x j, s j. Множество R хранится в двусвязном списке L, обращение к элементам которого осуществляется через вектор указателей (адресов прямого доступа) P. Элемент этого вектора содержит адрес элемента двусвязного списка, если x i X равен x j X к. В противном случае элемент вектора равен нулю.

103 Модель комбинированной одноуровневой структуры Моделью этой комбинированной структуры является граф – объединение моделей вектора прямого доступа P и двусвязного списка: G C ({z Б, Z ЭP,{z у.н, z у.к }, Z ЭD, YP, YD}, FZ P, FZ D ).

104 Модель комбинированной одноуровневой структуры В этом графе: z Б а Б, Z ЭP A ЭP, Z ЭP = {z i / i = 1, n}, A ЭP – адреса элементов вектора, n = X ; z у.н а у.н, z у.к а у.к, Z ЭD A ЭD, Z ЭD = {zd j / j = 1, m}, A ЭD – адреса элементов списка, m = X к. Для реализации прямого доступа к элементам списка L использовано отношение P «координата элемента в записи множества B соответствует координате ассоциированного с ним элемента в записи множества С». Элементы остальных множеств определяются по правилам: YP = {yp i / i = 1, n}, yp i = zd j, если x i = x j r j, zd j Z ЭD, x i X, x j X k и yp i =0 в противном случае; YD = {yd j / j = 1, m}, yd j = x j, s j, x j X k, s j S k ; Z P = {z Б, Z ЭP }, F 1 z Б = Z ЭP F 1 -1 z Б = и z i Z ЭP (F 2 zi = Z ЭP \ z i, F 3 z i = =yp i );

105 Модель комбинированной одноуровневой структуры Z D = {{z у.н, z у.к }, Z ЭD }, Fz у.н = zd 1, Fz у.к = zd m, Fzd 1 = yd 1,, zd 2, Fzd j = yd j, zd j-1, zd j+1 для 1 j m, Fzd m = yd m, zd m-1,. Добавление вектора прямого доступа к двусвязному списку не только позволяет снизить вычислительную сложность операции поиска элемента по номеру до q i = 1 вместо Q = n, но и не влияет на сложность выполнения остальных операций доступа. Рассмотренная структура приводит к увеличению емкостной сложности представления данных, так как вектор адресов прямого доступа должен иметь размер соответствующего универсума (в нашем примере множества X).

106 Двухуровневые структуры данных Представление графов множествами вершин, рёбер и их образов (прообразов) требуют организации двухуровневых структур, так как образы и прообразы вершин (рёбер) – это множества подмножеств, каждое из которых соответствует элементу множества X (U). Таким образом, Г 1 X, Г 2 U, F 1 X, F 2 U и т. д. – должны быть связанными с X и U множествами одноуровневых структур с учетом их иерархической подчиненности (в графе множества вершин X и ребер U – первичны, а образы и прообразы вершин и ребер – вторичны). Связь между элементами множеств вершин (рёбер) и их образами (прообразами) относительно предикатов инцидентности и/или смежности реализуется биективным отношением (предикатом) R1 в трактовке «координатам элементов множества в указанной структуре соответствуют базы (указатели) структур данных, хранящих их образы».

107 Двухуровневые структуры данных Ниже рассмотрены структуры для представления графа в форме G(X,F 1 X). Неориентированный граф Матрица смежности Вектор векторов Вектор списков

108 Двухуровневые структуры данных Список векторов Список списков Вектор n-связных списков Список n-связных списков

109 Модель двухуровневой структуры данных список- списков Модель двухуровневой структуры данных рассмотрим для части аналитического представления гиперграфа H(X, U)

110 Модель двухуровневой структуры данных список- списков В данной структуре хранятся два вида данных: множество ребер U и множество образов этих ребер ГU = {Гu j j = 1, m}, m = |U|. Первые организованы в двухсвязный список L D, а вторые собраны в m односвязных списков L j, хранящих образ каждого элемента u j U. Для реализации связи между ребром u j и его образом Гu j в каждом элементе двусвязного списка L D предусмотрено дополнительное поле, в котором записан указатель на начало списка L j.

111 Модель двухуровневой структуры данных список- списков Моделью этой двухуровневой структуры является граф G S ({Z у, Z ЭD, ZУ, Z ЭL, Y D, Y L }, FZ D, FZ L ).

112 Модель двухуровневой структуры данных список-списков Правила перехода от двусвязного списка к его модели те же, что и выше. Моделью каждого односвязного списка L j является граф G Lj ({z у.нj, ZЭ Lj, Y Lj }, FZ Lj ), в котором: – z у.нj а у.нj, где а у.нj адрес указателя начала списка; – Z ЭLj A ЭLj, где AЭ Lj = {аj i i = 1, |X j |} адреса элементов списка, Z ЭLj = {zj i i = 1, |X j |}, zj i аj i, |X j | = Гu j ; – Y Lj Гu j, Y Lj = {yj i i = 1, |X j |}, yj i x l, x l X j ; –Z Lj = {z у.нj, Z ЭLj }; – FZ Lj = {Fz у.нj, FZ ЭLj }, Fz у.нj ={zj 1 }, FZ ЭLj = {Fzj i i = 1, |X j |}, Fzj i = yj i, zj i+1. Организация двухуровневых структур требует дополнительной информации в представлении множества. В двусвязном списке LD - это дополнительное информационное поле в его элементе.

113 Пример двухуровневой комбинированной структуры данных добавления подразумевают предварительный поиск с вычислительной сложнос- тью O(n) необходимо орга- низовать прямой доступ к вершинам и ребрам графа. Вершины взвешены значени- ями некоторого локального критерия. Таким образом для представ- ления X и U следует ис- пользовать комбинацию вектора указателей с дву- связным списком. Добавление/удаление верши- ны x i влечет добавление/ удаление всего множества Г 1 x i, следовательно Г 1 X – множество векторов. Необходимо разработать структуры данных для представления гипергра- фа в форме H(X,U,Г 1 X,Г 2 U). Основные операции алгоритма – добавле- ние/удаление вершин и удаление ребер только из множества U. Поскольку операции удаления /

114 Пример двухуровневой комбинированной структуры данных (2) При удалении вершины из множества X ее необходимо удалять из всех Г 2 u j, в которых она присутствует. Таким образом Г 2 u j в простейшем случае – списковая структура.

115 Пример двухуровневой комбинированной структуры данных (3) В разработанной выше структуре поиск x i в Г 2 U требует максимум nm операций сравнения. Для организации прямого доступа к x i во всем Г 2 U достаточно использовать вектор указателей IX 1 и соответствующие указатели в списковых структурах Г 2 U.

116 Трехсвязный список с векторами прямого доступа

117 Модель двухуровневой комбинированной структуры На рисунке представлена модель двухуровневой структуры – комбинация трехсвязного списка с векторами прямого доступа

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

119 Математическая модель алгоритма Элементарный базис логической структуры алгоритма составляют операторы: начала и конца работы алгоритма; ввода/вывода (передачи) данных; обработки данных, изменяющие их значения; вычисления условий; ветвления потоков управления; слияния потоков управления. Таким образом, множество типов операторов V = {v i / i = 1, 8}, где v 1 – начало, v 2 – ввод данных, v 3 – обработка данных, v 4 – слияние потоков управления, v 5 – вычисление условий, v 6 – ветвление потоков управления, v 7 – вывод данных, v 8 – конец.

120 Математическая модель алгоритма Помимо операций и их связей, компонентами алгоритма, отражающими процедурный подход, являются входные и получаемые данные, а также связи данные-операции и наоборот. Оценка вычислительной и емкостной сложности требует следующей информации: вид операций, их вычислительная сложность в функции от базисных и количество повторений этих операций; характеристики входа задачи, промежуточных и окончательных данных, типы структур, в которые эти данные организованы, вычислительную сложность базовых операций над используемыми структурами данных. Для оценки количества операций и вычислительной сложности алгоритма необходимы также сведения о связях между операциями и вероятностях передач управления.

121 Математическая модель алгоритма В математической модели должны быть отражены следующие компоненты алгоритма, связи между ними, характеристики компонентов и свойства связей: 1) операторы ввода/вывода данных; 2) операторы преобразования данных, их типы, реализуемые ими функции и вычислительная сложность их выполнения; 3) операторы вычисления условий, предикаты, реализующие проверку условий, и вычислительная сложность этой проверки; 4) управляющие связи между операторами с учетом отношений следования, условий и вероятности их реализации, причем последние две характеристики относятся только к альтернативным передачам управления; 5) исходные, промежуточные и окончательные данные, их вид, размерности и, возможно, структуры;

122 Математическая модель алгоритма 6) связи данные – операторы и наоборот, их типы, определяющие вычислительную сложность чтения-записи данных для различных структур. 7) связи данные – данные, позволяющие решать вопрос об их независимости. Для отображения операторов и отношений между ними используется управляющий граф G у (X, F 1 X) с двумя выделенными вершинами x 1 (x н ) и x n (x к ) - начало и конец. Управляющий граф называется правильным, если все его вершины принадлежат хотя бы одному пути из x н в x к. Алгоритмы, построенные в одном операторном базисе с одинаковой структурой, выполняющие обработку данных по различным функциональным зависимостям, ход работы которых определяется результатами проверки разных наборов условий, составляют некоторый класс.

123 Математическая модель алгоритма Моделью алгоритмов данного класса является управляющий граф, в котором не отражены конкретные наборы данных, функциональные зависимости и предикаты, реализующие проверку условий. Эта модель несет информацию необходимую для изучения свойств всего класса алгоритмов. Кроме структуры алгоритма класс определяет базис B, в который входят четыре непересекающихся множества B = {D B, Φ B, P B, O B }, где D B – символы переменных; Φ B – символы функций; P B – символы предикатов, реализующих проверку условий; O B – символы операторов. В нашем случае O B = V, а операторы обработки данных O O и вычис­ления условий O O, где O – множество операторов алгоритма, должны быть помечены функциональными и предикатными символами из Φ B и P B соответственно.

124 Математическая модель алгоритма События передачи управления порождают отношения достижимости оператор – оператор, обозначим его Д 1 (О, О). Связи между операторами и данными, определяющими является ли данное выходным или входным, задаются отношениями Д 2 (О, D) и Д 3 (D, О) соответственно. Поскольку эти события и связи не являются «самостоятельными» элементами, граф алгоритма целесообразно в большинстве случаев задавать множеством вершин и предикатом их смежности. Основываясь на выполненном анализе, переход от алгоритма к управляющему графу осуществляется по следующим правилам: 1. Множеству операторов алгоритма О поставим во взаимно однозначное соответствие множество вершин графа Х: О Х.

125 Математическая модель алгоритма 2. Тип и вычислительную сложность оператора отобразим, задав однозначное (возможно, взаимно однозначное) отношения R 1 и R 2 из множества Х во множества V и Т: Х R 1 V и Х R 2 T, где v V и t T, V и T – множество типов операторов и значений их вычислительной сложности. 3. Символы множеств Φ B и P B базиса отобразим в модели, задав однозначные (возможно взаимно однозначные) отношения R 3 и R 4 из множеств X O вершин обработки данных и X O вершин вычисления условий во множества Φ B и P B соответственно: Х R3ΦB и Х R4 PB. 4. Множеству передач управления алгоритма C поставим во взаимно однозначное соответствие множество рёбер графа U: C U.

126 Математическая модель алгоритма 5. Отношения П 1 (O, С) – «управление передаётся от оператора» и П 2 (С, O) – «управление передаётся к оператору» будут соответствовать двуместным предикатам инцидентности: П 1 (O, С) ~ Г 1 (Х, U) и П 2 (С, O) ~ Г 2 (U, Х). 6. Отношение достижимости операторов Д 1 (О, О) будет соответствовать двуместному предикату смежности F 1 (Х, Х) множества вершин: Д 1 (О, О) ~ F 1 (Х, Х). 7. Вершинам, принадлежащим образам F 1 x i вершин разветвления потока управления, присвоим вес из множества L = {true, false}, определяющий связь со значением предиката, вычисленным в вершине проверки условия, и вес из множества Е – вероятностей переходов. Для чего, зададим однозначные отношения R 5 и R 6 из подмножеств F 1 x i во множества L и E: F 1 x i R 5 L, F 1 x i R 6 E.

127 Математическая модель алгоритма 8. Вершинам прообразов F 1 -1 x i вершин разветвления потока управления, присвоим аналогичные веса: x i R 7 L, x i R 8 E. Полученный ориентированный управляющий граф с взвешенными вершинами в множестве Х и в подмножествах, представляющих их образы и прообразы, задает структуру класса алгоритмов с учетом порядка выполнения операторов, их типов или вычислительной сложности и вероятности осуществления передач управления. Как правило его достаточно задавать в форме Gу(, {, }).

128 Математическая модель алгоритма На рисунке следующего слайда показаны схемы алгоритмов программ: А1 – определения номера последнего равного нулю элемента массива S (рис. а), А2 – нахождения максимального элемента массива X (рис. б) и схема класса алгоритмов, к которому они принадлежат (рис. в).

129 Математическая модель алгоритма Схемы алгоритмов

130 Математическая модель алгоритма На рис. в: D B ={d i /i = 1,6}, где d i – символы данных; Ф B = {φ inp, φ 1 (1), φ 2 (1), φ 3 (2), φ 4 (1), φ 5 (2), φ oupt }; где φ 1 (1), φ 2 (1), φ 4 (1) – символы одноместных функций присваивания значения аргумента, φ 3 (2) – символы двуместных функций сложения аргументов, φ 5 (2) – символ двуместной функции определения адреса элемента массива; PB = {p 1 (2), p 2 (2) }, где p 1 (2), p 2 (2) – символы двуместных предикатов, реализующих проверку условий (верхний индекс обозначает местность функционального или предикатного символа).

131 Математическая модель алгоритма Граф G У алгоритмов данного класса

132 Математическая модель алгоритма Вторая компонента модели алгоритма должна отображать отношения данные – операторы, разделяя для каждого оператора данные на входные и выходные, и позволять определять функциями каких входных данных является результат выполнения оператора (в том числе и управления). Таким образом, отношение данное – оператор или оператор – данное является бинарным. В этой модели нет необходимости задавать связи между операторами, типы операторов (вычислительную сложность их выполнения), так как они уже отображены в графе G У. Связи данные – данные, задающие их зависимость, также являются бинарными и могут быть определены по связям данные – оператор, в этом случае данные являются входными, и связям оператор – данное, которое является результатом функции, реализуемой в этом операторе.

133 Математическая модель алгоритма Тогда вторая модель алгоритма будет представлять собой двудольный граф, множество вершин которого Z = X Y, причем X O, Y D, где O – множество операторов алгоритма, D – множество данных, принадлежащих области определения. Для класса алгоритмов множество данных D – это множество символов переменных базиса D B. Элементы множества D B абстрагированы от таких свойств и характеристик как вид данных (скаляр или множество), их размерность и структура. Таким образом, в качестве второй компоненты модели алгоритма (модели «операторы – данные») будем использовать взвешенный двудольный ориентированный граф.

134 Математическая модель алгоритма Переход к этому графу выполняется по правилам: 1. Множеству операторов алгоритма О поставим во взаимно однозначное соответствие подмножество вершин X Z, а множеству данных D (символов переменных базиса D B ) – подмножество вершин Y Z: O X, D Y, причем X Y =, X Y = Z. Здесь во множество данных D включены и промежуточные результаты работы алгоритма. 2. Отношения Д 2 (О, D) и Д 3 (D, О) будут соответствовать двуместным предикатам смежности F 2 (Х, Y) и F 3 (Y, Х): Д 2 (О, D) ~ F 2 (Х, Y) и Д 3 (D, О) ~ F 3 (Y, Х). В качестве второй компоненты модели класса алгоритмов, отобра­ жающей данные, операторы и отношения между ними, получаем ориентированный двудольный граф: Go.д({X, Y}, F 2 Х, F 2 -1 Х, F 3 Y, F 3 -1 Y).

135 Математическая модель алгоритма Модель класса алгоритмов, отображающая отношения между данными и операторами

136 Математическая модель алгоритма Интегральной моделью класса алгоритмов будет граф: G A ({X, Y}, F 1 Х, F 1 -1 Х, F 2 Х, F 2 -1 Х, F 3 Y, F 3 -1 Y) = G У G o. д.

137 Математическая модель алгоритма В модели конкретного алгоритма должны быть отражены реализуемые функции и предикаты, а также вид данных области его определения. Для получения модели конкретного алгоритма необходимо выполнить интерпретацию I 1 модели класса алгоритмов в область определения данного алгоритма. Для алгоритма A1 получим: I 1 (D B ) : d 1 = I, d 2 = S, d 3 = n, d 4 = 0, d 5 = i, d 6 = 1; I 1 (Ф B ) : I 1 (φ inp (D B )) = I, S; I 1 (φ 1 (1) (D B )) = φ 1 (1) (d 4 )= 0; I 1 (φ 2 (1) (D B )) = φ 2 (1) (d 6 ) = 1; I 1 (φ 3 (2) (D B )) = φ 3 (2) (d 2, d 5 ) = S[i]; I 1 (φ 4 (1) (D B )) = φ 4 (1) (d 5 ) = i; I 1 (φ 5 (2) (D B )) = φ5 (2) (d 5, d 6 ) = i + 1;

138 Математическая модель алгоритма I 1 (P B ) : I 1 (p 1 (2) (D B )) = p 1 (2) (d 5, d 1 ) = «i меньше или равно I»; I 1 (p 2 (2) (Ф B, D B )) = p 2 (2) ( φ 3 (2) (d 2, d 5 ), d 4 ) = «S[i] равно 0»; I 1 (φ outp (D B )) = n; I 1 (O B ) = V. В модели «операторы - данные» конкретного алгоритма должны быть отражены такие свойства и характеристики данных области определения как вид, размерность и структура памяти для множеств, вычислительные сложности чтения и записи данных для определенных структур.

Модель сети Неформально сеть можно определить следующим образом: имеется система, состоящая из некоторого множества объектов, связанных каналами передачи сообщений. Один из этих объектов является только источником сообщений (s), другой – только приемником (t). Остальные объекты выполняют прием и дальнейшую передачу сообщений без потерь. Каналы передачи сообщений имеют ограниченную пропускную способность. Необходимо определить максимальное количество сообщений по сети. На следующем слайде (рис.а) показано исходное состояние некоторой сети. Около каналов в круглых скобках через косую черту указаны количество сообщений при данном состоянии системы и пропускная способность канала.

140 Модель сети Моделью сети является ориентированный граф G (X, ) X О, где О = {s, о 1, о 2,.., о n-2, t} – объекты системы, и X ={x s, x 1, x 2,.., x n-2, x t }; К U, где К – каналы передачи сообщений, U ={u 1, u 2,.., u m }; функция f: U R – поток в сети, значение которой показывает количество сообщений по каналам в данном состоянии системы; c – функция, задающая пропускную способность каналов. Таким образом f(u j ) – поток, передаваемый по ребру u j, а c(u j ) – пропускная способность этого ребра.