автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Система построения генераторов комбинаторных множеств на основе деревьев и/или

На правах рукописи

Титков Антон Вячеславович

003493845

СИСТЕМА ПОСТРОЕНИЯ ГЕНЕРАТОРОВ КОМБИНАТОРНЫХ МНОЖЕСТВ НА ОСНОВЕ ДЕРЕВЬЕВ И/ИЛИ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

Томск-2010

1 8 МАР 2010

003493845

Работа выполнена в Томском государственном университете систем управления и радиоэлектроники (ТУСУР)

Научный руководитель

кандидат технических наук, доцент Кручинин Владимир Викторович

Официальные оппоненты

доктор технических наук, профессор Погребной Владимир Кириллович

кандидат технических наук, доцент Осипов Александр Леонидович

Ведущая организация

Новосибирский государственный технический университет

Защита состоится «14» апреля 2010 г. в 15.00 на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 при ГОУ ВПО «Томский политехнический университет» по адресу: 634034, г. Томск, ул. Советская, 84/3, институт «Кибернетический центр».

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Томский политехнический университет» по адресу: г. Томск, ул. Белинского, 55.

Автореферат разослан «10» марта 2010 г.

Ученый секретарь совета по защите докторских и кандидатских

диссертаций Д 212.269.06, к.т.н., доцент

Сонъкин М. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Темп развития инструментальных средств построения генераторов не соответствует теоретическим достижениям, полученным в области комбинаторной генерации. На сегодняшний день создано большое количество библиотек алгоритмов комбинаторной генерации, реализованных на различных языках программирования. Однако данные библиотеки не обеспечивают системного подхода при построении генераторов, т.к. обладают ограниченным функционалом и не используют главного преимущества универсальных методов построения алгоритмов генерации — единого подхода к построению программных генераторов. Для некоторых универсальных методов существуют программные наработки в виде специализированных библиотек для пакетов математического моделирования (СотЫпаЮпса для МаАетайса, МиРАЭ-СотЫпа1 для МиРАВ). Использование таких средств в прикладном программном обеспечении затруднено в связи с тем, что данные библиотеки разработаны в первую очередь для научных исследований. Пакеты математического моделирования, на которых основаны данные библиотеки, не предназначены для использования в разработке программного обеспечения (ПО), что является серьезным недостатком, т.к. генераторы обычно используются как часть программных комплексов и систем. Таким образом, актуальной является задача разработки программных систем построения

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

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

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

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

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

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

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 Всероссийская научно-методическая конференция «Телематика'2007», Санкт-Петербург (2007);

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

■ позволять осуществлять последовательную генерацию элементов комбинаторного множества;

■ позволять осуществлять нумерацию всех элементов комбинаторного множества;

■ позволять осуществлять генерацию элементов комбинаторного множества по номеру;

" позволять осуществлять случайную генерацию элементов комбинаторного множества;

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

■ обладать богатым функционалом, ориентированным на разработку программных генераторов;

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

В представленном обзоре инструментальных средств построения генераторов ни одна из систем не удовлетворяет всем требованиям.

Вторая глава посвящена анализу метода построения алгоритмов генерации и нумерации, основанного на деревьях И/ИЛИ, с целью формализовать процесс построения деревьев И/ИЛИ, что необходимо для автоматизации процесса построения генераторов на основе этого метода.

Деревом И/ИЛИ называется дерево, состоящее из узлов 2-х типов: И-узел и ИЛИ-узел. На рисунке 1 изображено схематическое представление узлов дерева И/ИЛИ.

Рисунок 1. Схематическое представление узлов дерева И/ИЛИ

Вариантом дерева И/ИЛИ называется дерево, полученное из данного путём отсечения всех дуг, кроме одной, у ИЛИ-узлов. Корнем варианта будет корень исходного дерева. На рисунке 2 показано дерево И/ИЛИ и все его варианты.

Рисунок 2. Дерево И/ИЛИ и все его варианты

Мощностью дерева И/ИЛИ называется количество вариантов, которое оно содержит.

