ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
135
УДК 004.3+519.6
В . А . О в ч и н н и к о в , Г . С . И в а н о в а
МЕТОДИКА ФОРМАЛЬНОГО СИНТЕЗА
КОМБИНИРОВАННЫХ СТРУКТУР ДАННЫХ
ДЛЯ ПРЕДСТАВЛЕНИЯ ГРАФОВ
На примере организации хранения множества ребер гиперграфа и их
образов относительно предиката инцидентности рассмотрена ме-
тодика синтеза комбинированных многоуровневых структур данных.
Математическими моделями базовых и производных структур дан-
ных являются ориентированные графы. Модель синтезированной
структуры формируется в результате выполнения операции объеди-
нения модели исходной структуры и модели отношений, обеспечива-
ющих эффективную реализацию заданных операций.
E-mail:
vaovchinnikov@gmail.com
,
gsivanova@gmail.com
Ключевые слова:
графы, математические модели, структуры
данных, формальный синтез.
Формальный синтез комбинированных структур базируется на
анализе данных, отношений между ними и набора выполняемых опе-
раций. Целью синтеза является получение такой структуры, которая
обеспечивала бы высокую эффективность выполнения заданных над
данными операций.
Возможность формального синтеза обеспечивается наличием биб-
лиотеки моделей базовых и производных структур данных, а также
процедур отношений и предикатов (биективного, сюръективного и
инъективного отношений, предиката принадлежности элементов под-
множества множеству и т. д.). При автоматизированном синтезе поль-
зователю необходимо задать имена, размеры множеств, отношения
между ними и имена моделей базовых или производных структур для
их хранения.
Рассмотрим механизм такого синтеза на следующем примере.
Пусть необходимо построить структуру для представления множе-
ства ребер и их образов гиперграфа, заданного в форме
H
(
X
,
<
U
,
W
>
,
Г
X
,
Г
U
).
Над гиперграфом выполняются операции поиска ребер
с максимальным весом, удаления вершин и «пустых» ребер, т. е.
тех, у которых |Г
u
| = 0. Количество ребер |
U
⎢
после удаления «пу-
стых» может быть значительно меньшим, чем до удаления, которое
обозначим как |
U
исх
⎢
.
При удалении вершин и «пустых» ребер по-
рядок их записи необходимо сохранять. Все операции следует вы-
полнять с минимально возможной вычислительной сложностью.
Дальнейшие оценки даются в количестве операций сравнения для
худшего случая.