Математическое и программное обеспечение обучающих систем, основанное на генерации функционально зависимых цепочек и специализированных алгоритмах выборки

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

Оглавление
Введение

1 Генерация математических задач при помощи модификации формальных грамматик

1.1 Введение

1.2 Функции математического ядра .

1.3 Обзор существующих математических ядер

1.3.1 Полностью раздельное описание задач.

1.3.2 Подстановка зависимых параметров, основанная на

случайном выборе

1.3.3 Языки программирования общего назначения

1.3.4 Использование математических пакетов

1.4 Применение порождающих грамматик
1.4.1 Требования к генератору задач.
1.4.2 Реализация простейшего примера ах Ь.
1.4.3 Сравнение предлагаемого подхода с существующими
1.5 Грамматики с детерминированными правилами.
1.6 Дерево и граф вывода детерминированной грамматики .
1.6.1 Дерево вывода детерминированной грамматики .
1.6.2 Граф вывода детерминированной грамматики
1.7 Генерация цепочек с функциональными зависимостями .
1.7.1 Обобщенные символы. Объектные грамматики
1.7.2 Отображаемые объекты. Функции грамматики
1.7.3 Грамматика с функциональными зависимостями .
1.7.4 Применение грамматик для генерации задач.
Язык описания грамматик
2.1 Введение в ЬоджТавк.
2.1.1 Пример описания семейства задач на Ьод1сТазк .
2.1.2 Компоненты языка.
2.2 Грамматика ЬодгсТавк.
2.2.1 Внешняя грамматика
2.2.2 Внутренняя грамматика
2.3 Интерпретатор Ьод1сТак .
2.3.1 Основные типы объектов.
2.3.2 Деление объектов по иерархиям
2.3.3 Компиляция грамматики
2.3.4 Генерация
2.3.5 Пример компиляции
2.3.6 Структура правил.
2.3.7 Команды .
2.3.8 Интерпретация правил.
Многокритериальные ограниченные сортирующие выборки в реляционных базах данных. Метод деревьев битовых карт.
3.1 Введение
3.2 Задача ограниченной сортированной многокритериальной
выборки
3.3 Способы решения задачи ф
3.3.1 Пересечение битовых карт
3.3.2 Сканирование Бдсрсва.
3.3.3 Геометрические индексы ГЧгее, кстее, ХЬтее и др.
3.3.4 Метод упорядоченных битовых карт
3.3.5 Комбинированные методы
3.4 Дерево битовых карт.
3.4.1 Принципы построения индекса.
3.4.2 Структура индекса
3.4.3 Вставка записи в основное дерево поиска
3.4.4 Удаление записи
3.4.5 Блокировка и одновременный доступ
3.4.6 Поиск по дереву битовых карт.
3.4.7 Размер основного дерева поиска.
3.4.8 Дополнительные оптимизации
3.5 Оценка операций при поиске.
3.6 Выбор параметра ВИтарБге
3.6.1 Оптимизация операций вводавывода
3.6.2 Влияние на стоимость поиска
3.6.3 Оценка плотности при равномерном распределении .
3.7 Сравнение со сканированием Бдерева.
3.8 Сравнительное тестирование.
3.8.1 Методы поиска.
3.8.2 Размеры индексных структур
3.8.3 Агрегатные результаты
3.8.4 Результаты по времени и блокам
3.8.5 Дополнение
Заключение
Приложения
Приложение 1 Системы математического обучения.
Список использованной литературы


Ввиду своей эффективности на рассматриваемом классе задач эта индексная структура также весьма востребована в системах с большим объемом миогопараметризовапных данных, оперирующих в реальном времени. Если расширить сферу применения поискового алгоритма на произвольные данные, то дерево битовых карт полезно для многокритериальных сортированных выборок с небольшим окном поиска, т. Например, типичная задача такой выборки - нахождение первых самых дешевых предложений в большой базе, причем па параметры искомых предложений накладывается большое количество разнообразных условий. Сотни условий на параметры накладываются при многокритериальных сортированных выборках также в задачах астрономии /2, 3/. Высокоэффективная индексная структура особенно актуальна в системах реального времени. То есть, когда на максимальное время выполнения запроса накладываются жесткие временные ограничения. Основной целью работы является разработка языка описания и алгоритмов генерации и поиска цепочек с функциональными зависимостями, включая создание интерпретатора и генератора математических задач, а также создание и реализацию индексной структуры для поиска но метаданным цепочек в РСУБД. Новый язык должен обеспечивать следующие основные возможности. Описывать большое количество вариантов в рамках единой схемы решения задачи. Использовать существующие описания задач при создании новых. Предоставлять удобные средства описания задач. Требуемый класс выборок формализован как много-критериальные отсортированные выборки с заданным окном. Это такие выборки, где кроме сильно меняющегося набора ограничений на поля, требуется сортировка по одному или нескольким фиксированным атрибутам, и указан промежуток порядковых номеров искомых записей. В частности, такая структура должна поддерживать эффективный поиск при большом количестве записей. Дополнительно, для практического тестирования и внедрения должна быть создана практическая реализация индексной структуры, произведена апробация и сравнительный анализ. Характеристики новой индексной структуры следует сравнить с традиционными индексными структурами. Создание математической модели, описывающей структуру условия и хода решения математической задачи и использующей цепочки с функциональными зависимостями. Ма^ешаНса. Программная реализация генератора задач, удовлетворяющего описанным требованиям и основанного на новом языке. Проверка математической модели и реализации путем внедрения генератора в обучение. Реализация индексной структуры на основе СУБД Cache’, тесты новой структуры, сравнение с традиционными индексами в РСУБД Oracle g. Был проведен анализ методов генерации задач в современных системах электронного обучения, сформулированы основные требования к генератору задач. Описана модель на основе цепочек с функциональными зависимостями, создан язык для задания цепочек. С использованием теории графов, формальных грамматик, объектно-ориентированного программирования и ЬЬ(*)-геиератора парсеров /4/, создан генератор задач. Изучены существующие алгоритмы многокритериального поиска, включая методы, основанные на как деревьях /3, 5, 6, 7/ и битовых картах /8, 9/. Рассмотрены их характеристики в приложении к рассматриваемой задаче. Разработана новая индексная структура, получены оценки ее размера, стоимостная оценка поиска, ряд дополнительных оценок. Показан класс задач, на которых новая структура работает эффективнее прочих рассмотренных. Приведен ряд рекомендаций рекомендации но выбору параметров индексной структуры и предложены некоторые оптимизации. С использованием постреляционной СУБД Cache’ // произведена реализация новой индексной структуры. Получены данные по производительности на синтетических тестах по сравнению с традиционными методами поиска. Произведена проверка надежности и эффективности поиска на реальных базах данных. Научной новизной обладают следующие результаты диссертационной работы. В работе описан новый грамматик — грамматики с функциональными зависимостями. Создан язык для описания порождающих грамматик для семейств математических задач. Реализован интерпретатор и генератор задач, работающий на созданном языке.