и
T
3
(
X
) =
P
(
X
)
∨
Q
(
X
)
.
Их характеристические множества имеют вид
T
1
=
{
x
i
:
P
(
x
i
) =
“и
”&
Q
(
x
i
) =
“и
”
/x
i
∈
X
}
,
T
2
=
{
x
i
:
P
(
x
i
) =
“и
”&
Q
(
x
i
) =
“и
”
/x
i
∈
X
}
и
T
3
=
{
x
i
:
P
(
x
i
) =
“и
”
∨
Q
(
x
i
) =
“и
”
/x
i
∈
X
}
.
Операции & и
∨
обладают свойством коммутативности:
P
(
X
)&
Q
(
X
) =
Q
(
X
)&
P
(
X
)
, P
(
X
)&
Q
(
X
) =
Q
(
X
)&
P
(
X
)
и
P
(
X
)
∨
Q
(
X
) =
Q
(
X
)
∨
P
(
X
)
.
Очевидно, что при определении
T
1
или
T
2
, если
P
(
x
i
) =
“л
”
,
то значение
Q
(
x
i
)
или
Q
(
x
i
)
нет необходимости проверять, а при
определении
T
3
нет необходимости проверять значение
Q
(
x
i
)
, если
P
(
x
i
) =
“и
”
. Отсюда следует, что использование свойства коммута-
тивности приведет ксокращению числа операций сравнения, если при
определении
T
1
или
T
2
предикаты
P
(
x
i
)
и
Q
(
x
i
)
или
P
(
x
i
)
и
Q
(
x
i
)
соответственно располагать по возрастанию вероятности исхода “ис-
тина”, а при определении
T
3
предикаты
P
(
x
i
)
и
Q
(
x
i
)
располагать по
убыванию того же параметра.
Отметим, что при выполнении операций над более чем двумя пре-
дикатами их ранжирование правомерно на основании законов ассоциа-
тивности и коммутативности. Использование данного преобразования
возможно, если существуют или могут быть получены за приемлемое
время оценки вероятности исхода “истина” соответствующих преди-
катов.
Заключение.
Выполненные в работе исследования показали вы-
сокую эффективность большинства оптимизирующих преобразований
данного класса. Это обусловливает целесообразность их широкого ис-
пользования при разработке алгоритмов на графах и множествах.
ЛИТЕРАТУРА
1.
Овчинников В.А.
Алгоритмизация комбинаторно-оптимизационных задач при
проектировании ЭВМ и систем: М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 c.
2.
Судоплатов С.В.
,
Овчинникова Е.В.
Элементы дискретной математики: учебник.
М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. 280 с.
3.
Ахо А.В.
,
Хопкрофт Д.Э.
,
Ульман Д.Д.
Построение и анализ вычислительных
алгоритмов: пер. с англ. М.: Мир, 1979. 535 с.
4.
Ахо А.В.
,
Хопкрофт Д.Э.
,
Ульман Д.Д.
Структуры данных и алгоритмы: пер. с
англ. М.: Вильямс, 2001. 384 с.
ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4 65
