Большие системы. Связность, сложность и катастрофы - Касти Дж.
Скачать (прямая ссылка):
учитывать эти структурные компоненты системы. Обозначив 0(E) произвольную
вещественную меру сложности, определенную для системы Е, введем следующие
аксиомы.
Аксиомы сложности
1. Иерархия. Если Е0 подсистема Е, то
0(ЕО)<0(2),
т. е. подсистема не может быть более сложной, чем система в целом.
2. Параллельное соединение. Если Е - 2i 0 S2 (r) ... ф Е*, т. е. Е
является параллельным соединением систем {2;}, то
0(2) = max 0(Ег).
Kl<k
3. Последовательное соединение. Если Е = Ej (r) 22 (r) ... ... (r)Е*, т. е.
Е является последовательным соединением подсистем {Е,}, то
0(2)<0(Е,) + 0(Е2) + ... +0(2*).
4. Соединение с обратной связью. Если присутствует операция обратной
связи (c) из системы Е2 в систему Еi, то
0 (2, (c)2г) < 0 (2,) + 0 (2,) + 0 (22 (c) 2,).
(Заметим, что аксиома 3 является частным случаем аксиомы 4, если
отсутствуют обратные связи.)
Сложность структуры больших систем
119
5. Нормализация. В классе систем, удовлетворяющем этим аксиомам,
выделено подмножество систем ??, для которых
0(2) = 0 для всех
Этих аксиом оказывается вполне достаточно для определения меры сложности
систем, задаваемых различными способами; в некоторых случаях они
однозначно определяют меру сложности.
Заметим, что эти более или менее стандартные декомпозиционные аксиомы
учитывают изложенные выше представления о сложности. Поскольку любая
система может быть представлена в виде последовательно-параллельно или
ка-скадно (иерархически) соединенных подсистем (возможно, с обратной
связью), то аксиомы 2-4 поясняют структуру связности таких декомпозиций.
Иерархические аспекты отражены в аксиоме 1, в то время как динамические
аспекты - в аксиоме 5. Таким образом, приведенные аксиомы сложности
кажутся довольно разумными по крайней мере потому, что не упущен ни один
важный аспект сложности.
При изучении процессов с конечным числом состояний, эти аксиомы являются
наименьшим множеством, задающим меру сложности однозначно. Это еще раз
подтверждает естественность выбранных аксиом. Наконец, аксиомы очень
удобны для различных алгебраических подходов к анализу и вычислению
сложности.
Теория сложности для топологических форм также представляет значительный
интерес, хотя, к сожалению, до сих пор не ясно, как задавать топологию
форм с помощью алгебраического аппарата. Поэтому необходимо либо найти
такие процедуры, либо ввести новую меру топологической сложности. В
последнем случае, для того чтобы успешно выполнить задачу, необходимо
модифицировать вышеприведенные аксиомы.
СЛОЖНОСТЬ АВТОМАТОВ
С системно-теоретической точки зрения наиболее продвинутой теорией
является теория сложности процессов, моделируемых конечными автоматами.
Напомним, что каждый автомат М порождает конечную полугруппу
преобразований (Q, &~*), где Q - пространство состояний автомата М, а -
полугруппа всех преобразований Q. Дадим определение сложности, используя
алгебраическое понятие узлового произведения, и рассмотрим связь этого
определения с автоматами и аксиомами сложности.
120
Сложность структуры больших систем
Определение 4.1
Назовем групповой сложностью S) полугруппы
(X, 5) наименьшее целое п, такое, что
где Gi, ..., Gm - конечные простые группы, Со, ..., Са - конечные
комбинаторные полугруппы (триггеров); "ш" обозначает операцию узлового
произведения.
Следовательно, групповая сложность полугруппы (X, S)- это минимальное
число возможных комбинаций простых групп и комбинаций комбинаторных
полугрупп, составляющих (X, S). Используя теоремы декомпозиции, можно
определить сложность в терминах декомпозиции фазового пространства.
Например,
Так как комбинаторные полугруппы представляют автоматы, а не вычисления,
то основным сложным элементом является простая группа, в которой
производятся такие элементарные арифметические действия, как сложение и
умножение. В соответствии с теорией Крона - Роудза, возможна декомпозиция
автомата в примитивные и неприводимые подавтоматы, причем решение задачи
зависит от структуры компонент и длин вычислений. Поэтому и сложность
зависит не только от длины цепи вычислений, но и от степени сложности
каждой компоненты, входящей в цепь. Таким образом, сложность учитывает не
только общее число вычислений в цепи (вычислительный аспект), но и
внутреннюю сложность подавтоматов, отражаемую узловым произведением
(структурный аспект). Эвристически вычислительная часть автомата
представляется количеством "циклов" в машинной программе, которая
вычисляет действие на Q.
Рассмотрим взаимосвязь этого определения групповой сложности и
вышеприведенных аксиом сложности.
Теорема 4.1х)
Пусть 0: Mjr^N (где N - множество неотрицательных чисел, а М$т-множество
всех конечных автоматов) удовлетворяет всем аксиомам сложности, причем
аксиома нормализации (аксиома 5) имеет место с
#о(*. 5) - min #G |
Т\Т - последовательно-параллельная или каскадная декомпозиция
}•
0(?/3) = О, 0 (/>,)=" 0,
]) Доказательство теоремы можно найти в работах, приведенных в конце
