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

• Автор: Кручинин, Владимир Викторович
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Томск
• Количество страниц: 395 с. : ил.

Содержание
Введение .

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

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

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

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

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

Глава 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. Деревья со степенью узлов больше 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), I = 1, к, то можно получить рекурсивную функцию для числа вариантов дерева И/ИЛИ. Для этого но дереву (1д строится функция д(х), а для - функция /і(х). Затем записывается рекурсивная схема функции /(п) = Я(<;,/1). Рассмотрим пример. Пусть дана схема рекурсивной композиции (см. С(п),С(п)), п > 0. Тогда по <1д и с1ь строим /Г-деревья и получаем функции д(х) = 1, И(х) — 1 4- х * х. Дп) • /(п), п > 0. Теперь покажем, что если Дп) Є A(N, 4, x. Дп) Є Л. Ьі Є Л Отсюда д(п) € Л. Дп) = ^СЦ/1(П) - /(ТЬ). О, тогда ai — 1 > 0 G N. G Л. Учитывая, что Дп 4- 1) > Дп) и ДО) > 0, то ^(n+ 1) G Л. Поскольку д(п) G Л, то, в силу предыдущего, р(п + 1) = д(п + 1) - д(п) G Л. G N. Следовательно, если некоторое множество представлено как разность двух множеств, мощности которых описываются функцией / G Л, то для такого множества также можно построить схему рекурсивной композиции деревьев И/ИЛИ. Рассмотрим задачу подсчета числа вариантов в дереве И/ИЛИ. Для листа дерева число вариантов равно единице. Предположим, что для каждого сына Si узла 2 известно число вариантов в соответствующем поддереве и равно Тогда число вариантов для ИЛИ-узла будет равно сумме числа вариантов его сыновей, поскольку в вариант включится только один сын ИЛИ-узла. Для И-узла все сыновья входят в вариант, тогда общее число вариантов для И-узла будет равно произведению числа вариантов для всех его сыновей. Подсчитав значение функции для корня дерева, можно получить общее число вариантов, имеющихся в данном дереве. При этом будет подсчитано количество вариантов для каждого узла всего дерева. Пример подсчета вариантов показан на рис. Алгоритм вычисления числа вариантов. Введем обозначения 2 - текущий узел; кг - число сыновей узла г; г. Count [z. Count (z. Алгоритм СоипЦг) носит рекурсивный характер. Число операций пропорционально числу вызовов алгоритма, поскольку каждый узел дерева просматривается один раз, то вычислительная сложность алгоритма пропорциональна числу узлов в дереве И/ИЛИ. Для подсчета числа вершин в дереве И/ИЛИ можно воспользоваться простыми правилами: число вершин в дереве равно сумме чисел вершин каждого поддерева сына корня плюс единица; если вершина является листом, то это число равно 1. N0dez і (1. Nodez - число вершин в поддереве узла z,nz - число сыновей узла г. Leafz = { і=і (1. Если за,дана схема рекурсивной композиции дерева И/ИЛИ, то выражение формулы числа вершин находится из рекурсивной формулы подсчета числа вариантов следующим образом: подсчитываем число вершин в дереве dg, тогда Node(0) = Nodeg, затем в функции h(x) все операции умножения заменяем на сложение, подсчитываем число сложений и прибавляем к полученному выражению, это выражение обозначим как функцию h+(x) и затем записываем рекурсивную функцию Node(n). Рассмотрим пример. Соответственно,д(х) = 1,/г(ж) = 1 4- х • х. Тогда функция И+(х) = 1 -|- х 4-я 4-2. Используя схему рекурсивной композиции для дерева И/ИЛИ, можно получить функцию для подсчета числа листьев. В нашем случае (см. Рассмотрим свойства вариантов в конкретном дереве И/ИЛИ. Вариант дерева И/ИЛИ будем называть максимальным, если у него максимальное число вершин. Алгоритм подсчета максимального числа вершин в варианте аналогичен алгоритму подсчета числа вариантов. Обозначим через Дг максимальное число вершин в варианте в поддереве вершины г. Тогда если г- лист, то д2 = 1. Ьеа/(ть) 4-1, п > 0. Если ? ИЛИ-узел, то необходимо среди сыновей данного згзла выбрать г — сына, у которого максимальное число вершин, плюс единица (необходимо подсчитать сам узел г). Л.Л5Т ИЛИ-УЯПЛ. Аналогично можно получить максимальное число листьев в варианте. Необходимо в выражении (1. Для подсчета числа узлов необходимо в выражении (1. Вариант будем называть минимальным, если у него минимальное число вершин. Используя такие же рассуждения, как для вычисления максимального числа вершин в варианте, получим следующее выражение для подсчета минимального числа вершин в варианте дерева И/ИЛИ.