Синтез оптимальных структур данных для алгоритмов решения комбинаторных задач на графах

Актуальность. К задачам структурного анализа и синтеза относят задачи исследования или определения некоторого варианта структуры объекта, под которой понимают совокупность составляющих его элементов и связей между ними [19]. В качестве моделей объекта и результата в этих задачах обычно используются графы различных типов, позволяющие отображать существенные с точки зрения решаемой задачи отношения между компонентами рассматриваемой структуры.

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

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

Вычислительная сложность вариантов реализации алгоритма при использовании различных структур данных может отличаться на несколько порядков. Данная задача, т. е. задача синтеза оптимальных структур данных, является самостоятельной научной проблемой, актуальной для многих научно-технических направлений. На данный момент существуют системы, которые решают лишь задачу выбора оптимальной структуры данных [32, 49, 51], в то время как формальной постановки задачи синтеза до сих пор не было получено.

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

Цель работы — создание комплекса математических, лингвистических и программных средств автоматической генерации структур данных, оптимальных с точки зрения вычислительной сложности операций над данными и используемых для представления объектов задач структурного синтеза.

Основные решаемые задачи. Для достижения указанной цели в работе потребовалось:

1. Выполнить анализ существующих структур данных с целью выявления Pix свойств и классификации основных операций над ними.

2. На основании проведённого анализа разработать модели структур данных, позволяющие оценивать влияние организации данных на ёмкостную и вычислительную сложность.

3. Выполнить формальную постановку задачи синтеза оптимальной структуры данных и разработать метод её решения.

4. Разработать способ генерации синтаксически корректных конструкций описаний оптимальных структур данных.

5. Разработать программную систему синтеза оптимальных структур данных для представления взвешенных множеств и графовых моделей.

6. Выполнить экспериментальную проверку полученных теоретических результатов.

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

Научная новизна работы. В процессе исследования получены следующие новые научные результаты, представляемые на защиту:

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

2. Разработаны структурные модели базовых и комбинированных способов организации данных, применимые для автоматической оценки вычислительной и ёмкостной сложностей алгоритмов решения задач на графах, а также определены формальные правила перехода от объектов к моделям.

3. Формально определена операция объединения моделей структур данных, позволяющая получать модели комбинированных структур данных и их характеристики из базовых.

4. Получена формальная постановка задач синтеза оптимальных с точки зрения минимума вычислительной сложности алгоритма одноуровневых и двухуровневых структур данных для представления графовых моделей, разработаны и реализованы алгоритмы их решения.

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

Практическая ценность работы. По результатам проведенных исследований создана программная система синтеза оптимальных структур данных, которая включает модуль генерации оптимальных структур данных, анализатор вычислительной и емкостной сложности структур данных, библиотеки шаблонов описаний классов абстракций, а также макрогенератор описаний структур данных. Система позволяет автоматизировать процесс синтеза структур данных, а также позволяет получать оценки вычислительной и ёмкостной сложностей для сгенерированных структур.

Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 175-летию МГТУ им. Н. Э. Баумана (Москва, 2005), на научной конференции «Информатика и системы управления», проходившей в МГТУ им. Н. Э. Баумана (Москва, 2007).

Реализация и внедрение. Все основные теоретические и практические результаты работы в виде методик и программных средств внедрены в промышленность. Они использованы при разработке очередной версии системы защиты Windows-приложений StarForce Protection Builder 5.70 в ООО «Протекшей Технолоджи» (StarForce) и при создании системы анализа и классификации текстов БКФ 2.00 в ЗАО «ИнфоВотч» (дочерняя компания ЗАО «Лаборатория Касперского»). Документы, подтверждающие внедрение, приведены в приложении.

Публикации. По результатам диссертационной работы автором опубликовано 7 статей.

Объем и структура диссертации. Диссертационная работа включает введение, четыре главы, заключение и список литературы, занимающих 159 страниц текста, в том числе 32 рисунка и 23 таблицы, список использованной литературы из 58 наименований на 6 страницах.

ВЫВОДЫ.

1. Для представления простых структур разработаны модели базовых структур данных, позволяющие оценивать вычислительную сложность базовых операций и емкостную сложность исследуемой структуры, а также обладающие меньшей избыточностью по сравнению с моделями, предложенными В [13].

2. Поскольку в алгоритмах решения задач на графах используются также многоуровневые структуры данных, были определены и сформулированы правила перехода от объекта к модели для многоуровневых и комбинированных структур данных, а также определены расчетные соотношения для оценки вычислительной и емкостной сложности таких структур по построенным моделям.

3. Для получения комбинированных структур данных из базовых структур, разработана и формально определена операция объединения базовых структур данных. Для упрощения внесения изменений в библиотеку шаблонов предложен вариант реализации операции объединения базовых структур, который существенно упрощает как модификацию существующих шаблонов базовых структур данных, так и добавление новых шаблонов структур данных.

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

5. Для решения задачи синтеза оптимальной структуры данных предложены алгоритмы синтеза одноуровневых и многоуровневых структур, позволяющие получать результирующие структуры посредством комбинации базовых, а также автоматически получать оценки вычислительной и ёмкостной сложности.

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