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

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

004612743

Кручинин Владимир Викторович

МЕТОДЫ, АЛГОРИТМЫ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ КОМБИНАТОРНОЙ ГЕНЕРАЦИИ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

1 8 НОЯ 201О

Томск - 2010

004612743

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

Научный консультант: д.т.н., профессор,

Шелупанов Александр Александрович.

Официальные оппоненты: д.т.н., профессор,

Костюк Юрий Леонидович д.т.н.,профессор, Рябко Борис Яковлевич, д.т.н. профессор, Марков Николай Григорьевич.

Ведущая организация: Московский государственный универси-

тет приборостроения и информатики

Защита состоится 24 ноября 2010 г. в 15 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 при Национальном исследовательском Томском политехническом университете, расположенном по адресу: Россия, 634050, г.Томск, проспект Ленина 30.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского Томского политехнического университета.

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

Ученый секретарь совета, к.т.н.

Сонькин Михаил Аркадьевич

Общая характеристика работы

Актуальность. Комбинаторная генерация - это научное направление, находящееся на стыке комбинаторики, информатики и программирования. Объектом исследования являются алгоритмы генерации и нумерации элементов комбинаторных множеств. Комбинаторное множество - это конечное множество, элементы которого имеют некоторую структуру и имеется процедура построения элементов этого множества. Примерами таких множеств являются перестановки, сочетания, размещения, композиции, разложения, разбиения, графы и деревья, выражения языков, заданных контекстно-свободными грамматиками и т.д. Исторический обзор развития этого направления дает Д. Кнут в 4 томе «Искусство программирования». Однако, классификация алгоритмов генерации и определения понятий здесь не приводятся. Такую классификацию приводит Ф. Раски в работе «Комбинаторная генерация». Он выделяет 4 класса алгоритмов генерации: последовательная генерация всех элементов комбинаторного множества; нумерация всех элементов комбинаторного множества; генерация элементов комбинаторного множества в соответствии с процессом нумерации; случайная генерация элемента комбинаторного множества (random selection). Алгоритмы последовательной генерации комбинаторных множеств наиболее изучены. Обобщенная схема их работы следующая: установка начального элемента комбинаторного множества; организация цикла, в котором производится вывод следующего элемента комбинаторного множества или его конструирование из данного. Этот процесс можно реализовать двумя способами. Первый способ предполагает реализацию процедуры генерации как контейнера, т.е. для всех элементов данного комбинаторного множества вызывается некоторая заданная процедура. Обычно такой механизм реализуется в виде процедуры под названием ForEach. Второй способ подразумевает реализацию процедур генерации First и Next. Процедура First обеспечивает установку начального элемента. Процедура Next генерирует следующий элемент. Нумерация рассматривается как процесс упорядочения множества комбинаторных объектов. Если некоторое комбинаторное множество упорядочено, то номер позиции некоторого элемента в этом упорядочении будет являться порядковым номером (rank). Соответствующий алгоритм или процедуру обычно называют Rank. Процесс генерации комбинаторного объекта (unranking) по его номеру (рангу) является обратным процессу нумерации. Соответствующий алгоритм или процедуру называют Generate. В некоторых случаях желательно наличие алгоритма генерации со случайным выбором (random selection), когда последовательность объектов не упорядочена или не требуется все комбинаторное множество. Методы и алгоритмы комбинаторной генерации приобретают важное научное и практическое значение в следующих отраслях: в программировании, в про-

Рис. 1. Основная схема алгоритмов генерации и нумерации элементов комбинаторных множеств

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

Generate : Nm —> Arn,

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

Rank : Ат —► Nm.

На рис. 1 показаны основные элементы и схема взаимодействия алгоритмов Generate и Rank. Алгоритм Generate на основании числа пит € Nm к некоторого описания D создает элемент а е Ат. Алгоритм Rank производит обратное действие на основании а S Ат и некоторого описания D, формирует номер пит € Nm.

Методы построения алгоритмов генерации и нумерации комбинаторных множеств самые разнообразные и зависят от конкретного рассматриваемого комбинаторного объекта. Следует отметить, что сравнительно недавно появились методы, претендующие на некоторую универсальность применения. Так, Э.Ренгольд, Ю.Нивергельт, Н.Део для генерации комбинаторных объектов предложили использовать метод, основанный на поиске с возвращением (backtracking), дальнейшее развитие этого метода предложено Д.Крехером и Д.Стинсоном в работе «Combinatorial Algorithm: Generation, Enumeration and Search». Однако во многих случаях этот метод используется только для последовательной генерации всех объектов.

Другим методом, претендующим на некоторую универсальность, является метод ECO (Enumeration Combinatorial Object), предложенный Баргутччи,

Дел Лунго, Пергола и Пинзани, в основе которого лежит использование следующих рекурсивных правил:

1) комбинаторные объекты размера п + 1 строятся из объекта n-го размера;

2) каждый объект п + 1 размера имеет одного родителя n-го размера.

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

Следует отметить также метод, предложенный Ф. Флажолетом, Б. Кат-семем и П. Циммераманом для построения алгоритмов генерации элементов комбинаторных множеств со случайным выбором, который был развит К. Мартинец и X. Мулинеро для построения алгоритмов последовательной генерации, нумерации и генерации по номеру. Этот метод базируется на построении соответствий между производящими функциями, описывающими мощности комбинаторных множеств и некоторыми операциями, определенными над этими множествами. Кроме известных операций над множествами + и х вводятся специальные операции Seq, Set, PSet, Circle. Например, операция Seq представляет собой следующее выражение:

Seq(A) = е + А + (АхА) + (АхАхА) + ...

Если множество А конечно для всех конечных множеств Seq(A), то можно задать алгоритмы комбинаторной генерации. Основные недостатки данного метода:

1. Невозможно воспользоваться методом для построения алгоритмов комбинаторной генерации, если нет производящей функции.

2. Если производящая функция имеется, то ее надо выразить в терминах операций {+, x,Seg, Set, Pset}, что является довольно сложной задачей.

3. Не учитывается рекурсивный характер комбинаторного множества.

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

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

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

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

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

Основные задачи:

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

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

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

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

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

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

7. Создать и внедрить прикладное программное обеспечение для:

- информационных систем, основанных на реляционных базах данных;

- систем идентификации и прослеживаемости изделий;

- систем построения и использования генераторов тестовых заданий;

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

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

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

1. Разработана новая методология построения алгоритмов комбинаторной генерации, основанная на применении деревьев И/ИЛИ.

2. Впервые получено:

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

курсивная функция алгебры {JV, +, х, 11}, вычисляющая мощность данного множества.

2) Если мощность комбинаторного множества задана в виде функции /(п) алгебры {Аг, +, х, /?}, то для такого множества можно однозначно построить алгоритм последовательной генерации и алгоритмы генерации элемента по номеру и нумерации элемента.

3. Для построения алгоритмов последовательной генерации элементов комбинаторных множеств разработан новый формализм в виде автомата, представляющего четверку {В, N, Ppirst, PNext}, где В- начальный магазинный символ, N- множество магазинных символов; правила Pt-lrst для операции First, правила Pyext для операции Next. Разработан алгоритм построения автомата по схеме рекурсивной композиции деревьев И/ИЛИ, получено выражение для определения временной сложности алгоритмов последовательной генерации.

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

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

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

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

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

2. Решение задач кодирования. Если для некоторого множества объектов строится дерево И/ИЛИ, то алгоритм Rank будет кодировать объект, а алгоритм Generate - декодировать.

3. Решение задач сжатия информации. Если для некоторого множества объектов построить дерево И/ИЛИ, то алгоритм Rank будет производить сжатие объекта, а алгоритм Generate - восстанавливать объект. Причем, если при передаче объектов по каналам связи само дерево И/ИЛИ не передавать (т.е. дерево И/ИЛИ имеется на стороне приемника и на стороне передатчика), то

можно получить уменьшение объемов передаваемой информации.

4. Решение задач тестирования. Если для множества тестовых примеров построить дерево И/ИЛИ, то можно, используя алгоритм Generate, строить тестовые выборки. Особенно это касается задач тестирования программ с некоторым входным проблемно-ориентированным языком.

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

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

7. Для реляционных баз данных:

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

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

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

1. Для любой рекурсивно-примитивной функции можно взаимно-однозначно поставить в соответствие схему рекурсивной композиции дерева терма.

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

1) алгоритм вычисления мощности данного множества;

2) алгоритм последовательной генерации элементов этого множества;

3) алгоритм генерации элемента множества по номеру;

4) алгоритм нумерации элементов этого множества;

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

3. Рекуррентные и закрытые формулы для числа разбиений и композиций натурального числа п с ограничениями на части А; ^ т. Выражения производящих функций, треугольник разбиений.

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

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

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

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

Внедрение. Основные результаты диссертационной работы внедрены и используются:

1. На ОАО ТПО «Контур», при создании системы идентификации и прослеживаемое™ изделий телекоммуникационной механики и узлов структурных кабельных систем.

2. На ЗАО НПФ «Сибнефтекарт», при создании и тиражировании:

- Автоматизированной системы управления технологическими процессами и безналичными расчетами на автозаправочных станциях и комплексах « Сибнефтекарт-АЗС ».

- Автоматизированной системы централизованного ведения и прогрузки на АЗС справочников товаров и контрагентов, приема, накопления и обработки сменных отчетов и протоколов с АЗС — «Сибнефтекарт-Офис».

- Программно-аппаратного комплекса эмиссии карт и учета транзакций процессингового центра «Сибнефтекарт-ПЦ».

3. На ООО НПФ «Информационные системы безопасности» при разработке архива удостоверяющего центра.

4. В дистанционной технологии обучения студентов: Томского государственного университета систем управления и радиоэлектроники по 38 специальностям, в Кемеровском технологическом институте пищевой промышленности по трем специальностям, в Югорском государственном университете по двум специальностям. Система проведения контрольных работ и экзаменов передана в отраслевой фонд алгоритмов и программ Министерства образования Российской Федерации (свидетельство регистрации №3524). Инструментальная система «Фея-3» передана в отраслевой фонд алгоритмов и программ Министерства образования Российской Федерации (свидетельство регистрации №3510). Пакет генераторов по дисциплине «Высшая математика» для проведения экзаменов передан в отраслевой фонд алгоритмов и программ Министерства образования Российской Федерации (свидетельство регистрации №3536).

5. В учебном процессе Томского университета систем управления и радиоэлектроники.

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

Апробация результатов диссертации. Основные результаты диссертации были доложены на международных, всесоюзных, всероссийских, региональных конференциях и семинарах. В том числе: на Международной конференции «Application of the Conversion Research Results for International

Cooperation, SIBCONVERS '99» Томск, 1999; на Международной конференции «Градоформирующие технологии XXI века», Москва, 2001; на второй Международной конференции «2-nd WBLE Conference» 2001, Lund University, Швеция; на Международной методической конференции «Новые информационные технологии в университетском образовании», Кемерово, 2002; на Всероссийской конференции «Современная образовательная среда», Москва, 2002; на Международной научно-методической конференции, Новосибирск, 2003; на Международной научно-методической конференции «Развитие системы образования в России XXI века», Красноярск, 2003; на Международном конгрессе «Информационные технологии в образовании», 2003; на Всероссийской конференции «Телематика», Санкт-Петербург, 2003; на III Всероссийской научно-практической конференции-выставки «Единая образовательная информационная среда: проблемы и пути развития», Омск, 2004; на Международной научно-методической конференции «Инновационные технологии организации обучения в техническом ВУЗе: на пути к новому качеству образования», Пенза, 2004. на Всероссийской научно-методической конференции «Телематика», Санкт-Петербург, 2007; на Международной конференции «Образование и виртуальность», Ялта, 2007; на Всероссийской конференции «Системы автоматизации в образовании, науке и производстве», Новокузнецк, 2007; на Всероссийской конференции «Телематика», Санкт-Петербург, 2008; на Международной научной конференции «Космос, астрономия и про-граммирование[Лавровские чтения]»,Санкт-Петербург, 2008; на 9 Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография», Омск, 2009; на городском алгебраическом семинаре Сибирского федерального университета, Красноярск, 2010.

