ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
144
По постановке задачи синтеза структур данных для представле-
ния объектов задач рассматриваемого класса на основании выпол-
ненного анализа можно сформулировать следующие положения:
1)
объект задачи структурного анализа или синтеза (граф) задает-
ся аналитически совокупностью множеств и множеств подмножеств.
(
При матричном задании задача синтеза эффективных структур дан-
ных не стоит.);
2)
между элементами указанных множеств и подмножествами
существуют отношения соответствия, определяемые предикатами
инцидентности или смежности, которые востребованы для данного
алгоритма. Эти отношения являются взаимно однозначными и долж-
ны быть реализованы в производной структуре данных для аналити-
ческого представления графа;
3)
структуры данных для представления множеств и подмно-
жеств выбирают в соответствии с требованием минимальной вычис-
лительной сложности выполнения комплекса операций, заданных над
этими множествами в алгоритме, с учетом ограничения на емкост-
ную сложность представления объекта (вектор, односвязный или
двусвязный список);
4)
необходимость эффективного выполнения на полученном
представлении объекта операций, связанных с преобразованием со-
ответствующих иерархических структур данных, обусловливает по-
явление дополнительных отношений и реализующих их структур;
5)
каждая дополнительная структура требует затрат памяти на ее
организацию.
Исходными данными для синтеза структуры, представляющей
объект задачи структурного анализа или синтеза являются:
•
совокупность множеств, представляющих объект и основные
отношения между этими множествами и их элементами, а также раз-
мер элемента данных каждого множества;
•
множество базовых и производных структур данных для пред-
ставления множеств и их подмножеств;
•
множество операций, выполняемых над объектом, и описания
этих операций на языке уровня множеств, что позволит определить
множество операций над данными структуры;
•
количество повторений каждой операции над объектом в алго-
ритме;
•
совокупность дополнительных отношений между компонента-
ми данных, реализация которых позволяет задать альтернативные
варианты выполнения операций над синтезируемой структурой дан-
ных с меньшей вычислительной сложностью;
•
совокупность структур, реализующих дополнительные отноше-
ния в основной структуре данных;