Введение
1. Анализ существующих методов синтеза структур данных и постановка задачи 10
1.1. Анализ существующих методов оптимизации структур данных 10
1.1.1. Языки сверхвысокого уровня и абстрактные типы данных 10
1.1.2. Специализация структур данных 12
1.1.3. Оптимизация структур данных, использующих указатели 15
1.1.4. Оптимизация структур данных с большим количеством элементов 18
1.2. Анализ методов автоматического выбора оптимальных структур данных 20
1.3. Анализ существующих формальных описаний структур данных 27
1.4. Постановка задачи синтеза оптимальных структур данных 28
2. Разработка моделей структур данных 33
2.1. Анализ операций над структурами данных 33
2.2. Модели базовых одноуровневых структур данных 38
2.3. Модели комбинированных одноуровневых структур данных 53
2.4. Формальная постановка задачи синтеза одноуровневой структуры данных 68
2.5. Модели базовых двухуровневых структур данных 71
2.6. Формальная постановка задачи синтеза двухуровневой структуры данных 88
3. Разработка методики синтеза оптимальных структур данных и генерации их описаний 93
3.1. Синтез комбинированных одноуровневых структур данных 93
3.1.1. Разработка алгоритма решения задачи синтеза оптимальной одноуровневой структуры данных 93
3.1.2. Входные данные и способы их представления 97
3.1.3. Способ задания функций одного переменного 101
3.1.4. Реализация операции объединения структур данных 106
3.1.5. Генерация описания одноуровневой структуры данных 108
3.2. Синтез многоуровневых структур данных 111
3.2.1. Разработка алгоритма синтеза двухуровневой структуры 111
3.2.2. Генерация описания многоуровневой структуры данных 115
4. Экспериментальные исследования полученных результатов 118
4.1. Программное обеспечение системы синтеза оптимальных структур данных 118
4.2. Исследование зависимости вычислительной сложности реализации алгоритма уравновешенной двоичной свертки от структур данных 120
4.3. Исследование зависимости вычислительной сложности алгоритма неуравновешенной двоичной свертки от свойств входных данных 135
4.4. Исследование зависимости вычислительной сложности алгоритма лингвистического анализа текста от структур данных 146
Выводы 152
Список литературы 154
Приложения 159