Публикации. Результаты диссертационной работы опубликованы в 104 научных работах, в том числе в четырех монографиях, в пяти учебных пособиях и в 17 статьях журналов, рекомендованных ВАК РФ для опубликования научных результатов диссертаций на соискание ученой степени доктора наук.

Структура и объем работы. Диссертация состоит из введения, 6 глав, заключения, списка литературы, трех приложений. Общий объем диссертации составляет 387 страницы, включая 43 таблиц, 116 рисунков, библиографический список из 130 наименований, приложения (67 стр.)

Содержание работы

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

В первой главе введены и рассмотрены основные элементы предлага-

Рис. 2. Схема рекурсивной композиции деревьев

емой методологии: дерево И/ИЛИ, операция рекурсивной композиции деревьев, вариант дерева И/ИЛИ.

Определение 1. Пусть имеется множество помеченных деревьев й = {¿¡¿}"=1, в дереве dj 6 О имеется гп листьев, тогда операция композиции деревьев формулируется следующим образом: В дереве к листьев (к < т) заменяются корнями деревьев из множества Д. В результате получается новое дерево с1г. Эта операция обозначена как:

где ¡| 6 В для всех I = 1, к и гь г2,..., - метки листьев дерева dj. Дерево йг однозначно определяется фиксацией параметров ], ¿1,..., г'ь tl,..., Определение 2. Пусть Д) = {г19, с^,} и (/д имеет не менее т листьев, тогда схемой рекурсивной композиции деревьев будет

где к <т, Д, = Ц,-1 и С(п — 1), 6 Д, для I = 1, к. Схему рекурсивной композиции С(п) удобно представлять графическими, рис. 2): на графическом изображении дерева выделяются листья, к которым присоединяются деревья С{п — 1), изображенные треугольниками. С(0) представляется отдельным изображением, в котором представлено дерево йд. Если в схеме рекурсивной композиции отсутствует йд, то подразумевается, что дерево Ля состоит из единственного узла. Математические выражения однозначно представляются в виде /-("-дерева (дерево Кантаровича, абстрактное синтаксическое дерево), во внутренних узлах которого записаны операции, а в листьях - операнды. Показано, что если йа и г1/, в схеме рекурсивной композиции С(п) являются К-деревьями и соответствуют функциям д(х1,х2,..., хт) -т-местная, }г(х\ , ..., хт+2) - т + 2-местная в операторе примитивной рекурсии то схема рекурсивной композиции С(п) однозначно задает рекурсивную функцию /(и).

Определение 3. Дерево И/ИЛИ - это корневое дерево, содержащее два типа

ЛТ — ¿1,..., и),

тг = О, ъ •••,£*:)> п> О,

(1)

Рис. 3. Пример дерева И/ИЛИ и всех его вариантов

узла: И-узел и ИЛИ-узел.

Определение 4• Вариантом дерева И/ИЛИ назовем поддерево, которое получается из заданного путем отсечения выходных дуг кроме одной у всех ИЛИ-узлов. Вариантов в дереве И/ИЛИ может быть некоторое множество. На рис. 3 показан пример дерева И/ИЛИ и всех его вариантов. Получено следующее рекуррентное выражение для подсчета числа вариантов:

2 Ч?> Для ИЛИ-узла;

^ = < •Рг - тл (2)

дляИ-узла; ^ '

г=1

1, для листа.

где г - рассматриваемый узел дерева; {а?}"^ - множество сыновей узла г; ал - число вариантов для узла л. Подсчитав значение функции для корня дерева, получим общее число вариантов, имеющихся в данном дереве. При этом будет подсчитано число вариантов для каждого узла всего дерева. Теперь, если записать '1' во все листья дерева И/ИЛИ,'+' - во все ИЛИ-узлы; ' х' - во все И-узлы, то получится абстрактное синтаксическое дерево, значение, которого будет равно числу вариантов в дереве И/ИЛИ. Таким образом, деревья И/ИЛИ однозначно строятся для выражений алгебры {1,+, х}. Запишем алгебру А = {./V, +, х, /?}, где Аг- множество натуральных чисел, Я-оператор примитивной рекурсии. Покажем, что для любой функции / £ А можно взаимно-однозначно поставить в соответствие схему рекурсивной композиции деревьев И/ИЛИ. Пусть / не рекурсивна, тогда ее выражение можно представить в виде дерева, где во внутренних узлах записаны операции '+' или ' ха листья будут содержать переменные или константы. При фиксации аргументов функции / получим, все константы. Далее, каждую константу пг-представляем в виде ИЛИ-узла, у которого ровно п, листьев, получим дерево И/ИЛИ. Если / рекурсивна, то для функций д и /г строятся деревья И/ИЛИ

о

Рис. 4. Схема рекурсивной композиции деревьев И/ИЛИ для функции /(n+1) = 2f(n) +3

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

Были рассмотрены алгоритмы First()/Next() для генерации вариантов дерева И/ИЛИ, для этого был разработан механизм стекового представления варианта(см. рис. 5). Первоначально создается главный стек, в который заносится корень дерева. Операция FirstQ обеспечивает построение самого левого варианта и выполняется по следующим правилам:

1) рассматривается узел в текущем стеке;

2) если на вершине текущего стека находится ИЛИ-узел, то его самый левый сын заносится в стек и выполняется операция First для данного стека;

3) если на вершине - И-узел, то самый левый сын заносится в текущий стек, а для остальных сыновей создаются новые стеки, и в каждый из них заносятся сыновья И-узла, для всех стеков выполняется операция FirstQ;

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

Были получены следующие правила для операции NextQ:

1) первоначально текущим становится главный стек;

2) рассматривается узел на вершине текущего стека;

3) если узел является листом, то удаляется из стека, переход на шаг 2;

4) если узел является ИЛИ-узлом, то, если у удаленного узла имеется соседний брат справа, то он помещается в стек и выполняется операция First(), выход из Next (). Если удаленный был последним, то из стека удаляется данный ИЛИ-узел, происходит переход на шаг 2;

5) если узел является И-узлом, то для стеков правых сыновей выполняется

Рис. 5. Структура стеков для И-узла Z(Sl,S2,Sk)

операция Next, до тех пор пока не будет успешно выполнена эта операция, если операция Next выполнилась неудачно (стек пуст) для самого правого сына, то данный И-узел удаляется из стека и происходит переход на шаг 2, если операция завершилась удачно, то для всех левых сыновей относительно данного выполняется операция First (), выход из NextQ; 6) если в стеке пусто, то все варианты поддерева просмотрены и выполняется возврат, если это главный стек, то все варианты дерева просмотрены, выполняется завершение.

Данные правила формализованы в виде автомата последовательной генерации вариантов: (В, Ад, Pplrs(. P\'CTi), где АЪ- множество магазинных символов; В - начальный магазинный символ; Pf„« - правила для операции First; Рыехг правила для операции Next;

Множеством магазинных символов А д является множество помеченных узлов дерева И/ИЛИ. Начальным магазинным символом В 6 N^ является корень дерева. Правила Pf,rst описывают порождение первого варианта для каждого внутреннего узла дерева И/ИЛИ. Для ИЛИ узла правило гласит, что если на вершине магазина записан ИЛИ-узел s2,..., Sfc)> то в магазин помещается левый сын узла sf. Это правило будет записано следующим образом:

First(z) First(sl).

Для И-узла правило гласит, что если на вершине магазина записан И-узел z(si,s — 2,.., S)t), то для всех сыновей, кроме самого левого создаются новые стеки. В первичный стек заносится левый сын, во вновь созданные стеки заносятся соответствующие сыновья узла z. Выполняется операция First для всех стеков. Это правило будет записано следующим образом: First(z) —> First{s\)First(sl)... First(szk).

Рассмотрены правила P_\ext- Для устранения неоднозначности в применении правил для выполнения операции Next задан предикат Prev(s), который разрешает применение правила, если из текущего стека был удален символ s. Для обозначения операции удаления символа из стека вводится символ pop. Тогда:

1. Правила для листьев, если в стеке лист дерева, то он вынимается из стека.

Next(z)Prev(Nil) —^ pop

