Математическое и программное обеспечение обучающих систем, основанное на генерации функционально зависимых цепочек и специализированных алгоритмах выборки тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Кантор, Илья Александрович

• Кантор, Илья Александрович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Кантор, Илья Александрович

Введение

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 Реализация простейшего примера ах — b.

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 Язык описания грамматик

2.1 Введение в LogicTask.

2.1.1 Пример описания семейства задач на LogicTask

2.1.2 Компоненты языка.

2.2 Грамматика LogicTask.*.

2.2.1 Внешняя грамматика

2.2.2 Внутренняя грамматика.

2.3 Интерпретатор LogicTask.

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 Многокритериальные ограниченные сортирующие выборки в реляционных базах данных. Метод деревьев битовых карт.

3.1 Введение.

3.2 Задача ограниченной сортированной многокритериальной выборки.

3.3 Способы решения задачи Q.

3.3.1 Пересечение битовых карт.

3.3.2 Сканирование Б-дерсва.

3.3.3 Геометрические индексы: i?*-tree, Ы-tree, X-tree и др.

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 Выбор параметра BitmapSize.

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 Дополнение.

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

Актуальность темы

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

Однако, теоретической базы в виде классификации по Хомскому часто не хватает для полного описания предметной модели. Например, в молекулярной биологии добавляются вероятности, в лингвистике - специальные статистики.

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

В настоящей работе порождающие грамматики применяются для систем электронного обучения математике.

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

Такой способ обладает рядом известных недостатков, например:

• небольшое количество вариантов задач,

• нельзя использовать элементы одной задачи для описания другой.

Актуально создание новых математических моделей для описания задач, которые этих недостатков лишены.

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

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

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

Ни одна из известных систем электронного обучения (MathAid, Angel Learning, "1С Репетитор: Математика", всего рассмотрено 14 различных систем см. в приложении) такого не может Большое количество вариантов задач весьма востребовано при обучении, проведении экзаменационных, тестовых работ.

Правила вывода одной порождающей грамматики могут применяться в часть другой (наследование грамматик /1/). Это позволяет описывать

Например, в системе "1С Репетитор: Математика" находится всего около 600 задач, в системе "MathAid" - порядка 1500 задач, по несколько - на каждую тему сложные задачи в виде композиции нескольких подзадач. Такая возможность в существующих системах математического обучения отсутствует.

Можно кратко сформулировать актуальные преимущества использования предлагаемого в работе метода генерации задач как:

1. большое количество вариантов в рамках единой схемы решения,

2. возможность описания сложной задачи как композиции подзадач.

Для систем электронного обучения также актуальны технические возможности:

1. возможность применения в интернет, в браузере,

2. интегрируемость генератора в независимую систему обучения.

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

Стандартом де-факто для такого хранения являются реляционные базы данных.

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

Но объем такой базы, в отличие от традиционных систем, составляет не тысячи, а сотни тысяч, миллионы и более записей. Поэтому актуально создание специализированной индексной структуры. В работе предложено "дерево битовых карт".

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

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

Такие выборки нужны не только в высоконагружепных системах, включая:

• интерфейсы по выбору товара, маршрута и т.д в реальном времени,

• системы оптимизации,

• системы принятия решений.

Например, типичная задача такой выборки - нахождение первых 20 самых дешевых предложений в большой базе, причем на параметры искомых предложений накладывается большое количество разнообразных условий.

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

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

Цель и задачи работы

Основной целью работы является разработка языка описания pi алгоритмов генерации pi поиска цепочек с функциональными зависимостями, включая создание интерпретатора и генератора математических задач, а также создание и реализацию индексной структуры для поиска по метаданным цепочек в РСУБД.

Новый язык должен обеспечивать следующие основные возможности.

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

2. Использовать существующие описания задач при создании новых.

3. Предоставлять удобные средства описания задач.

