авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 |

«В.Е. ПОДОЛЬСКИЙ, С.С. ТОЛСТЫХ ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ РЕГИОНАЛЬНЫХ ОБРАЗОВАТЕЛЬНЫХ КОМПЬЮТЕРНЫХ СЕТЕЙ С ИСПОЛЬЗОВАНИЕМ ЭЛЕМЕНТОВ СТРУКТУРНОГО АНАЛИЗА И ТЕОРИИ ...»

-- [ Страница 3 ] --

На рис. 2.10 приведен взвешенный орграф GD, полученный из GС (см. рис. 2.2), а в табл. 2.3 – взвешенная матрица контуров CD.

9 2 2 1 1 8 3 3 2 Рис. 2.10. Взвешенный орграф GD 2.3. Взвешенная матрица контуров CD для орграфа GD 2 1 3 7 8 6 1 8 7 2 4 5 3 6 6 3 4 4 5 Дуги 3 2 4 6 7 1 8 1 8 1 5 6 8 5 7 2 3 7 2 1 24 2 72 14 12 20 3 24 2 3 72 14 4 72 14 12 20 5 72 14 К 20 6 72 о 12 н 10 12 21 8 т 12 21 4 10 16 9 у 10 р 11 ы 12 72 14 42 10 8 13 14 42 10 8 15 10 Вес дуги 9 2 2 7 2 2 3 5 1 7 8 1 1 2 3 5 8 11 15 Контур 8 7 6 5 4 3 2 ность В матрице CD наиболее приоритетной дугой является дуга (2 3), она входит в 8 контуров, а наименее приоритетной – дуга (5 4), входящая лишь в 1 контур.

Ранее, в 2.2, было показано, что сложность невзвешенного орграфа можно оценить как произведение числа дуг на число контуров. Взвешенный орграф представляет собой совокупность вершин, дуг и их весов. Эта со вокупность представлена двумя матрицами – взвешенными матрицами смежности и инцидентности. Контуры представлены взвешенной матрицей контуров. Таким образом, чтобы оценить сложность взвешенного орграфа необходимо, прежде всего, найти произведение матриц: взвешенная матрица смежности умножается на взве шенную матрицу инцидентности, а затем полученное произведение – на транспонированную взвешенную мат рицу контуров. На рис. 2.11 дана иллюстрация к данной аналогии.

На рис. 2.11 показано, что аналогом первого сомножителя в критерии S (3), числа дуг m, является произ ведение матриц XB с результирующей размерностью ( n m ). Аналогом второго сомножителя, числа контуров K, является транспонированная взвешенная матрица контуров C*. В результате перемножения получается матрица XBC* размерности ( n K ).

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

(n K ) ( n m) ( n m) (m K ) (n n) Транспонированная Взвешенная Взвешенная мат- взвешенная матрица матрица рица инцидент- контуров С смежности ности B X * ?

[+ S (3) ( G ) = mK 1 1 G = (V, D ) G = (V, D, ) Рис. 2.11. Аналогия между структурными сложностями Введем новое понятие – «матрица сложности»

W = ( XBC* )( XBC* ), dim W = ( n n ).

* (2.18) Норма матрицы W – это и есть то преобразование, которое было обозначено вопросительным знаком на рис. 2.11. Получаем критерий структурной сложности взвешенного сильно связанного орграфа S (4) ( G ) = W 2 = max i ( W ), (2.19) 1 i n где i ( W ), i = 1, n – спектр матрицы W. В формуле (2.19) нет нужды в точности следовать определению нормы матрицы, согласованной с Евклидовой нормой вектора [114, 115], согласно которому W 2 = max i ( W ) : знак модуля можно опустить, так как матрица сложности – симметричная, положительно 1 i n полуопределенная.

Ранее (табл. 2.2) мы ввели понятие «приоритетность дуги»: это свойство дуги, по которому можно оценить ее вклад в структурную сложность. Ярким примером орграфа, позволяющим продолжить дальнейшие рассуж дения, является гамак: это орграф с критической дугой, через которую проходят сугубо все контуры. Если про извести разрыв критической дуги, получим орграф без контуров. Пример гамака показан на рис. 2.12. Критиче ская дуга (1 2) разрывает все контуры, и она – наиболее приоритетная, если i j: i ~ j;

i, j = 1, 17.

Критическая дуга 1 8 7 Рис. 2.12. Гамак с критической дугой (1 2) Однако если предположить, что 1 i, i = 2, 17, то наиболее приоритетной дугой может оказаться от нюдь не критическая дуга.

Вводится определение: мера приоритетности дуги 1 S ( G di i + ) S (4) ( G ) (4) S ( d i ;

), i = 1, m. (2.20) i Поясним формулу (2.20):

• S ( d i ;

) – мера приоритетности дуги di ;

функция имеет параметр ;

• знаки и означают, соответственно, «равно по определению» и «сопоставлено», т.е. присвоено ло кально в пределах терма.

• S (4) ( G di i + ) – структурная сложность орграфа G, в котором дуге di сопоставлен вес i с при ращением 0.

• мера приоритетности – по характеру формирования – мультипликативная величина, что объясняется необходимостью баланса структурных и алгебраических свойств дуги;

• алгебраические свойства взвешенной дуги проявляются в первом сомножителе: чем вес больше, тем приоритет дуги меньше;

• структурные свойства дуги оцениваются вторым сомножителем – чем меньше приращение сложности в числителе дроби, тем в меньшей мере дуга может повлиять на оценку структурной сложности;

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

Кроме положительной полуопределенности, необходимо отметить еще одно важное свойство матрицы сложности: норма W 2 связана с весом любой дуги монотонно-возрастающей зависимостью. Что же касается критерия S (4) ( G ), он обладает «полезным» качеством: при увеличении веса наиболее приоритетной дуги 1 в зависимости S = S ( di ;

), i = 1, 20 наблюдается смещение индекса наибольшей приоритетности вправо (рис. 2.13).

Рассмотрим простейший взвешенный орграф GE на рис. 2.14 и продемонстрируем на этом орграфе ис пользование критерия S (4) ( G ).

Взвешенная матрица смежности орграфа GE 0 a X= (2.21).

b i ~ idem S = S ( di ;

) 1 i, i = 2, m Наиболее приори тетная дуга di d m1 d m d1 d Рис. 2.13. Смещение индекса наибольшей приоритетности a b Рис. 2.14. Простейший взвешенный орграф GE Взвешенная матрица инцидентности a 2b B= (2.22).

2a b Транспонированная взвешенная матрица контуров a C* =. (2.23) b Матрица сложности ( 2a3 + ab2 ) ( 2a + ab ) 2 3.

W= (2.24) ( a b + 2b ) ( 2a + ab )( a b + 2b ) 2 2 3 Характеристический полином матрицы сложности P2 ( ) = 2 ( 4a 6 + 5a 4 b 2 + 5a 2 b 4 + 4b6 ). (2.25) Спектр матрицы сложности (корни уравнения P2 ( ) = 0 ) 1 = 4a 6 + 5a 4 b 2 + 5a 2 b 4 + 4b 6, 2 = 0, (2.26) и вполне очевидно, что a, b R +, = 1 0.

W Без ограничения общности полагаем a b. В этом случае дуга (1 2) – более приоритетная, чем (2 1).

Остается показать, что приращение веса дуги (1 2) дает более существенное приращение величины W 2 (в соответствии с теорией И. Пригожина, познание сложного осуществляется путем разложения системы на про стые элементы наименее трудоемким способом [83, 101], поэтому ожидается, что разрыв дуги с меньшим весом – и есть наименее трудоемкий способ познания сложности орграфа GE ).

Проверяем выполнение неравенства 1 1 1. (2.27) a 2 a b 2 b Перенесем выражение из правой части (2.27) в левую часть и представим полученное выражение как функцию двух переменных 24a 5 + 20a 3b 2 + 10ab 4 10a 4 b + 20a 2 b3 + 24b ( a, b ) =. (2.28) a2 b На рис. 2.15 представлен 3D-график функции ( a, b ), где в левой части поверхности находится область a b. На этой затемненной части графика видно, что функция ( a, b ) положительная, т.е. неравенство (2.27) выполнено.

Вернемся к невзвешенному орграфу GC (см. рис. 2.2). Назначим всем дугам этого орграфа единичный вес.

Как показано в табл. 2.2, наибольший приоритет имеет дуга (2 3) – она входит в наибольшее число контуров.

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

При небольшой размерности орграфа GC элементы матрицы W – уже довольно большие числа. Было за мечено, что при увеличении размерности орграфа порядок чисел в матрице W растет, и для больших размер ностей орграфа необходимо предусмотреть использование на ЭВМ нестандартных вещественных типов данных с повышенным числом разрядов [77].

Рис. 2.15. 3D-график функции (а, b) 2.4. Матрица сложности орграфа GC 7978 8097 9558 7139 8817 7628 4505 9303 10234 7738 10 042 7837 4208 11895 9102 11 224 9148 5199 9102 9100 7522 4482 W= 11 544 8874 4836 8783 5458 3831 На рис. 2.16 приводится диаграмма приоритетности дуг. Индекс наибольшей приоритетности получился равным единице, что подтверждает правомерность применения критерия S (4) не только к взвешенным, но и к невзвешенным орграфам.

Оставляя неизменными значения параметричностей всех дуг, кроме первой (ранее она была наиболее при оритетной), увеличим 1 с 1 до 10. Результаты вычислений приводятся на рис. 2.17. Дуга (2 3) теряет свою наибольшую приоритетность. Наиболее приоритетной дугой становится дуга (3 4), разрывающая 6 контуров.

Продолжаем процесс: устанавливаем параметричность дуги (3 4) равной 10. Результат приведен на рис. 2.18.

Как видно из рис. 2.18, пик чувствительности сместился вправо – наиболее приоритетной дугой стала дуга ( 2), разрывающая всего 2 контура.

S ( d k ;

0,1) di 2 1 3 7 8 6 1 8 7 2 4 5 3 6 6 3 4 4 5 3 2 4 6 7 1 8 1 8 1 5 6 8 5 7 2 3 7 2 di Рис. 2.16. Диаграмма приоритетности дуг орграфа GC S ( d k ;

0,1) di 2 1 3 7 8 6 1 8 7 2 4 5 3 6 6 3 4 4 5 3 2 4 6 7 1 8 1 8 1 5 6 8 5 7 2 3 7 2 di Рис. 2.17. Смещение индекса наибольшей приоритетности, 1 = S ( d k ;

0,1) di 2 1 3 7 8 6 1 8 7 2 4 5 3 6 6 3 4 4 5 3 2 4 6 7 1 8 1 8 1 5 6 8 5 7 2 3 7 2 di Рис. 2.18. Случай 1 = 3 = Интересно выяснить: при каких значениях 1 происходит смена индекса наибольшей приоритетности? Во обще говоря, смена индекса наибольшей приоритетности – явление, которое можно охарактеризовать как структурную бифуркацию (катастрофу [83, 92, 101]): в данном случае – скачкообразное изменение структурных свойств сильно связного взвешенного орграфа. На рис. 2.19 показаны результаты соответствующих расчетов.

Проследим, как меняется значение критерия S (4) ( G ) для исходного орграфа GC, когда вес наиболее при оритетной дуги d1 постепенно увеличивается. На рис. 2.20 продемонстрированы результаты расчетов.

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

На рис. 2.21 представлена диаграмма меры приоритетности дуг для взвешенного орграфа с произвольными весами дуг (см. орграф GD на рис. 2.10).

Индекс наибольшей приоритетности в матрице C 1, 1 2 3 4 5 6 7 8 9 10 Рис. 2.19. Структурная бифуркация в орграфе GC S (4) Рис. 2.20. График зависимости S (4)(GC) как функции веса дуги Наиболее приоритетной дугой оказалась дуга d 2 = (1 2 ), что само по себе не удивительно – эта дуга разрывает лишь чуть меньше контуров, чем ( 2 3), но в отличие от дуги ( 2 3) имеет в 4,5 раза меньший вес. Налицо баланс структурных и алгебраических свойств дуги: критерий S (4) этот баланс выявляет.

S ( d k ;

0,1) di 2 1 3 7 8 6 1 8 7 2 4 5 3 6 6 3 4 4 5 3 2 4 6 7 1 8 1 8 1 5 6 8 5 7 2 3 7 2 di Рис. 2.21. Диаграмма приоритетности дуг орграфа GD Таким образом, вычислительные эксперименты продемонстрировали, что критерий структурной сложно сти S (4) ( G ) позволяет выявить индекс наибольшей приоритетности. В главе 3 мы еще вернемся к этому поня тию и покажем, что на основе этого индекса можно сделать ряд уточнений, повышающих достоверность оцен ки структурной сложности.

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

3. СТРУКТУРНАЯ СЛОЖНОСТЬ ЗАМКНУТЫХ ДЕТЕРМИНИРОВАННЫХ ТЕХ НИЧЕСКИХ СИСТЕМ Предыдущая глава была посвящена вопросам оценки структурной сложности орграфов;

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

3.1. ТЕРМИНОЛОГИЯ И ОСНОВНЫЕ КОНЦЕПЦИИ Вводим систему математических обозначений, направленную на перевод выражений на языки программи рования алгоритмических спецификаций и искусственного интеллекта [78, 131].

1. Множество1 J, состоящее из целочисленных n1, n1 + 1,..., n2 1, n2, обозначается J = {n1..n2 }. Если индекс i последовательно приобретает значения от n1 до n2 включительно, это обозначается i = n1..n2.

{a }, an1 +1,..., an2 1, an2, обозначается A = { ai, i = n1..n2 }.

2. Множество А, состоящее из элементов n 3. Множество, обозначаемое J [1..n ] и состоящее из целочисленных элементов j1, j2,..., jn 1, jn, называ ется перестановкой отрезка [1..n ] при выполнении условия i = 1.. n : 1 ji n, { k1, k2,..., kn } |1 k g n, (3.1) g = 1..n, jkl = jkl +1 1, l = 1.. n 1.

4. Множество A ( J [1.. n ]) называется подстановкой множества A = {ai, i = 1..n} и это означает, что { } A ( J [1..n ]) = a j1, a j2,..., a jn1, a jn = {ai, i = j1.. n }. (3.2) Далее вводится определение «объект формальных знаний».

Определение 3.1.

Объект формальных знаний – это упорядоченное множество A = { ai, i = 1.. n } с элементами ai без какой либо конкретной сущности (т.е. без принадлежности каким-либо пространствам, полям и другим математиче ским понятиям).

В следующей группе обозначений A и B – объекты формальных знаний;

они конкретизируются в процессе изложения материала. Два объекта формальных знаний A и B могут участвовать в предикатах:

1) A = B – равенство, ( ai = bi, i = 1.. A A = B ) 1 ;