2. Правила ИЛИ-узла, правила замены Next(z)Prcv(s\) —> First(s|) Next{z)Prev{s\) First(s()

Next(z)Prev(szk_1) —> First(szk) Next(z)Prev(sk) —> pop

3. Правила для И-узла: Next(z)Prev(s{) —> First(sl)Next(s2) Next(z)Prev{sl) —> First{si)First(s2)Next(sl)

Next{z)Prev(sl_1) First{s\)First(s... First{sf._j)Next(si) Next(z)Prev{s2k) —»pop

Операция First реализована в виде следующего алгоритма algorithm First(siac/t) begin do begin

z:=stack.top() { определяем символ на вершине стека} Rule(^,i/-!rii) {выполняем правило для узла z} end

while(2<>lcaf) {конец если на вершине находится лист } end

Операция Next реализована в виде следующего алгоритма algorithm Next (stacA;) do {

z:=stack.top() { определяем символ на вершине стека } if z=leaf then { если это лист } begin

stack.pop() {выталкиваем его} prev := z { устанавливаем значение prev } end

else begin { если это не лист } iRule=TNext[z,prev| { ищем номер правила по таблице } if Run(iRule) then { выполняем это правило } return; { если нашли лист } end

while(siadc.size() >0) end

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

формирование следующего варианта путем замены одного поддерева варианта на другое. После генерации последнего варианта операция Next выталкивает все элементы из всех стеков. Таким образом, число операций push и pop при генерации всех вариантов будет одинаковое. Тогда общее число операций push для дерева И/ИЛИ будет равно:

Op(z) = <

Ef= i Op(Sj) + 1, для ИЛИ-узла;

+ + дляИ-узла; (3)

1, для листа.

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

ных символов равно множеству \dh]n + Начальный символ будет Z[n\. Правила First и Next будут иметь рекурсивную структуру.

Основная идея алгоритма генерации варианта по номеру заключается в том, что, зная номер варианта для заданного узла z, можно пересчитывать этот номер в номера вариантов для поддеревьев его сыновей, основываясь на значениях u)s*. Алгоритм пересчета для И-узла основан на использовании выражения

1=1

и для некоторого номера 1г, такого, что 0 < lz < шг, воспользовавшись алгоритмом преобразования числа lz в число со смешанной системой счисления, в которой основаниями являются {wf}"^, получим значения для номеров варианта I, всех сыновей И-узла z. Отсюда, между числом L и множеством {¿;}"=i будет взаимно-однозначное соответствие. Для ИЛИ-узла определяется не только номер варианта для сына 1Я, но и номер соответствующего сына. Основываясь на выражении подсчета вариантов для ИЛИ-узла, можно предложить следующий алгоритм: ищется интервал, в который попадает /,. Если lz < wj'', то выбирается первый сын ls := lz ; Если L < oJf1 + (J2Z\ то выбирается второй сын и /, := L —

Если L < SLi Ч-2' j то выбирается /с-й сын и ls := L — Sti ш\г)■ Очевидно, что между lz и парой (к, It) взаимно-однозначное соответствие. Тогда алгоритм генерации варианта следующий:

1. В стек помещается пара (пит, root): номер варианта и корень дерева.

2. Из стека вынимается очередная пара (I, z).

3. Если % это И-узел, то вычисляются k для всех сыновей s, узла z, все пары

(¿¡,3*) заносятся в стек, переход на шаг 2.

4. Если г это ИЛИ-узел, то определяется пара (4, заносится в стек, переход на шаг 2.

5. Если г лист, то переход на шаг 2.

6. Если стек пуст, то останов.

Алгоритм генерации варианта задает биективное отображение ЛГ„ на множество вариантов И'; дерева И/ИЛИ й.

Для схемы рекурсивной композиции алгоритм генерации варианта носит рекурсивный характер и не требуется явного построения дерева И/ИЛИ. При этом:

1) число вариантов для всех узлов в схеме рекурсивной композиции выражается через рекурсивную функцию ш(п);

2) поскольку дерево И/ИЛИ строится из деревьев <4 и (1и, то необходимо построить алгоритм Сепе^еУапа^ для случаев <4 и и записать рекурсивный алгоритм. Алгоритм нумерации варианта дерева И/ИЛИ следующий. Производится сопоставление варианта V € V в дереве (I и вычисление соответствующего номера г. Алгоритм сопоставления следующий:

1. В стек заносим корень варианта, в стек з,1 заносим корень дерева.

2. Из стека й,, вынимаем узел варианта 2 и ищем этот узел в дереве И/ИЛИ.

3. Если это лист, то на шаг 2.

4. Если это ИЛИ-узел, то находим к-го сына в дереве И/ИЛИ, помещаем его в стек сына узла варианта г помещаем в стек в,..

5. Если это И-узел, то всех сыновей дерева И/ИЛИ заносим в стек за, а сыновей варианта в з„.

6. Если стек пуст, то завершить работу алгоритма.

В результате работы алгоритма сопоставления в стеке 3,1 будут находиться все узлы дерева И/ИЛИ, входящие в вариант. Далее, используя стек вычисляются значения номеров вариантов для всех узлов, находящихся в стеке.

Вычисление номера начинается с рассмотрения листьев варианта V. Все листья варианта имеют значения 0.

1. Для каждого И-узла г вычисляется

/г = ¿! + Шх(12 + Ы2(.Д,_1и/,,)...)),

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

2. Для каждого ИЛИ-узла вычисляется

где к- номер соответствия для узла ИЛИ в дереве (¿, 4 - помер варианта для этого сына.

1-1

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

{Td=i[("* - + ОРнЬ для ИЛИ-узла;

+ дляИ-узла; (4)

О, для листа.

Отношение Opz/ш, дает среднее число операций на один вариант, сгенерированный по номеру.

Предложенная методология базируется на возможности создания дерева И/ИЛИ с заданным множеством вариантов. Если мощность некоторого комбинаторного множества задана в виде числа п, то строится конкретное дерево И/ИЛИ, число вариантов которого равно п. Если мощность некоторого класса комбинаторных множеств задана в виде функции / 6 {Аг, +, х, R}, то можно задать схему рекурсивной композиции деревьев И/ИЛИ. При фиксации параметров этой функции и, соответственно, схемы рекурсивной композиции значение функции совпадает с числом вариантов в дереве И/ИЛИ, полученном по схеме рекурсивной композиции.

Кроме того, схему рекурсивной композиции деревьев И/ИЛИ можно получить не зная функции мощности класса комбинаторного множества, основываясь на некоторых правилах и свойствах порождающего алгоритма для данного класса. Например, множество перестановок из (п +1) элементов может быть получено из множества перестановок п элементов. Или множество двоичных деревьев высотой не более п+1 может быть получено из множества двоичных деревьев высотой не более п. Отсюда, используя свойства деревьев И/ИЛИ, можно построить биективное отображение между комбинаторным множеством и множеством вариантов:

G : СМ -> \Vdl

где СМ - комбинаторное множество, Wd - множество вариантов дерева d.

На основе полученной биекции предложены методы комбинаторной генерации:

1. Метод построения алгоритмов последовательной генерации элементов комбинаторного множества СМ\

- Строится фиксированное дерево И/ИЛИ d или схема рекурсивной композиции Cd(n).

- Записывается автомат (В, Np, Pr,rst, Pxrit)-

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

- Реализуются алгоритмы First()/Next().

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

2.Метод построения алгоритмов генерации элементов комбинаторного множества СМ по номеру:

- Строится фиксированное дерево И/ИЛИ d или схема рекурсивной композиции Cd(n).

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

- Записывается процедура получения элемента комбинаторного множества по варианту.

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

3. Метод построения алгоритмов нумерации элементов комбинаторного множества СМ:

- Строится фиксированное дерево И/ИЛИ d или схема рекурсивной композиции Са(п).

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

- Записывается процедура получения варианта по элементу комбинаторного множества.

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

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

п « [ \/пит ■ т\ + (5)

где тг - номер бита, т - общее число единиц в сочетании.

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

Рт{п) = рт{п -т)+ pm+l(n). (6)

На основании данной формулы были получены оригинальные алгоритмы: последовательной генерации для разбиений, генерации разбиений по номеру и нумерации разбиений с указанными ограничениями. Отличительной особенностью данных алгоритмов от известных является универсальность, при условии, что среднее число операций push и pull на одно разбиение равно 4. Это объясняется тем, что по формуле 6 получается дерево И/ИЛИ, которое является полным двоичным деревом и число узлов в таком дереве равно (2п — 1), где п - число листьев. Откуда число операций push на один вариант будет равно . Это согласуется с известным алгоритмом генерации разбиений, у которого число операций равно 4 — С/ \Дп) 4- 0(1/п) (Д. Кнут "Генерация всех разбиений"). Построен треугольник разбиений, получены производящие функции для разбиений рт(п).

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

Для перестановок имеется большое число алгоритмов комбинаторной генерации, это объясняется большим числом разнообразных форм представления. Мощность множества перестановок выражается через рекуррентные формулы, основанные на числах Стирлинга, Эйлера, Каталана. Все эти формулы имеют рекуррентную природу. Предложен метод построения алгоритмов генерации перестановок на основе формулы перестановок мультимножества: параметр множества перестановок п представляется как композиция натурального числа, щ + пг + ... 4- Пк = п. Тогда

п\= ( п Уть-

V пип2,...,пк I -11

Или

к

п\ = [С-С^П1С^П1_П2... С£] ]>'!

! = 1

Отсюда, задавая алгоритмы генерации композиции числа п, алгоритм генерации перестановки мультимножества и алгоритмы генерации перестановок для п;, получим уникальный алгоритм генерации перестановки (см. рис. 6).

Используя данный подход можно предложить следующий алгоритм генерации перестановки. Число n > 1 представляется в виде 2 + ЗА:, '¿к. 4 + 3к.

Таблица 1. Схемы рекурсивных композиций, полученных в главе 3

1 Перестановки (инверсии) Жт

2 Перестановки (формула Эйлера)

3 Перестановки (формула Стирлинга)

4 Перестановки (возрастающие деревья)

5 Беспорядки

6 Числа Каталана

7 Числа Стирлинга 2 рода 4----

8 Числа Сильвестра

21

)

Рис. 6. Комбинация алгоритмов генерации перестановок

Рис. 7. Схема рекурсивной композиции для множеств, описываемых числами Каталана

Необходимо иметь все перестановки для чисел 2, 3 и 4. Тогда все перестановки мощностью 2, 3, 4 могут быть представлены массивами констант. А сочетания примут вид С^С^С,^, для которых можно построить эффективные алгоритмы генерации.

Рассмотренный метод применен для построения алгоритмов комбинаторной генерации для множеств, описываемых числами Каталана. Представленное рекуррентное выражение Сп+\ = СоСп+С1Сп~\+.. .+СоСп, Со = 1, является рекурсивной функцией алгебры {Л?-, +, х, Д}. Тогда для данной функции строится схема рекурсивной композиции дерева И/ИЛИ. Правила построения следующие:

1. Корнем будет узел {С„+1}, это будет ИЛИ узел, у которого ровно п + 1 сыновей.

2. Каждый г-й сын ИЛИ-узла является И-узлом, имеющий поддеревья С, и С„_г'. Схема рекурсивной композиции представлена на рис. 7. Вариантом для дерева И/ИЛИ, основанного на данной схеме рекурсивной композиции, будет являться двоичное дерево, т.к. все И-узлы имеют двух сыновей. Тогда автомат последовательной генерации будет иметь следующий вид:

1. Множество магазинных символов:

{Сг}"=о — символы, соответствующие з^злам вычисления чисел Каталана.

{Т»};и — символы, соответствующие членам суммы. 1 — константа, соответствующая листу.

Рис. 8. Представление вариантов для множеств Каталана

Таблица 2. Значения функции числа операций для генерации элементов множеств, описываемых формулой Каталана_____

п Ор(п) Сп Ор(п) с„

7 625 429 1.4568764568

8 2055 1430 1.4370629370

9 6917 4862 1.4226655697

10 23713 16796 1.4118242438

11 82499 58786 1.4033783553

12 290511 208012 1.396606926

13 1033411 742900 1.3910499394

14 3707851 2674440 1.3864027609

15 13402696 9694845 1.3824559340

2. Начальный символ Cn+i.

3. Правила First

1) First (С,) - First^"1)

2) First(rj) -» First(Ci)First(C1_j)

3) First (Со)->1

4. Правила Next

1) Next(q)Prev(7])(j < *>>First(7]+1)

2) Next(C;)Prev(7^) (j = г)->pop

3) Next(C0)Prev(l)->pop

4) Next(7j)->First(C,)Next(Ci-j)

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

Рис. 9. Схема рекурсивной композиции для полных двоичных деревьев высотой

получим, ЧТО

п

Ор(п + 1) = [Ор(г) ■ Сп-г + Ор(п - г) + 1] + 1.

¿=о

Для листа Ор(0) = 1. Работу автомата можно оптимизировать, заметив, что от магазинных символов 7] можно избавиться. Тогда число операций будет выражаться формулой

п 1=0

Результаты моделирования для полученной рекуррентной формулы приведены в таблице 2. Как видно из приведенной таблицы 2 результаты согласуются с формулой, приведенной Д.Кнутом 4С„/3 + 0(1/п2).

Четвертая глава посвящена разработке алгоритмов комбинаторной генерации корневых деревьев. Показано эффективное применение предложенной методологии для генерации практически всех классов корневых деревьев: двоичных деревьев с высотой не более п, с заданной высотой п, с заданным числом узлов п, полных двоичных деревьев, АВЛ деревьев, красно-черных деревьев, 2-3 деревьев, крашеных деревьев, троичных деревьев, ¿-арных деревьев, упорядоченных, неупорядоченных, деревьев Кемпа, Шредера, Риорда-на. Приведем пример использования методологии для получения алгоритмов комбинаторной генерации для полных двоичных деревьев высотой не более п. Первым шагом предлагаемой методологии является построение рекурсивной композиции деревьев И/ИЛИ полных двоичных деревьев высотой не более п. Для этого предположим, что имеется множество полных двоичных деревьев высотой не более п — 1 и для этого множества имеется схема рекурсивной композиции (п — 1). Тогда множество полных двоичных деревьев высотой не более п состоит из дерева высотой 0 и деревьев, у которых левое и правое поддеревья высотой не более п — 1. Отсюда, схема рекурсивной композиции будет следующая (см. рис. 9)

Рис. 10. Пример дерева И/ИЛИ для п = 3 и всех его вариантов

II 2) М

РнмО N-1X111 N^11,

41 5!