Автор метода, Кручинин В.В., в своей работе показал, что между вариантом дерева И/ИЛИ и элементом кодируемого множества существует однозначное биективное отображение.

Анализ деревьев И/ИЛИ как алгебраической структуры показал, что на деревьях И/ИЛИ определены теоретико-множественные операции \ Т\, I), П, х. Действительно, между вариантом дерева И/ИЛИ и элементом множества есть биективная связь:

А ТА, где ТА - дерево И/ИЛИ для множества А;

В <-► ТВ, где ТВ - дерево И/ИЛИ для множества В;

а <-> м>ТА, где ас- Л, мТЛ еТА - множество вариантов дерева ТА;

Ъ <-> у/ТВ, где Ь е В, \vTfi е ТВ - множество вариантов дерева ТВ,

следовательно,

С = АорВ,С*-+ТС, если ТС = ТА ор ТВ = и>7Х ор у/ТВ, где ор - бинарная операция.

Например, для операции объединения можно записать:

С= Л11 В, ТСС, где ТС = ТА(]ТВ = м>ТА\}кТВ.

Таким образом, результатом объединения двух деревьев И/ИЛИ является дерево И/ИЛИ, вариантами которого будет объединение вариантов двух

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

Приведенные на рисунке 3 операции возможны только в том случае, если структура деревьев имеет идентичную структуру. При несовпадении структур деревьев произвести операции над ними таким способом невозможно. Анализ деревьев И/ИЛИ показал, что можно производить эквивалентные преобразования деревьев И/ИЛИ путем добавления и удаления узлов таким образом, чтобы не менялась мощность дерева. Поэтому операцию объединения предлагается осуществлять ИЛИ-узлом, а операцию декартового произведения И-узлом, сыновьями которых становятся деревья операнды (рисунок 4). Такие

or and

операции будем называть ИЛИ-объединением (U) и И-произведением ( х ).

Для формализации процесса построения деревьев И/ИЛИ предлагается использовать формальную систему лямбда-исчисления. Использование лямбда-исчисления для формализации процесса построения деревьев И/ИЛИ дает возможность применять для автоматизации процесса построения генераторов

Рисунок 3. Объединение и разность двух деревьев И/ИЛИ

Рисунок 4. ИЛИ-объединение и И-произведение деревьев И/ИЛИ

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

В.В. Кручинин для построения деревьев И/ИЛИ, заданных выражениями, вводит операции композиции и рекурсивной композиции деревьев И/ИЛИ. Композиция S, определяется как построение дерева D3 путем замены листа /¡б£>, на корень дерева £>2: D3=SXD„D2). Применяя каррирование и /?-редукцию лямбда-исчисления, операцию композиции деревьев И/ИЛИ можно записать следующим образом:

Лх. Лу. (Лг. х)у,

где х - выражение построения дерева И/ИЛИ, свободно содержащее z; у — выражение построения дерева И/ИЛИ, которое требуется подставить в выражение х вместо переменной z.

Для выражения D} = S,(D„D2) дерево D, является х, D2-у, /, — переменной

z:

.?,(£>, ,D2) = (Лх. Лу. (Л z. х) у) D, D21, Любая алгебраическая операция на деревьях И/ИЛИ записывается в виде:

Dj op Di = (Лх. Лу. хору) Di D2 Операция рекурсивной композиции выражается через Y-комбинатор: Y= Л/. (Лх./(хх)) (Лх./(хх)) S = (Лх. Лу. (Лг. х)у) Sn= Л/тп. (iszero т—*0) |/(т-1) п Sr = YSn

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

or and

И/ИЛИ и все операции в выражении имеют отображения в алгебре {Т, U, х ,

tree or and

- , R}, где Г - дерево И/ИЛИ, U - операция ИЛИ-объединения, х - операция

tree

И-произведения, - — операция удаления ветви дерева И/ИЛИ, R - оператор рекурсии.

Третья глава посвящена разработке системы построения генераторов комбинаторных множеств.

Процесс построения генераторов комбинаторных множеств на основе деревьев И/ИЛИ можно разделить на 3 части:

