Название: Инвариантно-параметрическое представление и обобщенная ассоциативная обработка символьной и смысловой информации(Токмаков Г. П)

Жанр: Информационные системы и технологии

Просмотров: 2886


2.3. ипп отношения двух компонентов

Формально множество компонентов и элементов объединяются в целое через систему отношений. Любое отношение предполагает сохраняющиеся свойства, а структура целого определяется совокупностью инвариантных отношений между его составными частями. Поэтому сначала приведем формальное определение отношения. Как известно из работ [72,73], бинарное отношение R на двух множествах А и В определяется как подмножество декартова произведения АхВ, определенное высказываниемр(а,Ь), а е А, Ь е В: R= {а: А; Ь:В / р(а,Ь)} с АхВ.Другими словами, в подмножество R входят только те совокупности элементов из подмножеств А и В, для которых высказываниер(а,Ь) принимает значение ИСТИНА. В этом определении отношение определяется через инвариантное свойство, которое выражается через предикатную функцию. Приведенное определение в целом удовлетворяет нашим целям, но для дальнейших построений, в основе которых лежит отношение между двумя компонентами, каждое из которых обладает множеством свойств, необходимо распространить его на случай многомерных пространств. При этом рассматриваемое отношение между двумя компонентами можно представить как частный случай объекта, состоящего из двух компонентов, связанных между собой структурными взаимосвязями. Затем полученные результаты с необходимыми дополнениями распространим на объекты произвольного типа.2.3.1. Описание объекта из двух компонентовС этой целью рассмотрим объект S, состоящий из компонентов KuKj, описываемых п свойствами х},...,х'„, т.е. S—>Ki(x'i,...,xJn),Kj(x'],...,x'tl). Другие свойства объекта S пока рассматривать не будем, а зафиксируем наше внимание на том, что данный объект состоит из двух компонентов. Множество компонентов Kj(xJ],...,х1 J данного объекта и других подобных объектов можно представить как точки в пространстве Х=(Х1,...,Хп), где хeXh...,х'„еХ„, a Kj -идентификатор /-го компонента в пространстве X.А теперь рассмотрим всевозможные пары К^х,            KJ{x'i,...,x'n) в этомпространстве, где i,j=l,...,M, i^j, в результате чего получим пространство компонентов, описываемое как декартово произведение ХхХ. Затем определим "взаиморасположение" компонентовK^xj,...,Хг) kKj(x! 1,...,х!п) в пространствеX по соотношению их одноименных свойств, что можно записать как zv=fv(xV)x!v), где v~l,...,n, fv - функция, определяющая характер соотношения свойств х и х'у, zv - значение, которое сопоставляется значениям х и x*v, находящимся в соотношении, определенном функцией fv. Всевозможные значения zv(v=l, ...,п) для всех пар Kj(x'},...,xlr) и К/х'1,...,х'п) формируют пространство Z=(Z1,...,Zn), где Zv={£i,...,£Nv}.Таким образом, с одной стороны, мы получаем пространство, описываемое декартовым произведением ХхХ, в котором объекты, состоящие из пар компонентов, описываются в терминах свойств компонентов, с другой стороны, получаем пространство Z, в котором объекты описываются через соотношения этих свойств. Данные пространства связаны между собой функционаломF=F(f1(x],x!]), .../„(х^п)),

который производит отображение пространства ХхХ в пространство Z. В про-

странстве Z все пары компонентов К{(х1], ...,х1„) и K/x/j,         для которыхzh...,zn ^-F(f1(xl1,xj1), ...fnfx'nx/J), сливаются в точку z = {zr h...,z), поэтому каждой точке пространства Z соответствует подпространство пространства ХхХ, что можно записать какrl г]X   ],..., X 2пz i,...,z „ ->Zrrk rk X  ],...,Х 2пгде г = 1,...,N. Отсюда следует, что функционал осуществляет гомоморфное отображение пространства ХхХ на пространство Z, т.е. F: Z <—ХхХ.Нас будет интересовать и обратное отображение, т.е. отображение точки пространства Z на пространство ХхХ. Но, как мы уже отметили, отображение F: Z <— ХхХ представляет собой гомоморфизм, поэтому без дополнительных условий произвести однозначное отображение произвести нельзя. В качестве такого дополнительного условия можно приять свойства одного из компонентов рассматриваемого отношения. В этом случае с помощью функций fv(zv,x!v) мы можем определить значения свойств х другого компонента. При этом мы фактически определяем отображение F':ZxX—>X. Итак, значения свойств обоих компонентов отношения нам теперь известны, и мы определили требуемую точку в пространстве ХхХ с помощью функционалаF^FW^O.-Jn'^Jn).Таким образом, мы определили пространство X, в котором заданы компоненты объекта, пространство Z, в котором каждой паре компонентов из пространства X соответствует точка, и функционалы F и F которые отображают пары компонентов пространства ХхХ в точки пространства Z и обратно. Пространство Z, как и пространство X, «-мерное. Полученная конструкция приведена на рис. 17. Этим мы завершили построение конструкции, на которой будем определять отношения между компонентами.Выше для определения совокупностей компонентов Kj и Щ мы применили термин "взаиморасположение". Сделали это мы потому, чтобы отличить определенные таким образом совокупности от объекта, в котором должно быть зафиксировано некоторое свойство. Под термином "взаиморасположение" имеется в виду определение характера вычисляемых соотношений между значениями одноименных свойств, задаваемых функциями fvQ, v=l, ...,п.Таким образом, определить "взаиморасположение" двух произвольных компонентов в пространстве Х - значит определить упорядоченную последовательность значений функций fv(xx^v) для всех v=l,...,n. Так как в качестве аргументов этих функций могут быть любые значения x,xlveXv, то мы можем записать эту последовательность функций в обобщенном виде fv(Xv,Xv) для всех

Y  ' V J X Х J X ',XJ v ' vX ',хJп ' п

f/x/.x/), ... JJx^xJ), ... JJx^i), ... fnCKj,xJ) zl(x' V—-x' 2n)

