Система построения генераторов комбинаторных множеств на основе деревьев и/или тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Титков, Антон Вячеславович

• Титков, Антон Вячеславович
• кандидат технических наук
• 2010

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

ВВЕДЕНИЕ.

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

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. Интерпретатор языка GIL.

3.4. ВЫВОДЫ.

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

4.1. Технология построения генераторов.

4.2. Исследование алгоритмов комбинаторной генерации.

4.3. Генерация тестовых заданий.

4.4. Тестирование программных комплексов.

4.5. Генерация штрих-кодов.

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

4.7. Эффективность внедрения системы построения генераторов .99 Выводы.

Введение диссертации (часть автореферата) на тему «Система построения генераторов комбинаторных множеств на основе деревьев и/или»

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

За время существования информатики как дисциплины комбинаторная генерация стала самостоятельным, динамично развивающимся направлением. Комбинаторной генерации посвящено множество работ. Основной вклад в её развитие внесли Д. Кнут [1], Э. Рейнгольд [2], Ф. Раски [3]. С развитием комбинаторной генерации развивались и методы построения алгоритмов генерации. Самый распространённый, эмпирический метод стал уступать по эффективности методам построения алгоритмов генерации, претендующим на некоторую универсальность (Д. Крехер [4], Е. Баргутччи [5], Ф. Флажоле [6], К. Мартигец [7]). Такие методы позволяют строить алгоритмы генерации для целого ряда предметных областей, однако сильно к ним привязаны и обладают рядом существенных ограничений, что затрудняет автоматизацию процесса построения программных генераторов на их основе.

Сравнительно недавно появился метод построения алгоритмов генерации и нумерации комбинаторных множеств на основе деревьев И/ИЛИ, предложенный В.В. Кручининым [8]. Метод заключается в представлении множества, элементы которого требуется генерировать, в виде дерева И/ИЛИ. В этом случае дерево И/ИЛИ является генератором элементов данного множества. Этот метод обладает широкой областью применения и не имеет таких существенных ограничений, как другие методы.

Темп развития инструментальных средств построения генераторов не соответствует теоретическим достижениям, полученным в области комбинаторной генерации. На сегодняшний день создано большое количество библиотек алгоритмов комбинаторной генерации, реализованных на различных языках программирования. Однако данные библиотеки не обеспечивают системного подхода при построении генераторов, т.к. обладают ограниченным функционалом и не используют главного преимущества универсальных методов построения алгоритмов генерации — единого подхода к построению программных генераторов. Для некоторых универсальных методов существуют программные наработки в виде специализированных библиотек для пакетов математического моделирования (Combinatorica для Mathematica [9], MuPAD-Combinat для MuPAD [10]). Использование таких средств в прикладном программном обеспечении затруднено в связи с тем, что данные библиотеки разработаны в первую очередь для научных исследований. Пакеты математического моделирования, на которых основаны данные библиотеки, не предназначены для использования в разработке программного обеспечения (ПО), что является серьезным недостатком, т.к. генераторы обычно используются как часть программных комплексов и систем. Таким образом, актуальной является задача разработки программных систем построения генераторов комбинаторных множеств на основе универсальных методов построения алгоритмов генерации и нумерации.

Целью диссертационной работы является разработка и исследование системы построения генераторов комбинаторных множеств на основе деревьев И/ИЛИ.

Задачи исследования:

1) анализ методов и инструментальных средств построения программных генераторов, выявление требований к системе построения генераторов комбинаторных множеств;

2) формализация процесса построения генераторов комбинаторных множеств на основе деревьев И/ИЛИ;

Зл разработка математического, алгоритмического и программного обеспечения системы построения генераторов комбинаторных множеств;

4) разработка технологии построения генераторов на основе деревьев И/ИЛИ;

5) экспериментальные исследования системы построения генераторов комбинаторных множеств на примерах практических задач.

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

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

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

1) Впервые определены теоретико-множественные операции на деревьях И/ИЛИ, введены операции И-произведения и ИЛИ-объединения. Показано, что выявленное множество алгебраических операций на деревьях И/ИЛИ и система лямбда-исчисления позволяют формализовать процесс построения деревьев И/ИЛИ.

2) Создан оригинальный язык описания генераторов GIL, реализующий метод построения алгоритмов генерации и нумерации комбинаторных множеств на деревьях И/ИЛИ.

3) Разработана архитектура универсального STL-совместимого контейнера для представления древовидных структур данных, на основе которой реализован интерпретатор языка GIL.

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

Основные положения, выносимые на защиту:

1) Теоретико-множественные операции на деревьях И/ИЛИ позволяют формализовать процесс построения деревьев И/ИЛИ.

2) Функциональный язык программирования GIL обладает удобными выразительными средствами для описания программных генераторов на основе деревьев И/ИЛИ.

