Таблица 1
Зависимость суммарного числа операций сравнения от порядка нахождения
пересечения множеств
X
,
Y
,
Z
№ варианта Порядок
определения
Число
сравнений
Мощность
множества
Суммарное число
сравнений
F
i
1
D
=
X
∩
Y
,
D
∩
Z
nm
r
1
k
r
1
=
|
X
∩
Y
|
nm
+
r
1
k
2
D
=
Y
∩
Z
,
X
∩
D
mk
nr
2
r
2
=
|
Y
∩
Z
|
mk
+
r
2
n
3
D
=
X
∩
Z
,
D
∩
Y
nk
r
3
m
r
3
=
|
X
∩
Z
|
nk
+
r
3
m
множеств равно
nm
при
X
∩
Y
=
∅
, максимальное для второго и
третьего равно
k
(
n
+
m
)
при
Z
⊂
Y
.
Таким образом, в указанных
предположениях преобразование эффективно, если
nm > k
(
n
+
m
)
.
В случае, если
Z
⊂
Y
⊂
X
, имеем:
r
1
=
m
,
r
2
=
k
и
r
3
=
k
. Тогда
F
2
=
F
3
,
F
1
> F
2
,
F
1
/F
2
= (
n/k
+ 1)
/
(
n/m
+ 1)
>
1
, таккак
m > k
и
F
1
−
F
2
=
n
(
m
−
k
)
.
При большом числе множеств целесообразно решение задачи вы-
бора оптимального порядка пересечения множеств по критерию ми-
нимума числа операций сравнения решать методом динамического
программирования.
Пример использования преобразования: для декомпозированной на
R
подсистем структуры известны цепи, связывающие пары подсистем
— ребра гиперграфа
U
i,j
,
i, j
= 1
, R
,
i
=
j
. Необходимо определить
цепи, общие для всех подсистем.
Четвертый способ использует свойство дистрибутивности опе-
раций над множествами:
(
X
∪
Y
)
∩
(
X
∪
Z
) =
X
∪
(
Y
∩
Z
)
. Для
(
X
∪
Y
)
∩
(
X
∪
Z
)
минимальное число операций сравнения будет, если
Y, Z
⊂
X
:
F
1
=
nm
+
nk
+
n
2
.
Максимальное число операций сравнения при определении
X
∪
∪
(
Y
∩
Z
)
будет, если
Y
=
Z
:
F
2
=
m
2
+
n
×
m
. Тогда
Δ
F
1
,
2
=
n
2
+
+
nk
−
m
2
. Преобразование эффективно, если
n
2
+
nk > m
2
.
Пример применения преобразования: в схеме заданы три ча-
сти Сх
1
(Э
1
, С
1
), Сх
2
(Э
2
, С
2
), Сх
3
(Э
3
, С
3
) — три куска гиперграфа
H
к
1
(
X, U
1
)
,
H
к
2
(
Y, U
2
)
,
H
к
3
(
Z, U
3
)
. Необходимо определить множество
элементов, общих для соединения Сх
1
с Сх
2
и Сх
1
с Сх
3
.
Оптимизирующие преобразования, использующие свойства
предикатов и операций над ними.
Пятый способ заключается в за-
дании предикатами или соответствующими им отношениями таких
связей между множествами, которые позволяют снизить вычисли-
тельную сложность операций над этими множествами.
Примером
58 ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4
