Материал: Алгебра_кортежей

Скачать

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

произведений мер компонент, содержащихся в каждом C-кортеже ортогональной C-системы.

Рассмотрим еще одно важное соотношение, позволяющее во многих случаях существенно сократить перебор при преобразовании АК-объектов в альтернативные классы. Дело в том, что D-кортеж, содержащий не менее двух непустых компонент, можно представить как ортогональную C-систему не единственным способом. Допустим, даны равенства

A

 

 

A

 

 

 

 

 

B

 

 

 

 

 

 

 

 

A

 

B

]A B C[ =

 

 

 

=

 

 

 

 

 

.

 

 

 

C

 

A

 

 

B

C

 

 

 

 

 

 

 

 

 

Если в промежуточном АК-объекте переставить местами C-кортежи, то эквивалентность не нарушится, но при ортогонализации после перестановки будет получено другое изображение того же D-кортежа. В итоге, для D-кортежа ]A B C[ формируется совокупность следующих равенств:

A

 

 

 

 

 

 

B

 

 

 

]ABC[=

 

 

 

=

 

 

 

 

C

A

 

 

 

 

 

 

C = AB

B

 

 

 

 

 

 

 

 

 

 

 

B

C

= A

B

 

C

 

 

 

 

 

 

 

 

 

 

C

 

 

C

 

 

 

 

A

 

 

 

 

C

=...

 

 

=

 

 

 

B

 

 

A

 

B

C

 

 

 

 

 

 

 

 

 

Таким образом, если задан D-кортеж, в котором содержится k непустых компонент, то алгоритм, описывающий получение из этого D-кортежа всех возможных эквивалентных ему ортогональных С-систем, состоит из трех шагов:

1)по теореме 2.19 перевести D-кортеж в C-систему P с k C-кортежами;

2)выбрать произвольную перестановку C-кортежей в P (число таких перестановок равно k!) и записать P в порядке, соответствующем этой перестановке;

3)для каждой неполной компоненты Pij (i – номер строки, j – номер столбца) преобразованной C-системы P заменить все фиктивные компоненты

Pmj (m > i), находящиеся ниже Pij, ее дополнениями Pij .

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

105

значительно больше пустых C-кортежей, которые не участвуют в последующих вычислениях. Этот прием особенно эффективен при преобразовании D-систем в C-системы в рамках исчисления высказываний, но и для более широкого класса АК-объектов он также позволяет иногда получить существенное уменьшение трудоемкости. Для иллюстрации повторим ранее выполненное преобразование D-системы P в C-систему, но при этом первый и второй D-кортежи преобразуем в ортогональные C-системы иначе.

При анализе структуры исходной D-системы можно заметить, что в третьем столбце две компоненты {b, d} и {a, c} – взаимно дополнительны. D-кортежи, содержащие эти компоненты, преобразуем в C-системы и переставим в них C-кортежи так, чтобы данные компоненты оказались в первой строке. Выполним ортогонализацию полученных C-систем. Тогда в результате их пересечения получается большое число пустых C-кортежей. Для нашего примера:

P= {a,c}{b,d}

 

{b,d}

 

 

{a,c}

 

 

{b,c}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.

{a,c}

 

 

 

 

 

{d} {a,c}

 

{a,d} {b,d}

{a,d}

{b}

 

 

 

 

 

 

 

 

 

 

 

Для первого пересечения имеем:

 

 

 

{b,d}

 

 

 

 

 

 

 

 

 

 

 

 