2) A B – неравенство, (( i {1, A } : a b ) (i {1, B } : b a ) A B ) 1 ;

i i i i 3) A B, C D – соответственно, «A является подмножеством B и C не является подмножеством D»;

4) A B – «A содержит в себе B»;

5) A B – «либо A B, либо A = B »;

6) A B – «либо A B, либо A = B ».

Объекты A и B могут участвовать в бинарных операциях:

{ } 1. A B – объединение, a1.. A, b1.. B ;

2. A B – пересечение C = {ci, i = 1.. C } = A B ci A ci B.

В табл. 3.1 содержится перечень нововведений – некоммутативных операторов, действующих на пару ( A, B ).

Дадим краткие пояснения к обозначениям в табл. 3.1:

1. Связывание – выражает назначение (присваивание) элементам множества A новых значений. Размер ность результата определяется размерностью B. Старое значение A «забывается».

2. Следование – из A следует B, если A – не пусто. Иными словами B является следствием непустого A.

Эта операция не отождествляется с традиционным обозначением «отсюда следует» ().

3.1. Перечень новых операторов Обозначение Формализация ( A, B ) ( A ( A = B ) ) 1. Связывание A k B ( A, B ) ( C C k B, A ) 2. Следование Al B Термин «множество» мы используем здесь для соблюдения традиций;

на самом деле везде в этой главе, где этот тер мин употребляется, имеется в виду конечный, упорядоченный набор элементов произвольной природы, т.е. кортеж. Эле менты такого «множества» могут быть атомарными (одиночными объектами) и неатомарными (например, кортежами). Сре ди элементов кортежа могут повстречаться одинаковые элементы. Равенство двух кортежей устанавливается путем парного сравнения элементов с одинаковыми индексами. Ряд свойств у кортежей и множеств являются аналогичными: мощность, принадлежность и др.

Формула (3.1) читается следующим образом: «Для любого i от 1 до n свойственно (знак «:»), что ji находятся в пре делах от 1 до n включительно, и (знак «,») найдется множество из элементов { k1, k2,..., kn }, таких, что (знак «|») и т.д.

(далее идет ряд предикатов, соединенных союзом «и»).

A = B = C k, A Ck A ( A, B ) C 3. Обобщенное «ИЛИ» A B A B C k A, A = B Ck B A =, B =, ( A, B ) C A = B =, 4. Обобщенное «И» A B A B { A, B} ( A B ) A l B C k A, ( A, B ) C 5. Характеризация Ad B ( A B ) = Al B C k ( A B ) Al B C k A, ( A, B ) C 6. Конкретизация Ac B ( A B ) = A l B Ck ( A, B ) ( C ( Ad B,Bc A C k ) ) A;

7. Соответствие Ae B 3. Обобщенное «ИЛИ» следует понимать так: если A не пусто, то результат равен A;

если A пусто, а B – нет, то результат равен B;

если же и A, и B – оба пусты, результат равен пустому множеству (есть некоторая аналогия с «исключающим ИЛИ»).

4. Обобщенное «И» – результат равен пустому множеству, если или A, или B, или оба сразу – пустые. В противном случае результат равен A.

5. Характеризация – оператор, благодаря которому можно утверждать, что A является некоей характери стикой B, но не наоборот. При этом в паре ( A, B ) должны существовать общие элементы и B не может являть ся следствием A.

6. Конкретизация – оператор, результатом работы которого является A, если A и B имеют непустое пере сечение, и, к тому же, B – своего рода «второстепенный элемент» – следствие A. Назовем B конкретизатором.

Для объекта A нам также потребуется отдельный термин – назовем его объектом конкретизации. Особенность конкретизации в том, что между объектами A и B, помимо собственно конкретизации, в одном терме могут дей ствовать и другие отношения из табл. 3.1.

7. Соответствие – следует особо отметить, некоммутативный оператор. Утверждается, что A соответству ет B, но не наоборот. О таком соответствии будем говорить: если A является характеристикой B и B конкрети зируется A, то A соответствует B, иначе наблюдается несоответствие, и результатом действия оператора e ста новится пустое множество (знак « » означает «в противном случае»).

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

3.1:

1) A k B – «A не связано с B»;

2) A l B – «B не является следствием A»;

3) A d B – «A не является характеристикой B»;

4) A c B – «A не конкретизируется B»;

5) A e B – «A не соответствует B».

Важную роль в представлении знаний играет постулирование. Дадим определение понятию «постулат».

Определение 3.2.

Выражение A называется постулатом и обозначается А А, если конкретизатор C не связан с объектом конкретизации ( ( B op C, Bc C ) l (op k ) ).

(А А ) k (3.3) Оператор op, участвующий в записи постулата A, будем обозначать op [ A] и называть оператором по стулата.

Вводим определение дескриптор. Это постулат, в котором утверждается, что объект A является описате лем (дескриптором) объекта B, выражая этим приобретенные знания об особенностях и отличиях его от других объектов.

Определение 3.3.

Объект A называется дескриптором объекта B и обозначается A k de ( B ), если ( ( Ae B ) k ( ( Ad B ) ( B e A) ) ).

( Ak de( B) ) l (3.4) Выражение (3.4) – постулат ( P( ) k ) (( Cc ( ( Ad B) ( B e A) ) ) C=(A k de( B))), P( ) k 1 (3.5) op P (1) = l.

Будем обозначать постулаты P (i ), i = 1, 2,... по мере их появления в тексте. Постулат превращается в оп ределение, если op [ P ] = k, и в таком случае знак связывания k заменяется на стандартный знак («равно по определению»).

Определение 3.4.

Постулат P называется совершенным, если он дает исчерпывающее представление об объекте конкрети зации ( C op B, Cc B ) l ( op k ), ( ) P P: ( Ce P ) Ce P, P P k P (3.6) ( ) ( Be P ) Be P, ( ) ( ope P ) ope P.

Будем считать, что на объектах формальных знаний F ={ f i, i = 1.. n} задана система S, если она конкрети зируется множеством бинарных отношений предшествования {( f } f j ) i, j {1.. n}.

Sc (3.7) i (f f j ) означает, что любое взаимодействие, существующие между объектами в системе S, име Запись i ет направленность от fi к fj, иными словами, fi предшествует fj. Запись (3.7) можно расценивать как результат формального наблюдения за исследуемой системой, так как нет правил, по которым индексируются элементы конкретизатора и (3.7) нельзя назвать постулатом.

