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

• Автор: Пасечников, Константин Алексеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 161 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ СИНТЕЗА СТРУКТУР ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ

1.1. Анализ существующих методов оптимизации структур данных .

1.1.1. Языки сверхвысокого уровня и абстрактные типы данных.

1.1.2. Специализация структур данных

1.1.3. Оптимизация структур данных, использующих указатели

1.1.4. Оптимизация структур данных с большим количеством элементов.

1.2. Анализ методов ав томатического выбора оптимальных структур данных.

1.3. Анализ существующих формальных описаний структур данных

1.4. Постановка задачи синтеза о тимальньх структур данных.

Выводы по главе 1.
2. РАЗРАБОТКА МОДЕЛЕЙ СТРУКТУР ДАННЫХ.
2.1. Анализ операций над структурами данных.
2.2. Модели базовых одноуровневых структур данных.
2.3. Модели комбинированных одноуровневых структур данных.
2.4. Формальная постановка задачи синтеза одноуровневой структуры данных
2.5. Модели вазовых двухуровневых структур данных.
2.6. Формальная постановка задачи синтеза двухуровневой
струк гуры данных.
Выводы по главе 2.
3. РАЗРАБОТКА МЕТОДИКИ СИНТЕЗА ОПТИМАЛЬНЫХ СТРУКТУР ДАННЫХ И ГЕНЕРАЦИИ ИХ ОПИСАНИЙ.
3.1. Синтез комбинированных одноуровневых структур данных
3.1.1. Разработка алгоритма решения задачи синтеза оптимальной одноуровневой структуры данных
3.1.2. Входные данные и способы их представления.
3.1.3. Способ задания функций одного переменного
3.1.4. Реализация операции объединения структур данных
3.1.5. Генерация описания одноуровневой структуры данных
3.2. Синтез многоуровневых структур данных
3.2.1. Разработка алгоритма синтеза двухуровневой структуры.
3.2.2. Генерация описания многоуровневой структуры данных.
Выводы по главе 3.
4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ.
4.1. Программное обеспечение системы синтеза оптимальных
СТРУКТУР ДАННЫХ.
4.2. Исследование зависимости вычислительной сложности
РЕАЛИЗАЦИИ АЛГОРИТМА УРАВНОВЕШЕННОЙ ДВОИЧНОЙ СВЕРТКИ
ОТ СТРУКТУР ДАННЫХ
4.3. Исследование зависимости вычислительной сложности алгоритма
НЕУРАВНОВЕШЕННОЙ ДВОИЧНОЙ СВЕРТКИ ОТ СВОЙСТВ ВХОДНЫХ ДАННЫХ .
4.4. Исследование зависимости вычислительной сложности алгоритма
лингвистического анализа текста от структур данных
Выводы по главе 4.
СПИСОК ЛИТЕРАТУРЫ


В литературе встречается упоминание о частичной специализации функций программы [, ], однако можно также специализировать структуры данных [, ]. Специализация структур данных подразумевает их оптимизацию под конкретные операции. Существует класс программ (например, сервера приложений), которым вследствие их функционального предназначения приходится постоянно работать с одинаковыми или похожими наборами входных данных. Рассмотрим в качестве примера программу учёта книг в большой электронной библиотеке. Каждой книге в электронной картотеке соответствует номер и название. Программа выполняет две основные функции - добавление новой книги в библиотеку и поиск книги по номеру. На основании данных статического анализа невозможно сделать предположение о том, как будут соотноситься на этапе исполнения количества операций вставки и доступа, так как эти параметры существенно зависят от входных данных, т. В этом случае можно предположить, что количество операций доступа примерно равно количеству операций вставки. С учетом этого в качестве структуры данных можно использовать бинарное дерево, которое обеспечивает одинаковую вычислительную сложность O(log^n) для операций вставки и доступа по ключу. Далее рассмотрим процесс применения данной программы в двух случаях - когда уже имеется большое количество книг, которые необходимо поместить в библиотеку (после чего книг и добавляются редко) и когда заполнение книгами идёт по мере использования. Очевидно, что выбранная структура данных будет эффективна только во втором случае. В первом же случае было бы логично на первом этапе (заполнение книгами) использовать связный список, с вычислительной сложностью операции добавления 0(1), а на втором - вектор, либо список с вектором прямого доступа, т. В литературе встречается упоминание о статической, динамической и адаптивной специализации функций [, ], однако проведённый анализ показывает, что эти же методы можно использовать и при специализации структур данных. При статической специализации разработчик на этапе проектирования программы определяет особенности входных данных, позволяющие предсказать вид управляющего графа на этапе исполнения программы. Существенным недостатком данного способа является то, что он требует от разработчика знания о возможных способах применения разрабатываемой программы. К достоинствам данного способа относится простота его реализации. При динамической специализации программа перед началом эксплуатации запускается на типовых наборах входных данных. В результате этих прогонов собирается статистическая информация, достаточная для генерации оптимальных структур данных для заданных входных наборов. Недостатком данного способа является дополнительная нагрузка на пользователя результирующей программы. В случае адаптивной специализации программа в процессе эксплуатации сама собирает статистическую информацию и перестраивает структуры данных. Этот способ наиболее сложен в реализации, однако при его применении отсутствует дополнительная нагрузка на разработчика или пользователя. Необходимо также учитывать, что перестройка структур данных может потребовать значительного объёма памяти и времени, что также может негативно сказываться на функционировании программы. Если рассматривать вышеприведённый пример, то данный вид специализации является предпочтительным. Сначала будет сгенерирована структура данных, оптимальная для большого количества операций вставки, затем, когда количество операций вставки и доступа будет примерно одинаковым, эта структура будет заменена другой, выполняющей эти операции одинаково быстро, и, наконец, когда количество операций доступа существенно превысит количество операций вставки, структура данных будет заменена на оптимальную для операций доступа. Сравнение всех способов специализации приведено в таблице 1. В процессе специализации структур данных требуется их перестройка в соответствии с выполняемыми над ними операциями. Очевидно, что без использования абстрактных типов данных и синтеза оптимальных структур данных, этот процесс практически невозможен.