Система построения генераторов комбинаторных множеств на основе деревьев и/или

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

ВВЕДЕНИЕ

1. ГЕНЕРАТОРЫ КОМБИНАТОРНЫХ МНОЖЕСТВ И СИСТЕМЫ ИХ ПОСТРОЕНИЯ

1.1. Генераторы. Основные определения.

1.2. Методы построения алгоритмов г енерации

1.3. Инструментальные средства построения генераторов.

1.3.1. Языки программирования.

1.3.2. Библиотеки алгоритмов генерации

1.3.3. Пакеты математического моделирования.

1.3.4. Требования к инструментальным средствам построения генераторов.

1.4. Вывода.

2. ДЕРЕВЬЯ ИИЛИ И ОПЕРАЦИИ НАД НИМИ.

2.1. Деревья ИИЛ И.
2.2. Метод построения алгоритмов генерации и нумерации комбинаторных множеств на деревьях ИИЛИ
2.2.1. Алгоритм получения варианта дерева ИИЛИ.
2.2.2. Алгоритм нумерации варианта дерева ИИЛИ.
2.2.3. Операция композиции
2.2.4. Рекурсивная композиция.
2.2.5. Представление комбинаторных множеств деревьями ИИЛИ.
2.2.6. Представление комбинаторных множеств рекурсивной композицией деревьев ИИЛИ
2.2. Теоретикомножественные операции на деревьях ИИЛИ
2.4. Формализация процесса построения деревьев ИИЛИ
2.5. Выводы.
3. СИСТЕМА ПОСТРОЕНИЯ ГЕНЕРАТОРОВ КОМБИ НАГОРНЫХ МНОЖЕСТВ
3.1. Библиотека комбинаторных алгоритмов.
3.1.1. Библиотека алгоритмов комбинаторной генерации.
3.1.2. Библиотека деревьев.
3.2. ЯЗЫК ОПИСАНИЯ ГЕНЕРАТОРОВ I.
3.2.1. Операции над деревьями ИИЛИ
3.2.2. Добавление ветви
3.2.3. Поиск по образцу.
3.2.4. Удаление ветви
3.2.5. Замена ветви
3.2.6. Правила преобразования деревьев ИИЛИ.
3.2.7. Пространства имн.
3.2.8. Предопределнные правила преобразования.
3.3. Интерпретатор языка 1.
3.4. ВЫВОДЫ
4. АНАЛИЗ ПРИМЕНЕНИЯ СИСТЕМЫ ПОСТРОЕНИЯ ГЕНЕРАТОРОВ КОМБИНАТОРНЫХ МНОЖЕСТВ
4.1. Технология построения генераторов.
4.2. Исследование алгоритмов комбинаторной генерации.
4.3. Генерация тестовых заданий
4.4. Тестирование программных комплексов.
4.5. Генерация штрихкодов.
4.6. Исследование системы построения генераторов.
4.7. Эффективность внедрения системы построения генераторов Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Пакеты математического моделирования, на которых основаны данные библиотеки, не предназначены для использования в разработке программного обеспечения (ПО), что является серьезным недостатком, т. Таким образом, актуальной является задача разработки программных систем построения генераторов комбинаторных множеств на основе универсальных методов построения алгоритмов генерации и нумерации. Пелыо диссертационной работы является разработка и исследование системы построения генераторов комбинаторных множеств на основе деревьев И/ПЛИ. Методы исследования. В работе использованы понятия и методы системного анализа, теории множеств, теории алгоритмов, лямбда-исчисления, формальных грамматик, теории объектно-ориентированного и функционального программирования. Впервые определены теоретико-множественные операции на деревьях И/ИЛИ, введены операции И-произведения и ИЛИ-объедипсния. Показано, что выявленное множество алгебраических операций на деревьях И/ИЛИ и система лямбда-исчисления позволяют формализовать процесс построения деревьев И/ИЛИ. Создан оригинальный язык описания генераторов GIL, реализующий метод построения алгоритмов генерации и нумерации комбинаторных множеств на деревьях И/ИЛИ. Разработана архитектура универсального STL-совместимого контейнера для представления древовидных структур данных, на основе которой реализован интерпретатор языка GIL. Предложена технология построения программных генераторов, обеспечивающая разработку генераторов для широкого круга предметных областей. Теоретико-множественные операции на деревьях И/ИЛИ позволяют формализовать процесс построения деревьев И/ИЛИ. Функциональный язык программирования GTL обладает удобными выразительными средствами для описания программных генераторов на основе деревьев И/ИЛИ. Архитектура универсального STL-совместимого контейнера для представления древовидных структур данных позволяет создавать классы деревьев с заданными свойствами. Технология построения программных генераторов обеспечивает снижение сроков разработки генераторов и объема их программного кода. Практическая ценность. Исследовать алгоритмы генерации и нумерации комбинаторных множеств на основе деревьев И/ИЛИ в разработанной системе построения генераторов. Разрабатывать генераторы комбинаторных множеств на основе библиотеки комбинаторных алгоритмов и языка построения генераторов GIL для различных предметных областей. Применять разработанные модели генераторов на основе грамматик, представленных в виде дерева И/ИЛИ, для построения генераторов тестовых заданий систем контроля знаний и генераторов тестовых данных систем тестирования программного обеспечения. Разработанная библиотека комбинаторных алгоритмов, включающая библиотеку деревьев и библиотеку алгоритмов комбинаторной генерации, расширяет возможности комбинаторной генерации библиотеки STL, позволяет создавать контейнеры деревьев с заданными свойствами. Достоверность результатов работы. Достоверность полученных результатов достигается применением научных основ системного анализа, теории множеств, лямбда-исчисления, а также широким внедрением результатов диссертационной работы в практику. Внедрение результатов. Эль Софт» и «Томск Софт». Апробации результатов. Результаты исследований представлены в публикациях различного уровня. Две из них опубликованы в рекомендованных ВАК изданиях. Всероссийская научно-техническая конференция студентов и молодых ученых «Научная сессия ТУСУР-», Томск (). Работа выполнена в рамках ведомственной научной программы «Развитие научного потенциала высшей школы», подпрограммы 1 «Фундаментальные исследования», фундаментальных ПИР, выполняемых в Томском государственном университете систем управления: 1. Создание и исследование методов и алгоритмов комбинаторной генерации». Личный вклад. GIL и его интерпретатор, библиотека комбинаторных алгоритмов, примеры практического применения системы построения генераторов комбинаторных множеств получены лично автором. Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы из наименований, одного приложения. Общий объем диссертации 5 страниц, в том числе рисунка, 4 таблицы.