УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Применение деревьев для реализации массовых операций на многомерных массивах данных

© 2011, А.Г. Банных

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Полный текст работы
Презентация

Аннотация

Широко известны методы выполнения массовых операций на линейных массивах данных при помощи деревьев. В настоящей работе был произведен обзор существующих алгоритмов реализации массовых операций на многомерных массивах данных. Было показано, что обобщение классического подхода на многомерные структуры данных не позволяет добиться желаемой эффективности.

Был исследован вопрос реализации массовых операций на многомерных структурах данных для случая абелевых групп. Был разработан метод построения многомерных деревьев для эффективного вычисления сумм и прибавления на гиперпараллелепипедах.

В связи с простотой реализации и эффективностью использования памяти, разработанные структуры данных могут быть использованы в различных задачах обработки многомерных массивов данных. Практичность метода была продемонстрирована на примере задачи «прибавление числа и сумма на прямоугольнике».