Подпись: 	
z2
V	\
	\
	
z3
V	\
     , \

К}(х/, .

Ку(х,2, .

 

 

К,(х/, .

■ ,х •)

 

 

 

 

К (xN

 

 

z *

 

 

z k

 

 

zk

 

 

 

и

 

 

V

 

  ,

1

     ,

z,(x3,,...,x32n)Z,(xk,   ^2 J

 

 

 

7 N "u

 

ZNV

 

ZN n

 

 

 

 

 

4

к

 

 

 

X J xJ *1

Рис. 7 7. Отображение пространства XxX в пространство Z и обратноv=l,...,n. Это позволяет нам рассматривать данную последовательность как некоторую процедуру, которая при подстановке определенных значений x,xlveXv v=l,...,n в качестве аргументов вычисляет упорядоченную последовательность значений zj, ...,z„, что можно записать как^i,---,^w,---,^n ^fiiXhXi):!], ...$п(ХП)Хг)> (1) где qw=zi ,...,z„ - w-я точка пространства Z.А теперь зафиксируем одну из переменных пространства zv <eZv, присвоив одно из возможных значений из множества Zv, т.е. zv=^JvZv (Jv=l, ...,NV). Отсюда следует, что функция fv(x'V)x/v) получает постоянное значение и в качестве ее аргументов уже не могут быть произвольные значения из Xv. На эти значения налагается условие, которое на языке исчисления предикатов можно записать как^v&Z>!w^, (2) что означает, "существуют такие xJv, для которых при различных значениях х справедливо ^JvZv=fv(x,v,x'v) ". Предикат pv в этом выражении отражает функциональную зависимость fv между переменными х, л/у и константой \%JvZv. Другие же переменные,как и прежде,могут принимать произвольные значения из заданных областей определения.Данное условие, которое можно записать как qvj : (fvJv = fv(x,x*v), разбивает пространство компонентов на два класса: класс пар компонентов, для которых это условие выполняется, и класс пар компонентов, для которых условие не выполняется. Для пар компонентов второго подпространства зафиксируем еще одно условие, которое разбивает второе подпространство еще на два класса. Этот процесс можно продолжать и таким образом можно выделить Kv фиксированных значений таких, чтоq i :ifV] =/у(х,х*у),qvJv :^vjv =fv(x'v,x!v),    (j)q Kv -'<fv —fv(x\^v)разбивают пространство ХхХ на Kv+1 подпространств. Причем первые Kv подпространств определяются константами из множестваt = fl,-,tjV,..,tKv, (4)а в последнее входят те пары компонентов, для которых ни одно из условий (3) не выполняется. Из условий (3) следует, что 2п-1 свойств пространства компонентов ХхХ по-прежнему не подвержены ограничениям, тогда как значение свойства х обусловлено значениями свойства x*v и констант из (4). Поэтому можно сделать вывод, что каждый из объектов полученных подпространств описывается с помощью 2п-1 свойств компонентов Kf и Щ и константы из (4), которая является общей для всего подпространства пар компонентов. С учетом принятых условий разбиение пространства компонентов ХхХ на классы можно записать как

zl ■■■ ^Jv ■■• z„ —>Tjv 1 1X J...X 2n-lJv    ' ' Jv X   ]...X 2n-l1 1 X J...X 2n