Отношение предшествования является базовым при конкретизации взаимодействий среди элементов системы S : на его основе будут определены другие взаимодействия. По сути дела, отношением предшествова ния характеризуются бинарные отношения порядка в системе;

но совокупность этих отношений не является совершенным постулатом.

Запись f i f j (используется, в частности, в [117]) означает, что «fi предшествует fj и находится с ним в непосредственной связи»

)) ) (i, j { 1..n} (( f ( (( f f ) ( f ) f j ) d S k { 1.. n} fj ) d S.

i i k k (3.8) Объект ( fi f j ) будем обозначать P k, k = 1.. m и называть дугой {} (P ) ( f k de(P (f fj ) l ), f j k de(P k ) ) ;

i, j 1, n ;

k = 1.. m.

k k i i k (3.9) Введем в рассмотрение множество дуг системы S {P } (f f j ) ;

k = 1.. m;

i, j {1.. n}.

(3.10) : Pkk k i Отметим, что и S образуют бинарное отношение Sc, но ни в коем случае не S d. Теперь, когда мы говорим «структура системы S », это обозначается k Str ( S ).

Запись f i f j формально означает, что объект fi достижим из объекта f j ( i, j {1.. n}, f fj ) i ( (u 1) ((( {k.. k } {1.. n}) ( {k.. k } J [1.. n])) 1 u 1 u ) ( S c (( f f ), ( f f ),..., ( f f ), ( f f ))) ( f fi ).

j k1 k1 k2 ku 1 ku u i j (3.11) Запись f i q f j формально означает, что объект fi не достижим из объекта f j.

Введем понятие множества достижимостей системы, как свойство ее структуры.

}) d Str ( S ).

({ G = g r g r ( f i f j ) ;

r = 1..;

i, j { 1.. n } (3.12) e { g r, r = 1.. } Следует отметить, что в формуле (3.12) мощность множества достижимостей обозначена.

С множеством достижимостей связано понятие «сильно связная структура системы». Если структура системы является сильно связной, то система – замкнутая. Замкнутость и сильная связность обозначаются одинаково: ( Sr S ) (система) и r (структура). Условие сильной связности удобно записать в следую щем виде )) ( = n2 n ).

( ( Sr S )e ( r (3.13) Далее потребуется определение подсистемы.

Определение 3.5.

Система S является подсистемой системы S, и это обозначается S S, в том и только в том случае, если среди дескрипторов системы S найдется хотя бы один, посредством которого S не конкретизируется и за этим следует, что в подсистеме S нет ни одного дескриптора, которым бы не конкретизировалась система S (рис. 3.1) ( S S ) ( ( ( a k )).

)( de ( S ) ) S c a ( b k de ( S ) ) S c b (3.14) Итак, запись S S означает, что S является подсистемой S и, если подсистема является сильно связ ной, то это обозначается S r S. Среди всех возможных подсистем нас интересуют исключительно только сильно связные подсистемы.

Термин «абстрактор» (синоним: компрегенсор) используется во многих областях знаний, в частности, в алгебре предикатов [131]. В нашей работе этот термин удобен, и поэтому имеет смысл дать ему уточняющее определение.

( a k de ( S ) ) S S c a S Все дескрипторы S' одновременно являются конкретизаторами S Рис. 3.1. Иллюстрация к определению подсистемы Определение 3.6.

Абстрактор «•» – формальная запись абстрактных знаний, конкретизируемых контекстом, а именно: «•»

означает, что на этом месте может присутствовать что-либо конкретное ниже по тексту.

Так, например, если известно, что – некоторая функция одного аргумента, принадлежащего эффектив ной области определения данной функции, это обозначается ( • ).

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

Этап наблюдения относится к области когнитивных представлений информации [119, 121, 129] и здесь не рассматривается. Поэтому уместно будет говорить об абстрактных системах, абсолютно наблюдаемых, замкну тых и базирующихся на аксиоматической теории в предшествующем изложении материала.

Определение 3.7.

Формальным определением абстрактной системы является утверждение вида ({•, •,..., •}c {•, •,..., •}), S (3.15) а именно: абстрактная система – это совокупность конечного числа абстракторов, конкретизируемых конеч ным множеством свойств, сущность которых не определена.

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

Аксиома 3.1.

Не существует двух одинаковых абстрактных систем ( S1, S 2 ) ( 3.15 ) : ( S1 S 2 ) e ( S1 S 2 ). (3.16) В записи (3.10) количество элементов в структуре обозначено как m;

в дальнейшем для множества дуг удобнее будет использовать более короткую запись: = {P k, k = 1.. m}.

Пусть все дуги = {P k, k = 1.. m} конкретизируются лишь одним свойством – параметричностью (обоб щение понятия «вес», см. предыдущую главу) k, P k c k. Ограничимся случаем k [ +.

Абстрактная система конкретизируется совокупностью бинарных отношений в виде дуг, конкретизируемых параметричностями, а также множеством объектов, между которыми эти бинарные отношения действуют (( c ) F).

Sc (3.17) В выражении (3.17) = ( 1, 2,..., m ) – вектор параметричностей.

Определение 3.8.

Отображение Str: S называется структуризацией абстрактной системы S, а отображение Par: – параметризацией.

Возникает вопрос: какова связь между понятиями «система», «структура» и «параметричность»? Ответом является следующая аксиома.

Аксиома 3.2.

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

это равносильно утверждению, что параметричность является свойством структуры, но не наоборот (( S c Str ( S ) ) ( S c Par (Str ( S ) ) )) (3.18) (( Par (Str ( S ) ) d Str ( S ) ) (Str ( S ) e Par (Str ( S ) )) ).

3.2. ПАРАМЕТРИЗАЦИЯ СТРУКТУР Класс систем, который будет рассматриваться далее, конкретизируется математическими моделями (ММ) объектов f i, i = 1.. n, находящихся в состоянии статики ( (( c ) ( Fe ))).

S k Sc (3.19) Здесь = {µ1 ( • ), µ 2 ( • ),..., µ n ( • )} – множество ММ, представляющее собой, соответственно, математи ческое описание объектов множества F = { f i, i = 1.. n}. Будем считать, что µi ( • ), i = 1.. n – вектор-функции, осуществляющие преобразование вектора входных переменных Yвх) • в вектор выходных перемен (i ных Yвых •. В каждой i-й ММ зависимость Yвых от Yвх) устанавливается неявно в виде системы операторных (i ) (i i уравнений:

( ) µ i(1) Yвх), Yвых = 0;

(i (i ) ( ) µ (2) Y (i ), Y ( i ) = 0;

i вх вых (3.20)...

(U ) (i ) (i ) ( ) µ i i Yвх, Yвых = 0, где U i – размерность замкнутой системы уравнений ММ, соответствующей объекту fi, i = 1.. n.

Введем обозначения (рис. 3.2):

1) множество дуг на входе в объект { } (f f i ), j {1.. n}, k {1.. m} ;

in ( f i ) = P k : P k k (3.21) j 2) множество дуг на выходе из объекта { } (f f j ), j {1.. n}, k {1.. m}.

out ( f i ) = P k : P k k (3.22) i {} {} Каждая дуга на входе в объект P k in ( fi ), k 1, m, i 1, n обладает определенной информативно стью, принимая участие в формировании вектора Yвх) входных переменных. Обозначим вклад дуги в размер (i ность вектора входных переменных q ( P k ). Сумма вкладов дуг на входе равна размерности вектора входных переменных q ( P k ) = dim Yвх).

(i (3.23) P k in ( fi ) Аналогичным образом вводится r ( P k )e ( P k out ( f i ) ), r ( P k ) = dim Yвых.

(i ) (3.24) P k out ( fi ) Методика назначения параметричностей k во многом определяется целью анализа системы. Вообще го воря, назначение параметричности – критический процесс, важность которого несомненна. Конкретизация структуры моделируемой системы может сильно повлиять на характеризацию этой системы.

in ( fi ) out ( fi ) fi c µi Рис. 3.2. Объект fi, конкретизируемый математической моделью µi В качестве параметричности могут использоваться, в наиболее общем случае, фреймы знаний [119]: они выражают одновременно и количественные знания о взаимодействиях между объектами сложной системы, и процедурные знания, отражающие качество этих взаимодействий.

В данной работе мы рассматриваем лишь самую простейшую форму назначения параметричностей – ве щественные числа.

Как один из наиболее общих способов назначения параметричности бинарных отношений вида « » (не посредственная связь), применительно к системе ММ можно использовать следующий прием. Полагаем, что для каждой дуги P k назначается экспертная оценка [124, 128], вычисляемая по формуле {q ( P ) r ( P k )}.

k = k (3.25) k k Назовем k : 1 k основанием параметричности дуги P k, а величину k : k – степенью параметричности P k.

Рассмотрим характерные случаи назначения величин k и k.

1) k ~ 2, k +0 k, дуге P k назначается континуально большая параметричность;

2) k = 1, k k = {q ( P k ) r ( P k )} ] +, параметричность назначается равной либо числу входных, либо числу выходных переменных (одно исключает другое);

3) k ~ 2, k 0 k +0, дуги P k, по мнению эксперта, как бы не существует, объекты, соединен ные такой дугой, «схлопываются»;

4) k ~ 2, k 1 k + {q ( P k ) r ( P k )} [ +, этот случай отличается от случая 2 тем, что в назна чении параметричности участвует вещественное число («усилитель») 0.

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

Сформулируем цель анализа структуры системы:

«Цель анализа A ( S ) системы S c ( ( c ) ( F c ) ) заключается в нахождении наиболее эффективно (i ) го расчетного модуля, обеспечивающего получение всех векторов выходных переменных Yвых, i = 1.. n, с наименьшими затратами машинного времени на вычислительном кластере».

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

Предположим, что на первом (начальном) этапе познания сложной системы удалось выявить размерность множества объектов, из которых данная система состоит: число n. Формально полагаем, что состояние каждого объекта однозначно определяется переменной zi •, i = 1.. n, и записываем в операторном виде совокупность ММ как систему уравнений 1 ( z1, z2,..., zn ) = 0, 2 ( z1, z2,..., zn ) = 0, e ( Z ) = 0. (3.26)...

( z, z,..., z ) = n 1 2 n Априори полагаем, что размерность системы (3.26) столь велика, что для ее решения невозможно исполь зовать обычные методы (без декомпозиции), такие, например, как метод Ньютона-Раффсона [130].

Самым простым декомпозиционным методом решения систем уравнений можно считать метод Зейделя (с практической точки зрения имеющим, однако, лишь методологическую ценность – более совершенные методы уже известны [122, 126, 127]).

Система уравнений решается в двух итерационных циклах [126, 130]: на внешнем уровне производится задание начального приближения, уточнение начального приближения и проверка сходимости по норме век тор-функции левой части системы. Во внутреннем цикле производится последовательное решение одномерных уравнений системы, причем каждое отдельное уравнение тоже решается итерационно.

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

Предположим, что в результате структурного анализа удалось найти оптимальную перестановку J * [1.. n ] уравнений в системе (3.26) – такую, что итерационный процесс по методу Зейделя сходится к решению с мак симальной скоростью. Тогда алгоритм решения системы уравнений (3.26) методом Зейделя, абстрагируясь от достижений науки в области итерационных методов решения систем уравнений большой размерности, можно считать удовлетворительным для поставленной ранее цели анализа A ( S ). Сформулируем соответствующий алгоритм:

1. Ввод а) Z (0) – начальное приближение;