КсмП N«({1

Рис. 11. Стековое представление вариантов для С(3)

Получим рекурсивное выражение для мощности полных двоичных деревьев высотой не более п. Для этого по схеме рекурсивной композиции получим деревья йд и <4 (рис. 9). Тогда д{х) = 1, /¡(.г) = 1 + х ■ х. Отсюда, множество полных двоичных деревьев высотой не более п выражается следующим рекурсивным выражением:

, . Г 1 г п = 0,

"(") = { 1+^(п-1), тг > 0. М

Данное выражение согласуется с формулой, полученной А.Ахо и Н.Слоун. При п = 3 получим следующее И/ИЛИ дерево (см. рис. 10) Число вариантов в дереве равно 5. По каждому варианту однозначно получается соответствующее полное двоичное дерево.

Алгоритм последовательной генерации. Запишем автомат (В, ЛГ, Р\-Г».Т(): Магазинные символы: {Д }"=1, {А}Г= 1-

Таблица 3. Результаты моделирования для среднего числа операций в алгоритме последовательной генерации___

n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Op(n)/ui(n) 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

Начальный символ: Dn. Правила для операции First: First(Di) Li

First(Vi) First{Di-i)First(Di-i). Правила для операции Next: Next(Di)Prev(Li) —> pop Next(Di)Prev{Li) Firsi(H) Next(Di)Prev(Vi) —► pop Next{Vij -» First{Di-{)Next(Di-i).

На рис. 11 перечислены все стековые конфигурации для последовательной генерации полных двоичных деревьев высотой не более 3.

Запишем число операций push для последовательной генерации вариантов:

0P(DH) = Op(Ln) + Op(Vn) + 1, Op(Ln) = 1,

Op(Vn) = OpiDn-.Mn - 1) + Op(Dn+1. Тогда Op(n) = Op(n - 1 )[w(n - 1) + 1) + 3.

Результаты моделирования приведены в таблице 3. Запишем алгоритм генерации полных двоичных деревьев высотой не более п. algorithm GenFullBinaryTree(num,n) begin if n=0 then return Nil Create(node) { создается узел дерева } if num==0 then return Nil; {сыновей нет} begin {есть два сына } пит := num. — 1 l\\=num mod u>(n — 1) li~num/u>{n — 1)

node.left :=GenFullBinaryTree(/i,n - 1)

node.right:=GenFulBinaryTree(i2,ri -1)

end

return node

end

algorithm RankFullBinaryTree(Node,n) begin if Node=Nil or n=Q then return 0

begin

Zi:=RankFullBinaryTree(Node.left,n - 1) /2:=RankFullBinaryTree(Node.right ,n - 1) return l\ + l2Uj(n — 1) end

end

Модифицирована процедура полного разбиения, которую впервые предложил Н.Я. Виленкин, как подсчет процессов последовательных разбиений конечного множества, а Р.Стенли использовал эту процедуру для полного разбиения конечного множества S, в результате выполнения которой получается некоторое корневое помеченное дерево. В этой процедуре предложено вместо конечного множества S использовать натуральное число п. Тогда, имея некоторый алгоритм R(n) представления натурального числа п в виде суммы, в общем случае, неотрицательных чисел Л;, строится непомеченное тг-узловое корневое дерево. Алгоритм построения дерева следующий:

1. Создаем корень дерева г и пару < п, г > заносим в стек;

2. Если стек пуст, то завершаем процедуру.

3. Вынимаем из стека очередную пару < к, г >. Если к = 1, то данный узел становится листом и переходим на шаг 2, иначе, в соответствии с алгоритмом R, получаем представление 7г : [Ai + Аг + ... + А,„], такое, что Sili Aj = А; — 1, и переходим на шаг 4.

4. Создаем т узлов присоединяем их в качестве сыновей к узлу г в соответствии с порядком, заданным в представлении {А,-}™!- Все пары < A,-, Si > записываем в стек. Переходим на шаг 3.

Свойства предложенного алгоритма полного разбиения:

1. Если задан R(n), п > 0 и \ > 1 для всех представлений тг £ Рп, то предложенный алгоритм всегда строит дерево. 2. Число деревьев для заданного числа узлов равно:

т

вд=£П*(А')> (8)

iteP„-i ¿=1

где 7г = {Ai + Аг +... + Am = п — 1}, Pn~i - множество представлений числа (п — 1), в соответствии с алгоритмом R.

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

Таблица 4. Схемы рекурсивных композиций, полученных в главе 4

1 двоичные деревья высотой не более п

2 двоичные деревья с заданным числом узлов

3 двоичные деревья высотой п

4 полные двоичные деревья с числом узлов 2п + 1

5 АВЛ-деревья высотой п

6 2-3 деревья высотой п А

7 2-3-4 деревья высотой п

8 красно-черные деревья высотой п А &

9 цветные двоичные деревья высотой не более тг

10 дерево операций

ной на композициях была получена новая функция:

та) = |

1,

Т(г - 2'")

>т\«+2 ' > к+2 '

г = О, г > О,

где т = |к^(г)]

& =

т - |^(2т+1 - г - 1)]

-1, 0 < г < 2т+1 — 1, г = 2т+1 - 1.

В пятой главе показано применение предложенной методологии для построения алгоритмов комбинаторной генерации для множеств выражений языков, описываемых однозначными контекстно-свободными грамматиками (В, Т, ЛГ, Р), где В - начальный символ, Т - множество терминальных символов, N - множество нетерминальных символов, Р - правила подстановки. Для построения схемы рекурсивной композиции деревьев И/ИЛИ предложены следующие правила: для каждого нетерминала А € N строится И/ИЛИ дерево. Корнем этого дерева будет являться узел, помеченный нетерминалом А, это будет ИЛИ-узел, у которого число сыновей равно числу правил подстановки, у которых в левой части записан этот нетерминал (они помечаются номерами Р^Рг - ■ ■ Рк)- Каждый узел Р, является И-узлом, у которого каждый сын соответствует символу грамматики, присутствующий в правой части правила Р*. Для каждого дерева И/ИЛИ нетерминала грамматики вводится параметр рекурсии, при фиксации которого для рекурсивной композиции получается фиксированное дерево И/ИЛИ, описывающее подмножество выражений данного языка. Отсюда вариант дерева И/ИЛИ, построенного для грамматики будет являться деревом вывода для конкретного выражения. Поскольку между вариантом и выражением должно быть взаимно-однозначное соответствие, то контекстно-свободная грамматика должна быть грамматикой с однозначным выводом.

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

Таблица 5. Схемы рекурсивных композиций, полученных в главе 5

1 выражения языка Дика

2 выражения языка Дика длиной п

3 выражения языка Моцкина

4 выражения языка Моцкина длиной п

5 выражения языка Лу-касевича длиной п

6 арифметические выражения

I уровень

Рис. 12. Уровни программного комплекса комбинаторной генерации

Рис. 13. Описание структуры базы данных

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

1) библиотеку шаблонов для работы с деревьями И/ИЛИ;

2) программный сервер, обеспечивающий основные функции метода комбинаторной генерации;

3) библиотека шаблонов классов комбинаторных множеств, исследованных в диссертации.

Для реализации сервера были разработаны программные интерфейсы: для представления деревьев И/ИЛИ и вариантов, для представления и манипулирования системой стеков.

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

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

Для кодирования реляционной базы данных предложен метод, основанный на представлении доменов атрибутов реляционной таблицы в виде дерева И/ИЛИ (рис. 13). Тогда алгоритм Иапк(а) будет кодировать кортеж а, алгоритм СепегсЛе(пит¡) по номеру пит^ генерировать этот кортеж. Так как значение а € х Лг х... х Ап является комбинацией элементов из множеств {Д}™=1, то корень дерева будет И-узлом, имеющим п сыновей, каждый г'-й сын соответствует множеству А¿, графическое изображение такого соответствия показано на рис. 14.

Общее число множества значений определяется по формуле:

п

ы(Г) = П^)-

Рис. 14. Соответствие между таблицей и деревом И-ИЛИ

1 <чначснис 1>

2 <'шачснпс 2>

п «'значение п>

1

m

используется

используется

Рис. 15. Соответствие между справочником и деревом И-ИЛИ

Далее для каждого множества строится свое дерево И-ИЛИ. В общем случае можно выделить следующие типы:

1. Множество значений представлено справочником.

2. Множество значений представлено числовым интервалом.

3. Множество значений представлено деревом И-ИЛИ.

Для представления множества уникальных объектов, которые используются в базе данных для некоторого домена, используется справочник. Справочник имеет две части, первая часть содержит пронумерованные уникальные объекты, вторая часть - резервная, предназначена для внесения новых объектов. Соответствие между справочником и деревом И-ИЛИ показано на рис. 15. Справочник представляется ИЛИ-узлом, а все сыновья являются элементами справочника. Тогда общее число вариантов дерева (или элементов множества) равно:

ui{Ai) = п + т.

Использование данного подхода позволило создать защищенный архив удостоверяющего центра с историями сертификатов открытого ключа. Обобщенная структура архива показана на рис. 16. Основные модули и подсистемы: подсистема ввода сертификата; подсистема поиска, обеспечивающая контекстный поиск в архиве; подсистема управления доменами, обеспечивающая поиск и занесение заданных значений полей; модуль Rank, выполняющий формирование номера (кода) для данного сертификата; модуль Generate по номеру (коду) в базе данных формирует соответствующий кортеж сертификата; индексный файл для организации поиска (Idx); база данных (Base), хранящая коды кортежей; D(K) - домен, хранящий значения атрибута K(C,L,ST, 0,0U,CN); Si - кортеж сертификата; пит, - код сертификата.

Рис. 16. Структура архива

Применение инструментального ПО при разработке и серийном производстве систем управления технологическими процессами и безналичными расчетами за нефтепродукты с применением магнитных, электронных и смарт -карт в ЗАО НПФ "Сибнефтекарт"позволило:

1) построить экономные алгоритмы представления и хранения реляционных баз данных, сокращающие на 18% объем баз данных;

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

1. Модели и алгоритмы генераторов тестовых заданий, основанные на применении деревьев И/ИЛИ.

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

3. Пакет генераторов тестовых заданий общим числом 130, число шаблонов - 6428.

4. Система проведения компьютерных экзаменов, реализованная в двух вариантах: локальном и сетевом на сайте Томского межвузовского центра дистанционного образования (www.tcde.ru).

5. Система проведения компьютерных контрольных работ.

6. База компьютерных контрольных работ и экзаменов, насчитывающая

Рис. 17. Система тестирования уровня знаний на основе генерации тестовых заданий

1300 единиц, общим числом вопросов свыше 150000.

Эффект от внедрения следующий:

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

• организовать действенный текущий и итоговый контроль в дистанционной технологии обучения;

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

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

Перечисленные программные системы используются для 20 специальностей ТУСУРа, общим числом в 900 дисциплин, с числом студентов, обучающихся по дистанционной технологии, 7500. В год система проведения компьютерных контрольных работ тиражируется объемом 15 000 компакт дисков. В год обрабатывается 120000 протоколов компьютерных экзаменов и контрольных работ.

Заключение. Совокупность полученных в настоящей диссертации на-

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

1. Показано, что между функцией /(га) € А = {N, +, х, R}, где N - множество натуральных чисел, R - оператор примитивной рекурсии, и схемой рекурсивной композиции Rn(dg, <4) деревьев И/ИЛИ существует взаимнооднозначное соответствие, которое обеспечивает следующие свойства:

- при фиксации параметра га = п* по схеме рекурсивной композиции Яп-строится дерево И/ИЛИ, число вариантов которого равно значению /(га*);

- если для некоторого комбинаторного множества получена схема рекурсивной композиции Rn, то мощность этого множества выражается функцией /(«);

- между комбинаторным множеством, мощность которого равна f{n*) и множеством вариантов дерева И/ИЛИ существует биекция.

2. Если для некоторого комбинаторного множества Еп существует дерево И/ИЛИ Rn, то:

- Однозначно строится автомат последовательной генерации {В, М, Pfsu PiVxt}> где В - начальный магазинный символ, М - множество магазинных символов, Pfst - правила для операции First, P\-Xt - правила для операции Next. Временная сложность алгоритма последовательной генерации равна

{£?=i Op{si) + 1, для ИЛИ-узла;

EjtiPpfe)' ntj+i w(s*)] + Op(sk) + 1, для И-узла; 1, для листа.

- Строится алгоритм генерации элемента комбинаторного множества по номеру.