V VI    X J...X 2n     I 7где z7.-Z7;...;z;.-Zv-(fZv;...;2„.-Z№ Jv = l,...,Nv.Приведенное описание пространства компонентов ХхХ назовем инвариантно-параметрическим представлением, где константы <fvJv (JV=1,...,KV) играют роль инвариантов, определяющих подпространства пространства компонентов, а 2п-1 свойств выделяют в этих подпространствах конкретные пары компонентов, удовлетворяющих заданным условиям, играют роль параметров.Полученные совокупности компонентов можно рассматривать как реализацию абстрактного объекта, характеризующегося отношением Бх1 хрх(£,^,х,х^v). При этом символ ZJvY, обозначающий подпространство этих реализаций, можно рассматривать как имя для обозначения абстрактного объекта, а символы <\%] <§vv ~ - как обозначение реализаций данного объекта. Итак, мы установили бинарное отношение над пространством ХхХ, которое выделяет в пространстве Z подпространства реализаций ZJvY, что формально можно записать, несколько видоизменив выражение (1),&Zv,---, $VvZv     ' (Xi,Xj), ...,fn (Хп,Ху)где ZJ^-Zi, ...,\%JvZv, ...,zNvm* всех w=l, ...,NV.2.3.2. Изменения реализаций двухкомпонентных объектов как группы преобразованийДля полного описания объекта крайне важно выяснить закономерности, по которым меняются его реализации при вступлении в различные отношения с другими объектами. С этой целью абстрактный объект, обозначаемый символом ZJvY, представим как некоторую физическую систему состояний, относительно которого известно, что он может находиться в одном из состояний <\%iZ-, ...,<§v/-. Рассматриваемая система при вступлении во взаимодействие с другими системами подвергается некоторым воздействиям. Каждое воздействие определяется тем, что если система находится в состоянии £„z~, то в результате данного воздействия она перейдет в состояние \%wz-, которое может совпадать с исходным состоянием Таким образом, каждое воздействие можно представить как преобразование в пространствеyJv г г Zv е Zv е Zv е Zv е Zv > L   v      Ы   > ■■■>Ъи   > ■ ■ • > bv   > • • • > bw   >      QVv   / ■Результат двух воздействий можно рассматривать как воздействие, а преобразование, производимое им, как произведение тех преобразований, которые соответствуют двум последовательным воздействиям, результатом которых явилось рассматриваемое воздействие. Совокупность рассматриваемых воздействий на физическую систему состояний, будучи замкнута относительно последовательного применения воздействия, представляет полугруппу преобразований множества всех рассматриваемых состояний системы. При этом мы не налагали никаких условий на преобразование, а просто определили умножение на произвольном замкнутом множестве преобразований. Но относительно преобразований объектов РД легко можно ввести еще одно условие - это наличие для любого преобразования Т обратного преобразования Т ~]. В этом случае множество преобразований состояния объекта превращается в группу преобразований. Наша задача показать, что множество преобразований объектов, определяемых выражением (6), является группой преобразований, а структура этих объектов, определяемая выражением (2), - инвариантом данной группы преобразований.Рассматривая свойства подмножества ^^находим, что любая точка данного подмножества описывается кортежем zIt ...,<^jZv, ...,zn, где ^JvZv=const, а zusZu для всех u^v. Это означает, что значениями свойств x,xlu (u^v) могут быть любые значения из Хи. Что касается переменных x,x'v, то изменение одной из них влечет изменение другой по зависимостям: х=fv(^jZ'",х), xjv=fv(^jvZv,x,v). Задав эти условия, мы по сути дела определили допустимые преобразования, связывающие любые пары компонентов, для которых это условие выполняется. Обозначим эти преобразования как T={TUW} u,w=l,...,Nv и запи-t-  Zv       гт-i W J- Zvшем    - =ГЦ 4 -.&Zv, ■■■><\%NvZv<={fi(Xi,X]), ...,fn(Xn,X^Итак,объект, состоящий из двух компонентов Kt(xl],...д'^ и K/x'i,...,x'n)) обладает свойствами x'i,...,xn, и х7;,...,*7,,, изменяющимися при преобразованиях из множества Т. Объект обладает свойством <^vZv~^xw*V, которое остается неизменным при любом преобразовании из семейства Т. Именно это инвариантное свойство задает качественную определенность объекта и характеризует его структуру. С учетом вышеизложенного описание объекта ZJvY, включающее его интенсиональное (через инвариант и допустимые преобразования) и экстенсиональное (через перечисление реализаций) описания, можно получить выражениеvPv(^Jv   >Х vt^v)}(7)g Zv   rp w p Zvдополнив выражение (6) закономерностями, связывающими любые две реализации. В результате ситуация, изображенная на рис. 17, примет вид, изображенный на рис. 18. Полученное выражение можно интерпретировать следующим образом. Функция f=fj, ...,/„, удовлетворяющая условию (2), отображает всевозможные пары компонентов Kt(xl 1г ..^х1^, K/x/j, ...,х!п) пространства ХхХ в подпространство Z пространства систем Z, точки которой связаны друг с другом преобразованиями с помощью соотношения \%WZ-=TUW<!;UZ-. По существу выражение (7) содержит развернутое описание класса эквивалентных реализаций E,z- <=Z\_ объекта, состоящего из компонентов Kh Kj, структура которых является интенсионалом   или   инвариантом   класса   и   описывается выражением 3^vpv(^v,x,^x), а реализации, составляющие объем или экстенсионал класса, связаны друг с другом преобразованиями Tuw еТ.Можно показать, что определенное таким образом множество преобразований обладает всеми свойствами группы. Роль групповой операции для преобразований играет последовательное выполнение преобразований, которое для краткости назовем умножением преобразований. Чтобы некоторое множество объектов и операции, которым они подвергаются, составляли группу, они должны удовлетворять трем условиям:Первое, основное свойство группы гласит, что в результате проведения любого числа групповых операций мы получаем элемент группы. В нашем случае любая последовательность преобразований из заданного семейства в результате дает пару компонентов, для которых выполняется условие Bxtvpv(?;?v,x,yjv). Преобразование ГД являющееся произведением Т{*Т/ двух произвольных преобразований множества Т, должно также принадлежать множеству Т. Это основное свойство группы в нашем случае доказывается легко. Предположим, что в результате преобразования Т{еТ объекта £z- мы получили объект <§z-, а в результате преобразования Т/еТ объекта <§z- -объект Последовательное выполнение двух преобразований Г/ и 7}* можно рассматривать как преобразование Г* объекта £z- в объект Так как любые точки пространства Z связаны преобразованиями из множества Т, то Т*еТ.Любое преобразование Т{ еТ имеет обратное преобразование Т/ еТ. Так как любой объект связан с любым другим объектом §Ze преобразованием Т/, то и объект §z- связан с объектом £z- преобразованием Т/, обратным Т{.На множестве преобразований Т имеется единичный элемент 7*0=7^ для всех i,j=l,...,Nv такой, что £z-=77£z-. Этот элемент соответствует нулевому преобразованию, т.е. отсутствию преобразования.Итак, мы доказали, что описанное семейство преобразований двухком-понентного объекта, описываемого выражением (7), представляет собой группу преобразований, что позволяет нам воспользоваться свойствами теории групп в плане разбиения пространства на классы эквивалентности. Для того чтобы разбить множество реализаций пространства Z на классы эквивалентности относительно группы преобразований Т, зафиксируем для переменной zv eZv остальные значения из Zv=z{^]Z', ...,<^NZ-}. При этом мы получим разбиение пространства Z на классы эквивалентности ZJvv(Jv=l, ...,NV), удовлетворяющие условиюZlvu...UZ?u...UZ» = Z,Z1vn...nZJu...nZN = 0.         ( 1Реализации каждого из этих классов эквивалентности описываются кортежами zv+],...,zn, где zueZu /u^v, a zv=\%JvZv (jV=1,...,NJ, которые являются инвариантами этих классов эквивалентности.

2.3.3. Родовидовые связи между реализациями двухкомпонентньгх объектов

Итак, на базе структурной взаимосвязи компонентов объекта мы определили множество всевозможных изменений его реализаций как группу преобразований, а множество реализаций, на котором действует эта группа преобразований, как классы эквивалентности относительно данной группы преобразований. Дальнейшее развитие полученной конструкции можно провести на основе понятия подгруппы. Подгруппой называется та часть группы, которая сама представляет собой группу [69,72].В группе преобразований, описываемой выражениями z^Zi/i^u, zu=^uJu, рассмотрим ту ее часть, которая описывается какz,-:Z,- /iVm,v, zu=<fuJw zv=<fvjZi'.Zj (i &u,v)JvZu.Zu      ^JU !Zv <fjv /Jv 1,...,NV.

При этом для каждой комбинации значений zu=^uJu и zv=<fvJv, для всех Ju=l, ...,NU и Jv-1, ...,NV получаем подпространства Z7"-7^, где каждая точка £Jy. jZuZv (Jg7y=l, ...,NUNJ описывается п-й zj ...c^juZu ...c^jZv ...zn, которая является инвариантом соответствующего подпространства. Как и для подпространства Zu" можно показать, что при этом мы имеем группу преобразований, следовательно, подпространства ^jujZuZv также являются классами эквивалентности и удовлетворяют условию (8) для соответствующих подпространств. Реализации полученных классов эквивалентности описываются «-мие zu       х ZvZh •••> С/г/   > •••> Ov    j • ■ • >ZVi • ■ • >Znдля всех Ju = 1, ... ,NU, Jv = 1, ... ,NV, которые полностью представляют подпространство Zu".В свою очередь любое подпространство ZuyJuJv также можно разбить на классы эквивалентности. Для этого в дополнение к зафиксированным значениям zu и zv зафиксируем еще одну переменную zw=^JwZw, в результате чего получим преобразование, описываемое как zf: Zj (i^u, v, w) Z„=£//";7        Zv ■<w-t-'v    bJv >Zw=£jwZW/Jv = l> •••,N}JuJvJwКаждое из полученных при этом подпространств Zuvw   состоит из точекf ZuZvZw       у ZuZvZw       е JuJvJw            "           \% zu       -с Zv       г  Zw _>■■■>Zjidvjw     ZnuNvNw, описываемых п-и zh...,&„   -    \%Jw - ...,z„.Присвоив переменной zw остальные значения из Zw,получим Nuvw подпространств, удовлетворяющих условиюZJuJvl .     .   /7            JuJvJw .   /7     JuJvNw                   rj JuJvUVW        • • ^^UVW     ■ ■ ^^UVW   — ^UV     ,     (Q )ZJuJvl            ry      JuJvJw   ry      JuJvNw        s~x ("/uvw ■ -^'^uvw      ^ ■ ■'i^uvw       — xV.Реализации полученных при этом классов эквивалентности описываются п-миZu       с Zv        Zw ,21,--->Ыи   >---,<-Jv   >•••> hJw   >—,Zn, (10)где Ju = 1,...,NU, Jv = i,...,JVw Jw = l,...,Nw-Теоретически этот процесс можно продолжить до тех пор, пока таким образом не будут зафиксированы все п переменные (i=l,...,n). Однако такая ситуация не будет иметь практического значения, т.к. каждый класс эквивалентности будет состоять из одной единственной точки, т.е. мы при этом возвращаемся к исходной ситуации, когда над пространством Z не были определены никакие конструкции. Поэтому практический интерес представляют именно те ситуации, когда часть переменных зафиксирована, а другая часть переменных варьируется в заданных пределах. Описанная ситуация представлена на рис. 18, где изображено множество иерархически организованных подпространств, к рассмотрению свойств которого мы приступим ниже.Определяя преобразования, оставляющие инвариантным заданное отношение, мы определяли отношение эквивалентности, которое определяет разбиение пространства, удовлетворяющее свойствам (9). Поэтому процесс, описанный выше, можно представить как процесс разбиения пространства, который можно обозначить какP(Z) = {Z1U,...,Z*,...,Z»K}.Полученные при этом множества снова подвергаем разбиению, и получим    при    этом    множество    разбиений,    называемых уточнениями,P(Zlj ),...,P(Z£U),...,P(Z\%U), таких, чтоГ) / ry Jll                      ( ry Jul     ry JuJv ry JuNv )алее множества Zyy    снова подвергаем уточнению, получив при этом уточненияр / rj JuJv              ( rj JuJvl        ry JuJvJw        ry JuJvNw )rLUV  )    i LUVW >••■' Ll)VW   '■■■'ZjUVW /•Множества Z^/w снова могут быть подвергнуты разбиению и т.д., приэтом каждое разбиение множества называется потомком своего множества, а каждое множество предком своего разбиения. Как показано в [73], исходное множество, его разбиение и возможные уточнения образуют вложенное множество С-[С],...,СР}, такое, что для любых двух множеств Q, CjeC либо CinCj=0, либо QnCj^Q, либо Qr>C}=C}.Пусть Z={&,...,£n} - множество объектов и пусть C={Ci,...,Cpj - набор вложенных множеств, определяемый множеством Z, его разбиением P(Z) и возможными уточнениями. Множество С включает в себя и такие элементы, которые соответствуют классам эквивалентности, состоящим из единственного элемента (i=l,...,N). Как мы уже отметили выше, такие классы не представляют для нас интереса,и поэтому мы их выведем из рассмотрения. Предположим, что ...,£n}= {Cp-n+i, ...,СР}. Тогда для каждого Q^C, 1 <к <p-Nсуществует отношение эквивалентности q^ которое определяет разбиение P(Ck)czC.Полученную конструкцию удобно представлять в виде древовидной структуры, которую можно определить как конечное множество Т, состоящее из одного или более узлов таких, что:Существует один выделенный узел, обозначаемый root(T) и называемый корнем дерева.Корень root(T) разбивается на m непересекающихся подмножеств Th...,Tm, называемых узлами, каждое из которых в свою очередь является деревом.В соответствии с этим определением корень root(T) является представителем всех объектов множества, т.е. Z=Cj. Отношение эквивалентности4i- &uZu=f(Xu',xJ) разбивает Z на Nu классов эквивалентностиP(Z) = {Zu,    ZuNu}= {С2,..., CNu+i},каждый из которых представлен корнем поддеревьев по отношению к root(T). Число элементов в разбиении называется степенью узла: для узла С] степень равно Nu. Каждый такой класс может быть определен с помощью функционалаF, инварианта ^ и параметров х,х( ,...,x}u,...,xln,xjn, которые перепишем какX],. ..,Х2п-1.Затем рассмотрим отношение эквивалентности

42 ^Ju f(\%u >Хи), &v V=f(Xvxv) ■

После аналогичных рассуждений определяем, что каждый класс эквивалентности, определяемый на основе отношения ^характеризуется функционалом F,инвариантами qJu,gJv и параметрами х],...,х2п_2.Отношение эквивалентностиЧз- £j^=f(xu,xi)^Jw ~f(xw,Xw)определяет классы эквивалентности, характеризующиеся функционалом F, инвариантами ^j^.Zjv.Zj™ и параметрами х1,...,х2„-з- Итак, в соответствии с данным определением множество элементовЛ)->Л17 y^UV  '^UVW      Z1W>для удобства обозначенных нами как С],...,Cp.N, определяет древовидную структуру, узлы которой представляют собой классы эквивалентности на пространстве Z относительно заданных на них преобразованиях, выраженные изменениями параметров xh...,x2n.^ оставляющих инвариантными структурные отношения.Деревья, эквивалентные набору вложенных множеств, называются ориентированными, поскольку во внимание принимается только относительная ориентация узлов. Упорядоченное дерево получается путем некоторого упорядочения классов эквивалентности С, е Р(С^). Упорядочение всех классов эквивалентности предполагает упорядочение объектов £w е Z для всех w=l, ...,N.Таким образом, на множестве Z мы определили классификацию, которая определяется как многоступенчатое разветвленное деление множества или класса. В нашем случае в результате классификации мы получили систему соподчиненных классов эквивалентности, в которой:делимый класс является предком или родом;полученные при этом классы эквивалентности называются потомками или видами.Рассматривая список п-к выражения (10), нетрудно заметить, что принадлежность той или иной п-к к определенному классу эквивалентности определяется только постоянными ее значениями. Переменные, компоненты значения которых не зафиксированы и варьируются в заданных пределах, определяют объем класса эквивалентности, - его конкретные реализации. Таким образом, каждый класс характеризуется постоянной инвариантной составляющей и переменной параметрической составляющей,соответствующей п-и.Значения переменных в параметрической части могут изменяться в пределах заданных диапазонов. Всевозможные сочетания этих значений можно записать в виде матрицы, которую назовем параметрической матрицей. С учетом вышеизложенного и по аналогии с выражением ИПП (5) на базе трех инвариантных свойств класса Z]\%^w можно записать, как показано на рис. 18. Наприведенном рисунке можно обнаружить зависимость между инвариантной и параметрической составляющими ИПП: чем большим числом констант представлена инвариантная составляющая, тем меньше свойств содержится в параметрической части, и наоборот. Данная зависимость является формализацией отношения между интенсионалом и экстенсионалом понятия и будет играть большую роль в наших последующих конструкциях.Таким образом, мы построили классификационную надстройку над пространством компонентов, которая делит его на классы эквивалентности. Имея описанную классификацию и ИПП объектов, лежащего в ее основе, уточним определение двух универсальных задач, называемых анализом (распознаванием) и синтезом:Задача анализа описывается следующим образом. На входе имеется произвольная реализация некоторого объекта. Требуется определить, к какому объекту относится данная реализация. Решение задачи анализа (распознавания) заключается в следующем. На вход процедуры fi(XhXi), .../„(Х^Х^ поступают значения свойств xlh ...,х1„ и х1 ь ...,х?„ компонентов рассматриваемой реализации, по которым данная процедура вычисляет значения z}, ...,zn. После этого производится сравнение полученной последовательности значений с набором кортежей из рис. 18. По результатам сравнения последовательность zi, ...,z„ относится к тому пространству Z7^^, с кортежем которого произошло совпадение. •  В процессе синтеза решается обратная задача. Задан объект Z^^uy, т.е. задана последовательность zh ...,zv.h^JvZv,zv+i, ...,z„, требуется построить реализацию данного объекта. Так как отображение Z<—f(XxX) имеет гомоморфный характер, то данному условию соответствует целый класс реализаций. Поэтому для того, чтобы построить конкретную реализацию, необходимо определить конкретные значения свойств x'j, ...,х'„, х?],...,х?„. Здесь важно отметить то обстоятельство, что при этом не требуется определить все 2п свойств, а только те, которые не связаны структурными взаимосвязями, а из тех, которые связаны структурными взаимосвязями, определению подлежит только одно свойство. В нашем случае требуется определить 2п-1 свойств. Для практического решения этих задач необходимо реализовать функционал F = F(fj(xlj,^j), ...,f„(x'„,x1^) в виде машинной процедуры, которая осуществляет отображение пространства компонентов ХхХ на пространство объектов Z, а также функционал F' = F'(f'i(zn,x'}), ...,/'„(2„,У,Д с помощью которого осуществляется отображение пространства объектов Z на пространстве его компонентов ХхХ. Перечисленные функционалы представляют собой обобщенные структуры, управляющие процедурами анализа и синтеза соответственно. Именно эти структуры реализуют структурные взаимосвязи между компонентами объектов в процессе анализа и синтеза объектов. Описанная ситуация проиллюстрирована на рис. 18.Родовидовые связи в ИПП объектов, описанные выше, заданы неявно, и для их установления необходимо провести определенные процедуры. Но если задать эти связи явно, можно получить ряд важных преимуществ, о которых мы скажем ниже. Поэтому, прежде чем приступить к рассмотрению перечисленных задач, проведем в полученной структуре дополнительные построения.Как известно, решение задачи распознавания сводится к поиску в списке L п-и, которая совпадает со входной п-й, полученной в результате выполнения процедуры/ Задача поиска формулируется следующим образом: дан список п-к L и входное слово zh...,zn. Требуется найти значение индекса / такое, что L(I)= zj,...,zn. Если такого значения не существует, то устанавливается значение 1=0. Для нашего случая индекс / соответствует индексу классов из множества С= {Ch...,Cp.N}, т.е. порядковому номеру классов эквивалентности, полученных путем разбиения множества Z.