3") Архитектура универсального STL-совместимого контейнера для представления древовидных структур данных позволяет создавать классы деревьев с заданными свойствами.

4) Технология построения программных генераторов обеспечивает снижение сроков разработки генераторов и объема их программного кода.

Практическая ценность. Результаты диссертационной работы позволяют:

1) Исследовать алгоритмы генерации и нумерации комбинаторных множеств на основе деревьев И/ИЛИ в разработанной системе построения генераторов.

2) Разрабатывать генераторы комбинаторных множеств на основе библиотеки комбинаторных алгоритмов и языка построения генераторов GIL для различных предметных областей.

3) Применять разработанные модели генераторов на основе грамматик, представленных в виде дерева И/ИЛИ, для построения генераторов тестовых заданий систем контроля знаний и генераторов тестовых данных систем тестирования программного обеспечения.

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

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

Внедрение результатов.

Разработанное программное обеспечение внедрено в технологии дистанционного обучения Томского политехнического университета, Томского государственного университета систем управления и радиоэлектроники, Новосибирского государственного университета экономики и управления, применяется для разработки и тестирования программного обеспечения компаниями «Эль Софт» и «Томск Софт».

Апробация результатов.

Результаты исследований представлены в 12 публикациях различного уровня. Две из них опубликованы в рекомендованных ВАК изданиях. Представлено 15 докладов на различных научно-методических и научно-практических конференциях, среди которых:

1) Международная научно-методическая конференция «Современное образование: проблемы и перспективы в условиях перехода к новой концепции образования», Томск (2009);

2) Международная научная конференция «Космос, астрономия и программирование» (Лавровские чтения), Санкт-Петербург (2008);

3) Международная научно-методическая конференция «Современное образование: вызовам времени — новые подходы», Томск (2008);

4) VII межрегиональная конференция «Информационные технологии и решения для «Электронной России», Ханты-Мансийск (2008);

5) XIV Всероссийская научно-методическая конференция I

Телематика'2007»; Санкт-Петербург (2007);

6) XI Международная научно-практическая конференция студентов и молодых ученых «Современные техника и технологии», Томск (2005);

7) Всероссийская научно-техническая конференция студентов и молодых ученых «Научная сессия ТУСУР-2005», Томск (2005).

Работа выполнена в рамках ведомственной научной программы «Развитие научного потенциала высшей школы», подпрограммы 1 «Фундаментальные исследования», фундаментальных НИР, выполняемых в Томском государственном университете систем управления: 1.3.09 «Создание и исследование методов и алгоритмов комбинаторной генерации».

Личный вклад.

Основные результаты работы, алгоритмы автоматизации процесса построения генераторов на основе деревьев И/ИЛИ, язык построения генераторов GIL и его интерпретатор, библиотека комбинаторных алгоритмов, примеры практического применения системы построения генераторов комбинаторных множеств получены лично автором. Структура и объем диссертации.

Работа состоит из введения, четырех глав, заключения, списка литературы из 67 наименований, одного приложения. Общий объем диссертации 105 страниц, в том числе 23 рисунка, 4 таблицы.

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

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

Заключение

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

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

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

Разработанное программное обеспечение реализует метод построения алгоритмов генерации и нумерации комбинаторных множеств на основе деревьев И/ИЛИ и позволяет строить программные генераторы для широкого круга предметных областей. Разработанная технология построения генераторов апробирована на широком круге задач и показала свою эффективность.

Список литературы диссертационного исследования кандидат технических наук Титков, Антон Вячеславович, 2010 год

1. Knuth, D. Generating All Trees; History of Combinationatorial Generation / Knuth, D. 2006. - 120 pp.

2. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. М.: Мир, 1980. - 496 с.

3. Ruskey, F. Combinatorial generation / F. Ruskey. Working version of book in progress.

4. Kreher, D. L. Combinatorial algorithms: Generation, Enumeration and Search / D. L. Kreher, D. S. Stinson. CRC Press, 1998. - 329 pp.

5. Barcucci, E. Eco: a methodology for the enumeration of combinatorial objects / E. Barcucci, A. Lungo, E. Pergola, R. Pinzani // Journal of Difference Equations and Applications. 1999. - no. 5. - Pp. 435-490.

6. Flajolet, P. A calculus for the random generation of combinatorial strctures / P. Flajolet, P. Zimmerman, B. Van Cutsem // Theor. Comput. Sci. 1994.- Vol. 132, no. 1-2. Pp. 1-35.

7. Martinez, C. A generic approach for the unranking of labeled combinatorial classes / C. Martinez, X. Molinero // Random Struct. Algorithms. 2001. -Vol. 19, no. 3-4. - Pp. 472-497.

8. Кручинин, В. В. Методы построения алгоритмов генерации и нумерации комбинаторных объектов на основе деревьев И/ИЛИ. / В. В. Кручинин — Томск: «В-Спектр», 2007. 200 с.