б) – точность решения системы;

в) J * [1.. n ] – оптимальный порядок рассмотрения уравнений в системе ( Z ) = 0, результат структурного анализа;

г) i, i = 1.. n – массив точностей решения одномерных уравнений вида i ( •, •,..., •, zi, •, •,..., • ) = 0 (в об щем случае для решения одномерных уравнений используется соответствующий численный метод, где итера ции должны сходиться с некоторой наперед заданной точностью;

в частных случаях одномерные уравнения могут иметь аналитические решения).

2. Производим перестановку уравнений в соответствии с J * [1.. n ].

3. В цикле по i = 1.. n решаем уравнение с номером i с точностью i : находим компоненту zi из уравне ния i ( z1,..., zi1, zi, zi(0),..., zn ) = 0. В решаемом уравнении переменные z1,..., zi 1 считаются константами: они (0) + известны из решения предшествующих уравнений, а переменные с индексами, превышающими i, считаются равными соответствующим значениям из вектора начального приближения Z (0).

4. Проверяем условие завершения итераций ( Z ) •. Если неравенство верное, решение считается полученным;

в противном случае полагаем Z (0) k Z и возвращаемся к началу итерационного цикла – к п. 3.

На следующем этапе структуризации необходимо выявить, какие компоненты вектора Z принимают уча стие в отдельно взятых уравнениях с номерами i = 1.. n. Если (3.26) – система нелинейных уравнений (СНУ) с дважды дифференцируемыми i, то участие переменной z j в i-м уравнении фактически означает, что (i, j)-й элемент матрицы Якоби ( Z ) = ( ), = i, i = 1.. n, j = 1.. n (3.27) ij n n ij z j отличен от нуля.

Если 0, то делается вывод об участии переменной z j в уравнении с индексом i.

ij Рассмотрим пример. Пусть система (3.26) после структуризации принимает следующем вид:

1 ( z1, z8 ) = 0;

2 ( z2, z3, z6, z7, z8 ) = 0;

z, z = 0;

3( 1 3) ( z, z, z ) = 0;

4 3 4 (3.28) 5 ( z4, z5, z8 ) = 0;

z, z, z = 0;

6( 2 4 6) 7 ( z1, z4, z5, z7 ) = 0;

8 ( z1, z8 ) = 0.

dim G = ( 8, 16 ), G = (V, D ), Изобразим структуру системы уравнений (3.28) в виде орграфа dim µ i = 1, i = 1..8 (рис. 3.3). Вершины графа характеризуются объектами системы с соответствующими ММ, т.е. vi d ( f i e µ i ), а дуги, исходящие из вершины vi, демонстрируют передачу переменной zi после решения i-го уравнения в другие уравнения системы.

f8 f5 f µ µ8 µ f f µ µ f1 f4 f µ4 µ µ Рис. 3.3. Орграф системы уравнений (3.28) Построим транспонированную матрицу смежности X* = ( xij ) * (см. п. 2.3, формула (2.8)) для системы * (3.28). В транспонированной матрице смежности x =1, если переменная z j участвует в i-м уравнении;

в про ij * * тивном случае xij = 0. На рис. 3.4 показана матрица X и ее квазитреугольная форма [118]. Подсистемы выде лены на рисунке как диагональные подматрицы. Присутствующий в матрицах значок «+» потребуется нам чуть позже.

Рис. 3.4 наглядно демонстрирует, как исходная система (3.28) «распадается» на четыре подсистемы (чтобы как-то выделить подсистемы, используем «~» – знак тильды), и результаты решения первых трех подсистем, будучи получены, могут сразу же использоваться в решении подсистем, рассматриваемых ниже по иерархии (см. граф Герца на рис. 3.5).

J * [1..8] 1 2 3 4 5 6 7 8 1 8 3 4 5 7 2 1 1 + 1 1 1 1 + *(1) X 2 1 1 1 1 1 8 1 3 1 1 3 1 1 *(2) X 4 1 1 1 4 1 1 5 1 1 1 5 1 1 1 *(3) X 6 1 1 1 7 1 1 1 7 1 1 1 1 2 1 1 1 1 1 *(4) X 8 1 1 6 1 1 *(1..4) * X X Рис. 3.4. Матричные представления системы (3.28) 1, 4,5, 2, Рис. 3.5. Граф Герца для системы (3.28) Проследим теперь, что изменится в структурном анализе системы (3.28), если в первое уравнение доба *(1..4) * на рис. 3.4. В этом случае, квазитреугольная форма матрицы X* не суще вить z2 : «+» в матрицах X и X ствует: нет такой перестановки J * [1..8], чтобы исходную систему можно было представить как иерархию замкнутых подсистем.

Система (3.28) становится замкнутой, а соответствующий ей орграф – сильно связным.

( ) Дуги нового орграфа G k G V, D k D {( 2 1)} после модификации сведены в табл. 3.2.

*(1..4) Если оставить прежними подсистемы X (как и без участия z2 в первом уравнении системы (3.28)), получаем агрегированный орграф, показанный на рис. 3.6. Двойная линия соответствует добавленной перемен ной z2. Знак «~» теперь обозначает не только замкнутые подсистемы, но и состояние агрегирования для обоб щенных дуг. Следует обратить внимание, что знак подчеркивания в обозначениях подматриц матрицы смежно сти уже не используется – орграф после параметризации стал взвешенным.

3.2. Дуги орграфа G 1 1 1 2 2 3 3 4 4 4 5 6 7 7 8 8 3 7 8 1 6 2 4 5 6 7 7 2 2 4 1 2 P1 P2 P3 P4 P5 P6 P7 P8 P9 P 10 P 11 P 12 P 13 P 14 P 15 P 16 P P P X( * 4) X() X( * 2) X( * 3) * P P P f1 f2 f3 f P P Рис. 3.6. Агрегирование в G e (3.28) после добавления переменной z Состояние агрегирования отражено в табл. 3.3.