Наиболее простым и наиболее расточительным с точки зрения временных затрат является сравнение входного слова с каждой п-й из L путем полного перебора п-к. Так как число п-к в L равно p-N, то при этом потребуется осуществить максимально p-N, а в среднем ~(p-N)/2 сравнений п-к. С точки зрения снижения временных затрат при поиске интересно рассмотреть особый вид списковой структуры, называемый деревом.Выше мы уже описали процедуру построения древовидной структуры на множестве, элементами которого служили классы эквивалентности. В данном случае построим древовидную структуру на множестве, называемом списком, элементами которого являются и-и. Как и в предыдущем случае, построение древовидной структуры будет базироваться на понятии "отношение эквивалентности", в качестве которого в этот раз будем иметь в виду равенство элементов п-к одной позиции. А в остальном процедура построения древовидной структуры остается той же. Перед тем как приступить к построению древовидной структуры, присвоим значение ПУСТО всем тем элементам, значения которых не зафиксированы.Сначала определим отношение эквивалентности q}, которое гласит: "к одному классу эквивалентности относятся те п-и, первые элементы которых равны". В нашем случае все переменные zj = ПУСТО, следовательно,все они относятся к одному классу Zj. Объединим все п-и списка в один класс^записав для них общий элемент z}. Аналогичную ситуацию имеем и для остальных элементов вплоть до (u-l)-ro элемента. При этом все п-и списка L будут объединены в один класс, и все они идентифицируются последовательностью zh...,zu.h все элементы которого имеют значение ПУСТО. В u-й позиции элементам приписаны различные значения из Z=-{^uh ...,<fuju, ---^m}- Поэтому на этот раз мы имеем разбиение списка L на Nu классов эквивалентности, в которых в один класс будут отнесены те п-и, u-е элементы которых имеют одинаковые значения.В каждом из полученных классов эквивалентности проведем разбиение описанным выше образом. При этом в каждом из этих классов будут получены одинаковые фрагменты последовательностей zu+h ...,zv.h элементы которых имеют одинаковое значение ПУСТО, т.е. пока мы имеем те же Nu классов эквивалентности, которые мы получили на элементах u-й позиции. В v-й позиции, как и в случае u-й позиции, элементы списка имеют различные значения. Поэтому в каждом из классов эквивалентности проведем разбиение на 7VV классов эквивалентности. Затем описанная ситуация со значениями ПУСТО повторяется, и последнее разбиение проведем в позиции w. После этого процедуру повторяем до п-й позиции, но разбиение на классы эквивалентности при этом уже не получим, так как все последующие элементы п-к списка имеют значение ПУСТО. В результате описан-ной процедуры получаем список п-к в виде древовидной структуры, фрагмент которой изображен на рис.19. Как видно из рисунка, каждый листовой узел полученной древовидной структуры соответствует