1) реализация обобщённых алгоритмов деревьев И/ИЛИ (нумерации и генерации вариантов);

2) реализация алгоритма построения дерева И/ИЛИ; .

3) получение варианта дерева И/ИЛИ по объекту в алгоритмах нумерации и получение объекта по варианту в алгоритмах генерации.

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

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

Рисунок 5. Структурная схема системы построения генераторов комбинаторных множеств

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

Библиотека комбинаторных алгоритмов является расширением библиотеки STL и реализована средствами обобщенного программирования, что позволяет применять её для различных типов данных.

Библиотека комбинаторных алгоритмов состоит из следующих модулей:

1) Библиотеки алгоритмов комбинаторной генерации, включающей функции для нахождения основных комбинаторных величин (вычисление факториала, подсчет количества сочетаний, перестановок

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

2) Библиотеки деревьев, включающей реализацию контейнеров «дерево», «дерево И/ИЛИ» и алгоритмы на деревьях И/ИЛИ.

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

Библиотека STL предоставляет все возможные контейнеры, кроме деревьев. Это связано с тем, что при решении различных задач к деревьям предъявляются разнообразные требования и выработать обобщенный шаблон этой структуры данных достаточно сложно. Несмотря на это, существуют несколько реализаций контейнеров деревьев, таких как библиотека Kasper Peeters, библиотека STL+ Andy Rushton, библиотека TCL, Mitchel Haas. Был произведен анализ этих библиотек по следующим критериям:

■ универсальность интерфейсов классов;

" совместимость с STL;

■ возможность расширения и модификации;

■ возможность написания источников данных для узлов дерева;

■ возможность наследования от базового класса дерева различных реализаций деревьев.

Всем требованиям не удовлетворяет ни одна из рассмотренных библиотек.

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

1) Логика отдельных модулей контейнера дерева выделяется в отдельные сущности с заданными интерфейсами:

а) Узел дерева. Осуществляет логику хранения данных узла и предоставляет доступ к ним остальным классам библиотеки.

б) Итераторы. Предоставляют доступ к данным узла дерева и позволяют осуществлять обход узлов дерева.

в) Класс-контейнер. Реализует логику работы с древовидными структурами: вставка, удаление, замена узлов; доступ к итераторам дерева.

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

2) Для реализации дерева с заданными свойствами необходимо реализовать только те компоненты, которые отвечают за эти свойства.

В библиотеке деревьев реализованы контейнеры «n-арное дерево», «бинарное дерево», «дерево И/ИЛИ».

Для описания процесса построения деревьев И/ИЛИ разработан оригинальный язык GIL - Generation and Identification Language (язык

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

Для записи деревьев И/ИЛИ в языке GIL используется скобочная нотация: круглыми скобками обозначаются И-узлы, фигурными — ИЛИ-узлы, узлы без скобок являются листами: root (alpha {a, b}, digit {1, 2, 3,4,5}).

Операция объединения и декартового произведения деревьев И/ИЛИ в языке GIL моделируются операциями ИЛИ-объединения и И-произведения. Введены операции добавления, удаления и поиска узла/ветви, причем операция поиска рассматривается как операция поиска по образцу (pattern matching).

Все выражения GIL делятся на 2 категории: простые выражения (описание дерева И/ИЛИ) и правила преобразования деревьев И/ИЛИ. Операции над деревом записываются в квадратных скобках после выражения, описывающего дерево. Если требуется произвести несколько операций, то они записываются через запятую. Образец для поиска является шаблоном дерева И/ИЛИ или его ветви, по которому ведётся поиск подходящего выражения. В образце для поиска можно задать как строгое, так и нестрогое соответствие узлов дерева:

root (1{а, Ь}, 2 {с, d}, 1{а, b})[- l{c@ch}]; - выражение описывает дерево И/ИЛИ, в котором удаляется ветвь, соответствующая образцу 1 {c@ch}, где c@ch означает любой список сыновей.

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

pow(@x, @у) = x*pow(x, у-1);

pow(@x, 1) = х;

find_pow(pow(2, 4), pow{x, 2});

Результатом выполнения будет дерево И/ИЛИ

find_pow(16, pow{x, 2});

Для разграничения программного кода модулей в GIL используется механизм пространства имён. Интерпретатор языка выполняет только простые выражения из глобального пространства имён в порядке их объявления.

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

Интерпретатор имеет возможность расширения путем подключения внешних функций, реализованных на языке программирования С++. Таким способом реализованы алгоритмы генерации и нумерации вариантов дерева И/ИЛИ (правила var (@ tree, ngnum) и num(@tree, Svar)).

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

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

1) Если имеется конечное множество, то оно представляется как ИЛИ-узел, листьями которого являются элементы этого множества.

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

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