- Строится алгоритм нумерации элементов комбинаторного множества.

- Временная сложность алгоритма генерации по номеру и нумерации равна:

~ + Для ИЛИ-узла;

(nz - 1 + E;=i • шх, для И-узла; О, для листа.

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

Рт(п) = Рт{п -т)+ pm+l(n).

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

4. Эффективное применение разработанных методов убедительно показано на классических комбинаторных множествах: классов перестановок, множеств, описываемых числами Фибоначчи, Каталана, Стирлинга, Сильвестра.

5. Разработаны схемы рекурсивных композиций деревьев И/ИЛИ для построения алгоритмов генерации и нумерации классов деревьев: двоичных деревьев высотой не более п, заданным числом узлов и высотой, полных двоичных деревьев, АВЛ-деревьев, 2-3-деревьев, 2-3-4-деревьев, красно-черных деревьев, цветных двоичных деревьев, деревьев операций.

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

- Алгоритмы генерации ¿-арных и полных ¿-арных деревьев с заданным числом узлов.

- Выдвинута гипотеза, что для разложений справедлива формула:

Пя"4+1.(А,-) = ((

¡=1 V

(к + £)п + ¿Л к + 1

ч п ) {k + t~l)n + k + l,

где Ь - число частей разложения числа п, £ > 2, Аг = п, к - смещение относительно большего разложения (Ь + к).

- Алгоритм генерации упорядоченных корневых деревьев.

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

ТП\ - / * =

¿>0.

/ [Мг)] - - г - 1)] - 1, 0 < г <

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

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

8. Разработано универсальное программное обеспечение направленное на:

1) проектирование и исследование алгоритмов комбинаторной генерации;

2) создание генераторов тестовых заданий для систем контроля знаний студентов;

3) проектирование программных систем сжатия и кодирования в автоматизированных и информационных системах. Данное программное обеспечение внедрено на производственном объединении «Контур», на ЗАО НПФ «Сибнефтекарт», в дистанционные технологии обучения студентов: Томского государственного университета систем управления и радиоэлектроники по 38 специальностям, в Кемеровском технологическом институте пищевой промышленности по трем специальностям, в Югорском государственном университете.

Список публикаций

Монографии

1. Кручинин, В. В. Комбинаторика композиций и ее приложения / В. В. Кручинин. — Томск: Изд-во «В-Спектр», 2010. — 156 с.

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

3. Кручинин, В. В. Генераторы в компьютерных учебных программах / В. В. Кручинин. - Томск: Изд-во Том. ун-та, 2003. - 200 с.

4. Кручинин, В. В. Разработка компьютерных учебных программ / В. В. Кручинин. — Томск: Изд-во Том. ун-та, 1998. — 211 с.

Статьи в журналах из списка ВАК

1. Кручинин, В. В. Подходы к созданию защищенного архива на основе разделения секрета / В. В. Кручинин, А. А. Шелупанов // Доклады ТУ-СУР. - 2008. - № 2 часть 1. - С. 67-72.

2. Кручинин, В. В. Представление множеств деревьями И/ИЛИ / В. В. Кручинин // Доклады ТУСУР. - 2008. - № 2(17). - С. 107-112.

3. Кручинин, В. В. Алгоритмы генерации и нумерации композиций и разбиений натурального числа п / В. В. Кручинин // Доклады ТУСУР. — 2008.-№2(17).-С. 113-119.

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

5. Кручинин, В. В. Рекурсивные композиции деревьев и их свойства / В. В. Кручинин // Доклады ТУСУР. - 2007. - Т. 16. - С. 74-80.

6. Кручинин, В. В. Подход к созданию баз данных, основанный на алгоритмах генерации и идентификации кортежей / В. В. Кручинин, С. Л. Хо-

мич, А. В. Титков// Известия Томского политехнического университета. — 2006. - Т. 309, № 8. - С. 28-32.

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

8. Кручинин, В. В. Программные генераторы (обзор) / В. В. Кручинин // Доклады ТУСУР. - 2004. - № 2(10). - С. 64-68.

10. Компьютерный учебник «ТМЦДО. Высшая математика-1» / С. И. Борисов, А. В. Долматов, В. В. Кручинин, В. А. Томиленко // Открытое образование. - 2004. - № 3. - С. 12-17.

11. Кручинин, В. В. Применение генераторов в компьютерных технологиях обучения / В. В. Кручинин, С. И. Борисов // Интеграция образования. — 2004. — № 4,- С. 116-121.

12. Кручинин, В. В. Модели и алгоритмы генерации задач в компьютерном тестировании / В. В. Кручинин, Ю. В. Морозова // Известия Томского политехнического университета. — 2004. — № 5. — С. 127-131.

13. Кручинин, В. В. Алгоритмы и перечислительные свойства деревьев И/ИЛИ / В. В. Кручинин, Вестник ТГУ, №284, серия «Математика. Кибернетика. Информатика», декабрь 2004 - С.181-184.

14. Кручинин, В. В. Система тестирования, основанная на генерации вопросов и тестовых заданий / В. В. Кручинин, М. Ф. Молочко // Открытое образование. - 2004. - № 4. - С. 30-35.

15. Кручинин, В. В. Использование деревьев И/ИЛИ для перечисления выражений контекстно-свободных языков / В. В. Кручинин // Вестник Томского государственного педагогического университета. — 2004. — № 6(43). — С. 84-88.

16. Жуков, В. К. Новые подходы к организации контроля знаний в вузе /

B. К. Жуков, В. В. Кручинин // Известия МАН ВШ. - 2004. - № 2(28). -

C. 113-118.

17. Кручинин, В. В. Число разбиений натурального числа п на части, каждая из которых не менее тп// Матем. заметки .— 2009.— № 4(86).— С. 538-542.

18. Кручинин, В. В. Алгоритмы генерации корневых деревьев на основе процедуры полного разбиения// ПДМ. Приложение 1 . — 2009. — С. 99-101.

19. Кручинин, В. В. Метод кодирования информационных объектов на основе деревьев И/ИЛИ / В. В. Кручинин Б. А. Люкшин // Доклады ТУСУР. - 2010. - № 1(21), ч. 1. - С. 170-172.

Тираж 100. Заказ №912. Томский государственный университет систем управления и радиоэлектроники 634050, г. Томск, пр. Ленина, 40. Тел.: 53-30-18.

Введение

Глава 1. МЕТОДОЛОГИЯ КОМБИНАТОРНОЙ ГЕНЕРАЦИИ,

ОСНОВАННАЯ НА ДЕРЕВЬЯХ И/ИЛИ

1.1. Рекурсивные композиции деревьев И/ИЛИ и их свойства

1.2. Деревья И/ИЛИ: основные понятия и определения, связь с алгебраическими структурами и свойства

1.3. Алгоритмы комбинаторной генерации для деревьев И/ИЛИ

1.4. Методы построения алгоритмов комбинаторной генерации . . 71 Выводы

Глава 2. АЛГОРИТМЫ ГЕНЕРАЦИИ НА ОСНОВЕ ДЕРЕВЬЕВ РЕШЕНИЙ.

2.1. Алгоритмы генерации и нумерации сочетаний.

2.2. Генерация разложений числа п

2.3. Генерация и нумерация множеств, заданных числами Фибоначчи

2.4. Генерация разбиений

2.5. Алгоритмы генерации и нумерации композиций.

2.6. Выводы.

Глава 3. АЛГОРИТМЫ КОМБИНАТОРНОЙ ГЕНЕРАЦИИ ДЛЯ ПЕРЕСТАНОВОК И МНОЖЕСТВ, ЗАДАННЫХ ФОРМУЛАМИ КАТАЛАНА, СТИРЛИНГА И СИЛЬВЕСТРА

3.1. Генерация и нумерация перестановок

3.2. Генерация и нумерация множеств, заданных формулой Ката-лана.

3.3. Генерация и нумерация разбиений множества мощностью п на к групп.

3.4. Генерация и нумерация множеств, заданных формулой Сильвестра

3.5. Выводы.

Глава 4. АЛГОРИТМЫ КОМБИНАТОРНОЙ ГЕНЕРАЦИИ ДЛЯ КОРНЕВЫХ ДЕРЕВЬЕВ

4.1. Двоичные деревья.

4.2. Деревья со степенью узлов больше

4.3. Помеченные деревья

4.4. Генерация корневых деревьев на основе разложений

4.5. Генерация упорядоченных корневых деревьев на основе композиций

4.6. Генерация корневых неупорядоченных деревьев.

4.7. Выводы.

Глава 5. ГЕНЕРАЦИЯ ВЫРАЖЕНИЙ ЯЗЫКОВ, ОПИСЫВАЕМЫХ КС-ГРАММАТИКАМИ

5.1. Генерация выражений языка Дика

5.2. Генерация выражений языка Моцкина

5.3. Генерация выражений языка Лукасевича.

5.4. Генерация арифметических выражений.

5.5. Выводы.

Глава 6. ПРОГРАММНЫЙ КОМПЛЕКС ИССЛЕДОВАНИЯ, РАЗРАБОТКИ И ПРИМЕНЕНИЯ АЛГОРИТМОВ КОМБИНАТОРНОЙ ГЕНЕРАЦИИ

6.1. Инструментальное программное обеспечение комбинаторной генерации.

6.2. Реляционные базы данных, основанные на алгоритмах генерации и идентификации кортежей

6.3. Система тестирования уровня знаний студентов, основанная на генерации тестовых заданий

6.4. Метод и система идентификации сложных технических изделий, основанные на применении деревьев И/ИЛИ.

6.5. Сравнительный анализ методов генерации

Выводы

Актуальность

В работе «Три подхода к определению понятия «Количество информации» академик А.Н. Колмогоров предложил в качестве меры сложности «минимальную длину программы 1(р) программы р, получения у из х» [1]. Развивая эту мысль, Г. Чейтин вводит понятие программного генератора некоторого информационного объекта как меры алгоритмической сложности этого объекта [2]. Однако суть алгоритмов таких генераторов не раскрывается. С другой стороны, развитие исследований в области комбинаторики и методов программирования привело к возникновению комбинаторной генерации, где исследуются алгоритмы генерации и нумерации комбинаторных множеств. Здесь под комбинаторными множествами понимаются множества, имеющие финитную природу и полученные по конечным правилам для некоторого конечного числа конечных множеств. Важно отметить, что элементы таких множеств имеют некоторую структуру. К таким комбинаторным множествам относятся сочетания, перестановки, размещения, разбиения, разложения, деревья, графы, контекстно-свободные грамматики и т.д. [3].

Исторический обзор развития этого направления дает Д.Кнут в 4 томе «Искусство программирования» [4]. Однако, классификация алгоритмов генерации и определение понятий здесь не приводится. Такую классификацию приводит Ф.Раски в работе «Комбинаторная генерация» [5]. Он выделяет 4 класса алгоритмов генерации:

1) последовательная генерация всех элементов комбинаторного множества (listing);

2) нумерация всех элементов комбинаторного множества (ranking);

3) генерация элементов комбинаторного множества в соответствии с процессом нумерации (unranking);

4) случайная генерация элемента комбинаторного множества (random selection).

Алгоритмы последовательной генерации комбинаторных множеств наиболее изучены. Общая схема их следующая[6-9]:

1)установка начального элемента комбинаторного множества;

2)организация цикла, в котором производится вывод следующего элемента комбинаторного множества или его конструирование из данного.

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

Второй способ подразумевает реализацию процедур генерации First и Next. Процедура First обеспечивает установку начального элемента. Процедура Next генерирует следующий элемент.

Нумерация рассматривается как процесс упорядочения множества комбинаторных объектов. Если некоторое множество комбинаторных объектов упорядочено, то номер позиции некоторого объекта в этом упорядочении будет являться порядковым номером (rank). Соответствующий алгоритм или процедуру обычно называют Rank.