После добавления новой переменной в орграфе системы (3.28) появились 4 контура, причем дуга P 7 = ( 4 1) встречается во всех контурах. Поэтому мы предназначаем дугу P 7 к разрыву и итерациям по пе ременной z2. Блок-схема расчетного модуля представлена на рис. 3.7. В ней присутствуют два процедурных блока: « z2 k z2 ) и решение µ 2...4 » и «Уточнение z2 ) ». В первом производится последовательное решение урав ( ( 0 нений математических моделей (с учетом агрегирования), в итоге получаем вектор Z. Во втором производится уточнение начального приближения с использованием какого-либо численного метода (например, метода Нью тона). В простейшем случае можно положить z20) k z2.

( 3.3. Агрегирование в (3.28) Объекты f1 f2 f3 f f1, f8 f3 f 4, f5, f7 f 2, f Замкнутые подсистемы µ1 d X ( ) µ2 d X ( * 2) µ3 d X ( * 3) µ4 d X ( * 4) * (1,8) (1,8) (3) (3) (4, 5, 7) (4, 5, 7) (2,6) (2,6) Дуги и параметричности P1 P2 P3 P4 P5 P6 P P 2, P 17 P 9, P P1 P 16 P7 P6 P 1 = 1 2 = 2 3 = 1 4 = 1 5 = 1 6 = 2 7 = Контуры Начало ( ) Ввод Z ( ), z2 k z2 ) и ( Уточнение z2 ) ( решение µ1.. нет (Z) Вывод ( Z ) Конец Рис. 3.7. Блок-схема решения системы (3.28) на основе разрыва P Продолжим добавление новых переменных в (3.28): вводим переменную z6 в уравнение 8 (рис. 3.8).

Оставляя агрегирование прежним, дуга P 7 будет конкретизироваться уже двумя переменными, итериро вание которых осуществлять сложнее. И, наконец, если бы подсистема X*(4) содержала еще большее число пе ременных, как показано на рис. 3.9, то из агрегирования X*(1..4) следует, что в итерациях участвует вектор из 94 х переменных.

В таком случае, при одинаковой значимости всех переменных, выгоднее организовать итерирование по вектору из первых восьми переменных z1..8. Агрегирование X*(1..4) становится невыгодным, не согласованным с целью анализа A ( S ). Возникает вопрос: как найти оптимальную стратегию агрегирования в структурирован ной замкнутой J * [1..8] 1 8 3 4 5 7 2 1 1 1 + *(1) X 8 1 1 + 3 1 1 *(2) X 4 1 1 5 1 1 1 *(3) X 7 1 1 1 2 1 1 1 1 1 *(4) X 6 1 1 *(1..4) X Рис. 3.8. Дополнение системы (3.28) новыми переменными 1 8 3 4 5 7 2 6 9 10 … 99 1 1 1 + + … + 8 1 1 + + … + 3 1 1 … 4 1 1 1 … 5 1 1 1 … 7 1 1 1 1 … 2 1 1 1 1 1 1 1 … 1 6 1 1 1 1 1 … 1 9 1 1 1 1 … 1 10 1 1 1 1 … 1 … … … … … … … … … … … … … … 99 1 1 1 1 … 1 100 1 1 1 1 1 1 1 1 1 1 … 1 Рис. 3.9. Дополнение системы (3.28) переменными z9.. системе? Можно ли найти такой критерий оценки структурной сложности замкнутой системы, который был бы согласован с целью анализа A ( S ) и, одновременно, порождал бы оптимальный алгоритм расчета этой системы на вычислительном кластере? Если ответы на эти вопросы будут найдены, то, поставив другую цель анализа или взяв другую систему, мы сможем построить шкалу сложности и утверждать, что количественная оценка сложности является конструктивным этапом познания системы.

Рассмотренный выше пример агрегирования системы (3.28) позволил сделать следующие выводы:

1. Различные способы агрегирования замкнутой системы, изначально наблюдаемой как система уравне ний, порождают структуры, обладающие подчас совершенно разными свойствами по отношению к цели анали за A ( S ) ;

и здесь налицо противоречие с критерием S (4) ( G ), который не затрагивает вопросы агрегирования и не вырабатывает никаких побочных эффектов, связанных с оптимизацией вычислений.

2. Если отказаться от проведения агрегирования замкнутых систем, то параметризация k = idem, k = 1.. m, является единственно возможной оценкой, согласованной с (3.25). Более того, в таком виде параметризация удовлетворяет любой цели анализа, то есть никакой.

3. При одинаковой степени параметризации всех дуг агрегированной замкнутой системы k = idem, k = 1.. m, величину k d P k = ( f i f j ) вполне оправданно сопоставлять с числом переменных, ха рактеризующих переход от объекта fi к объекту f j в расчетном модуле.

4. Чем выше уровень знания особенностей перехода от объекта fi к объекту f j, тем выше можно назна чать основание предпочтительности, параметр k.

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

3.3. ФОРМАЛИЗАЦИЯ СТРУКТУРНОЙ СЛОЖНОСТИ Для количественной оценки структурной сложности необходимо найти дескрипторы – непротиворечивые деклараторы искомой шкалы сложности, отображающей меру достижения A ( S ) – цели анализа системы S.

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

Упростим обозначение (3.17): систему S со структурой, конкретизируемой вектором, обозначим Sc. При этом мы опираемся на аксиомы 3.1 и 3.2.

Вернемся к системе (3.28). Общепринято считать [91, 113, 126], что вычислительная сложность пропор циональна сумме элементарных операций: в данном случае это относится к прямому ходу алгоритма итераци онного расчета (3.28), к отдельно взятой итерации. Конкретика стоимости вычислений в замкнутой системе большой размерности напрямую связана с особенностями агрегирования: как объектов этой системы, так и свя зей между ними. Для системы (3.28) характерно следующее: чем размерность подсистемы X*(4) больше, тем менее выгодно итерировать переменными, входящими в дугу P 7.

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

Вполне своевременно получить ответ на вопрос: «измеримо ли соотношение сложностей итерационного расчета системы, сопоставленного с разрывом критической дуги P 7 c ( 7 k (1 2 ) ) при неизменном агрегиро ( )) ( вании X*(1..4) e P 7 c ( 7 k (1 2 ) ) = idem »?

Вводим обозначения.

1. ( S ) – структурная сложность системы S, согласованная с целью анализа A ( S ).

2. Пусть S и S – сильно связные подсистемы S, S S. Для ( S ) и ( S ), структурных сложно стей подсистем, определяемое бинарное отношение ( S ) ( S ) «мультипликативно сложнее»

( ( S ) ( S ) ) e ( ( c, d [, c d ) : c d S, d d S, ( ( c / d ) d ( S l S ) ), + (3.29) ( ( d / c ) d ( S l S) ), ( S, S) S ).

) (( Z ) ( ) Z d ( ) 3. Iter S e ( ( Z ) = 0 ) k – итератор системы уравнений ( Z ) = 0, где Z Z– подвектор, характеризующий подмножество дуг во внешнем итерационном цикле в оптимальном алго ритме решения ( Z ) = 0 (блок-схема показана на рис. 3.10).

(() ) S e Z = 0 S S, ( ( )) ( ) 4. Domen S e ( ( Z ) = 0) k Zd Z \ Z e – домен системы уравнений ( Z ) = 0, подсис (()( ( ))) Z d ( Z) \ Z тема системы (3.26), возникающая после разрыва итератора.

( ) 5. ( Z ) = 0 – вычислительная сложность решения системы уравнений ( Z ) = 0 c итератором ( ) Iter Se ( ( Z ) = 0 ).

6. !v – означает, что структура не содержит в себе ни одной другой подсистемы, которая была бы сильно связной.

Прокомментируем (3.29): подсистема S мультипликативно сложнее подсистемы S, если найдутся веще ственные числа с и d, c d, характеризующие подсистемы S и S, а также их соотношения, числа c / d и d / c, характеризующие порядок сравнения.

Введем понятие «нулевая структурная сложность 0 ». Сложность ( S ) системы равна 0, только в слу чае, если S не содержит ни одной сильно связной подсистемы:

(o ( S ) k 0 ) e ( ( S S ) : Sr S). (3.30) Системы со структурной сложностью 0 назовем простыми.

Рассмотрим ситуацию: пусть в результате агрегирования орграф системы (3.26) оказался в топосе [133, 134] двойных гамаков (см. рис. 3.11). В орграфе на рис. 3.11 обе дуги: и P 1, и P 2 – критические. Будучи уда ленной, каждая из них приводит орграф к дереву с нулевой структурной сложностью. Если соотношение пара метричностей 1 2 = 1 2, то и соотношение вычислительных сложностей тоже 1/2, это очевидно даже в слу чае, если двойной гамак несимметричен.

Начало Ввод: ( Z ),, Z ( 0).

Структуризация ( Se ( ( Z ) = 0 ) ) c ( = Str ( S ) ) Нахождение итератора (Z ) Z d ( ) и разрыв дуг подмножества Задание начального приближения Z( 0) Z( 0) Расчет домена Уточнение начального ( ) Domen S e ( ( Z ) = 0 ) ( 0) приближения Z Нет Z Z( 0) Вывод: Z.

Конец Рис. 3.10. Блок-схема решения системы ( Z ) = P 1c ( 1 = 1) … … P 2c ( 2 = 2) Рис. 3.11. Двойной гамак Обобщением этой ситуации станет следующая аксиома.

Аксиома 3.3.

Сложность итерирования -м числом переменных в замкнутой системе S c мультипликативно сложнее итерирования -м числом с характеризацией ( / ) тогда и только тогда, когда и в том, и в другом случае во внешний итерационный цикл вложена подсистема с нулевой структурной сложностью.

Иллюстрация к аксиоме 3.3 дана на рис. 3.12.

Дополним алгебру структурной сложности рекурсивными операциями сложения и умножения подсистем S1, S 2 S.

1. Сложение сложностей, :

(( ( S ) ( S )) d ( S, S ))e 1 2 1 (( S S = ), ((( ( S ) ( S )) ( (S ) )))c (S2 )) (3.31) 1 2 1 2 (( ( c 1) : c R ) d ( S ) ).

+ ( / ) Рис. 3.12. Иллюстрация к аксиоме 3. 2. Умножение сложностей, :

(( ( S ) ) ( S 2 ) ) d ( S1, S 2 ) e (3.32) ((( ( S ) ) ) ( S2 )) ( (S ) ( S 2 ) ) e ( ( S 2 ) ( S1 ) ).

1 Наряду с нулевой структурной сложностью введем единичную структурную сложность (1 (S )) ( S ). (3.33) :

Следующее предложение является оптимистичной попыткой классификации алгебры структурной слож ности.

Предложение 3.1.

Алгебра сложения A = ;

,0 совместно с алгеброй умножения A = ;

, 1 – изоморфные полу группы.

Понятие «сложность итерирования» вводится как очередной постулат ( P( ) k )k ({P } ( d S ) ) e ({P }).

P( 2) (3.34) 1 Сложность итерирования переменных в дуге P 1 = ( f • f • ) есть сложность передачи информации от объ екта системы f • к объекту той же системы f • (знак • – абстрактное дополнение, т.е. нечто, отличное от абст рактора в данном терме).

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

Предложение 3.2.

Структурная сложность системы уравнений вида (3.26) определяется особенностями отождествления ин формации при разрыве дуг (см. рис. 3.13) )) ( ( ( Sk ( \ {P }) ) ( ) Se ( ( Z ) = 0 ) d ({P 1} ) (S) (3.35) d ( ( ( Z ) = 0 {P } ) ( ( Z ) = 0 ) ).

(( Y )) ) (Y e а• c ( Z ) = 0 P f f e а• k вых вх Yвых Yвх Se ( ( Z ) = 0 ) f• f• Рис. 3.13. Иллюстрация к предложению 3. Поясним (3.35). Структурная сложность системы S, соответствующей системе уравнений ( Z ) = 0 ха рактеризуется 1. сложностью отождествления информации в разрываемой дуге P 1 (индекс 1 не умаляет общности), ко торая, в свою очередь, мультипликативно меньше структурной сложности целостной системы ( S ) ;

2. предшествованием вычислительной сложности ( ) O ( Z ) = 0 {P 1} итерирования переменными в дуге P 1 по отношению к вычислительной сложности дезагрегированного расчета ( ) (Z) = 0.

Следующая аксиома весьма актуальна для дальнейшего познания сложности замкнутой системы S с уче том цели ее анализа A ( S ).

Аксиома 3.4.

Структурная сложность ( S ) замкнутой системы Sr S равна сумме сложности передачи информации от объекта f • к объекту f • и сложности этой системы без дуги P 1 = ( f • f • ) в том случае, если она является итератором P 1 = Iter ( S ) и разрыв этой дуги порождает итерационный процесс с минимальной вычислительной сложностью ( S c ) k ({P 1} ) l (( )) ) ( Str ( Domen ( S ) ) S c ( \ {P 1} ) (3.36) {( )}, ( ) ( Z ) = 0 {P 1} = min ( Z ) = 0 {P • } P • а сложность ({P 1} ) = 1.


( ) Следует уточнить, что структурная сложность системы без итератора Sc ( \ {P 1} ) отождествляется с ( ) только потому, что для системы S в аналогичной оценкой для структурированного домена Str ( Domen ( S ) ) целом используется один и тот же итерационный алгоритм.

Конструктивизм оценки структурной сложности ( • ) базируется на следующих метаязыковых суждени ях.

))). Руководству (( (( k (1 2) ) R+ Рассмотрим альтернативу из двух параметризаций: Par(1,2) ( S ) c P 1c (1,2) ясь аксиомой 3.1, введем в рассмотрение две системы S (1,2) e Par (1,2) ( S ). Считаем, что P 1 – итератор. Тогда ( ) – суть осуществление структурного анализа S ( ), по меньшей мере, в два раза легче S( ), а структура Str S( ) 1, 1 рекурсивный функтор ) : S ( k ({( P c ) ( P 1c 2 )} ( \ {P 1} ) ) ).

( Str S( 1,2 ) (3.37) 1 ( ) как мономор В силу принятия аксиомы 3.4, формулируем характеризацию искомого критерия S( 1,2 ) физм ( ( ) ( )) c S (1) S( ) 2. (3.38) true :

))) (( ) ( ( k 2 ) d ( S (1) (1) ( 2) c ( 2) 1 d S c 1 Цель анализа A ( S ) заключается в организации оптимального, минимального по вычислительной сложно ( out ( f ), i = 1.. n ) d S с вещественной параметризацией Par ( S ), критерий структурной сти расчета выходов i сложности ( S ) [ + – суть безразмерная величина, хотя бы в силу формализма абстрактной системы (3.15).

Связываем (согласно предложению 3.1 и мономорфизму (3.38)) нейтральные элементы полугрупп A и A : 1k (1 [ + ), 0 k 0. Теперь нам нужна теорема о рекурсивности структурной сложности, которая прибли жает нас к нахождению конкретных дескрипторов шкалы ( • ).

Теорема 3.1 (о рекурсивности структурной сложности).

Если параметричность Par ( S ) системы S характеризуется полем R + действительных чисел, то из этого следует, что структурная сложность ( S ) рекурсивно связана с параметричностью итератора отношением пропорциональности ( ))).

(( ( S c ) k 1 1 + S c \ {P 1 k Iter ( S )} (3.39) Доказательство.

Рассмотрим две возможные альтернативы: А и Б к (3.39) и покажем, что они, по крайней мере, противоре чат цели анализа A ( S ).

А) Предположим, справедлива формула ( ) ( S c ) k 1 S c ( \ {P 1} ). (3.40) Противоречие выявляется на циклическом топосе, как типичном индивиде категории замкнутых систем (см. рис. 3.14) ( ) P i = f •(i ) f•(i ), = P i, i = 1.. n. (3.41) ( j) ( ) ( j) ( j) (i ) !P j = f • f• : f• = f• Без ограничения общности полагаем i k i, i = 1.. ( n 1). В этом случае ) (( ( )) {} i 1, n : ( S c ) k i S c \ {P i } !v S 0, (3.42) что элиминирует мономорфизм (3.38) делением на 0. В то же время (3.39) оказывается явно разрешимым P 2 c ( 2 k 2) f2 f P 1c ( 1 k 1) P n 1c ( n 1 k ( n -1) ) f1 fn Рис. 3.14. Циклический топос ( ( ) ( )) S(1) S( 2) c i (1 + 0). (3.43) ( ) {} i 1, n : true : i d S(1) c (1) 2i (1 + 0) ( )) ( ( i k 2 i ) d S ( 2) c ( 2) Б) Предположим, справедлива формула ( ) ( S c ) k 1 + S c ( \ {P 1} ). (3.44) Рассмотрим антипод циклического топоса, а именно полный топос со структурой, изоморфной полному графу }) ({ = P i, i = 1.. n : P i, = n 1. (3.45) Рассмотрим два случая параметризации, как показано на рис. 3.15.

Ничто не мешает нам устремить n и проверить существование мономорфизма (3.38). Тогда для фор мулы (3.44) (( )) 1 + lim Sc ( \ ( P 1 c 1 ) ) = ( 1 ) R + : lim n = 1, (3.46) 2 + ( lim ( Sc ( \ ( P c 2 ) ) ) = ) n 1 1 n в то время как для формулировки теоремы ( ) ( ) 1 1 + lim Sc ( \ ( P 1 c 1 ) ) = = 1, (3.47) ( 1 ) R : lim n + ( ) ( ) 21 1 + lim Sc ( \ ( P 1 c 21 ) ) = n n поэтому (3.44) не соответствует (3.38).

P 1 c ( 1 ( 21 ) ) Рис. 3.15. Два случая параметризации полного топоса Других альтернатив в алгебрах A и A, кроме А) и Б) не существует, поэтому (3.39) – единственно воз можное рекурсивное связывание, что и требовалось доказать.

Вернемся к цели анализа A ( S ). Покажем, что известная задача поиска оптимального итерируемого мно жества (ОИМ) [116], будучи решена, не согласуется с A ( S ) по использованию возможностей вычислительно го кластера.

Сущность задачи поиска ОИМ состоит в следующем. Необходимо найти такое сочетание переменных сис темы вида (3.26) с примером агрегирования системы (3.28), что суммарная размерность этого сочетания была бы минимальной среди всех возможных сочетаний, само сочетание представляло бы собой итератор, а домен обладал бы (в нашей аксиоматике) нулевой структурной сложностью.

Введем обозначение: J i [ n1, n2 ] – i-е сочетание, среди упорядоченного множества пронумерованных лек сиграфически сочетаний из n1 по n2. Например, J 2 [ 7, 5] = {1, 2, 3, 4, 5, 7}.

Без ограничения общности считаем, что система Sc – изначально агрегирована. В задаче поиска ОИМ { } – оптимальное сочетание из общего числа дуг m кандидатов * необходимо найти J i* m, r *, r * m, i* 1, Cm r в итератор по искомому r * – мощности оптимального итерируемого множества (здесь C•• – общеизвестное число сочетаний из • по • ). Сформулируем задачу поиска ОИМ в наших обозначениях:

m J i* m, r * = Arg min j J i [ m, r ] J [ m, u ]d • (3.48) ( i*, r* ) jJ i [ m, r ] u = с абстрактором J [ m,u ] Sc ( S S )e \ {P k e J k [ m, u ]}.

• k Sk (3.49) k = Решая задачу (3.48), (3.49), мы не достигаем цели анализа A ( S ) : нет ясности, как организуются вычисле ния на кластере, ведь решением задачи поиска ОИМ является, по сути, множество индексов, а не иерархия. В дальнейшем мы покажем, что использование критерия структурной сложности дает нам возможность испра вить этот недостаток.

3.4. ОРГАНИЗАЦИЯ ИТЕРАЦИОННОГО РАСЧЕТА СЛОЖНОЙ ТЕХНИЧЕСКОЙ СИСТЕМЫ Предположим, тем или иным образом итератор P 1 выбран. Что происходит с системой при разрыве дуги P 1 ? Образуется подсистема по трем возможным вариантам связывания k ( \P 1 ) (см. иллюстра цию на рис. 3.16):

1. !v, : r, подсистема Sc имеет древовидную структуру с нулевой структур ной сложностью ( S ) =0.

2. v, : r, подсистема не сильно связная, но в ней существует по крайней мере одна сильно связная подсистема.

3. r, подсистема сильно связная.

В теореме 3.1 обосновано применение рекурсивной формулы для критерия оценки структурной сложно сти. Таким образом, разрыв дуги P 1 в случаях 2, 3 при доведенном до конца итерационном расчете системы S (т.е. до состояния ациклического топоса) – не единственный разрыв. В силу рекурсивности (3.39), в Domen ( S ) применяется тот же подход к оценке структурной сложности, что и во всей системе в целом. Таким образом, итератор P 1 порождает разрывы дуг внутри каждой сильно связной подсистемы (на рис. 3.16 они выделены серой заливкой).

Обобщением понятия «итератор» станет понятие «иерархия итераторов» *. Это рекурсивное множество ( ) * = {P i*, i = 1..} ( \ ) !r, ( Z ) = 0 {P 1* } inf. (3.50) * * В формуле (3.50) утверждается:

1) множество * содержит элементов;

