Порождающие системы

Лекция 9

4. Порождающие системы

4.1 Системы с поведением

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

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

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

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

Рекомендуемые материалы

, (4.1)   

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

, (4.2)

где — целая константа (положительная, отрицательная или нуль). При   называется тождественным правилом сдвига.

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

4.2 Выборочные переменные и маски

   Пусть задана обобщенная представляющая система I, опре­деляемая уравнением (2.12). Обозначим через V множество пе­ременных из I, а через R набор правил сдвига, рассматриваемых для этих переменных. Тогда множество переменных

,(4.3)

называемых выборочными переменными, может быть введено с помощью уравнений

,(4.4)

для некоторых переменных и правил сдвига ;  обозначает состояние выборочной переменной  при значении пара­метра w, а  — состояние переменной   при значении па­раметра , т. е. при значении, полученном для заданного w, при применении правила сдвига . Для полностью упорядоченно­го параметрического множества, правила сдвига которого имеют вид (4.2), уравнение (4.4) может быть переписано в более опре­деленном виде

,(4.5)

   Так как любое правило сдвига из набора R может быть примене­но к любой переменной из множества V, то множество всех воз­можных выборочных переменных представляется декартовым произведением . В действительности рассматриваются выборочные переменные, характеризуемые отношением

, (4.6)

так, что всякой паре  соответствует одно уравнение из (4.4). Отношение М представляет схему соседства на пара­метрическом множестве, в терминах которого определены выбо­рочные переменные. Эта схема обыч­но называется маской.

Для введения идентификато­ров выборочных переменных k должна быть введена некая одно­значная функция (кодирование).

, (4.7)

где — это количество элементов множества М.

Если выборочная переменная   определена через перемен­ную  и некоторое правило сдвига согласно уравнению (4.4), то множество состояний , очевидно, То же самое, что и множество состояний  т. е.  . Однако  для удобства обозначений будем множество состояний выборочной переменной обозначать ; смысл любого  однозначно определяется маской  в терминах одного из множеств . Таким образом, декартово произведение

,(4.8)

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

4.3 Маски в случае полностью упорядоченных параметрических множеств

   Рассмотрим сначала понятие маски и связанное с ним пове­дение представляющих систем для полностью упорядоченных па­раметрических множеств, а затем распространим его на частично упорядоченные параметрические множества. Обозначим полно­стью упорядоченные параметрические множества , а их элемен­ты . При этом уравнение (4.4) немного изменится:

, (4.9)

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

Состояние d для M при t=7	=		=	2
	=		=	0
k	=		=	3
	=		=	2
	=		=	1
	=		=	1
Маска M	=		=	0
	=		=	3
	=		=	0
Справочник	=		=	2

                     в)                                                                                       а)

                        б)

Рис.4.1. Пояснение понятия маски для полностью упорядоченных параметрических множеств.

переменных из множества V, a столбцы — целыми константами , связанными с правилами сдвига вида (4.2). Элементы матрицы или пусты, или представляют собой идентификаторы k выборочных переменных, приписанные парам согласно (4.6); пустые эле­менты матрицы соответствуют элементам , не входящим в маску. В визуальном представлении становится ясно, почему используется термин «маска».

Часто бывает удобно разбить маску М на подмаски М„ каж­дая из которых связана с одной переменной и, из подобной си­стемы. Формально

13 Фрактальные алгоритмы - лекция, которая пользуется популярностью у тех, кто читал эту лекцию.

, (4.10)

 В визуальном (матричном) представлении подмаски  представляют собой строки. В любой маске один столбец соответствует тождественному правилу сдвига . Этот столбец имеет особое значение, по­скольку связанные с ним выборочные переменные идентичны базовым переменным заданной представляющей системы. Будем этот столбец в масках называть справочником. Если маска по­мещена на матрицу данных таким образом, что справочник сов­падает с определенным значением t, то маска выделит только не­которое подмножество элементов, а именно элементы, представ­ляющие полное состояние выборочных переменных при данном значении t. Так, например, на рис. 4.1,б изображена маска (оп­ределенная на рис. 4.1,а), помещенная на матрицу данных d при t=7 (справочник маски совпадает с t=7). Полное состояние выборочных переменных для этого положения маски показано на рис. 4.1,в. Состояния справочника выборочных переменных  в точности те же (для любого t), что и состояние базовых переменных соответственно . Остальные выборочные переменные представляют собой состояния из параметрического соседства в t. Для лю­бой маски при любом t схема соседства сохраняется. Если t — время, то переменная  будет представлять будущее (относи­тельно рассматриваемого значения t) состояние переменной , а переменные  и будут представлять, прошлые со­стояния переменной  любая маска представляет определенную точку зрения, в со­ответствии с которой представляются ограничения на базовые переменные.

К.Р. № 9

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