Процесс генерации комбинаторного объекта (unranking) по его номеру (рангу) является обратным процессу нумерации. Соответствующий алгоритм или процедуру называют Generate.

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

Следует отметить, что, наряду с термином «генерация», в некоторых публикациях и переводах используется термин «порождение» [10]. Автор отдает предпочтение термину «генерация», подчеркивая тем самым технический и прикладной характер процесса получения элементов комбинаторных множеств.

Методы и алгоритмы комбинаторной генерации приобретают важное научное и практическое значение в следующих отраслях: в программировании, в проектировании информационных систем и баз данных [11-13], в теории кодирования и сжатия информации [14, 15] , в химии, при исследовании различных химических структур [16, 17], в биологии при моделировании ДНК-структур [18, 19].

В общем случае, для получения процедур генерации и нумерации комбинаторного множества необходимо задать биективное отображение [9]:

Generate : Nm Ат: где - Nm конечное подмножество натуральных чисел; Ат - комбинаторное множество. Тогда обратное отображение задает процедуру нумерации:

Rank : Ат Nm.

На рис. 1 показаны основные элементы и схема взаимодействия алгоритмов Generate и Rank. Алгоритм Generate на основании числа пит £ Nm и некоторого описания D создает элемент а £ Ат. Алгоритм Rank производит обратное действие, на основании а £ Ат и некоторого описания D, формирует номер пит £ Nm.

Методы построения алгоритмов генерации и нумерации комбинаторных множеств самые разнообразные и зависят от конкретного рассматриваемого комбинаторного объекта. Следует отметить, что сравнительно недавно появились методы, претендующие на некоторую универсальность применения. Так, Э.Ренгольд, Ю.Нивергельт, Н.Део для генерации комбинаторных

Рисунок 1. Основная схема алгоритмов генерации и нумерации элементов комбинаторных множеств объектов предложили использовать метод, основанный на поиске с возвращением (backtracking) [7], дальнейшее развитие этого метода предложено Д.Крехером и Д.Стинсоном в работе «Combinatorial Algorithm: Generation, Enumeration and Search» [9]. Однако во многих случаях этот метод используется только для последовательной генерации всех объектов.

Другим методом, претендующим на некоторую универсальность, является метод ECO (Enumeration Combinatorial Object), предложенный Бар-гутччи, Дел Лунго, Пергола и Пинзани [20, 21], в основе которого лежит использование рекурсивных правил:

1) комбинаторные объекты размера п + 1 строятся из объекта n-го размера;

2) каждый объект п 4-1 размера имеет одного родителя n-го размера.

По этим правилам строится генерирующее дерево, в узлах которого записано число объектов. Данный метод хорошо зарекомендовал себя для перечисления большого числа комбинаторных объектов [22]. Для генерации комбинаторных объектов используется идея перехода от объекта размером п к объекту размером п +1. Примером может служить алгоритм последовательной генерации некоторых классов полимино [23]. Число узлов в дереве пропорционально числу комбинаторных объектов рассматриваемого класса.

Следует отметить также метод, предложенный Ф.Флажоле, Б.Катсемем и П.Циммераманом [24] для построения алгоритмов генерации элементов комбинаторных множеств со случайным выбором, который развит К. Мар-тинец и X. Мулинеро для построения алгоритмов последовательной генерации, нумерации и генерации по номеру [25-27]. Этот метод базируется на построении соответствий между производящими функциями, описывающими мощности комбинаторных множеств, и некоторыми операциями, определенными над этими множествами. Кроме известных операций над множествами + и х, вводятся специальные операции Seq, Set, PSet, Circle. Например, операция Seq представляет собой следующее выражение:

Seq(A) = е + Л+(ЛхЛ) + (ЛхЛхЛ)-1---

Если множество А конечно для всех конечных множеств Seq(A), то можно задать алгоритмы комбинаторной генерации. Основные недостатки данного метода:

1. Невозможно воспользоваться методом для построения алгоритмов комбинаторной генерации, если нет производящей функции.

2. Если производящая функция имеется, то ее надо выразить в терминах операций {+, x,Seq, Set, Pset}, что является довольно сложной задачей.

3. Не учитывается рекурсивный характер комбинаторного множества.

Для нумерации элементов комбинаторных множеств Б. Я. Рябко предложил метод, основанный на представлении комбинаторного объекта в виде битовой последовательности [14, 28], однако получение битового представления элементов комбинаторного множества не приводится. В.А. Амелькин предложил метод нумерационного кодирования для сжатия информации в задачах [15].

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

Цели и задачи

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

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

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

Основные задачи:

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

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

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

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

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

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

7. Создать и внедрить прикладное программное обеспечение для:

- информационных систем, основанных на реляционных базах данных;

- систем идентификации и прослеживаемости изделий;

- систем построения и использования генераторов тестовых заданий;

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

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

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

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

1. Разработана новая методология построения алгоритмов комбинаторной генерации, основанная на применении деревьев И/ИЛИ.

2. Впервые получено:

1) Если для некоторого множества комбинаторных объектов имеется схема рекурсивной композиции построения дерева И/ИЛИ, то существует pell курсивная функция алгебры {N, +, х, .ft}, вычисляющая мощность данного множества.

2) Если мощность комбинаторного множества задана в виде функции /(п) алгебры {N, +, х, R}, то для такого множества можно однозначно построить алгоритм последовательной генерации и алгоритмы генерации элемента по номеру и нумерации элемента.

3. Для построения алгоритмов последовательной генерации элементов комбинаторных множеств разработан новый формализм в виде автомата, представляющего четверку {В, N, pFirst, PNext}, где В- начальный магазинный символ, N- множество магазинных символов; правила PFirst Для операции First, правила P^ext Для операции Next. Разработан алгоритм построения автомата по схеме рекурсивной композиции деревьев И/ИЛИ, получено выражение для определения временной сложности алгоритмов последовательной генерации.

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

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

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

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

Разработанная методология проектирования и анализа алгоритмов комбинаторной генерации с применением деревьев И/ИЛИ, полученные алгоритмы и программы комбинаторной генерации обеспечивают:

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

2.Решение задач кодирования. Если для некоторого множества объектов строится дерево И/ИЛИ, то алгоритм Rank будет кодировать объект, а алгоритм Generate - декодировать.

3.Решение задач сжатия информации. Если для некоторого множества объектов построить дерево И/ИЛИ, то алгоритм Rank будет производить сжатие объекта, а алгоритм Generate - восстанавливать объект. Причем, если при передаче объектов по каналам связи само дерево И/ИЛИ не передавать (т.е. дерево И/ИЛИ имеется на стороне приемника и на стороне передатчика), то можно получить уменьшение объемов передаваемой информации.

4.Решение задач тестирования. Если для множества тестовых примеров построить дерево И/ИЛИ, то можно, используя алгоритм Generate, строить тестовые выборки. Особенно это касается задач тестирования программ с некоторым входным проблемно-ориентированным языком.

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

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

7. Для реляционных баз данных:

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

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

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

1. Для любой рекурсивно-примитивной функции можно взаимно-однозначно поставить в соответствие схему рекурсивной композиции дерева терма.

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

1) алгоритм вычисления мощности данного множества;

2) алгоритм последовательной генерации элементов этого множества;

3) алгоритм генерации элемента множества по номеру;

4) алгоритм нумерации элементов этого множества;

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

3. Рекуррентные и закрытые формулы для числа разбиений и композиций натурального числа п с ограничениями на части Х{ ^ т. Выражения производящих функций, треугольник разбиений.

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

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

Достоверность

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

Внедрение

Основные результаты диссертационной работы внедрены и используются:

1. На ОАО ТПО «Контур», при создании системы идентификации и проел е-живаемости изделий телекоммуникационной механики и узлов структурных кабельных систем.

2. На ЗАО НПФ «Сибнефтекарт», при создании и тиражировании:

- Автоматизированной системы управления технологическими процессами и безналичными расчетами на автозаправочных станциях и комплексах « Сибнефтекарт-АЗ С ».

- Автоматизированной системы централизованного ведения и прогрузки на АЗС справочников товаров и контрагентов, приема, накопления и обработки сменных отчетов и протоколов с АЗС - «Сибнефтекарт-Офис».

- Программно-аппаратного комплекса эмиссии карт и учета транзакций процессингового центра «Сибнефтекарт-ПЦ»

3. На ООО НПФ «Информационные системы безопасности» при разработке архива удостоверяющего центра.

4. В дистанционной технологии обучения студентов: Томского государственного университета систем управления и радиоэлектроники по 38 специальностям, в Кемеровском технологическом институте пищевой промышленности по трем специальностям, в Югорском государственном университете по двум специальностям. Система проведения контрольных работ и экзаменов передана в отраслевой фонд алгоритмов и программ Министерства образования Российской Федерации (свидетельство регистрации №3524). Инструментальная система «Фея-3» передана в отраслевой фонд алгоритмов и программ Министерства образования Российской Федерации (свидетельство регистрации №3510). Пакет генераторов по дисциплине «Высшая математика» для проведения экзаменов передан в отраслевой фонд алгоритмов и программ Министерства образования Российской Федерации (свидетельство регистрации №3536).

5. В учебном процессе Томского университета систем управления и радиоэлектроники.

Личный вклад автора

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

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

Основные результаты диссертации были доложены на международных, всесоюзных, всероссийских, региональных конференциях и семинарах. В том числе: на Международной конференции «Application of the Conversion Research Results for International Cooperation, SIBCONVERS '99» Томск, 1999; на Международной научно-практической конференции «Градоформи-рующие технологии XXI века», Москва, 2001; на второй Международной конференции «2-nd WBLE Conference» 2001, Lund University, Швеция; на Международной методической конференции «Новые информационные технологии в университетском образовании», Кемерово, 2002; на Всероссийской конференции «Современная образовательная среда», Москва, 2002; на Международной научно-методической конференции, Новосибирск, 2003; на Международной научно-методической конференции «Развитие системы образования в России XXI века», Красноярск, 2003; на Международном конгрессе «Информационные технологии в образовании», 2003; на Всероссийской конференции «Телематика», Санкт-Петербург, 2003; на III Всероссийской научно-практической конференции-выставки «Единая образовательная информационная среда: проблемы и пути развития», Омск, 2004; на Международной научно-методической конференции «Инновационные технологии организации обучения в техническом ВУЗе: на пути к новому качеству образования», Пенза, 2004; на Всероссийской научно-методической конференции «Телематика», Санкт-Петербург, 2007; Международной конференции «Образование и виртуальность», Ялта, 2007; на Всероссийской конференции «Системы автоматизации в образовании, науке и производстве», Новокузнецк, 2007; на Всероссийской конференции «Телематика», Санкт-Петербург, 2008; на Международной научной конференции «Космос, астрономия и про-граммирование[Лавровские чтения]», Санкт-Петербург, 2008; на 9 Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография», Омск, 2009; на городском алгебраическом семинаре Сибирского федерального университета, Красноярск, 2010.

Публикации

Результаты диссертационной работы опубликованы в 104 научных работах, в том числе в четырех монографиях, в пяти учебных пособиях и в 17 статьях журналов, рекомендованных ВАК РФ для опубликования научных I результатов диссертаций на соискание ученой степени доктора наук.

Выводы ч

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

2. Программное обеспечение реализованное в технологиях: библиотека шаблонов для представления деревьев И/ИЛИ, программный СОМ-сервер, язык программирования GIL, библиотека шаблонов генераторов комбинаторных множеств, обеспечивает эффективное исследование, разработку и внедрение генераторов комбинаторных множеств.

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

- снижение уровня плагиата среди студентов;

- отсутствие списков правильных ответов;

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

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

4. Применение программного обеспечения, основанного на разработанном методе для информационных систем обеспечивает:

1) экономное представление реляционных баз данных;

2) возможность разделения реляционной базы данных на две составляющие, каждая из которых не раскрывает содержащеюся информацию в базе данных;

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

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

