структуру;
y
i
— признак вхождения
i
-й структуры в комбинированную
структуру;
r
s
(
n
)
— функция, определяющая число повторений опера-
ции типа
s
∈
S
в зависимости от размера входа задачи,
r
s
(
n
)
∈
R
;
Q
s
(
n
)
— оценка вычислительной сложности операции типа
s
над ре-
зультирующей структурой данных,
Q
s
(
n
)
∈
Q
∗
.
В этом случае задача определения оптимальной структуры данных
заключается в нахождении такого множества индексов
I
, при котором
Q
Σ
→
min
при сохранении истинности отношения
L
∗
(
n
)
L
доп
(
n
)
.
Таким образом, в соответствии с формальной постановкой основ-
ными этапами синтеза оптимальных структур данных являются: ото-
бражение описания схемы алгоритма в базис операций над структу-
рами данных; определение числа выполнений каждой операции для
каждой структуры данных (задание множества
R
); определение такого
множества индексов
I
, для которого значение приведенной целевой
функции минимально, т.е. определение такого набора структур дан-
ных, объединение которых дает оптимальный результат с точки зре-
ния указанного критерия; реализация объединения базовых структур
данных для получения комбинированной структуры данных.
СПИСОК ЛИТЕРАТУРЫ
1. А х о А., У л ьм а н Д., Х о п к р о ф т Д. Структуры данных и алгоритмы. –
М.: Вильямс, 2003. – 384 с.
2. И в а н о в а Г. С. Математические модели структур // Информационные тех-
нологии. – 2006. – № 9. – С. 44–52.
3. О в ч и н н и к о в В. А. Алгоритмизация комбинаторно-оптимизационных за-
дач при проектировании ЭВМ и систем. – М.: Изд-во МГТУ им. Н.Э. Баумана,
2001. – 288 с.
4. К о р м е н Т., Л е й з е р с о н Ч., Р и в е с т Р. Алгоритмы: построение и анализ.
– М.: МЦНМО, 2004. – 960 с.
Статья поступила в редакцию 28.02.2008
Константин Алексеевич Пасечников родился в 1982 г., окон-
чил МГТУ им. Н.Э. Баумана в 2005 г. Руководительдепарта-
мента технических проектов в ООО “Protection Technology”
(StarForce). Автор 6 научных работ в области вычислительной
техники. Специализируется в области автоматизации проекти-
рования компьютерных систем.
K.A. Pasetchnikov (b. 1982) graduated from Bauman Moscow
State Technical University in 2005. Head of Technical Projects
Department at limited-liability company Protection Technology
(StarForce). Author of 6 publications in field of computer science.
Primary specialization is design of program systems.
Галина Сергеевна Иванова родиласьв 1954 г., окончила МВТУ им. Н.Э. Баумана в
1978 г. Канд. техн. наук, доцент кафедры “Компьютерные системы и сети” МГТУ
им. Н.Э. Баумана. Автор 50 научных работ в области вычислительной техники. Спе-
циализируется в области проектирования программных систем.
G.S. Ivanova (b. 1954) graduated from Bauman Moscow Higher Technical School in
1978, PhD (Eng), assoc. professor of “Computers Systems and Networks” Department
of Bauman Moscow State Technical University. Author of 50 publications in field of
computer science. Specializes in the field of designing program systems.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 37