Требуется создать интерпретатор языка и использующий его генератор задач, обладающий следующими характеристиками:

1. реализует функционал, заложенный спецификацией языка,

2. предоставляет программные интерфейсы для интеграции с существующими системами обучения, с интернет-системами,

3. обеспечивает средства добавления новых задач, организацир! существующих задач,

4. гарантирует стабильное, не требующее приостановки операций внесение изменений в систему,

5. обеспечивает параллельный доступ к системе большого количества пользователей.

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

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

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

В соответствии с этим в диссертационной работе поставлены и решены следующие основные задачи:

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

2. Создание специализированного языка для описания таких цепочек, включая a) формальную грамматику языка, b) интерпретатор для его обработки, c) интеграцию с символьными вычислениями в системе Mathematica.

3. Программная реализация генератора задач, удовлетворяющего описанным требованиям и основанного на новом языке.

4. Проверка математической модели и реализации путем внедрения генератора в обучение.

5. Создание индексной структуры для высокоэффективного поиска по большой базе цепочек, включая a) описание алгоритмов построения, поиска и обновления индекса, b) исследование и стоимостные оценки предложенных алгоритмов, c) рекомендации по выбору параметров индексной структуры.

6. Реализация индексной структуры на основе СУБД Cache', тесты новой структуры, сравнение с традиционными индексами в РСУБД Oracle 10g.

Методика исследования

Был проведен анализ методов генерации задач в современных системах электронного обучения, сформулированы основные требования к генератору задач.

Описана модель на основе цепочек с функциональными зависимостями, создан язык для задания цепочек.

С использованием теории графов, формальных грамматик, объектно-ориентированного программирования и ЬЬ(*)-геиератора парсеров /4/, создан генератор задач.

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

Изучены существующие алгоритмы многокритериального поиска, включая методы, основанные на как деревьях /3, 5, 6, 7/ и битовых картах /8, 9/. Рассмотрены их характеристики в приложении к рассматриваемой задаче.

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

С использованием постреляционной СУБД Cache' /10/ произведена реализация новой индексной структуры.

Получены данные по производительности на синтетических тестах по сравнению с традиционными методами поиска. Произведена проверка надежности и эффективности поиска на реальных базах данных.

Научная новизна

Научной новизной обладают следующие результаты диссертационной работы.

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

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

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

4. Выполнена практическая реализация новой индексной структуры для постреляционной СУБД Cache', получены результаты практических тестов.

Практическая значимость

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

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

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

Реализация и внедрение результатов работы

Тестирование программных компонент системы начато в 2005 году. Элементы системы прошли апробацию на базе Московского технического университета связи и информатики (МТУСИ).

Индексная структура была создана в 2006 году, успешно прошла тестирование для поиска по грамматикам и, кроме того, произведено внедрение новой индексной структуры для подбора предложений по базе туристического агентства "Обновление", подбора жилья в риэлторской компании "Рестро", в ряде других компаний.

Доклады и печатные публикации

Результаты работы, связанные с интеграцией с системами обучения, докладывались на "Международной конференции РНР-разработ^иков" в 2006 году, па конференции "Российские Интернет-Технологии" в 2008 году.

Публикации:

1. Кантор И.А. "Метод нестрогого поиска в базах полуструктурированных данных" Технологии высокопроизводительных информационно-вычислительных систем: Сборник статей молодых ученых. Переславль-Залесский: "Университет города Пере-славля 2003г.

2. Кантор И.А. "Интернет-система дистанционного обучения на основе порождающих грамматик Хомского", сборник научных трудов, МИЭМ, 2007г.

3. Кантор И.А. "Многокритериальные ограниченные сортирующие выборки в реляционных СУБД. Метод деревьев битовых карт", журнал "Информационные Технологии", изд. "Новые Технологии", N2, 2008г.

Структура работы

Первая глава закладывает необходимые основы для создания языка описания математических задач.

