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

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

В работе «Три подхода к определению понятия «Количество информации» академик А. Н. Колмогоров предложил в качестве меры сложности «минимальную длину программы 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⁸^+1, где к — < - алго [1оё (г)], * = 1. ритм и функция для генерации неупорядоченных корневых деревьев относительно процедуры полного разбиения, основанного на разбиениях натурального числа п.

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

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

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

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

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