б) в полученном выражении операция объединения заменяется операцией ИЛИ-объединения;

в) в полученном выражении операция декартового произведения заменяется операцией И-призведения;

г) другие операции анализируются на предмет возможности реализации их через операции ИЛИ-объединения, И-произведения, добавления и удаления узлов;

д) определяются правила построения дерева И/ИЛИ для каждого операнда выражения;

е) если в выражении присутствует рекурсия, то задаются условия её ограничения.

3) Если требуется произвести объединение множеств, то оно производится при помощи операции ИЛИ-объединения.

4) Если требуется произвести декартово произведение множеств, то оно производится при помощи операции И-произведения.

5) Построенное дерево И/ИЛИ и его варианты анализируются для построения алгоритма получения элемента исходного множества.

6) Построенное дерево И/ИЛИ и элементы исходного множества анализируются для построения алгоритма получения варианта дерева И/ИЛИ по элементу множества.

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

Язык GIL прекрасно подходит для исследования алгоритмов комбинаторной генерации. С его помощью можно строить дерево И/ИЛИ для функции мощности множества, анализировать варианты дерева для построения генератора нужного комбинаторного множества, проверить реализацию генератора на GIL, при необходимости перенести полученный алгоритм на какой-либо из императивных языков программирования. Например, генерация сочетаний в виде битовой последовательности на основе рекурсивной формулы подсчета количества сочетаний С" = + C™~¡ осуществляется следующей

программной на языке GIL:

С (n@m, n@n) = {L(C(m, n-1) ) , R(C(m-l, n-1))}; C(0, n@m) = ; С(n@m, n@m) = ;

comb(n@m,_ n@n, n@num) = f lat (var (C (m, n) , num) [ L(@ch) ~> (0, ch) , R(@ch) —> (1, ch), C(@mm, @mm)->repeat(1, mm), C(0, @nn)->repeat(0, nn)

]) ;

Результатом выполнения comb (2, 4, 5) будет 1100. Показано применение языка GIL для генерации тестовых заданий по различным дисциплинам, таким как программирование, высшая математика. Рассмотрим пример генерации тестового задания по высшей математике (вычисление производной выражения), использующего возможности символьных вычислений языка GIL. Шаблон вопроса:

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

grammar -> Е (орТ | opD) func Е -> Т I Т орТ Т орТ -> + I -Т -> D I D opD D opD. -> * I /

D -> variable | func | number variable -> 'x'

number -> -3 I -2 | -1 I 1 I 2 | 3 func -> pow I In

pow -> 'pow('variable', 'number')' I 'pow(e, 'variable')' In -> 4n(' variable ') '

Студент должен вычислить производную для сгенерированного выражения. В ответ требуется ввести значение производной в точке а, a е (~5;5),аф0.

Генератор выражений на GIL для заданной грамматики будет следующим:

grammar = (Е, {орТ, opD}, func); Е = (Т, (Т, орТ, ТП; орТ ={' + ', '- ' ); Т = {D, (D, opD, D) } ; opD ={•*', •/'};

D = {variable, func, number}; variable = {x}; number = range{-3, 3}[-0]; func = {pow, In};

pow = {pow(variable, number), pow(e, variable)}; In = In(variable); a = range{-5, 6}[-0]; test = (grammar, a);

Проверку ответа осуществляет следующий код: answer((Sexp, Sa)) =

calculate.calc(differential.diff(exp), 'x', a); test_check(n@num, nßanswer) =

eq(answer(var(test, num)), answer); Мощность описанного генератора равна 138,532,800. Это гарантирует получение индивидуального задания для каждого студента. Ответ проверяется правилом answer, которому в качестве параметра передается вариант дерева

test. Ниже приведена • программа на GIL для дифференцирования математических выражений:

namespace differential {

diff((cgchilds)) = diff(Childs); diff(pow(e, n@x) ) = pow(e, x) ; diff(pow(s@x, n@y) ) = (y, '*', pow.(x, y-1) ) ; diff(ln(s@x)) = (1, '/', x);

diff(@u, '+', @v) = ((diff(u), '+', diff(v))); diff(@u, '*', @v) = ((diff (u) , '*', v), ' + ', (u, '*', diff(v)));

diff(@u, '/', @v) = (((diff(u), '*', v), '-', (u, '*', diff (v) ) ), '/', pow(v, 2)); diff(ls@x) = 1; diff(n@x) = 0;

diff (tg (@u) ) = ((1, V, cos2 (u) ) , '*', diff(u)); diff (pow (e, @u)) = (pow (e, u) , '*', diff(u));

}

Важным этапом разработки программного обеспечения является этап тестирования. Ни один серьезный программный продукт не обходится без него. Система построения генераторов комбинаторных множеств может быть успешно применена для тестирования ПО.

Построим генератор тестовых данных для конвертора математических формул. Конвертор преобразует формулы из формата MathML в TeX и обратно. Тестирование заключается в следующем:

1) генерируется выражение языка MathML;

2) полученное выражение конвертируется в TeX;

3) конвертированное выражение преобразуется конвертором обратно в MathML;

4) если исходное выражение не равно результату конвертирования, значит, конвертирование происходит неправильно.

Код генератора может быть следующим:

mathml = 'mathml'{mrow, mfrac};

operation = 'rrio'{'~\ ' + \ '*', '/'};

token = {mi, mn, func, msub, msup};

identificator = {'x', 'у'};

number = {10, 1234};

mi = 'mi'(identificator) ;

mn = 'mn'(number);

mnl = 'mn'(100);

msub = 'msub'(mi, mnl);

msup = 'msup'(mi, mnl);

func = 'mrow1(funcname, 'mo'('SApplyFunction;'), 'mrow'('mo'('('), {mi, mn}, 'mo'(')'))); funcname = 'mi'{'sin', 'In'}; mrow = {mrowl, mrow2};

mrowl = 'mrow'(token, operation, token); mrow2 = 'mrow'(token, operation, func); mfrac = 'mfrac'(mrow, mrow2);

Данный генератор строит дерево И/ИЛИ для грамматики, описывающей выражения на языке разметки математических формул MathML. Мощность

описанного генератора равна 787,968. Каждый вариант построенного дерева подается на вход конвертера для проверки корректности его работы.

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

В Томском межвузовском центре дистанционного образования (ТМЦДО) технология тестирования знаний обучающихся, основанная на использовании генераторов тестовых заданий, действует с 2003 года. За это время было создано большое количество генераторов тестовых заданий по различным дисциплинам. Генераторы создавались прямым кодированием на языке программирования С++ без использования специализированных библиотек. С целью экспериментальной проверки эффективности применения системы построения генераторов было решено реализовать несколько уже созданных на языке программирования С++ генераторов тестовых заданий с помощью системы построения генераторов.

Условия эксперимента были следующие:

1) специалист, реализовавший генератор на языке С++, реализовывал этот же генератор в системе построения генераторов, таким образом квалификация специалиста выполняющего работу оставалась неизменной;

2) генераторы выбирались по количеству шаблонов вопросов от 30 до 150.