Секции 1-4 содержат обзор существующих подходов к генерации и введение в новый подход. Представлено сравнение существующих методов с предлагаемым, обосновано создание метода, использующего порождающие грамматики.

Секции 5-6 вводят грамматики с детерминированными правилами. Описан граф вывода(аналог дерева вывода) для таких грамматик, показан способ его получения. Доказан ряд теорем о свойствах графа вывода и указан способ получения из него сентенциальной формы.

В секции 7 описаны грамматики с функциональными зависимостями и введено понятие обобщенного объекта.

Во второй главе рассматривается язык для описания грамматик, его грамматика и интерпретатор.

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

В секции 3 описаны алгоритмы разбора(полукомпиляция), внутренняя структура, основные объекты и работа интерпретатора языка.

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

Секции 1-3 содержат формализацию задачи, обзор и сравнение существующих подходов к ее решению.

В секциях 4-6 предложен новый метод: "метод деревьев битовых карт". Описана индексная структура, операции вставки, удаления и поиска.

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

В секциях 7-8 проведено сравнительное тестирование поиска по новой индексной структуре, реализованной на СУБД Cache', по сравнению с некоторыми традиционными способами на Oracle 10g, более подробно описанными в /11, 12, 13/.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Кантор, Илья Александрович

Выводы

Описание задач на специализированном языке обладает как достоинствами, так и недостатками, по сравнению с другими способами описания.

Однако, описанные недостатки частично нивелируются средствами, позволяющими использовать любой способ описания там, где он оптимален:

• Возможно отдельное описание конкретной задачи

• Специализированная графическая оболочка и язык-фасад для описание через набор параметров

• Есть программные и архитектурные решения для интеграции языка с программами на Java

Заключение

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

Для генерации таких цепочек предлагается использовать модификацию КС-грамматик и специализированный язык LogicTask. Это дает как возможность использования существующих задач для описание новых, так и удобную интеграции с системой символьных вычислений. На текущий момент существует ряд традиционных способов описания математических задач для систем обучения. Предложенный способ ни в коей мере не призван заменить их полностью, но дает новый баланс выразительных возможностей и сложности описания, что подтверждено сравнением в первой главе данной работы.

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

Для поиска по большой базе задач предложена новая индексная структура. Как и многие теоретико-практические результаты в области проектирования эффективных СУБД, она не привязана жестко к предметной области, а может быть применена в ряде смежных областей, включая САПР, пользовательские интерфейсы.

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

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

Список литературы диссертационного исследования кандидат технических наук Кантор, Илья Александрович, 2008 год

1. М. Aksit, R. Mostert, and B.R.H.M. Haverkort. Compiler generation based on grammar inheritance. 1990.

2. Parr and Quong. LL and LR translators need k>l lookahead. SPNOTICES: ACM SIGPLAN Notices, 31, 1996.

3. Christian Bohm, Stefan Berchtold, and Daniel A. Keim. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv., 33(3):322-373, 2001.

4. Marcel Kornacker. High-performance extensible indexing. In VLDB '99: Proceedings of the 25th International Conference on Very Large Data

5. Bases, pages 699-708, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.

6. John T. Robinson. The k-d-b-tree: a search structure for large multidimensional dynamic indexes. In SIGMOD '81: Proceedings of the 1981 ACM SIGMOD international conference on Management of data, pages 10-18, New York, NY, USA, 1981. ACM.

7. Ioannadis Y.E. Chan C.-Y. Bitmap index design and evaluation. In SIGMOD Conf., 1998.

8. Yu P.S. Wu K.L. Range-based bitmap indexing for high cardinality attributes with skew. Technical report, IBM Watson Research Center, 1996.

9. W. Kirsten, Michael Ihringer, and Anthony Rudd. Object-Oriented Application Development Using the Cache Postrelational Database. SpringerVerlag, 2003.

10. Donald K. Burleson. Oracle High-Performance SQL Tuning. McGraw-Hill, Inc., New York, NY, USA, 2001.