9. Pemmaraju, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica / S. Pemmaraju, S. Skiena — Cambridge University Press, 2003. 494 pp.

10. Thiery, N. M. MuPAD-Combinat Электронный ресурс./ N. M. Thiery- Режим доступа : http://mupad-combinat.sourceforge.net/.

11. Кнут Д. Искусство .программирования для ЭВМ. Т. 2. Получисленные алгоритмы / ред. пер. К.И. Бабенко; пер. Г.П. Бабенко, Э.Г. Белага, Л. В. Майоров. М.: Мир, 1977. - 723 с.

12. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. Спб.: Питер, 2000. - 304 с.

13. Белоглазов И.Н. Корреляционно-экстремальные системы./ Белоглазов И.Н., Тарасенко В.П. М.: Сов. радио, 1974. 392 с.

14. Фу К. Робототехника./ Фу К., Гонсалес Р., Ли К. М.: Мир, 1989. -621 с.

15. Амосов Н.М Нейрокомпьютеры и интеллектуальные роботы./ Амосов Н.М., Байрон Т.Н., Гольцев А.Д. Киев: Наук, думка, 1991. -271 с.

16. Горбань А.Н. Обучение нейронных сетей. М.: С.П. «ПараГраф», 1990.-56 с.

17. Липский, В. Комбинаторика для программистов / В. Липский. М.: Мир, 1988.-213 с.

18. Generating functions of generating trees / С. Banderier, M. Bousquet-Melou, A. Denise et al. // Discrete Mathematics. 2002. - March. - Vol. 246.

19. On the generation and enumeration of some classes of convex polyominoes / A. Del Lungo, E. Duchi, A. Frosini, S. Rinaldi // The Electronic Journal of Combinatorics. 2004. - Т. 11, № 1. - C. 46.

20. Martinez, C. A generic approach for the unranking of labeled combinatorial classes / C. Martinez, X. Molinero // Random Struct. Algorithms. 2001. - Vol. 19, no. 3-4. - Pp. 472-497.

21. Molinero, X. Ordered Generation of Classes of Combinatorial Structures: Ph.D. thesis / University Politecnical of Catalunya. -http://www.lsi.upc.edu/~molinero/homepublications.html. P. 181.

22. Рябко, Б. Я. Быстрая нумерация комбинаторных объектов / Б. Я. Рябко // Дискрет, матем. 1998. - Т. 10, № 2. - С. 101-119.

23. Nijenhuis, A. Combinatorial Algorithms / A. Nijenhuis, H.S. Wilf. -New York : Academic Press, Inc., 1978. 302 p.

24. Ruskey, F. The Combinatorial Object Server Электронный ресурс. / F. Ruskey. Режим доступа : http://www.theory.csc.uvic.ca/cos.

25. GNU Scientific Library Электронный ресурс. / Режим доступа : http://www.gnu.org/software/gsl/.

26. Бочканов, С. ALGLIB Электронный ресурс. / S. Petit Режим доступа: http://alglib.sources.ru/.

27. Плаугер, П. STL стандартная библиотека шаблонов С++ / П. Плаугер, А. Степанов. - Спб.: БХВ-Петербург, 2004. - 656 с.

28. Karlsson, В. Beyond the С++ Standard Library: An Introduction to Boost / B. Karlsson Addison Wesley Professional, 2005. - 432 pp.

29. Thiery, N. M. MuPAD-Combinat Электронный ресурс./ N. M. Thiery Режим доступа : http://mupad-cornbinat.sourccforge.net/.

30. Slagle, J. A heuristic program that solves symbolic integration problems in freshman calculus / J. Slagle // J. ACM. 1963. - Vol. 10, no. 4. - Pp. 507-520.

31. Нильсон, H. Принципы искусственного интеллекта > H. Нильсон. -М.: Радио и связь, 1985.

32. Хант, Э. Искусственный интеллект / Э. Хант. М.: Мир, 1978. - 558 с.

33. Попов, Э. В. Общение с ЭВМ на естественном языке / Э. В. Попов. -М.: Наука, 1986.

34. Ефимов, Е.И. Решатели интеллектуальных задач / Е.И. Ефимов. -М.: Наука, 1982.-С. 320.

35. Братко, И. Программирование на языке Пролог для искусственного интеллекта / И. Братко. М.: Мир, 1990. - С. 560.

36. Кручинин, В.В. Модель предметной области моделирования КЭНС и ее реализация / В.В. Кручинин, В.В. Одиноков // Корреляцинно-экстремальные системы и их проектирование. Томск: Томск.гос.ун-та, 1988.-№ 10.-С. 90-94.

37. Кручинин, В.В. Использование деревьев И/ИЛИ для генерации вопросов и задач / В.В. Кручинин // Вестник ТГУ. 2004. - № 284, серия «Математика. Кибернетика. Информатика». - С. 185-189.