Результаты эксперимента показали, что время разработки генераторов тестовых заданий уменьшилось в 2 раза, объем программного кода генераторов также сократился в 2 раза (рисунки 6, 7). Эксплуатация разработанных с помощью системы генераторов показала, что объем ошибок по сравнению с реализацией генераторов на языке программирования С++ уменьшился на 50%.

g 7000

S бооо

о 4000 ш 3000 g 2000 s 1000

S о

- - - С++

— — Система построения _генераторов_

30 60 90 120 150

Количество вопросов

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

ИЗ m-ns 5

CL g-

cs О

10 k

о 1С

_ О.

К О)

S X

a> о

Q. I-Ш

- С++

- Система построения генераторов_

30

60

90

120

150

Количество вопросов

Рисунок 7. Зависимость времени разработки генератора от количества шаблонов вопросов

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

В заключении сформулированы основные результаты диссертационной работы:

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

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

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

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

5) Разработанная технология построения генераторов апробирована на широком круге задач и показала свою эффективность.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2) Титков, A.B. Подход к созданию баз данных, основанный на алгоритмах генерации и идентификации кортежей. / В.В. Кручинин, A.B. Титков. // Известия Томского политехнического университета. —

2006. - Т. 309. - № 8. - С. 28-32.

3) Титков, A.B. Генерация тестовых заданий на основе грамматик в системе построения генераторов на деревьях И/ИЛИ. / A.B. Титков // Материалы международной научно-методической конференции «Современное образование». - 2010. - С. 163-164.

4) Титков, A.B. Применение системы программирования GIL для генерации тестовых заданий. / A.B. Титков, В.В. Кручинин // Материалы международной научно-методической конференции «Современное образование». - 2009. - С. 178-179.

5) Титков, A.B. Реализация библиотеки шаблонов алгоритмов комбинаторной генерации средствами STL / A.B. Титков // Материалы международной научной конференции «Космос, астрономия и программирование». - 2008. - С. 309-311.

6) Титков, A.B. Разработка алгоритмов параллельной генерации комбинаторных множеств / В.В. Кручинин, A.B. Титков // Труды XV Всероссийской научно-методической конференции «Телематика-2008». -2008. -С. 119.

7) Титков, A.B. Система курсового опНпе-обучения ТМЦДО / A.B. Титков // Труды XIV Всероссийской научно-методической конференции «Телематика-2007». — 2007. — Т. 1 — С. 228.

8) Титков, A.B. Технология проведения экзаменационных сессий с использованием сети Интернет / A.B. Титков, В.В. Кручинин // Доклады Международной научно-практической конференции "Электронные средства и системы управления". - Томск: Издательство Института оптики атмосферы СО РАН. - 2005. - С. 241— 242.

9) Титков, A.B. Компьютерные учебные программы томского межвузовского центра дистанционного образования / В.В. Кручинин, A.B. Титков, М.А. Песков // Дистанционное и виртуальное обучение. -

2007.-№5.-С. 35-37.

10) Титков, A.B. Система опНпе-обучения ТМЦДО / A.B. Титков // материалы отчетной конференции Томского межвузовского центра дистанционного образования. По итогам работы в 2006 г. - Томск : Томский межвузовский центр дистанционного образования. - 2007. -С. 58-63.

11) Титков, A.B. Электронный учебник «Информатика - I» / A.B. Титков, С.С. Свистунов, К.С. Балуева // Наука технологии инновации

часть 2 / Материалы всероссийской научной конференции молодых ученых. Новосибирск: Издательство НГТУ. - 2006. - С. 101-102.

12) Титков A.B. Мультимедийный компьютерный учебник «Программирование на языке С» / A.B. Титков, В.В. Кручинин, С.С. Свистунов, C.JI. Хомич, // Материалы всероссийской научной конференции молодых учёных. - Новосибирск: Издательство НГТУ. -2006.-С. 105-106.

Тираж 100. Заказ 193. Томский государственный университет систем управления и радиоэлектроники пр. Ленина, 40

ВВЕДЕНИЕ.

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 алгоритмами комбинаторной генерации и библиотекой деревьев, позволяющей создавать контейнеры деревьев с заданными свойствами.

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

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.