11. Gavin J. T. Powell. Oracle Performance Tuning for 10gR2, Second Edition. Digital Press, Newton, MA, USA, 2006.

12. Richard Niemiec. Oracle Database lOg Performance Tuning Tips & Techniques. McGraw-Hill Osborne Media, 2007.

13. Система электронного обучения "angel learning". http://angellearning.com/.

14. Система электронного обучения "atutor". http://www.atutor.ca/.

15. Документация по системе электронного обучения "blackboard", http: //www.blackboard.com/us/index.Bb.

16. Пинский А.И. Гуртовой А.В. Автоматизация и проектирование обучающих систем с использованием порождающих грамматик. НИИВО, 1989.

17. Ульман Дж. Ахо А. Теория синтаксического анализа, перевода и компиляции, Том 1. Издательство "Мир 1978.

18. Richard Н. et al. Gamma, Е. Design patterns: elements of reusable object-oriented software. Addison-Wesley Professional, 1995.

19. Wolfram Research. Wolfram Mathematica Documentation. http://documents.wolfram.com/mathematica/.

20. Кантор И.А. Интернет-система генерации задач на основе порождающих грамматик. МИЭМ, 2007.

21. Terence J. Parr and Russell W. Quong. ANTLR: A predicated-LL(k) parser generator. Software Practice and Experience, 25(7):789-810, 1995.

22. Rosanna Lee and Scott Seligman. The Jndi API Tutorial and Reference: Building Directory-Enabled Java Applications. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2000.

23. Alan Shalloway and James R. Trott. Design Patterns Explained: A New Perspective on Object-Oriented Design. Addison-Wesley Professional, Septembre 2001.

24. Дейт Дж. Введение в системы баз данных. Вильяме, 2006.

25. Quass D. O'Neil P. Improved query performance with variant indexes. In SIGMOD Conf, 1997.

26. Buchmann A. Wu M.C. Encoded bitmap indexing for data warehouses. In 14th ICDE, 1998.

27. Graefe G. O'Neil P. Multi-table joins through bitmapped join indices. In SIGMOD Record, 24(3j, 1995.

28. Кантор И.А. Метод нестрогого поиска в базах полуструктурированных данных. Переславль-Залесский: "Университет города Переслав-ля 2003.

29. Sarawagi S. Indexing olap data. In Bulletin of the Technical Committee on Data Eng., Vol 20, No. 1, 1997: ;

30. Яблонский С.В. Введение в дискретную математику. М.: Высш. шк., 2002.

31. К.Дж. Дейт. Введение в системы баз данных, изд-во Вильяме, 2006.

32. David Salomon. A Concise Introduction to Data Compression. 2008.

33. Faloutsos C. Sellis Т.К., Roussopoulos N. The r+-tree: A dynamic index for multi-dimensional objects. In Hammersley P. Stocker P.M., Kent W., editor, VLDB, pages 507-518. Kaufmann M., 1987.

34. Kriegel H.-P. et al. Beckmann N. The r*-tree: An efficient and robust access method for points and rectangles. In Jagadish H.V. Garcia-Molina H., editor, SIGMOD Conference, pages 322-331. ACM Press, 1990.

35. Kriegel H.-P. Berchtold S., Kcim D.A. The x-tree : An index structure for high-dimensional data. In Buchmann A.P. et al. Vijayaraman T.M., editor, VLDB, pages 28-39. Morgan Kaufmann, 1996.

36. Philip A. Bernstein and Nathan Goodman. Concurrency control in distributed database systems. ACM Comput. Surv., 13(2): 185-221, 1981.

37. Кантор И.А. Многокритериальные ограниченные сортирующие выборки в реляционных СУБД. Метод деревьев битовых карт. Новые Технологии, 2008.

38. Gurry М. Corrigan P. ORACLE Performance Tuning. 1993.