А.М. Андреев, Г.П. Можаров
4
нахождение частичного описания (построение начальных фраг-
ментаций
1
, ...,
H
P
P
и соответствующих последовательно-
стей
1
, ...,
);
H
P P
поиск общей трансверсали признаков для
H
последовательно-
стей
1
, ...,
H
P P
длины
M
семейства
, причем общая трансвер-
саль признаков для семейства
1
, ...,
H
P P
не обязательно существу-
ет. Это означает, что на заданном семействе признаков не может
быть реализовано ПО с требуемыми свойствами, следовательно, тре-
буется возврат с этого этапа синтеза к предыдущему и изменение ви-
да последовательностей
1
, ...,
H
P P
(возможно, придется изменить и
начальные разбиения);
построение разбиения
, соответствующего найденной
общей трансверсали признаков. Необходимость этого этапа обуслов-
лена тем, что семейство
'
'
'
1
,...,
M
, полученное на втором эта-
пе, может содержать пересекающиеся подмножества, а также, воз-
можно, что
'
'
1
...
M
, т. е. некоторые объекты программы
могут не попасть в подмножества семейства
'
. Поэтому следует
расширить подмножества
'
'
1
,...,
M
до подмножеств
1
,...,
M
семейства
'
так, чтобы
1
...
M
, а затем построить разбие-
ние
.
Опишем формальные комбинаторные схемы для решения задачи
частичного представления множества операций системой ПО.
Пусть
1
,...,
M
P P
семейство подмножеств на конечном
множестве
признаков ПО, a
p
семейство частичных трансвер-
салей ПО. Пара
,
M p
представляет собой матроид [9]. Введем
функцию
:
w R
, где
R
множество неотрицательных дей-
ствительных чисел, а значение
w
есть вес элемента
. Упо-
рядочим множество
1
1
, ...,
M
q
m
m
P
по невозрастанию ве-
сов:
1
...
q
w
w
.
Эта задача совсем нетривиальная, а для разнородных, программ-
ных компонентов ПО проблема еще больше усложняется [7–10].
Здесь важно, чтобы вес
w O
элемента (алгоритмического признака)
был инвариантен относительно будущей реализации ПО. Подобные
допущения оправданы лишь при определенных условиях и на ранних
