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

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

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

Введение

Глава 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 специальностям, в Кемеровском технологическом институте пищевой промышленности по трем специальностям, в Югорском государственном университете.

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

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