дает возможностьавтоматически определятьих вычислительные и
емкостные параметры.
Формальная постановка задачи синтеза оптимальных комби-
нированных структур данных.
Исходными данными [2] для синтеза
оптимальной с точки зрения вычислительной сложности заданного
алгоритма структуры данных являются:
1) описание множества и размер элемента его данных;
2) совокупностьбазовых структур данных
B
=
{
b
i
=
=
G
i
, Q
i
, L
i
(
n
)
}
;
3) совокупностьопераций, выполняемых над множеством, что по-
зволит определитьнабор операций над данными структуры;
4) число повторений каждой операции над множеством в алгоритме
(множество функций
R
=
{
r
(
n
) :
S
→
N
}
)
;
5) допустимый объем памяти
E
доп
(
n
)
, который может занятьсин-
тезируемая структура.
При этом операции, выполняемые над множествами, должны быть
представлены как базовые, поскольку базовые операции, реализую-
щие основные отношения между элементами множества, независимы
с точки зрения их вычислительной сложности.
На основе данных, приведенных в п. 1 и 2, можно сформировать
множество вариантов моделей структур данных, которые получаются
посредством объединения тех или иных базовых структур, и опреде-
литьих характеристики. Из полученного множества необходимо вы-
братьтакую структуру данных, которая для заданного набора опе-
раций обеспечивает минимальную вычислительную сложность и ем-
костная сложностькоторой не превышает допустимого значения. От-
сюда получаем формальную постановку задачи синтеза оптимальной
структуры данных в следующем виде:
M
opt
=
G
∗
, Q
∗
, L
∗
(
n
)
∈
M
;
G
∗
=
i
∈
I
G
i
:
Q
Σ
=
s
∈
S
r
s
(
n
)
∗
Q
s
(
n
)
→
min;
L
∗
(
n
)
L
доп
(
n
)
,
L
доп
(
n
) =
E
доп
(
n
)
−
nl
V
;
(1)
здесь
G
∗
∈
G
;
G
— множество вариантов структуры, которые реализу-
ют основные отношения, заданные на множестве элементов графа, и,
возможно, дополнительные отношения, вытекающие из выполняемых
над этими данными операций;
G
i
— базовая одноуровневая структу-
ра данных (см. п. 2);
I
=
{
y
i
∗
i
}
— множество индексов структур,
включенных в результирующую структуру;
i
∈
I
— множество индек-
сов структур данных — кандидатов на вхождение в комбинированную
36 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
