Алгоритмические исследования комбинаторных чисел и полиномов

• Автор: Баранчук, Антон Леонидович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Иркутск
• Количество страниц: 92 с. : ил.

Глава 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. Программный комплекс рркЛЗвиа! для изучения
комбинаторных полиномов и обобщенных пирамид Паскаля
Заключение Приложения Список литературы

В настоящее время в связи с развитием современных компьютерных и информационных технологий и близких к ним разделов науки существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности [28, 55, 64]. Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [1, 2, 3, 6, 12, 16, 58]. Конфигурации, построенные в соответствии с определенными правилами, называются обычно комбинаторными [51].
Настоящая диссертационная работа, принадлежащая области комбинаторного анализа, посвящена изучению свойств комбинаторных чисел и полиномов с точки зрения алгоритмов их построения на основе информации о внутренней структуре исследуемых объектов. Автор диссертационной работы не только изучает существующие комбинаторные объекты, но и конструирует новые, которые в свою очередь находят применение в различных практических приложениях.
Комбинаторные задачи алгоритмического характера на дискретных конечных математических структурах встречаются постоянно. Можно выделить два класса прикладных задач: создание алгоритмов и программ с преобладанием вычислений комбинаторного характера и алгоритмов, осуществляющих конструктивное перечисление комбинаторных объектов заданного класса [2, 4, 5, 11, 13, 15, 21-23, 25-28, 41, 47, 52, 54, 55, 57].
Конструктивное направление в математике - математика, строящаяся в соответствии с тем или иным конструктивным математическим мировоззрением, обыкновенно стремящимся связывать утверждения о существовании математических объектов с возможностью их построения. Конструктивизм в математике проявлялся на протяжении всей ее истории
[14]. Значительная часть соответствующих работ (при этом обнаружился достаточно широкий спектр толкования различными исследователями терминов «конструктивный», «эффективный» и т. д.) опиралась на успехи, достигнутые в изучении математического понятия алгоритма. Один из наиболее последовательных и законченных подходов к построению конструктивной математики на этой основе доставляется основанной А.А.Марковым советской школой конструктивной математики, формирование основных понятий которой относится к 50-м г.г. XX в. [63].
Конечный объект - это “объект, о котором можно мыслить не привлекая абстракции актуальной бесконечности” [60]. Некоторые из конечных объектов являются конструктивными объектами. Каждый конструктивный объект состоит из конечного числа множества элементов, принадлежащих каждый к одному из конечного числа типов и связанных некоторыми отношениями также из конечного числа типов. Таким образом, конструктивный объект имеет расчлененное строение и состоит из отдельных самостоятельных элементов. Большинство комбинаторных объектов являются конструктивными.
Среди множества чисел комбинаторного происхождения самыми работоспособными в теоретических исследованиях и различного рода приложениях, вне всякого сомнения, являются биномиальные коэффициенты, которые, при каждом фиксированном п, образуют (п+1)-ю строку таблицы, называемой треугольником Паскаля. В последние десятилетия расширился круг исследователей, как самого треугольника Паскаля, так и его плоских и пространственных аналогов и обобщений. Имеется ряд научных и методических публикаций, большей частью зарубежных математиков, но среди них только четыре книги. Это две монографии [7, 32] и два популярных издания [59, 73].
Идеи построения арифметических треугольников комбинаторного происхождения, родственных треугольнику Паскаля, и их приложений высказывались многими авторами (см., например, [18, 42, 72, 77, 82], а
формулу Бруно можно записать следующим образом (см., например, [44, С. 66]):
К ^A(n,k;g~)fk,n> 1.
Заметим, что в этом случае
A(nJqgln) = A[n^g(t)U.
В терминах рассматриваемых полиномов разбиений разрешение формулы Бруно относительно производных внутренней функции и внешней функции имеет, соответственно, следующий вид [44]:
*я=£л(л,*;^)2К*,1;/и), п>

/„ =2 B(n,k;gl'„)Fk, к> I.

Покажем, что А- и В-полиномы могут рассматриваться как элементы взаимно-обратных матриц.
Действительно, при любых натуральных к и г < п в области аналитичности функции g(t) справедливы [44] формулы:

Y, A(-n>k’S^)B(k,r;gT1) = Srk ,

S B(n,k-,grj)A(k,r;gr-) =
Содержание этого утверждения эквивалентно тому, что бесконечные нижние треугольные матрицы
Ag =A.k>s;g{t)~\

Bg = I В[к, s; g(/)]||, к> 1, 1 k,
являются двусторонними взаимно-обратными, в этом заключается алгебраическая двойственность А-иВ- полиномов.