1) минимальную разрядность номера при заданном множестве классификаторов;

2) возможность по номеру получить полный набор характеристик и деталей узлов телекоммуникационной механики и элементов структурированных кабельных систем;

3) в базе данных на изделия ПО «Контур» хранить только их идентификационные номера.

Заключение

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

1. Показано, что между функцией /(тг), принадлежащей алгебре А = {N, +, х, R}, где N -множество натуральных чисел, R - оператор примитивной рекурсии, и схемой рекурсивной композиции Rn(dg, dh) деревьев И/ИЛИ существует взаимно-однозначное соответствие, которое обеспечивает следующие свойства:

- при фиксации параметра п = п* по схеме рекурсивной композиции Rn* строится дерево И/ИЛИ, число вариантов которого равно значению /(п*);

- если для некоторого комбинаторного множества получена схема рекурсивной R^, то мощность этого множества выражается функцией /(п);

- между комбинаторным множеством, мощность которого равна f(n*) и множеством вариантов дерева И/ИЛИ Rсуществует биекция.

2. Если для некоторого комбинаторного множества Еп существует дерево И/ИЛИ Rn, то:

- однозначно строится автомат последовательной генерации{В, M, РFirst, PNext}, где - начальный магазинный символ, М- множество магазинных символов, PFirst - правила для операции First, P^cxt - правила для операции Next. Временная сложность алгоритма последовательной генерации равна ук

Op(z) = <

Ei=i Op{si) + 1, для ИЛИ-узла; д+1 ^Ог)] + Op(sk) + 1, для И-узла;

1, для листа.

- однозначно строится алгоритм генерации элемента комбинаторного множества по номеру.

- одназначно строится алгоритм нумерации элементом комбинаторного множества.

- временная сложность алгоритмов генерации по номеру и нумерации равна:

Орг = <

Г=1 [(пг - ¿К + Ор3], для ИЛИ-узла; К - 1 + ТЛ-1 • для И-узла; О, для листа.

- число эквивалентных деревьев и соответственно различных последовательностей генерации и нумерации элементов комбинаторного множества выражается следующей рекуррентной формулой: = I ч к\ П?=1 «¡0)> Для ИЛИ-узла, Пг^!^, для И-узла, 1, для листа.

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

1) Рекуррентная формула

Рт(.п) =рт{п- т) +Рт+\{п).

2) Производящая функция оо • к

Ц(1 - х1)-1 = 1 + ^хтк Д(1 - х1)-\ г=т г=1

3)рекуррентные формулы з(к, га, п) = <

0,

1,

3-т + 1],

I (п—Зто+З)2 —4 |

I- 12 -Ь п < кт, & = 1, к = 2 к = 3

Е[=0 — 1, 777., гг — 777, — Ы), П > кт. зр(к,п) = <

1,

О,

71 — 1, № с = О п < к к = 1, к = 2

ЕЙ ]0зр(к-1,п-2-Ы), X

Число разбиений ¿/¡¡(п) числа п на & позиций равно 1,п). Число разбиений рт{п) числа п на части не меньшие ттг равно

1 — 1

РшН = ^ ¿(/г, 777,77).

Число разбиений числа 7г.

Л5=1 Ш р(п) =

А;=1

Сумма разбиений чисел от 0 до п равна зр(п,п).

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

4. Эффективное применение разработанных методов убедительно показано на классических комбинаторных множествах: классов перестановок, множеств, описываемых числами Фибоначчи, Каталана, Стирлинга, Сильвестра.

5. Разработаны схемы рекурсивных композиций деревьев И/ИЛИ для построения алгоритмов генерации и нумерации классов деревьев: двоичных деревьев высотой не более п, заданным числом узлов и высотой, полных двоичных деревьев, АВЛ-деревьев, 2-3-деревьев, 2-3-4-деревьев, красно-черных деревьев, цветных двоичных деревьев, деревьев операций.

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

- алгоритмы генерации ¿-арных и полных ¿-арных деревьев с заданным числом узлов;

- выдвинута гипотеза, что для разложений справедлива формула: г=1 ^ ' 1 1)п +& + Г где ¿- число частей разложения числа п, ¿ > 2, Х{ = п, к-смещение относительно большего разложения (£ + к)]

- алгоритм генерации упорядоченных корневых деревьев;

- функция, связывающая номер композиции и значение числа упорядоченных корневых деревьев относительно процедуры полного разбиения для данной композиции * = т г = < Т(г- г > 0. [к^(г')] - ^(2^(^+1 — г — 1)] — 1, 0 < г < 2^8^+1, где к — < - алго [1оё(г)], * = 1. ритм и функция для генерации неупорядоченных корневых деревьев относительно процедуры полного разбиения, основанного на разбиениях натурального числа п.

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

8. Разработано инструментальное программное обеспечение направленное на:

1) проектирование и исследование алгоритмов комбинаторной генерации;

2) создание генераторов тестовых заданий для систем контроля знаний студентов;

3) проектирование программных систем сжатия и кодирования в автоматизированных и информационных системах. Данное программное обеспечение внедрено на производственном объединении «Контур», на ЗАО НПФ «Сибнефтекарт», в дистанционные технологии обучения студентов: Томского государственного университета систем управления и радиоэлектроники по 38 специальностям, в Кемеровском технологическом институте пищевой промышленности по трем специальностям, в Югорском государственном университете.

1. Колмогоров, А. Н. Три подхода к определению «количество информации» / А. Н. Колмогоров // Проблемы передачи информации. — 1965. — Т. 1, № 1.-С. 3-11.

2. Чейтин, Г. Пределы доказуемости / Г. Чейтин // В мире науки. — 2006. № 6. - С. 38-45.

3. Успенский, В. А. Теория алгоритмов: основные открытия и приложения / В. А. Успенский, А. Л. Семенов. — М.: Наука, 1987.— 288 с.

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

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

6. Nijenhuis, A. Combinatorial Algorithms for Computers and Calculators / A. Nijenhuis, H. Wilf. Academic Press, 1978. - 302 pp.

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

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

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

10. Шень, А. Программирование: теоремы и задачи / А. Шень. — М.: МЦ-НМО, 1995.- 262 с.

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

12. Кручинин, В. В. Подходы с созданию защищенного архива на основе разделения секрета / В. В. Кручинин, А. А. Шелупанов // Доклады ТУСУР. 2008. -К0-2 часть 1. - С. 67-72.

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

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

15. Амелъкин, В. А. Методы нумерационного кодирования / В. А. Амель-кин. — Новосибирск: Наука, 1986. — 160 с.

16. Polya, G. Combinatorial enumeration of groups, graphs, and chemical compounds / G. Polya, R. Read. — New York, NY, USA: Springer-Verlag New York, Inc., 1987.- 148 pp.

17. Химические приложения топологии и теории графов.— М.: Мир, 1987. 560 с.

18. Колчанов, Н. А. Моделирование биологической эволюции: Регулятор-ные генетические системы и кодирование сложности биологической организации / Н. А. Колчанов, В. В. Суслов, К. В. Гунбин // Вестник ВОГиС. 2004. - Т. 8, К0- 2. - С. 86-99.

19. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: информатика и вычислительная биология / Д. Гасфилд; Под ред. И. В. Романовский. — Спб.: Невский Диалект. БХВ-Петербург, 2003. — 654 с.

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

21. Exhaustive generation of combinatorial objects by eco / S. Bacchelli, E. Barcucci, E. Grazzini, E. Pergola // Acta Inf. 2004. — Vol. 40, no. 8. — Pp. 585-602.

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

23. 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. - T. 11, № 1. - C. 46.

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

25. 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.

26. Molinero, X. Ordered Generation of Classes of Combinatorial Structures: Ph.D. thesis / University Politecnical of Catalunya. — http://www.lsi.upc.edu/molinero/homepublications.html]. — 181 pp.

27. Martinez, С. Generic algorithms for the generation of combinatorial objects / C. Martinez, X. Molinero // Mathematical Foundations of Computer Science 2003. — Berlin: Springer, 2004. — Vol. 2747 of Lecture Notes in Computer Science. — Pp. 572-581.

28. Потапов, В. Обзор методов неискажающего кодирования дискретных источников / В. Потапов // Дискретный анализ и исследование операций. 1999. - Т. 6, № 4. - С. 49-91.

29. Стенли, Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции / Р. Стенли. — М.: Мир, 2005.— 767 с.

30. Кнут, Д. Искусство программирования."!!. Основные алгоритмы / Д. Кнут. М.: И.Д.Вильямс, 2007. - 720 с.

31. Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев. — М.: Наука, 1985. — 352 с.

32. Ахо, А. Теория синтаксического анализа, перевода и компиляции / А. Ахо, Д. Ульман. — М.: Мир, 1978. — 487 с.

33. Кнут, Д. Искусство программирования.Т2. Получисленные алгоритмы / Д. Кнут. М.: И.Д.Вильямс, 2007. - 832 с.

34. Кнут, Д. Искусство программирования.ТЗ. Сортировка и поиск / Д. Кнут. М.: И.Д.Вильямс, 2007. - 832 с.

35. Бердж, В. Методы рекурсивного программирования / В. Бердж. — М.: Машиностроение, 1983. — 248 с.

36. Кручинин, В. В. Рекурсивные композиции деревьев и их свойства / В. В. Кручинин // Доклады ТУСУР.- 2007.- Т. 16.- С. 74-80.

37. Канторович, JI. В. Об одной математической символике, удобной при проведении вычислений на машинах / JL В. Канторович // Доклады АН СССР. 1957. - Т. ИЗ, № 4. - С. 738-741.

38. Канторович, Л. В. О проведении численных и аналитических вычислений на машинах с программным управлением / J1. В. Канторович // Изв. АНАрмССР, сер. физ.-мат. наук. — 1957. — Т. 10, № 2. С. 3-16.

39. Мальцев, А. И. Алгоритмы и рекурсивные функции / А. И. Мальцев. — М.: Наука, 1986. — 368 с.

40. Клини, С. К. Введение в метаматематику / С. К. Клини. —- М.: ИЛ, 1957.- 526 с.

41. 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.

42. Нилъсон, H. Принципы искусственного интеллекта / H. Нильсон. — М.: Радио и связь, 1985. — 380 с.

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

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

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

46. Вратко, И. Программирование на языке Пролог для искусственного интеллекта / И. Вратко. — М.: Мир, 1990.— 560 с.

47. Flajolet, P. Analytic Combinatorics / P. Flajolet, R. Sedgewick. — Cambridge University Press, 2009. — 824 pp.

48. Gardy, D. And/or tree probabilities of boolean function // Discrete Mathematics and Theoretical Computer Science. — 2005. — Pp. 139-146.

49. And/or trees revisited / B. Chauvin, P. Flajolet, D. Gardy, B. Gittenberg-er // Comb. Probab. Comput. 2004. - Vol. 13, no. 4-5. - Pp. 475-497.

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

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

52. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. — М.: Мир, 1979. — 536 с.

53. Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. М.: Мир, 1987. - 119 с.

54. Гашков, С. В. Системы счисления и их применение / С. Б. Гаш-ков. — М.: МЦНМО, Библиотека «математическое просвещение», №29, 2004. 52 с.

55. Валъковский, В. А. Синтез параллельных программ и систем на вычислительных моделях / В. А. Вальковский, В. А. Малышкин. — Новосибирск: Наука, 1988. — 128 с.

56. Akl, S. Parallel computation: models and methods / S. Akl. — Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1997.

57. Тимошевская, H. О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования управляющих систем / Н. Тимошевская // Известия Томского политехнического университета. — 2004. — Т. 307, № 6. — С. 18-20.

58. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. — М.: Мир, 1985. — 510 с.

59. Кручинин, В. В. Представление множеств деревьями и/или / В. В. Кручинин // Доклады Томского университета систем управления и радиоэлектроники. — 2008. — № 2(17). — С. 107-112.