одному из узлов дерева, полученного на множестве классов эквивалентности пространства Z. Дерево, полученное на множестве п-к списка L,представляет собой структурную иерархию, а дерево, полученное на множестве классов эквивалентности, - родовидовую иерархию. Таким образом, мы получили структуру, в которой представлены две взаимопроникающие иерархии "часть-целое" и "род-вид". Список, представленный в виде древовидной структуры, имеет ряд существенных преимуществ перед его представлением в виде матрицы:во-первых, существенно сокращается число элементов, так как каждый узел древовидной структуры, за исключением листовых узлов, представляет не один элемент, а класс эквивалентных по некоторому отношению п-к;во-вторых, древовидная структура значительно ускоряет поисковые процедуры, так как поиск производится не по всему списку, а после каждого шага определяется подобласть на множестве п-к, среди которых следует производить дальнейший поиск;в-третьих, полученная структура обеспечивает естественное наследование свойств предков потомками или свойств родовых классов видовыми классами.2.3.4. Анализ и синтез двухкомпонентньех объектовИтак, мы провели все необходимые построения для решения задач анализа (распознавания) и синтеза и теперь можем приступить к рассмотрению собственно задач. Сначала рассмотрим процедуру анализа (распознавания), когда по входному описанию объекта в терминах свойств компонентов необходимо определить его принадлежность к определенному классу эквивалентности. При этом объект, описываемый свойствами х/х/,...,хигх^,...,хугХу,xjxj,...,xn'xj, обрабатывается функционалом F, в результате чего вырабатывается п-а zh ...,zn. Путем проведения процедуры поиска в списке L требуется определить, к какому классу эквивалентности принадлежит данная п-а.. Так как в нашем распоряжении список, представленный в виде древовидной структуры, то процедура поиска отличается от поиска в списке, осуществляемого путем последовательного перебора элементов списка, представленных в виде матричной структуры. Отличие заключается в том, что элементы входной последовательности сравниваются не с элементами одной п-и, а с элементами, представляющими классы эквивалентности. Это существенно сокращает время поиска.Процедуру поиска в древовидной структуре можно представить в виде рекурсивного выражения ST=S(zi,qi), где S(zj,qj) описывает процедуру поиска г-го цикла поиска, в которой входной элемент сравнивается с элементами-представителями классов эквивалентности qt, предок или родовой класс которых был определен в (i-l)-M цикле поиска. Таким образом, каждая процедура поиска г'-го цикла поиска описывает поиск среди элементов k(,'!)zk(i), где г'-номер позиции п-к в списке, k(i-l) — индекс родового класса эквивалентности, определенный в (i-l)-M цикле поиска, k(i)= l,...,k(m) - индекс видовых классов эквивалентности, родовой класс которых был определен в предыдущем цикле поиска.В г'-м цикле поиска определяется значение индекса k(i) с тем, чтобы для следующего (i+l)-vo цикла поиска определить множество видовых классов эквивалентности, среди которых будет осуществляться поиск элемента zi+1. В последнем п-м цикле поиска определяется листовой узел древовидной структуры, который связан с одним из узлов родовидовой древовидной структуры. Таким образом, поисковая процедура S производит отображение элементов пространства Z на множество С классов эквивалентности, что можно записать как Sf.Z—>C. Как мы уже отметили выше, экземпляры классов эквивалентности представлены теми переменными zh значения которых в списке L не зафиксированы. Поэтому те из переменных zh которые в списке L были представлены значением ПУСТО, составляют параметрическую часть представления и могут быть использованы для определения конкретного экземпляра выявленного класса эквивалентности путем их сличения с элементами параметрической матрицы.Так как объем параметрической матрицы, как правило, невелик, то поиск в ней осуществляется путем последовательного перебора п-к, который можно записать как SM=S(xlj, ...,xln.^), где / = 1, ...,7V. В результате этого поиска определяется индекс в параметрическом массиве, который идентифицирует конкретный экземпляр выявленного класса эквивалентности. Другими словами, поисковая процедура, реализуемая в параметрической матрице класса эквивалентности, осуществляет отображение SM:C—>C(i). В целом поисковые процедуры, реализуемые на ИПП классов эквивалентности и их конкретных реализаций, осуществляют два последовательных отображения S = St*Sm : Z —> С —> С(г). Блок-схема алгоритма анализа объекта приведена на рис. 20.А теперь рассмотрим обратную процедуру, называемую процедурой синтеза, когда описанные отображения осуществляются в обратном порядке. Задача синтеза формулируется следующим образом. Имеется ИПП z'-го объекта класса С,- (j=l,...,p-N). Требуется реализовать этот объект в терминах его компонентов. ИПП экземпляра класса эквивалентности содержит код С} и индекс экземпляра класса, идентифицирующий его среди остальных экземпляров данного класса, что можно записать как C/i). Как мы уже отмечали выше, отображение XxX—>Z имеет гомоморфный характер. Поэтому обратное отображение осуществляется с помощью функционала F который использует свойства одного из компонентов в качестве аргументов.На первом этапе синтеза по коду С, определяем позицию данного кода в ИПП рассматриваемого отношения. В результате этого мы находим матрицу параметров, листовой узел списка инвариантов данного класса в древовидной структуре L.

