Современные технологии разработки и тестирования программного обеспечения (ПО). Ч.1. Коварцев А.Н. - 33 стр.

UptoLike

ВУЗ: 

СамГУПС | Самара

Составители: 

Рубрика: 

2. Коммутативность для операции объединения:
A ∇ B = B ∇ A, но A Δ B
≠
B Δ A
3. Операция следования дистрибутивна слева относительно операции объединения:
A Δ ( B ∇ C ) = ( A Δ B ) ∇ ( A Δ C )
4. Идемпотентность операций следования и объединения:
A ∇ A = A
A
Δ B Δ A = A Δ B
5. Поглощение для операции следования относительно операции объединения:
( A Δ B Δ C ) ∇ ( A Δ B ) = A Δ B Δ C
6. Отбрасывание общего окончания для операции следования:
(A Δ B Δ C) ∇ (A Δ C) = (A Δ B) ∇ (A Δ C)
7. Свойство симметричного поглощения для операции следования:
(AΔC)∇(BΔC)∇(AΔB) = (AΔC)∇(BΔC)∇(BΔA) = (AΔC)∇(BΔC)
Представленные свойства операций следования и объединения позволяют
оптимизировать алгоритм классификации данных за счет сокращения количества
маршрутов и уменьшения их длины. Рассмотрим возможный способ применения этих
свойств на примере графа G1 (рис. 3.5). На первом этапе для каждого из четырех
маршрутов графа (см. рис.3.6) строятся паспорта, при этом используется операция
следования:
P(R1) = A1 Δ A2 Δ A3 Δ A6,
P(R2) = A1
Δ A2 Δ A4 Δ A3 Δ A6,
P(R3) = A1
Δ A3 Δ A6,
P(R4) = A1
Δ A5 Δ A6.
На втором этапе, полученные паспорта цепочек объединяются, образуя паспорт
данных граф-агрегата:
P(G1) = P(R1) ∇ P(R2) ∇ P(R3) ∇ P(R4) =
= ( A1
Δ A2 Δ A3 Δ A6 ) ∇ (A1 Δ A2 Δ A4 Δ A3 Δ A6 ) ∇ (3.1)
∇ ( A1 Δ A3 Δ A6 ) ∇ ( A1 Δ A5 Δ A6 ).
Полученное выражение можно существенно сократить, если применить к нему
преобразования, основанные на свойствах операций, в частности, свойство 6 -
отбрасывание общего окончания для операции следования. Очевидно, что выражения
для цепочек R1 и R2:
( A1 Δ A2 Δ A3 Δ A6 ) и ( A1 Δ A2 Δ A4 Δ A3 Δ A6 )
имеют общее начало ( A1 Δ A2 ) и общее окончание ( A3 Δ A6 ). На основании свойств 1
и 6 можно преобразовать к виду:
(A1 Δ A2 Δ A3 Δ A6) ∇ (A1 Δ A2 Δ A4 Δ A3 Δ A6) ∇ (A1 Δ A3 Δ A6) ∇
∇ ( A1 Δ A5 Δ A6 ) = ( A1 Δ A2 Δ A3 Δ A6 ) ∇ (A1 Δ A2 Δ A4 ) ∇ (A1 Δ A3 Δ A6) ∇
∇ (A1 Δ A5 Δ A6).
Таким образом, применяя последовательно свойства 1, 6 и 4 (поглощение
следования относительно объединения), имеем:
P(G1) = (A1 Δ A2 Δ A4) ∇ (A1 Δ A3 Δ A6) ∇ (A1 Δ A5 Δ A6).
(3.2)
3.3. Сжатие числа операций процедуры классификации данных

Страницы