2) удаление дуг множества * приводит систему в состояние ациклического топоса с древовидной струк турой;

3) вычислительная сложность применения итератора P 1* к системе ( Z ) = 0 – наименьшая.

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

S P 1 P P P Сильно связные подсистемы Рис. 3.16. Варианты состояния S после разрыва итератора P f• *(1,2) *(1,1) … *(1, • ) X X X … *(2, • ) X *(2,1) *(2,2) X X * = {P 1*,P 2,,...,...,...} *...,...

Рис. 3.17. Лексиграфический порядок в иерархии разрывов В работе [118] был предложен термин «пролонгатор» как критерий оценки сложности структурированных сильно связных систем. Забегая вперед, скажем лишь, что этот термин мы будем использовать далее по ходу изложения материала, а именно в разделе 3.5. Там же, в [118], было показано, как на основе вычисления слож ности по нерекурсивному критерию, можно сформировать алгоритм расчета замкнутой системы, состоящей из ММ. Следует заметить, что цель анализа A ( S ) остается идентичной цели анализа, принятой в работе [118], но критерий структурной сложности теперь классифицируется как рекурсивный оператор.

Будем называть A* ( S ) оптимальным алгоритмом итерационного расчета системы ММ. Определяем его и * из решения системы двух операторных уравнений:

) (( ( ) ) ( A* ( S) : S!v S)c ( Z) = 0 {P 1*} inf d A* ( S) ;

* )))) ( ((( ( ) ( S c ) k 1 1 + S c \ {P 1*} Sc k {*, \ •}.

= * inf • ( J ( +1) m ) (3.51) Переменные, участвующие в иерархии итераторов, составляют метавектор Z * = {z1, z1,..., z } Z, где Z n n n n Z = in ( fi ) out ( f i ) \ in ( f i ) out ( fi ), (3.52) i =1 i =1 i =1 i =1 а n, in ( f i ), out ( fi ), i = 1.. n – соответствуют агрегированному состоянию системы S.

Цель анализа будет достигнута на вычислительном кластере [122], если 1) количественная оценка структурной сложности подразумевает решение системы (3.51);

2) найден A* ( S ) – оптимальный алгоритм итерационного расчета системы ММ, по которому, кроме про чего, необходимо построить расчетный модуль системы.

Определение 3.9.

Расчетным модулем E y y системы S называется индивид программного обеспечения, разработанный для S получения всех переменных out ( f i ), i = 1.. n на выходе математических моделей из множества по алгорит му A* ( S ) на компьютерах вычислительного кластера ({µ ( •), i I } {P ), i I} c Ie ( Sc ( \ ) ).

Ey y S * min i i ( J 1 ) (3.53) В формуле (3.53) скобки y y символизируют программную реализацию с распределением вычислений.

В связи с введением понятия «расчетный модуль» для понятия «подсистема» имеет смысл сменить мат на индексированный терм S (j,) N [ j ]. В нем верхний индекс i служит для нумерации *( •,• ) i ричное обозначение X индексных блоков в *, соответствующих i-й подсистеме в иерархии, подобной той, что изображена на рис.


3.17. Индекс j нумерует уровень иерархии в блоке индексов, а индекс N [ j ] – размерность j-го уровня.

Иллюстрация к использованию E y y в соответствии с целью анализа дана на рис. 3.18. Расчет системы S начинается с разрыва итератора P 1* из иерархии * ;

формируется иерархия подсистем первого уровня вло женности. Далее, на втором уровне вложенности, выбирается P 2* и формируется иерархия подсистем второго уровня вложенности. Так продолжается до тех пор, пока удается путем разрыва и последующей структурной декомпозиции обнаруживать сильно связные подсистемы.

После того, как подсистема S1,1) полностью рассчитана, переходим к расчету S1,2 и так далее до S1, N [1]. За ( (1) 1 (1) тем рассматривается второй уровень в иерархии сильно связных подсистем, далее – третий и так вплоть до по следней подсистемы в иерархии разрывов.

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

f• Расчет подсис- (1) P 1* S темы завершен 1, П S1,1) ( () … … S1,1N [1] О Д С И S(2, ) S (2,)N [ 2] 1 … … С Т Е М S(u1),1 S (u1), N [u1 ] 1 … … Ы f• f• P 2* П S1,1) (2 () S1,2N [1] … … О Д С И S (2, N [2] 2) S1,1) ( … … С Т Е М S(u2 ), N [u2 ] Su2 ), ( Ы 2 … … f• f• f• P 2* Рис. 3.18. Иерархия расчетного модуля E y y S 3.5. ВЫЧИСЛЕНИЕ КРИТЕРИЯ СТРУКТУРНОЙ СЛОЖНОСТИ Начнем с того, что критерий структурной сложности будем называть пролонгатором.

Свяжем процесс вычисления пролонгатора с процессами назначения и модификации параметричностей.

Покажем, почему это необходимо сделать, прежде всего, на следующем рассуждении.

Предположим, в нашем распоряжении находятся две системы S1 и S 2 с одинаковой структурой связей между объектами систем, но с разной параметричностью: S1 c ( c 1 ) и S 2 c ( c 2 ). И пусть 1 = ( 1,..., (1) ), 2 = ( 1,..., (2) ), (1) = (2) / d, k = 1.. m.

(1) (2) Ограничимся рассмотрением случая m m k k (, k = 1.. m;

d ) ] +, d 1.

(1,2) k Возьмем в качестве примера 1 = 5, * = 6, * = 7, d = 10.

* 2 Пусть A* ( S ) – оптимальный алгоритм итерационного расчета системы S – нам известен. Тогда нам из вестен и способ вычисления пролонгатора.

Значения пролонгатора, в целях упрощения записи, будем обозначать 1 и 2 для систем S1 и S 2, соот ветственно. Предположим, согласно (3.39), 1 = 5 (1+ 6 (1+ 7 ) ) = 245;

2 = 10 5 (1+10 6 (1+10 7 ) ) = 210 000 210 3000 30 000 1 сдвиг + 50 5000 2 сдвига 213 050 245 Посмотрим на последнюю сумму более внимательно и сразу отмечаем, что число 245 можно получить, ес ли второе слагаемое сдвинуть влево на один, а третье – на два разряда. Аналогичная картина наблюдается в d ричной системе счисления. Сформулируем наше наблюдение в виде предложения.

Предложение 3.3.

Для пары систем: S1 c ( c 1 ) и S 2 c ( c 2 ), таких, что 1 = ( 1,..., (1) ), 2 = ( 1,..., (2) ), 1 2, (1) (2) m m (1) = (2) / d, k = 1.. m и (1,2), k = 1.. m, d ] +, d 1, вычисление пролонгатора вида (3.39) осуществляется по k k k схеме Горнера ( )) ( ( ) ( S1,2 ) = min S1,2 d ( d 1,2 ) = 1 1 + 2 1 + 3 (1 +... )..., (3.54) • а значение * = min { ( S1 ), ( S 2 )} можно получить из * = max { ( S1 ), ( S 2 )} путем сложения со сдвигом влево на l-е число разрядов самих слагаемых 1 *...* 1 ;

1 *...* 2 ;

...;

1, l = 1.. 1, участвующих в вычисле * * * 2 2 нии *, с последующим преобразованием вида * = d *.

Если предложение 3.3 доказать, то при d 1, d ] + и коллинеарности векторов параметричностей один пролонгатор может быть получен из другого без пересчета операторных уравнений. Можно показать спра ведливость этого при d 1, d [ + : только вместо сдвига на l-е число разрядов влево надо умножать на число d l. Следует еще раз особо подчеркнуть: векторы 1 и 2 не должны быть ортогональными.

Введем ряд определений.

Определение 3.10.

{ } Множество K ( ) = Ki, i = 1.., составленное из элементов )( ) ( f fl ( i ),..., fl(i ), fl(i ) l1( i ) 2 2 Ki e )( ) ( fl ( i ) fl(i ) fl ( i ), fl( i ) nd ( i )1 nd ( i ) nd ( i ) {P }) { j, j2i ),..., jcon ( i ) 1, jcon ( i ) } J [1.. m ], (i ) (i ) (i ) (, P j ( i ),..., P j ( i ), P j( i ) j1 i ) ( con ( i ) 2 con ( i ) {l, l2i ),..., lnd)( i ) 1, lnd)( i ) } J [1.. n ], (i ) (i (i ( (3.55) называется множеством контуров структуры.

Определение 3.11.

Матрица \ ( ) = ( ^ ij ), каждый (i, j)-й элемент которой бинарно выражает принадлежность j-й дуги к m каждому элементу множества …(), а именно 1, если P j K i ;

(3.56) ^ ij 0, если P j K i, называется матрицей контуров () структуры и является матричным образом множества …().

Определение 3.12.

Матрица V ( ) = ( gij ) nn, каждый (i, j)-й элемент которой выражает достижимость объекта f j из fi :

1, если f j f i ;

(3.57) gij 0, если f j q fi, называется матрицей достижимостей () структуры и является матричным образом множества G (см.

(3.12), раздел 3.1).

Определение 3.13.

Контурностью ( P k ) дуги P k называется величина, равная количеству вхождений P k в контуры структуры = de ( S ) ^ (P k ). (3.58) ik i = Определение 3.14.

{ } r, r 1, r = P 1, P 2,..., P m ( r ), Контуралом уровня называется подстановка подмножества )( ) ( ( ) r = J • {1...m}, r k m ( r ), такая, что каждый ее элемент имеет одинаковую кон турность, равную r, и, кроме того, элементы контурала упорядочены в порядке возрастания параметричности { } j 1, m ( r ) 1 :

m 1 P k | ( ( P k ) = r ) r. (3.59) ( ( )) ( )) ( j k de P j j +1 k de P k= j + Определение 3.15.

Контуриалом () структуры называется множество всех контуралов всех возможных уровней, свойст венных структуре {~ : ( ~ d ) ( ~ )}.

( d k +1 ), k = 1.. k J( ) J( ) (3.60) k + k k ~k Определение 3.16.

{ } структуры называется подстановка вида J [1.. m ], где Контурионом = P 1, P 2,..., P m J [1...m ] = { j1, j2,..., jm } – множество индексов, удовлетворяющих условию:

(( ))) ( )) ( ( l = 1.. m 1: jl k de P jl k de P jl + jl + (3.61) (( ) ( )) P jl P jl +1.

Определение 3.17.

Оператор Dec, являющийся решением операторного уравнения (( ( Dec ( k de ( S ) ) : i k de S i | k = 1.. 1:

i = )) ) ( )( i, j {1.. n} : fi d S K q f j d S k +1 (3.62) (( rank (V d ) = F d S ) (( Dec ( k de (S ))) = )), c i i i i i i i называется оператором структурной декомпозиции. Здесь – число сильно связных подсистем, порождаемых действием на структуру оператора Dec. Необходимо особо подчеркнуть: подсистемы Si, i = 1.. – иерархи чески упорядочены, что соответствует квазитреугольной форме матрицы смежности [42].

Определение 3.18.

Оператор Gm, являющийся решением операторного уравнения ( )( ) Gm ( S ) : Sc ( ( c ) F ) S c ( ( c ) F ) | Gm ( Sc ( ( c ) F ) ) = ( Sc ( ( c ) F ) ), \ ( ) c ( ( ( i {1.. \ ( ) }l ( j |^ =^, l = 1.. ) ) jl jl (j {1.. } (i | ^ =^, l = 1.. \ ))), lj li ( ((P,P ) = (( f f ), ( f f )), k de (P ), k de (P )) c * * 1 2 1 2 1 1 2 ( f F \ { f, f, f }, i {1.. n} :P k (( f f ) ( f f )) )) * * * i i i 1 2 ((((P c )d )e Gm ( S ))k ( f k ( f, f )) f )e ( )) * 1 1 1 1 2 1 (( f ( f k ( f, f ))) e ( ))) e ( k min (, )), (3.63) * 1 2 2 2 1 1 1 ( F \ • ) e ( ad Gm ( Sc ( ( ( c ), F k {•, f, •, f, •, f, •, f, •} :

1 2 3 ( ( P c )k ( f t f ), ( P c )k ( f t f ) ) )) :

• • 1 2 1 1 3 ) ( ( f f )( f f ) ) f k f f, f k f f, k + 1, • • 1 3 2 4 1 1 3 2 2 называется оператором минимизации структуры.

Интуитивно подразумевается, что оператор Gm продуцирует композицию из следующей пары гомомор физмов:

1) «стягивание» дуг для удаления «висячих» вершин с последующей минимизацией параметричностей;

2) «склеивание» кратных дуг и «схлопывание» вершин.

В операторном уравнении (3.63) присутствует обратный оператор Gm 1 : выдвигается требование обрати мости минимизации. Если это требование игнорировать, то мы не сможем восстановить обратный ход рекур сии при фиксации оптимального алгоритма A* ( S ).

Итак, наша цель сейчас заключается в поиске оператора, однозначно определяющего структурную слож ность системы Sc ( ( c ) ( F c ) ), т.е. надо найти конкретизацию (3.39) применительно к оценке структур ной сложности замкнутых технических систем большой размерности.

Так как мы рассматриваем строго детерминированные системы с однозначно определяемой структурой, то уместен еще более короткий терм: ( ), подразумевая при этом, что c.

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

Построим цепь дальнейших рассуждений. Пусть в сильно связной структуре некоторая дуга из первого контуриона P 1 ~1 предназначена к разрыву (рис. 3.19). Двойными линиями обозначены связи в системе, исчезающие под действием оператора структурной декомпозиции Dec. Подействуем на вспомогательное мно ( ) жество Q k \ P 1 ~1 оператором Dec. В результате этого Q будет поставлена в соответствие некоторая совокупность сильно связных подсистем (по крайней мере – одна подсистема), т.е. произойдет связывание по схеме e P 1 ( )).

( Q k { i } k Dec Q k \ P 1 ~1 (3.64) i =1 S # # # P ( ) Рис. 3.19. Удаление P 1 и образование e P 1 -го числа подсистем r На полученную совокупность подействуем оператором минимизации e P 1 { i } k i =1 Q k Q d Sk Gm Sc. (3.65) ( )) ( Dec k \ P 1 ~ Q Иллюстрация к полученному выражению дана на рис. 3.20. Сформировалась «новая» система S S с числом сильно связных подсистем e P 1, и подсистемы в ней никак не взаимодействуют. Это отнюдь не озна e P { } чает, что пропавшие связи навсегда потеряны. Если доопределить действие объединения (в данном i i = случае это просто удобное обозначение), то возврат из рекурсии обеспечен.

В безымянных подсистемах не осталось транзитивных замыканий к бинарному отношению : под дейст вием оператора Gm все они заменены обобщенными дугами. Объекты системы после действия оператора ми нимизации также становятся обобщенными (см. иллюстрацию на рис. 3.21).

(( c ) ( Fe )) Sc S c r e r r Разрыв ( 0) r P ( 0) e 0 \ P r ( S c ) S = Q r r r = Рис. 3.20. Иллюстрация к формуле (3.65) Протокол минимизации, показанной на рис. 3.21, выглядит так ab bc P ab k ;

bc k min ( ab, bc ) ;

f A k { f a, fb } ;

f B k f C ;

(3.66) P AB k ( f A f B ) ;

k ( f B f A ) ;

k ca ;

AB k ac + bc.

BA BA Если в качестве разрываемой дуги взять P 2 вместо P 1, а затем P 3 и далее до P ( ~1 ), то для каждого от дельно взятого k = 1.. ( ~1 ) мы будем использовать одни и те же незыблемые правила, и суть их уже проясняет ся – нас интересует оптимальный номер дуги в первом контурале, соответствующий (( ( \ {P }) + 1) ). Этот номер k * можно найти для каждого контурала.

min k k 1 k v ( ~) fb Транзитивное P bc P ab замыкание P ac fa fc P ca «Схлопывание» «Склеивание»

P bc P ab;

c f a, fb fc P ca P AB f B fA P BA Рис. 3.21. Иллюстрация к минимизации структуры Если перебирать все без исключения дуги исходного контурала и для каждой вычислять сложность, то по иск оптимального k * при значительной размерности исследуемой системы займет чрезвычайно много времени.

На рис. 3.22, а показана возможная диаграмма значений пролонгатора ( ) умозрительной системы, причем он изображен таким, каким его нам хотелось бы видеть, а именно: не рассматривать дуги, находящиеся правее минимума выпуклой оболочки. На том же рисунке, случай б), изображен наиболее нежелательный характер поведения ( ). Если обнаружится, что функция ( ) в самом общем случае все-таки может иметь такой вид, тогда придется вычислять пролонгатор путем полного перебора или, в лучшем случае, методом «ветвей и границ» [113] (почти полный перебор) Полный перебор крайне нежелателен всегда, а в данном случае особенно: использование пролонгатора подразумевает анализ систем большой размерности, а для них, как известно, методы, близкие по трудоемкости к полному перебору, являются непригодными [85, 86].

abcd P а) a b c d conv P ke P k * * k eP P Lin min P 1 r б) ke P k k * e P 1* Рис. 3.22. Иллюстрация к возможным случаям поведения функций ( P 1 ), conv ( ( P 1 ) ) и Lin min P 1 в контурионе r Вернемся к рис. 3.18. Показано, что на дне рекурсии находится (и это неизбежно в силу минимизации структуры перед вычислением ее структурной сложности) «элементарная» подсистема, в которой всего два объекта и две дуги: ( f1, f 2 ), ( P 1, P 2 ).