60. Виленкин, Н. Я. Комбинаторика / Н. Я. Виленкин. — М.: Наука, 1969. 328 с.

61. Сачков, В. Н. Комбинаторные методы дискретной математики / В. Н. Сачков. М.: Наука, 1997. - 317 с.

62. Волченская, Т. В. Компьютерная математика: Часть 1. Теория множеств и комбинаторика / Т. В. Волченская, В. С. Князьков. — Пенза: Изд-во Пенз. гос. ун-та, 2003. — 80 с.

63. Bender, Е. Foundations of Combinatorics With Applications / E. Bender, S. Gill.— Dover, Mineola Date Published: Williamson Edition, 2006.480 pp.

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

65. Knuth, В. Generating All Combinations and Partitions / D. Knuth.

66. Прасолов, В. В. Эллиптические функции и алгебраические уравнения / В. В. Прасолов, Ю. П. Соловьев. — М.: Изд-во «Факториал», 1997.— 288 с.

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

68. Риордан, Д. Введение в комбинаторный анализ / Д. Риордан.— М.: Изд-во ИЛ, 1963. 287 с.

69. Воробьев, Н. Н. Числа Фибоначчи / Н. Н. Воробьев.— М.: Наука, 1978. 141 с.

70. Холл, М. Комбинаторика / М. Холл. — М.: Наука, 1970. — 414 с.

71. Эндрюс, Г. Теория разбиений / Г. Эндрюс. — М.: Наука, 1982. — 256 с.

72. Гульден, . Перечислительная комбинаторика / . Гульден, Д. Джексон.- М.: Наука, 1990.- 504 с.

73. Sloane, A. The on-line encyclopedia of integer sequences / A. Sloane // http://www. research, att. com/ njas/sequences.

74. Кузьмин, О. В. Обобщенные пирамиды Паскаля и их приложения / О. В. Кузьмин. — Новосибирск: Наука, 2000. — 294 с.

75. Кручинип, В. В. Алгоритмы генерации и нумерации композиций и разбиений натурального числа п / В. В. Кручинин / / Доклады ТУ СУ Р. — 2008. № 2(17). - С. 113-119.

76. Стенли, Р. Перечислительная комбинаторика / Р. Стенли. — М.: Мир, 1990. 440 с.

77. Sedgewick, R. Permutation generation methods / R. Sedgewick // ACM Сот-put. Surv. — 1977. — Vol. 9, no. 2. — Pp. 137-164.

78. Bauslaugh, B. Generating alternating permutations lexicographically /

79. B. Bauslaugh, F. Ruskey // BIT. 1990. - Vol. 30. - Pp. 17-26.

80. Myrvold, W. Ranking and unranking permutations in linear time / W. Myrvold, F. Ruskey // Information Processing Letters.— 2000.— Vol. 79. Pp. 281-284.

81. Stanley, R. Catalan Addendum / R. Stanley. — www-math.mit.edu/ rstan/ec/catadd.pdf.

82. Гарднер, M. Числа каталана / M. Гарднер // Квант. — 1978. № 7.1. C. 20-26.

83. Ферма, П. Исследования по теории чисел и диофантову анализу / П. Ферма. М.: Наука, 1992.

84. Makinen, Е. Generating random binary trees, a survey. / E. Makinen // Information Sciences—Informatics and Computer Science. — 1999. — April. Vol. 115, no. 1-4. - Pp. 123 - 136.

85. West, J. Generating trees and the Catalan and schroder numbers // 247262. Department of Mathematics, Stockholms Universitet, S-106 91.— 1995. P. 146.

86. Pallo, J. M. Lexicographic generation of binary unordered trees. / J. M. Pallo 11 Pattern Recognit. Lett. 1989. - Vol. 10, no. 4. - Pp. 217221.

87. Kubicka, E. An efficient method of examining all trees. / E. Kubicka // Comb. Probab. Comput. 1996. - Vol. 5, no. 4. - Pp. 403-413.

88. Sawada, J. Generating rooted and free plane trees / J. Sawada // ACM Trans. Algorithms.— 2006. — Vol. 2, no. 1. — Pp. 1-13.

89. Constant time generation of free trees. / R. A. Wright, B. Richmond,

90. A. Odlyzko, B. D. McKay // SIAM J. Comput.- 1986.- Vol. 15.-Pp. 540-548.

91. Т., В. Constant time generation of rooted trees / В. Т., H. S. M. 11 SIAM J. Computing. 1980. - no. 9. - Pp. 706-712.

92. Кручинин, В. В. Комбинаторика композиций и ее приложения /

93. B. В. Кручинин. — Томск: Изд-во «В-Спектр», 2010. — 156 с.

94. Aho, А. V. Some doubly exponential sequences / A. V. Aho, N. J. A. Sloane // Fib. Quart. 1973. - no. 11,- Pp. 429-437.

95. Адельсон-Вельский, Г. M. Один алгоритм организации информации / Г. М. Адельсон-Вельский, Е. М. Ландис // ДАН СССР. 1962. - Vol. 146, по. 2. - Pp. 263-266.

96. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман. — М.: Изжательский дом "Вильяме 2000. — 384 с.

97. Bayer, R. Symmetric binary -trees / R. Bayer // Data Structures and Maintenance Algorithms. Acta Informat. — 1972. — Vol. 1. — Pp. 290-306.

98. Грэхем, P. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник. — М.: Мир, 1998. — 703 с.

99. Stanley, R. Hipparchus, plutarch, Schroder, hough / R. Stanley // Amer. Math. Monthly. 1997. - no. 104. - Pp. 344-350.

100. Кузьмин, О. В. Числа Шредера, их обобщения и приложения / О. В. Кузьмин, Т. Г. Тюрнева // Асимптотические и перечислительные задачи комбинаторного анализа. — Иркутск: Ирк-й Гос. ун-т, 1997. — Сб. науч. тр. С. 117-125.

101. Riordan, J. Enumeration of plane trees by branches and endpoints / J. Ri-ordan // J. Comb. Theory, Ser. A. ~ 1975. Vol. 19, no. 2. - Pp. 214-222.

102. Chen, W. Y. C. Riordan paths and derangements / W. Y. C. Chen, E. Y.-P. Deng, L. L. M. Yang // Discrete Mathematics.- 2008.- Vol. 308, no. 11.-Pp. 2222-2227.

103. Bernhart, F. R. Catalan, Motzkin, and Riordan numbers. / F. R. Bernhart // Discrete Mathematics. 1999.-Vol. 204, no. 1-3.- Pp. 73-112.

104. Kemp, R. Balanced ordered trees / R. Kemp // Random Structures and Algorithms. 1994. - Vol. 5, no. 1. - Pp. 99-121.

105. Оттер, P. Число деревьев / P. Оттер // Перечислительные задачи комбинаторного анализа / Под ред. Г. П. Гаврилова. — М.: Мир, 1979. — С. 139-159.

106. Delest, М. Algebraic languages: A bridge between combinatorics and computer science. — 1994.

107. Autebert, J. Context-free languages and pushdown automata / J. Autebert, J. Berstel, L. Boasson // Handbook of Formal Languages / Ed. by A. Salomaa, G. Rozenberg. — Berlin: Springer-Verlag, 1997. — Vol. 1, Word Language Grammar. — Pp. 111-174.

108. Пентус, A. E. Теория формальных языков / A. E. Пентус, M. P. Пен-тус. М.: Изд-во МГУ, 2004. - 80 с.

109. Ruskey, F. The Combinatorial Object Server / F. Ruskey. — http://www.theory.csc.uvic.ca/ cos.

110. Flajolet, F. Computer algebra libraries for combinatorial structures / F. Flajolet, B. Salvey //J. Symbolic Computation. — 1995.— no. 20.— Pp. 653-671.

111. Greene, D. H. Labelled Formal Language and Their Uses: Phd thesis / Computer Sci. Dept. — 1983. — 155 pp.

112. Бокс, Д. Сущность технологии СОМ. Библиотека программиста / Д. Бокс. Спб.: Питер, 2001. - 400 с.

113. Мейрс, С. Эффективное использование STL. Библиотека программиста / С. Мейрс. СПб.: Питер, 2003. - 224 с.

114. Musser, D. R. Generic programming // ISAAC '88: Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation. London, UK: Springer-Verlag, 1989. - Pp. 13-25.

115. Тиктов, А. В. Система построения генераторов комбинаторных множеств, на основе деревьев И/ИЛИ: диссертация на звание к.т.н. / Томский университет систем управления и радиоэлектроники. — Томск, 2010.- 108 с.

116. Кручинин, В. В. Язык описания генераторов комбинаторных множеств / В. В. Кручинин, А. В. Титков // Известия Томского политехнического университета. — 2008. — Vol. 312.

117. Титков, А. Применение системы программирования gil для генерации тестовых заданий // Материалы международной научно-методическойконференции «Современное образование» / ТУСУР. — Томск: ТУСУР, 2009. С. 178-179.

118. Титков, А. Реализация библиотеки шаблонов алгоритмов комбинаторной генерации средствами stl // Материалы международной научной конференции «Космос, астрономия и программирование» / ТУСУР. — Томск: ТУСУР, 2009. С. 309-311.

119. Аммераалъ, Л. STL для программистов на С++ / JI. Аммерааль. — М.: ДМК, 1999.- 240 с.

120. ISO/IEC 14882:1998 Programming Languages С++. - New-York: ANSI, 1998.- 748 pp.

121. Основы информационной безопасности / Е. Б. Белов, В. П. Лось, Р. В. Мещеряков, А. А. Шелупанов.— М.: Горячая линия—Телеком, 2006. 544 с.

122. Кручинин, В. В. Программные генераторы (обзор) / В. В. Кручинин // Доклады ТУСУР. 2004. - № 2(10). - С. 64-68.

123. Башмаков, А. И. Разработка компьютерных учебников и обучающих систем / А. И. Башмаков, И. А. Башмаков. — М.: Информационно-издательский дом «Филинъ», 2003. — 616 с.

124. Кручинин, В. В. Разработка компьютерных учебных программ / В. В. Кручинин, — Томск: Изд-во Том. ун-та, 1998. — 211 с.

125. Компьютерный учебник «тмцдо. высшая математика-1» / С. И. Борисов, А. В. Долматов, В. В. Кручинин, В. А. Томиленко // Открытое образование. 2004. - № 3. - С. 12-17.

126. Жуков, Д. О. Тестирование заданий по физике с помощью интеллектуальных генераторов / Д. О. Жуков // Информационные ресурсы России. — 2004.

127. Кручинин, В. В. Генераторы в компьютерных учебных программах / В. В. Кручинин. Томск: Изд-во Том^ ун-та, 2003. - 200 с.

128. Кручинин, В. В. Применение генераторов в компьютерных технологиях обучения / В. В. Кручинин, С. И. Борисов // Интеграция образования. 2004. - № 4. - С. 116-121. ^

129. Кручинин, В. В. Модели и алгоритмы генерации задач в компьютерном тестировании / В. В. Кручинин, Ю. В. Морозова // Известия Томского политехнического университета. А- 2004. — № 5. — С. 127131. \

130. Кручинин, В. В. Метод перечисления множества информационныхобъектов, заданных деревом и/или / В. В. Кручинин У/ Вестник Томского государственного педагогического университета. — 2004. — № 6(43).-С. 85-89. \

131. Жуков, В. К. Новые подходы к организации контроля знаний в вузе / В. К. Жуков, В. В. Кручинин // Известия МАИ ВШ.-Х 2004.- № 2(28).-С. 113-118. \

132. Швандар, В. А. Стандартизация и управление качеством продукции / В. А. Швандар, В. П. Панов, Е. М. Купряков. М.: ЮНИТИ-ДАНА, 2000. - 487 с.