{a,c

{a,c}

 

{b,d}

{d} {a,c}

{a,d}

 

 

 

 

 

 

{a,c}

 

 

{b,d} =

{a,c}

 

{b,d}

 

 

 

{a,d} {b,d}

{a,c} .

{d} {a,c}

Для второго:

{a,d} {b,{a,c} {a,{b,d} {d} {a,

d} c}

c}

 

{b,c}

 

 

 

 

 

 

{a,d}

{b}

{b,c}{a,d}

= {c}

{b}

{a,d} {a,d}

{d}

{b,d}

{b} .

{a,c} {a,c}

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

106

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

3.2. Матричные свойства АК-объектов

Рассмотренные структуры АК (кортежи и системы кортежей) внешне напоминают матрицы. И хотя операции с АК-объектами существенно отличаются от операций алгебры матриц, они все же имеют многие свойства матричных структур. Матричные свойства АК-объектов можно использовать при разработке методов уменьшения трудоемкости вычислительных алгоритмов во многих программных системах, в том числе в системах с применением логических исчислений [Кулик, 1995; Kulik, 2010]. В данном разделе рассматриваются методы уменьшения трудоемкости при решении переборных задач (см. п. 1.3), многие из которых сводятся к задаче "Выполнимость КНФ" [Гэри, 1982]. Используя эти методы, во многих случаях при решении задач удается обойтись без трудоемкой операции преобразования АК-объектов в альтернативные классы.

Рассматриваемые здесь матричные свойства АК-объектов обобщают предложенные А.Д. Закревским методы анализа знаний на основе их представления в пространстве многозначных признаков [Закревский, 1995].

Пусть имеется произвольный D-кортеж D = ]s1 s2 ... sn[. Представим его как строку из n литер (литерами здесь являются имена компонент D-кортежа), которую произвольно разобьем на R непустых подстрок. Тогда любая подстрока отображает какой-то D-кортеж Di с определенной схемой отношения. Если каждый Di записать в схеме отношения D-кортежа D, добавив недостающие фиктивные компоненты, то такой кортеж будет состоять из компонент кортежа Di в соответствующих атрибутах и пустых компонент во всех остальных атрибутах. Таким образом, каждой непустой компоненте D- кортежа Di соответствуют пустые компоненты во всех остальных кортежах множества. Из этого, а также из теоремы 2.13, следует:

R

 

D = Di

(3.1)

i 1

 

 

107

Например, если D-кортеж ]s1 s2 s3 s4 s5 s6 s7[ разбит на три D-кортежа ]s2 s4 s6[, ]s1 s3 s5[ и ]s7[, то после приведения их к общей схеме получим:

] s2 s4 s6 [; ]s1 s3 s5 [; ] s7[.

Объединение этих D-кортежей равно исходному D-кортежу. Аналогично для C-кортежей C, Ci при тех же условиях разбиения верно:

R

C = Ci .

i 1

Пусть T – D-система, представляющая собой матрицу компонент размерности M N (M строк и N столбцов). Разобьем эту D-систему с помощью вертикальных линий на R вертикальных блоков. Пусть N(R) – множество {1, 2, ..., R} индексов, а декартово произведение (N(R))M – множество последовательностей S(R, M), элементами которого являются M-размещения с повторениями из множества N(R). Так, если N(R) = {1, 2}, а M = 3, то

S(2, 3) = {1, 2}3 = {111, 112, 121, 122, 211, 212, 221, 222}.

Для этих условий справедливо следующее соотношение.

Теорема 3.3. При разбиении матрицы D-системы T размерности M N на R вертикальных блоков (R < N) справедливо равенство

 

M

 

T =

( Dij )

(3.2)

k S(R,M ) i 1

 

где Dij – D-кортеж, являющийся подстрокой i-ой строки, взятой из j-го блока

M

матрицы T, а индекс j в подформуле Dij пробегает все значения

i 1

соответствующего элемента k S(R, M).

Доказательство. Пусть D-кортеж Di (i = 1, 2, …, M) – i-ая строка матрицы

M

T, тогда T = Di . При разбиении на R вертикальных блоков это равенство с

i 1

M R

использованием (3.1) преобразуется в равенство T = ( Dij ) , где D-кортеж Dij

i 1 j 1

берется из подстроки i-ой строки, принадлежащей j-му блоку. Если в этом равенстве раскрыть скобки, то получим соотношение, сформулированное в

108

теореме. Конец доказательства.

Из теоремы 3.3, в частности, следует, что D-система непуста, если непуста

M

хотя бы одна D-система Dij при любом разбиении на вертикальные блоки.

i 1

 

t11

t12

t13

t14

 

 

 

 

 

 

t22

t23

t24

 

разбита

линией на два вертикальных

Например, D-система t21

 

 

t

31

t

32

t

33

t

34

 

 

 

 

 

 

 

 

 

 

 

блока. По теореме ее можно представить как объединение восьми D-систем

( t11

t12

 

t13

 

t14 ) ( t21

 

t11

t22 t23 t24 ) ( t31 t32 t33 t34 ) = t21

t31

t11

 

 

t

 

 

 

12

 

 

 

 

 

t

32

t

33

 

 

 

 

 

t12

t13

t

21

 

 

 

 

 

t

31

 

 

 

 

 

 

t11

 

 

 

 

 

 

t11

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t22

t23

 

 

 

 

 

t22

t23

 

 

 

 

 

 

 

 

 

 

 

 

 

t24

 

t24

 

 

 

 

 

 

 

t

34

 

t

31

 

 

 

 

 

 

 

t

32

t

33

t

34

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t14

 

 

t12

t13

t14

 

 

t12

t13

t14

 

 

t12

t13

t14

 

 

 

 

 

 

 

 

 

 

 

 

t22

t23

t24

 

 

 

 

t23

 

 

 

 

 

t21

 

 

 

t22

t24 .

 

 

 

t

32

t

33

t

34

 

t

31

 

 

 

 

t

32

t

33

t

34

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Если непуста хотя бы одна из этих восьми D-систем, то непуста и исходная D-система.

Если в качестве блока матрицы T (см. формулу 3.2) выступает векторстолбец, то его можно преобразовать в компоненту, значением которой является пересечение всех компонент вектора-столбца. В частности,

t11

t21 = t11 t12 t13.

t31

Это допустимо, так как компоненты относятся к одному атрибуту. Возвращаясь к примеру, иллюстрирующему теорему 3.3, заметим, что если

снова применить (3.2) к последнему АК-объекту разложения, то получим:

t12

t13

t14

 

 

t12

 

 

t13

 

 

t23

 

 

 

=

 

 

 

…

 

 

t22

t24

t22

 

t23

t

32

t

33

t

34

 

 

t

32

 

 

t

33

 

 

 

 

 

 

 

 

 

t14 t24 . t34

109

Смотрите также:

«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
Значение, сущность и содержание социально — педагогической деятельности в организации для детей-сирот и детей, оставшихся без попечения родителей
Проактивные методы PR-деятельности российских авиационных компаний «Россия», «Азимут»
__RGR2
__RGR2
_10_Эмиль Золя для эл версии
_11_А. Франс для эл версии
_3 тема - Диффузия