38. Верещагин, Н.К. Начала теории множеств / Н.К. Верещагин, А. Шень. М.: МЦНМО, 2002. - 128 с.

39. Барендрегт, X. Ламбда-исчисление. Его синтаксис и семантика. / X. Барендрегт. -М.: Мир, 1985.-606 с.

40. Вольфенгаген, В.Э. Методы и средства вычислений с объектами. Аппликативные вычислительные системы / В.Э. Вольфенгаген. М.: «Центр ЮрИнфоР», 2004. - 788 с.

41. Филд, А. Функциональное программирование / А. Филд, П. Харрисон. М.: Мир, 1993. - 637 с.

42. Цаленко, М.Ш. Основы теории категорий. / М.Ш. Цаленко, Е.Г. Шульгейфер. М.: Наука, 1974. - 256 с.

43. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Д. Ульман М.: «Вильяме», 2002. - С. 528.

44. Ландо, С. К. Лекции о производящих функциях. / С. К. Ландо. М.: МЦНМО, 2004. - 144 с.

45. Братчиков, И.Л. Синтаксис языков программирования. / И.Л. Братчиков. М.: Наука, 1975. - 232 с.

46. Дарахвелидзе, П. Г. Delphi среда визуального программирования / П. Г. Дарахвелидзе, Е. П. Марков. - СПб.: BHV, 1996. - 352 с.

47. Вандевурд, Д. Шаблоны С++. Справочник разработчика / Д. Вандевурд, Н.М. Джосаттис. М.: Вильяме, 2003. - 544 с.

48. Касьянов, В.Н. Методы построения трансляторов. / В.Н. Касьянов, И.В. Поттосин. Новосибирск: Наука, 1986. - 344 с.

49. Страуструп, Б. Язык программирования С++. Специальное издание / Б. Страуструп. СПб.: Бином, 2007. - 1099 с.

50. Kapur, D. Operators and Algebraic Structures. Электронный ресурс./ D. Kapur, D.R. Musser, A.A. Stepanov — Режим доступа : http://www.stepanovpapers.com.

51. Stepanov, A. The Standard Template Library Электронный ресурс./ A. Stepanov, M. Lee — Режим доступа : http://www.hpl.hp.com/techreports/95/HPL-95-l l.html.

52. Александреску, А. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования. / А.Александреску С. П.: Вильяме, 2008. - 336 с.

53. Мейерс, С. Эффективное использование STL / С. Мейерс. — СПб.: Питер, 2002. 224 с.

54. Wilson, М. Extended STL, Volume 1: Collections and Iterators. / M. Wilson. Addison Wesley US, 2007 - 624 pp.

55. Musser, D. The STL Tutorial and Reference Guide: С++ Programming with the Standard Template Library / D. Musser. Addison Wesley US, 2007. - 624 pp.

56. Кручинин, В.В. Подход к созданию баз данных, основанный на алгоритмах генерации и идентификации кортежей. / В.В. Кручинин, А.В. Титков. // Известия Томского политехнического университета. — 2006. Т. 309. - № 8. - С. 28-32.

57. Peeters, К. STL-like С++ tree class Электронный ресурс. / К. Peeters Режим доступа : http://www.aci.mpg.de/~peekas/tree/.

58. Rushton, A. STL+ Электронный ресурс. / A. Rushton Режим доступа: http://st1plus.sourceforge.net/.

59. Haas, М. TCL Электронный ресурс. / М. Haas Режим доступа : http://www.datasoftsolutions.net/.

60. Scharli, N. Traits: Composable Units of Behavior / N. Scharli, S. Ducasse, O. Nierstrasz, A. Black. // In Proceedings of European Conference on Object-Oriented Programming (ЕСООР'ОЗ), LNCS 2743, Springer Verlag, 2003. p.248-274.

61. Coplien, J. O. Curiously recurring template patterns / С++ Report, v.7 n.2, p:24-27.

62. Хювенен, Э. Мир Лиспа. Том 1. / Э. Хювенен, Й. Сеппянен. М.: Мир, 1990. -458 с.

63. Титков, А.В. Язык описания генераторов комбинаторных множеств / А.В. Титков, В.В. Кручинин // Известия Томского политехнического университета. 2008. - Т. 312. - № 5. - С. 89-93.

64. Душкин, Р. В. Функциональное программирование на языке Haskell. / Р. В. Душкин. М.: ДМК Пресс, 2006. - С. 608.

65. Фокс, Дж. Программное обеспечение и его разработка. / Дж. Фокс. М.: Мир, 1985.-368 с.

66. Кручинин, В.В. Генерация тестовых вопросов и заданий по информатике // Информатика и образование. 2005. - № 2. - С. 87-93.