4. Б а с к а к о в С. С. Алгоритм автоматического выбора опорных узлов в беспро-
водных сенсорных сетях // Тр. конф. “Информационные технологии и системы”
(ИТиС-2007). – Звенигород: 2007. – С. 2–8.
Статья поступила в редакцию 21.01.2008
Сергей Сергеевич Баскаков родился в 1981 г., окончил МГТУ
им. Н.Э. Баумана в 2006 г. Аспирант кафедры “Информацион-
ные системы и телекоммуникации” МГТУ им. Н.Э. Баумана.
Автор 3 научных работ в области беспроводных сетей и си-
стем связи.
S.S. Baskakov (b. 1981) graduated from the Bauman Moscow
State Technical University in 2006. Post-graduate of “Information
Systems and Telecommunications” department of the Bauman
Moscow State Technical University. Author of 3 publications in
the field of wireless networks and communication systems.
УДК 004.422.6
К. А. П а с е ч н и к о в, Г. С. И в а н о в а
СИНТЕЗ ОПТИМАЛЬНЫХ СТРУКТУР ДАННЫХ
ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ
Предложена модель, позволяющая адекватно отобразить харак-
теристические особенности базовых структур данных, используе-
мых для представления графовых моделей. Формально определена
операция объединения базовых структур данных, что позволило
автоматизировать расчет временн ´ых и емкостных параметров
полученных комбинированных структур данных. Предложена фор-
мальная постановка задачи синтеза оптимальной (с точки зрения
минимимизации вычислительной сложности выполнения заданного
набора операций) одноуровневой комбинированной структуры дан-
ных при условии допустимой емкостной сложности этой струк-
туры.
При решении задач структурного анализа и синтеза на графах при-
меняется большое число различных структур данных. Они использу-
ются для хранения не только основной (информации о графе), но и раз-
личной вспомогательной информации. Как было показано в работах
[1–4], способ организации элементов структуры данных существенно
влияет на вычислительную и емкостную сложности программ реше-
ния задач на графах. В работах [2, 3] показано, что применение лишь
базовых структур данных для решения задач на графах неэффективно
в силу отсутствия такой базовой структуры данных, которая обеспечи-
ла бы минимальную вычислительную сложность для любой операции.
Следовательно, необходим синтез комбинированных структур данных
и выбор из них оптимальной с точки зрения вычислительной слож-
ности.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 29