Согласно принятой аксиоматике, сложность «элементарной» подсистемы равна минимальной параметрич ности:

( ({P, P }c {, }))d min (, ) ( 1 0 )d min ( 1, 2 ).

S c (3.67) 1 2 1 2 1 В формуле (3.67) нулевая и единичная сложности сначала выписаны в соответствии с их определениями, а затем связывание с минимальным значением параметричности показывает, что в данной работе мы ограничива емся рассмотрением систем с вещественной параметризацией. В связи с этим, казалось бы, очевидным обстоя тельством формулируем следующую аксиому.

Аксиома 3.5.

Минимальная сложность системы, вычисляемая рекурсивно на основе понятия (3.29) «мультипликативно сложнее», определяется с точностью до нулевой и единичной сложности, и это связано с индукцией знаний, применяемых к цели анализа системы A ( S ).

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

Рассмотрим некоторую функцию ( x ) скалярного аргумента x : ± x = dom ;

:, где множе ство, равно как и сама функция ( x ), способны удовлетворить всем тем требованиям, которые могут предъявляться к ним по ходу рассуждений.

Определяем функцию * ( z ), как сопряженную к кусочно-постоянной функции ( x ) : = [ 0, C ), ( x j ) = x j, 0 = x0 x1... xn 1 xn C 0, (3.68) следующим образом * ( z ) = inf { ( x ) + x z}. (3.69) x Определение функции ( x ) проиллюстрировано на рис. 3.23.