Началоzp...,zn = F(fSx>,x/),...fJxn>,xJ))Установка начальной позиции п-ки zp...,zп в начальное состояние: s = 1 (s=l,...,n).Установка начальной позиции в древовидном пространстве инвариантов в начальное состояние: s = 1, k = 1.

s++; к++

 

 

Если z кsИначе

= 0X ',XJх xJs s

 

k++Выдача кода ошибки

 

Выдача н Определение массива парс

■ода ZJUшетров для данного кода

 

 

Поиск параметровхр...,х2пкв массиве параметров и выдача индекса массива параметров 1(р)

 

 

Выдача ИПП анализиру

гмого объекта Zju(I(p))

КонецРис. 20. Блок-схема алгоритма анализа объекта (по структуре на рис. 19)После этого по индексу i находим параметры zlh...,z.kтребуемого экземпляра класса. Так как по листовому узлу легко восстановить весь список в древовидной структуре, можно развернуть инвариантный список0,...,0,tju,0,..;0,tjV,0,...,0,tjw,0,...>0,соответствующий классу С}. Однако в этом списке только в выделенных позициях содержатся значения, а в остальных позициях содержится значение ПУСТО. Поэтому в эти позиции подставляем значения из списка параметров, что дает нам списокzh ■■•,zJu-b      JwzJu+h ••• >ZJv-hh   Jv>zJv+b ••• iZJw-hh    Jw>ZJw+l) •••>zn-Сформированный таким образом список поступает на соответствующие входы функций f1/,...,fu'...,fv'...,fw',...,f„/B качестве первых параметров. Вторыми аргументами этих функций принимаются сведения о свойствах компонента, выбранного в качестве исходного. После того как все аргументы функционала F' определены, вычисляются значения свойств другого компонента. Таким образом, все свойства экземпляра класса C/i) в терминах свойств его компонентов определены, и задача синтеза экземпляра класса по его ИПП решена. Блок-схема алгоритма синтеза объекта, состоящего из двух компонентов, приведена на рис. 21.Итак, мы рассмотрели бинарное отношение, заданное на пространстве ХхХ и отображаемое на пространство Z, построили его ИПП и уже с позиций ИПП рассмотрели отображения F:XxX—>Z и F':ZxX—>X. Для упрощения выкладок мы предположили, что оба компонента принадлежали одному пространству. Описанным образом можно определить произвольное бинарное отношение, в котором компоненты могут принадлежать разным пространствам, т.е. имеют место отображения F:XxY—>Z и F':ZxX->Y. Единственное дополнительное условие, которое ставится перед этими пространствами, заключается в том, что они должны иметь хотя бы одну пару одноименных осей координат, между значениями которых можно будет установить взаимные зависимости, лежащие в основе структурных отношений.Таким образом, задав множество пространств компонентов, можно определить множество функций для вычисления отношений J# = {Rh...,Rr>...,Rpj, каждое из которых отличается хотя бы одним пространством компонентов. Следовательно, каждое из этих отношений можно идентифицировать по совокупности пространств, на которых оно установлено. Каждое из перечисленных отношений Rr (г=1, ...,р) представлено функционалами Fr и F'r (г=1, ...,р), которые, в свою очередь, представлены последовательностями элементарных функциональных связей между отдельными свойствами соответствующих компонентов. Поэтому множество R можно представить двумя списками функционалов. Список функционалов инвариантного отображения представлен списком (11) ^1            (fl '■•> fu(l)'---> fv(l)       fw(l) )'Fr   ~ Fr (fl  fu(r)> — > fv(r)>'--> fw(r))(11)F   = F ( fp      fp      fp fp)p p J 1   >•■■> J u(p) >■■•> J v(p) >•••> J w(p) / •а функционалов параметрического отображения - списком (12)Fp ~Fp(fl  fu(l)>-"> fv(l) >•■' fw(l) )'Fr~Fr(fi   >••■> fu(r)>---> fv(r)>-"> fw(r)) > (12)F' =F' (f'p     f'p       f'p       f'p )1 p      1 p J 1    >•■•> J u(p)>-"> J v(p)>"-> J w(p)/■В этих списках, в отличие от списка инвариантов, функциональные последовательности могут иметь разную длину, но их легко можно привести к матричному виду, дополнив более короткие последовательности пустыми функциями .На полученной конструкции задачи анализа и синтеза решаются несколько иначе,чем как это было показано выше. В случае анализа отличие заключается в том, что в данном случае заранее не известно, какой из функционалов будет использоваться при анализе. Данная проблема решается довольно легко, так как предполагается, что известно, к каким классам или пространствам относятся компоненты анализируемого объекта. Как это было отмечено выше, любое отношение однозначно определяется пространствами своих компонентов, следовательно, зная принадлежность к классам компонентов рассматриваемого объекта, мы можем однозначно установить функционал, по которому осуществляется отображение пространства XxY в пространство Z.Для установки этого соответствия составим список всевозможных комбинаций компонентов, соответствующих функционалам отношений списка (11). Так как для установки соответствия необходимо произвести поиск входных компонентов в данном списке, целесообразно преобразовать его в древовидную форму, поставив в соответствие каждому концевому узлу полученного дерева соответствующий функционал, как показано на рис. 22.Еще проще данная проблема решается при синтезе. Так как функционал, отображающий пространство Z в пространство XxY, является общим для всех элементов классов эквивалентности, то эту информацию можно ввести в код класса, снабдив его указателем на соответствующий функционал обратного отображения. В этом случае сначала определяется функционал, а по функционалу определяется состав компонентов. Для этого также составляется список всевозможных комбинаций компонентов, соответствующих функционалам из

Установка листового узла древовидной структуры инвариантов по коду ZJU

Считывание кода текущего узла древовидной структуры инвариантовs— (определение позиции предка для текущего узла древовидной структуры инвариантов

Рис.21. Блок-схема алгоритма синтеза объекта (по структуре на рис. 19)

К/

к2"

 

 

 

 

 

 

 

 

к,