Справедливо равенство { } inf * ( z ) = inf ( x ) + x inf { z}. (3.70) z x z Скомпилируем формулу (3.70) в область наших исследований, оставляя при этом общепринятую символи ку:

– будем обозначать (временно) минимальную сложность системы z как inf * ( z ), тогда запись (3.70) продуцирует суждение «Величина inf * ( z ) равна нижней грани суммы двух слагаемых:

y = ( x) [ x2, x3 ) [ x2, x3 ) = 45° [ x0, x1 ) [ x1, x2 ) n { } y x j, x j +1 ) j = x X y = (x) y {[ xn 1, xn ),..., [ x0, x1 )} x ( x4, x3 ] ( x2, x1 ] ( x1, x0 ] ( x3, x2 ] Рис. 3.23. Функции (x) и (–x) 1) ( x ) – сложности разрыва самой первой дуги контурала, начиная с которой проводится анализ систе мы z. Для точки x справедливо равенство: x = ( x ) ;

2) x inf { z} = ( x ) inf { z} – произведение параметричности первой разрываемой дуги на величину оста z z точной сложности системы z без первой разрываемой дуги;

– заметим, что { ( y )}.

inf { z} = (3.71) inf y{[ xn1, xn ],..., [ x0, x1 ]} z X В итоге получаем некий абстрактный аналог пролонгатора в классе функций, сопряженных к кусочно постоянным функциям { } inf { ( z )} = inf ( x ) + ( x ) { ( y )}. (3.72) inf y{[ xn 1, xn ],..., [ x0, x1 ]} z X x X Подведем итог всех рассуждений данного пункта главы: дадим наконец определение пролонгатора как оператора Prl ( S ).

Определение 3.19.

Оператор Prl ( S ), действующий на систему S, переводит Sc ( ( c ) ( Fc )) в совокупность, состоя щую из оптимальной последовательности итераторов, по которой формируется расчетный модуль Ey y, осу S ществляющий рекурсивный итерационный расчет всех Yвых e µ i ( ), i = 1.. n на вычислительном кластере.

i Prl ( S ) : S Prl * ( S ) k k •, (0) min conv k (0) P k 0 k, k {1..m} 1 • k A rg, (3.73) ( 0) e 0 \ P 1 min conv r c r r = (r ) P j (3.74) Q r d r d r |(3.75), j 1.. m( r ) k r, (3.74) e r 1 \ P (jr ) Q Q r k r d S k Gm S c { i } k r r i = (3.75) (r) Q Dec r k r 1 \ P j.

3.6. АЛГОРИТМИЧЕСКИЕ АСПЕКТЫ ВЫЧИСЛЕНИЯ КРИТЕРИЯ СТРУКТУРНОЙ СЛОЖНОСТИ Из предыдущих параграфов данной главы выяснилось, что для сокращения числа вариантов при вычисле нии конструкций типа min ( conv(•) ) в уравнении (3.73) нам поможет выпуклость функции.

Возобновим рассуждения, проиллюстрированные на рис. 3.23.

1. Пространство кусочно-постоянных функций ( x ), : изоморфно пространству функций. Всегда можно найти такие функции 1 ( x1 ) e 1 1, 2 ( x2 )e 2 2, ( x1,2 X 1,2 )e 1 2, что из этого следует 1 ( x1 ) 2 ( x2 ) и 1 1 2 2.

( x ) = Lin ( x ), 2. Если обозначить то справедливо равенство i : x [ xi, xi +1 ], 0, ( ) Arg min Lin =, фактически означающее, что число локальных мини { ( x )} ( x ) = inf x x ( ), x + ( ) мумов непрерывной линейной оболочки функции ( x ) равно числу нарушений монотонности в последова тельности { xi, i = 1.. n} (рис. 3.24).

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

Введем в рассмотрение функцию () P k : ~k min e P k =P 1*, k = 1... 3.76) ~k () Полный перебор всех дуг контуриона заключается в нахождении всех P k, k = 1... В предыдущих () рассуждениях относительно функций ( x ) и ( x ) заменим на P k, тем самым мы • Совокупности контуралов и минимумов выпуклой оболочки (•) max{( )} ~k • … P1 P2 P • ( }) { min conv { ( r )} • r r Pk ( x ) = Lin ( x ) max{( )} • ( x) • P k ~k X xe J … xm = m x1 x2 xk Рис. 3.24. Изоморфизм функций P k, ( x ) и ( x ) разбиваем процесс поиска минимума пролонгатора на два вложенных цикла (рис. 3.25, где значком помечены те части контуралов, которые подлежат перебору):

1. Внешний цикл по перебору контуралов, k = 1...

2. Внутренний цикл, для каждого k-го контурала, по i = 1.. ~k.

3. Проверка условия выхода из k-го контурала, и, если оно выполнено, – выход из цикла по i.

4. Проверка условия выхода из контуриона. Если условие выполнено – выход на вышестоящий уровень рекурсии.

Теорема 3.2.

{ } При k = idem =, k = 1...m справедливо неравенство ( P 1,1 ) ( P 1,2 ), где P 1,1 2 = arg min ( P 1,1 2 ) – * * * ~1 такая дуга из контурала ~12, удаление которой обеспечивает минимальное значение величине оценки оста точной структурной сложности.

Доказательство.

Пусть ( P 1,1 ) = k1 k2 = ( P 1,2 ), например k1 = k2 + 1. Дополнительный контур, остающийся в структуре по * * * отношению к разрыву P 1,1, обозначим K. Тогда справедливо следующее:

{ } { } 1,1 ( • )d 1,1, 2,1,..., 1,1,1 1,2 ( • )d 1,2, 2,2,..., 1,2, * inf min ( • )k ( P 1,1 ) min ( • )k ( P 1,2 ) =, * ~2 ~1 Выход из рекурсии Рис. 3.25. Поиск * как минимизация выпуклых оболочек так как при вычислении ( P 1,2 ) мы вынуждены удалять K e 1,1 ( • ), а минимальная сложность этого разрыва * равна.

Следствие.

При вычислении пролонгатора системы, для которой = const, достаточно на каждом из этапов рекурсии разрывать только первую дугу контуриона.



Pages:     | 1 | 2 || 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.