Содержание к диссертации
Введение
Глава 1. Треугольники и пирамиды типа Паскаля 20
1.1. Сечения в треугольниках типа Паскаля 20
1.2.Многомерные пирамиды Паскаля 24
1.3. Обобщенный треугольник и обобщенная пирамида Паскаля 35
1.4. Алгоритмы взаимных преобразований 40
Глава 2. Комбинаторные полиномы 43
2.1. Однородные полиномы Белла 44
2.2. Расщепленные полиномы Белла 46
2.3. Полиномы Платонова 49
2.4. Расщепленные полиномы Платонова 51
2.5. Полиномы Каталана
2.6. Алгоритмы взаимных преобразований
Глава 3. Практические приложения
3.1. Конструктивное построение индекса релевантности на основе принципа n-мерных пирамид Паскаля 61
3.2. Модуль защиты от мошенничества в системе лицензирования программного обеспечения на основе механизма активации
3.3. Программный комплекс ppkVisual для изучения комбинаторных полиномов и обобщенных пирамид Паскаля 75
Заключение 80
Приложения
Список литературы
- Обобщенный треугольник и обобщенная пирамида Паскаля
- Расщепленные полиномы Платонова
- Конструктивное построение индекса релевантности на основе принципа n-мерных пирамид Паскаля
- Программный комплекс ppkVisual для изучения комбинаторных полиномов и обобщенных пирамид Паскаля
Введение к работе
В настоящее время в связи с развитием современных компьютерных и информационных технологий и близких к ним разделов науки существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности [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], а также обширную библиографию в [7, 32]), причем в некоторых работах, естественно, полученные результаты повторяются. Пирамиды и гиперпирамиды Паскаля открываются и переоткрываются, строятся и используются в ряде работ, в частности при построении различных семейств комбинаторных чисел [7]. Однако достаточно общий подход к изучению комбинаторных объектов, основанный на анализе свойств обобщенной пирамиды Паскаля, был предложен О.В. Кузьминым сравнительно недавно [32].
Частными случаями обобщенной пирамиды Паскаля являются многие комбинаторные объекты, в частности это: обобщенные числа Стирлинга В"к и В"к и обобщенные триномиальные коэффициенты В"к1 и А 1, первого и второго рода, соответственно, обобщенные числа Фибоначчи и Трибоначчи, числа Эйлера, присоединенные числа Лаха, и многие другие [48, 50, 79], в том числе комбинаторные полиномы. Изучение определенным образом заданных сечений и частей обобщенной пирамиды Паскаля позволяет строить новые соотношения между известными объектами, переносить свойства одних объектов на другие, а также строить конструктивные алгоритмы взаимных преобразований.
Различные, чаще всего ортогональные, полиномы комбинаторного характера широко применяются в ряде разделов математики и ее приложений (см., например, [8, 49, 56, 65, 66, 70, 74, 75, 76, 78, 81]). Понятие «полином разбиения» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса -введено Беллом [67, 68]. Один из таких полиномов, связанный с производными от композиции функций, Риордан [48, 49] назвал полиномом Белла. М.Л. Платонов [44] для получения явной формы обращения формулы Бруно ввел 5-полиномы, являющиеся, в алгебраическом и аналитическом смысле, обратными однородным ,4-полиномам Белла. Эти объекты О.В. Кузьмин [30] назвал полиномами Платонова.
Свойства однородных -полиномов Benna.A(n,k,g) и сопряженных им 5-полиномов Платонова B(n,k,g) изучались в работах В.Д. Жукова, О.В. Кузьмина, О.В. Леоновой, М.Л. Платонова, Б.И. Селиванова [19, 20, 31, 32, 37, 44, 45, 53] и др. В ряде работ [19, 26, 30, 33-37, 39, 40, 69, 71] изучались некоторые обобщения этих комбинаторных объектов. Комбинаторные А- и В-полиномы успешно применяются при решении целого ряда перечислительных задач [17, 32, 44,45, 46].
В указанной монографии [17] при моделировании дискретных распределений с помощью комбинаторных полиномов показано, что структура матрицы, составленной из однородных полиномов Белла, такова, что ее столбцы содержат полную информацию о свертках любых натуральных порядков дискретного вероятностного распределения.
Однородные полиномы Белла и полиномы Платонова применяются в задачах, связанных с дискретными процессами восстановления, однородными ветвящимися процессами и другими разделами теории вероятностей и ее приложений [17, 32, 44].
При рассмотрении суммы независимых случайных величин, в которой каждое слагаемое имеет отличное от других распределение, возникают так называемые расщепленные полиномы Белла [17]. Эти полиномы являются в некотором смысле обобщением однородных полиномов Белла.
В данной работе изучаются свойства известных комбинаторных полиномов - однородных полиномов Белла и Платонова, расщепленных полиномов Белла, а также введённых автором данной диссертационной работы расщепленных полиномов Платонова.
Построены алгоритмы взаимных преобразований исследуемых объектов. Спектр практических приложений изучаемых комбинаторных объектов достаточно разнообразен.
Основная цель работы состоит в исследовании свойств комбинаторных чисел и полиномов с точки зрения алгоритмов их построения исходя из общей схемы обобщенной пирамиды Паскаля, а таюке конструирование и преобразование ее частей, сечений и элементов, являющихся числами и полиномами комбинаторного происхождения.
Методы исследований. В диссертации используются методы комбинаторного анализа, линейной алгебры и компьютерного моделирования.
Научная новизна и основные результаты. Продолжена разработка метода Кузьмина О.В., основанного на применении обобщенной пирамиды Паскаля как единого инструмента получения, систематизации и изучения многих известных семейств комбинаторных чисел и полиномов. Обобщенные пирамиды Паскаля позволяют, по мере необходимости, конструировать для тех или иных приложений новые комбинаторные числа и полиномы. В частности, в диссертации введены и изучены новые комбинаторные полиномы, являющиеся обобщениями известных комбинаторных объектов, построены алгоритмы взаимных преобразований этих комбинаторных полиномов.
Основные результаты, выносимые на защиту:
1. Выведены новые свойства А- и В-пирамид и их сечений. Построена производящая функция сумм элементов различных сечений под фиксированными углами треугольников типа Паскаля, в том числе треугольников обобщенных и обычных чисел Стирлинга второго рода. Установлена новая связь обобщенных чисел Стирлинга с обобщенными триномиальными коэффициентами.
2. Исследованы расщепленные полиномы Белла, являющиеся обобщением однородных полиномов Белла. Введены и изучены новые объекты - расщепленные полиномы Платонова, являющиеся обобщением полиномов Платонова. Показано, что расщепленные полиномы Белла и Платонова образуют в совокупности квазиортогональную пару.
3. Построены алгоритмы с линейной трудоемкостью преобразования однородных полиномов Белла в расщепленные полиномы Белла и полиномов Платонова в расщепленные полиномы Платонова.
4. Предложено практическое применение алгоритмического подхода при построении индекса релевантности для структурирования информации на основе принципа n-мерной пирамиды Паскаля, а также при разработке подсистемы защиты от мошенничества в системе лицензирования программного обеспечения на основе механизма активации.
Личный вклад автора состоит в развитии общей теории построения комбинаторных чисел и полиномов на основе обобщенной пирамиды Паскаля, построении новых комбинаторных объектов, а также получении соотношений для известных. На примерах приложений демонстрируются преимущества алгоритмического подхода к изучению комбинаторных объектов. Все основные результаты, включенные в диссертацию, получены автором лично.
Практическая ценность. Полученные в диссертации результаты представляют интерес для развития теории комбинаторных чисел и полиномов. Исследования, проводимые по теме диссертации, были поддержаны:
- грантом для поддержки научно-исследовательской работы аспирантов государетвенных образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию (2004 г.);
- грантом Рособразования "Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов" (2005 г.);
- грантом поддержки научно-исследовательской работы аспирантов и молодых сотрудников ИГУ (2005 г.).
Апробация работы. Результаты работы были представлены на научно-теоретической конференции "Молодые ученые к 80-летию ИГУ" (Иркутск, 1998); всероссийском научно-практическом молодежном симпозиуме "Экология Байкала и Прибайкалья" (Иркутск, 2001); второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, 2003); научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ (Иркутск, 2003); всероссийской конференции "Информационные и вычислительные технологии и системы" (Улан-Удэ, 2003); III международной научно-практической конференции "Математическое моделирование в образовании, науке и производстве" (Тирасполь, 2003); VIII международном семинаре "Дискретная математика и ее приложения" (Москва, 2004); конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, 2004); конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" (Москва, 2004); международной конференции ISDEF-2004 (Москва, 2004); XVII международной научно-методической конференции "Математика в вузе"(Великий Новгород, 2005); VI всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2005); IV всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005); семинарах кафедры дискретной математики и теории вероятностей ИМЭИ ИГУ (2002-2005).
Публикации. Основные результаты диссертации опубликованы в работах [83]-[97].
Структура и объём работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 97 наименований. Общий объем диссертации - 92 страницы, включая 29 рисунков и 7 таблиц.
Кратко охарактеризуем содержание отдельных глав диссертации.
Во введении обосновывается актуальность темы диссертации, научная новизна и практическая ценность, кратко характеризуется ее содержание.
Первая глава диссертационной работы посвящена изучению свойств треугольника Паскаля, обобщенного треугольника Паскаля, а также свойств обычной и обобщенной пирамид Паскаля.
В параграфе 1.1 строятся сечения в треугольнике типа Паскаля. Конструктивный подход к изучению комбинаторных объектов иллюстрируется на примере построения формулы производящей функции сумм элементов различных сечений под фиксированным углом треугольника типа Паскаля, для которых известна производящая функция k-ого столбца (к О). Найдены соответствующие соотношения для треугольников обобщенных и обычных чисел Стирлинга второго рода.
Рассмотрим матрицу вида:
«оо «01 02 «03 «04
«10 «11 «12 «13 «14 "
«20 «2, «22 «23 «24
#30 «31 «32 «33 «34 "
«40 «41 «42 «43 «44 ••
(1)
обладающую свойством Паскаля:
аи
= UMJ_l+ai_lJ,0 j i, 1 0,0 і 0.
Пусть f(x) - производящая функция последовательности {а,0}™0, которая составляет первый столбец матрицы (1). Хоггат [72] показал, что производящая функция элементов А:-ого столбца матрицы (1) задается соотношением:
( ) = /( )
1-х
и получил формулу производящей функции чисел типа Фибоначчи (сумм элементов восходящих диагоналей):
f 2 \k л
1-х
Dix) = f(xj - =/(х)-і-іЦ.. (2)
v1- .
A=0
1 1-x-x
/w=-l
Если положим 1- , где /М- производящая функция
элементов столбца обычного треугольника Паскаля, то имеем производящую функцию обычных чисел Фибоначчи:
1 °°
Здесь Fn - n-ое число Фибоначчи:
Fn+2=Fn+1+Fn, п О, F0=0, F,=l.
В работе [80] получена формула вычисления сумм элементов различных сечений треугольника Паскаля под фиксированным углом.
Результаты работ [72, 80] были обобщены автором для произвольного треугольника типа Паскаля, заданного производящей функцией первого столбца f(x).
Будем строить (p,q)-ce4eHHe по двум фиксированным элементам А и В матрицы (1). При этом А выбираем в первом столбце матрицы, а элемент В зададим следующим образом: пусть р параметр, который задает на сколько элементов выше сечения, перпендикулярного главной диагонали и проходящего через А, лежит элемент В; q - параметр, задающий номер столбца, в котором лежит следующий за начальным элемент, принадлежащий искомому сечению.
s-Треугольником будем называть треугольник, образованный числами Стирлинга второго рода [32].
Производящая функция элементов этого треугольника имеет вид:
А-треугольником называется треугольник, образованный обобщенными числами Стирлинга второго рода [44]. При этом s-треугольник является частным случаем А-треугольника.
Теорема 1.1. Производящая функция сумм элементов (p,q)-сечения А-треугольника имеет вид:
R(x,r;p,q) = iz 1+p(k+i)fl(i-ymzrl.
/=0 /»=0
k=iq
Если в последнем соотношении положить q=0, то получим широко известную формулу производящей функции чисел Фиббоначи.
Формулу Хоггата (2) обобщает следующая теорема для треугольников типа Паскаля, для которых известна производящая функция k-ого столбца.
Теорема 1.2. Производящая функция сумм элементов (р,а)-сечения треугольника типа Паскаля имеет вид:
X
со
R{x;p,q) = f(x)Y,x
1=0
k=iq
Параграф 1.2 посвящен изучению свойств пирамиды Паскаля и ее многомерных аналогов [7, 32]. Построены сечения в многомерных аналогах пирамиды Паскаля и изучены их комбинаторные и алгебраические свойства. Предложены алгоритмы построения сечений в пирамиде и гиперпирамиде Паскаля.
В параграфе 1.3 обсуждены свойства обобщенного треугольника Паскаля и обобщенной пирамиды Паскаля. Известно, что исходя из общей схемы построения комбинаторных чисел, можно получить обобщенные триномиальные коэффициенты Bnkl и Ankl первого и второго рода [24, 32] соответственно. Изучена связь обобщенных триномиальных коэффициентов и обобщенных чисел Стирлинга. Изучены свойства сечений обобщенной пирамиды Паскаля, в частности для сечений А- и В-пирамид установлены оси квази-симметрии.
В параграфе 1.4 установлена новая связь обобщенных чисел Стирлинга первого и второго рода с обобщенными триномиальными коэффициентами первого и второго рода соответственно и построены алгоритмы построения Апк1 по А к\ а также В"к1 по В с линейной трудоемкостью.
Основные результаты первой главы опубликованы в работах [83, 84, 92, 93, 97].
Во второй главе дан краткий обзор свойств однородных полиномов Белла и расщепленных полиномов Белла, а таюке получены новые рекуррентные соотношения для этих комбинаторных полиномов. Рассматриваются полиномы Платонова, а также строятся и исследуются новые объекты - расщепленные полиномы Платонова. Изучаются свойства полиномов Каталана, коэффициенты которых также могут быть построены исходя из общей теории построения комбинаторных полиномов, основанной на обобщенной пирамиде Паскаля.
Построен ряд алгоритмов взаимных преобразований рассматриваемых полиномов, а также приведены таблицы расщепленных полиномов Белла и расщепленных полиномов Платонова.
В параграфе 2.1 рассматриваются однородные полиномы Белла, их свойства и доказывается новое рекуррентное соотношение для этих комбинаторных объектов.
Пусть задана последовательность g = {gx,g2 —)- Построим следующие разложения
00 я fl"
exp[xg(0] = і+ЕЕ А(п к S\ gi - г»- +і )хк—.
и=1 к=\ п Величины 4&%hg\,g2 — g„-k+\) называются однородными полиномами Белла. Для краткости будем обозначать их следующим образом A{n,k\g).
Известен явный вид этих полиномов
п-к+\ г -Г1
A(n,k;g) = я! П г№ J 1,1 к п,
п,к /=1
где сумма берется по всем разбиениям п на к слагаемых.
Для однородных полиномов Белла A(n,k;g) известны следующие экспоненциальные производные функции [42, с.179; 43, с. 57]:
,,=к п\ к\
A(t,x) = A{n,k;g)xk- = е .
/fc=0 n=i И !
Однородные полиномы Белла имеют многочисленные интерпретации, для них известен ряд рекуррентных соотношений [32, 44]. В данном параграфе доказано следующее утверждение:
Теорема 2.1. Для п 0,1 к п + 1 имеет место рекуррентное соотношение:
ґп А(п - i,k -l;g)
A(n + l,k;g) = J gt+l
\l;
1=0
Параграф 2.2 посвящен изучению расщепленных полиномов Белла, построена таблица этих полиномов и для них доказан ряд соотношений.
В работе [17] вводятся так называемые расщепленные полиномы Белла. Эти объекты рассматриваются как некоторое обобщение полиномов Белла (другое обобщение см., например, в [19, 30]) при моделировании дискретных распределений с помощью комбинаторных полиномов для рассмотрения суммы независимых случайных величин, каждая из которых имеет отличное от других распределение.
Расщепленные полиномы Белла имеют вид
Ґ „ Л A{n,k\ g) = {k\y X Yl gni,i = \,« ,n = k,K,
z ».=»
/=1
упх,..., пк J
где сумма распространяется на все композиции п в виде к натуральных слагаемых.
А(п,к; g) являются полиномами относительно совокупности
переменных gni,i = \,к,пі =1,п-к+1, однородными степени к по нижним индексам и симметрическими по верхним индексам.
Доказаны следующие соотношения для расщепленных полиномов Белла.
Теорема 2.2. Для п \,\ к п имеет место рекуррентное соотношение:
n-k+\ f ft \
A(n-i,k-l; g).
\Ч
A{n,k;ig)-rxYJkgi
Теорема 2.3. Для п 1,1 к п имеет место рекуррентное соотношение:
п-к+1 -а
А(п,к;1§)= YJkSi k—A(n,k;ig). м д g,
В [17] приведен следующий алгоритм "расщепления" однородных полиномов Белла: если в полиноме A(n,k;g) каждое слагаемое
п-к+1 г -Г1
П-К + 1 г -і •
расщепить
спецификации (гх,г2,...,гп_к+]), имеющее вид
/=1
v-l
на сумму k {ri r2 " rn-k+\) слагаемых с учетом соображений симметрии и однородности, мы получим соответствующий полином
А{п,к\ lg).
В параграфе 2.3 рассмотрены, тесно связанные с однородными полиномами Белла, 2?-полиномы Платонова, которые имеют вид
в(п к. _л - (-1)"" у (-РЧ и- - ,) .) 1 kV где суммирование ведется по всем к, О, таким что
п-к+\ я-А+1
к, = п-к, ikj =2п-2к. /=1 /=1
Экспоненциальные производящие функции полиномов Платонова В (п, к; g) имеют вид [39]:
ЇҐк п\ к\
к U _ xg(u)
B(u,x) = ( ,&;g)x —,=е
к=Оп=к П Формула Бруно выражает производные любого натурального порядка сложной функции F(t) = f[g(t)]. Будем называть f(u) внешней функцией, g{t) - внутренней функцией.
dn d" d"
Пусть F„ = rF(0» Sn = S(t), fn = j f№ где u = S(0 .
В области, где все участвующие производные существуют, выполняются соотношения, носящие название формулы Бруно:
К = nit ЛЕ ffV ! ,!(/! г г1, п 1.
ft=l п,к /=1
Если считать, что параметры gni \, участвовавшие в построении А и 5-полиномов, совпадают с употребляемыми сейчас производными
d ,, аналитической функции, имеющими те же обозначения g,--ту §"(/), то
формулу Бруно можно записать следующим образом [44, С.66]:
=2 ( Д; )Л,я 1.
к=\
Заметим, что в этом случае
A(n,k;g-)= A[n,k;g(t)]t=0.
В терминах рассматриваемых полиномов разбиений разрешение формулы Бруно относительно производных внутренней функции и внешней функции имеет, соответственно, следующий вид [44]:
g„ = А(п,к;Р-)В(к,\;1,л\ п \,
к = \
f„=t,B{n,kigltH)Fk, к \.
к=\
При любых натуральных к и г п в области аналитичности функции g(t) справедливы формулы [45]:
]ГЛ(гсД;-)Я(,г;-) = „,.,
k = r к=г
где дпЛ - символ Кронекера.
Содержание этого утверждения эквивалентно тому, что бесконечные нижние треугольные матрицы
Ag=\\A[k,s;g(t)
и
Bg=\\B[k,s;g(t)]\l k ! l s k
являются двусторонними взаимно-обратными, в этом заключается алгебраическая двойственность А - и В - полиномов.
Тот факт, что матрицы вида Ag и Bg являются двусторонними взаимно-обратными позволяет записать шесть фаз ротации, описывающих соотношения между А-и В -полиномами.
В параграфе 2.4 по аналогии с расщепленными А-полиномами введены новые объекты - расщепленные В-полиномы, называемые расщепленными полиномами Платонова. Для этих полиномов построена таблица, найден явный вид и доказан ряд соотношений.
Показано, что расщепленные однородные полиномы Белла связаны с расщепленными полиномами Платонова соотношениями квазиортогональности: 0,у; g)BU,k, 1Е) = дп
У=1
к где 5пк - символ Кронекера.
В работе [20] построен определитель, который позволяет выразить элементы одного компонента квазиортогональной системы через другой.
Воспользуемся этим результатом, чтобы построить явный вид расщепленных полиномов Платонова:
в(п,к )=(-1)"-кЦШл Ух
У=1 0 0 0 A(n,n l-Jg)
A(k+i,t;g) A(k+i,k+v;g) о
х
A(k+2,tjg) A(k+2,k+V;g) A(k+2M%g) A(k+3,klg) A(k+3,k+Xg) A(k+3,k+2;g)
AinXg) A{nMXg) Afak+Zg)
Теорема 2.4. Для w 1, \ k n -имеет место рекуррентное соотношение:
вы lg)A- B(n-Wmn,n-ys)
А(п,п; g)
В параграфе 2.5 изучаются некоторые свойства полиномов Каталана, коэффициенты которых [38] представляют собой обобщение известных чисел Каталана и строятся исходя из общей теории построения комбинаторных полиномов, основанной на обобщенной пирамиде Паскаля.
В параграфе 2.6, используя внутренние особенности изучаемых объектов и доказанные теоремы, построены алгоритмы с линейной трудоемкостью преобразования однородных полиномов Белла в расщепленные полиномы Белла и полиномов Платонова в расщепленные полиномы Платонова.
Основные результаты главы опубликованы в работах [87, 88, 91].
Третья глава посвящена некоторым практическим приложениям результатов проведенных исследований.
В параграфе 3.1. рассматривается конструктивное построение индекса релевантности на основе принципа n-мерных пирамид Паскаля. Использование структур типа пирамид Паскаля с весовыми коэффициентами [32] позволяет построить индекс, который отражает степень релевантности выдаваемых поисковых результатов [9]. В вершине пирамиды размещен элемент с ключевым понятием, на следующем уровне элементы, напрямую связанные с ключевым и в качестве весового коэффициента задается релевантность (в %) по ключу. На следующем уровне понятия сравниваются уже не с ключевым, а с первым уровнем, и так далее. Таким образом, мы сконструировали индекс, который точно отображает долю релевантного материала, а также соблюдается условие полноты при выборке по такому индексу.
В параграфе 3.2 приводится описание модуля защиты от мошенничества в системе лицензирования программного обеспечения ActivateSoft, в котором применены некоторые алгоритмы и соотношения для треугольников типа Паскаля и пирамид со схожей структурой. При анализе параметров в модуле защиты от мошенничества каждый параметр можно интерпретировать как узел в многомерной пирамиде Паскаля, а весовые коэффициенты задаются пользователем системы. Процесс получения результата в системе является, по сути, построением пути в пирамиде Паскаля.
В параграфе 3.3 приводится программного комплекса ppkVisual для изучения свойств комбинаторных полиномов и обобщенной пирамиды Паскаля. В систему входят: система визуального создания пирамиды и ее сечений, операции с полиномами (от вычисления коэффициентов до построения рекуррентных соотношений), а также все алгоритмы и классы, созданные для представления и обработки исследуемых комбинаторных объектов.
Основные результаты главы опубликованы в работах [85, 86, 89-91, 94-96].
В приложении приведены листинги некоторых программных модулей, использованных в системе изучения комбинаторных объектов.
Обобщенный треугольник и обобщенная пирамида Паскаля
В диссертации используются методы комбинаторного анализа, линейной алгебры и компьютерного моделирования.
Научная новизна и основные результаты. Продолжена разработка метода Кузьмина О.В., основанного на применении обобщенной пирамиды Паскаля как единого инструмента получения, систематизации и изучения многих известных семейств комбинаторных чисел и полиномов. Обобщенные пирамиды Паскаля позволяют, по мере необходимости, конструировать для тех или иных приложений новые комбинаторные числа и полиномы. В частности, в диссертации введены и изучены новые комбинаторные полиномы, являющиеся обобщениями известных комбинаторных объектов, построены алгоритмы взаимных преобразований этих комбинаторных полиномов.
Основные результаты, выносимые на защиту: 1. Выведены новые свойства А- и В-пирамид и их сечений. Построена производящая функция сумм элементов различных сечений под фиксированными углами треугольников типа Паскаля, в том числе треугольников обобщенных и обычных чисел Стирлинга второго рода. Установлена новая связь обобщенных чисел Стирлинга с обобщенными триномиальными коэффициентами. 2. Исследованы расщепленные полиномы Белла, являющиеся обобщением однородных полиномов Белла. Введены и изучены новые объекты - расщепленные полиномы Платонова, являющиеся обобщением полиномов Платонова. Показано, что расщепленные полиномы Белла и Платонова образуют в совокупности квазиортогональную пару. 3. Построены алгоритмы с линейной трудоемкостью преобразования однородных полиномов Белла в расщепленные полиномы Белла и полиномов Платонова в расщепленные полиномы Платонова. 4. Предложено практическое применение алгоритмического подхода при построении индекса релевантности для структурирования информации на основе принципа n-мерной пирамиды Паскаля, а также при разработке подсистемы защиты от мошенничества в системе лицензирования программного обеспечения на основе механизма активации. Личный вклад автора состоит в развитии общей теории построения комбинаторных чисел и полиномов на основе обобщенной пирамиды Паскаля, построении новых комбинаторных объектов, а также получении соотношений для известных. На примерах приложений демонстрируются преимущества алгоритмического подхода к изучению комбинаторных объектов. Все основные результаты, включенные в диссертацию, получены автором лично. Практическая ценность. Полученные в диссертации результаты представляют интерес для развития теории комбинаторных чисел и полиномов. Исследования, проводимые по теме диссертации, были поддержаны: - грантом для поддержки научно-исследовательской работы аспирантов государетвенных образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию (2004 г.); - грантом Рособразования "Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов" (2005 г.); - грантом поддержки научно-исследовательской работы аспирантов и молодых сотрудников ИГУ (2005 г.). Апробация работы. Результаты работы были представлены на научно-теоретической конференции "Молодые ученые к 80-летию ИГУ" (Иркутск, 1998); всероссийском научно-практическом молодежном симпозиуме "Экология Байкала и Прибайкалья" (Иркутск, 2001); второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, 2003); научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ (Иркутск, 2003); всероссийской конференции "Информационные и вычислительные технологии и системы" (Улан-Удэ, 2003); III международной научно-практической конференции "Математическое моделирование в образовании, науке и производстве" (Тирасполь, 2003); VIII международном семинаре "Дискретная математика и ее приложения" (Москва, 2004); конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, 2004); конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" (Москва, 2004); международной конференции ISDEF-2004 (Москва, 2004); XVII международной научно-методической конференции "Математика в вузе"(Великий Новгород, 2005); VI всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2005); IV всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005); семинарах кафедры дискретной математики и теории вероятностей ИМЭИ ИГУ (2002-2005). Публикации. Основные результаты диссертации опубликованы в работах [83]-[97]. Структура и объём работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 97 наименований. Общий объем диссертации - 92 страницы, включая 29 рисунков и 7 таблиц. Кратко охарактеризуем содержание отдельных глав диссертации. Во введении обосновывается актуальность темы диссертации, научная новизна и практическая ценность, кратко характеризуется ее содержание.
Первая глава диссертационной работы посвящена изучению свойств треугольника Паскаля, обобщенного треугольника Паскаля, а также свойств обычной и обобщенной пирамид Паскаля.
В параграфе 1.1 строятся сечения в треугольнике типа Паскаля. Конструктивный подход к изучению комбинаторных объектов иллюстрируется на примере построения формулы производящей функции сумм элементов различных сечений под фиксированным углом треугольника типа Паскаля, для которых известна производящая функция k-ого столбца (к О). Найдены соответствующие соотношения для треугольников обобщенных и обычных чисел Стирлинга второго рода.
Расщепленные полиномы Платонова
Мы рассмотрели коэффициенты для четырех слагаемых. При их выводе мы пользовались треугольником Паскаля и пирамидой Паскаля. Очевидно, что для вывода коэффициентов 5 слагаемых нужны будут треугольник Паскаля, пирамида Паскаля и гиперпирамида Паскаля.
Для 5 степени нужно рассматривать гиперфигуру в пятимерном пространстве. У нее каждая сторона будет являться 4D бесконечной гиперпирамидой. Очевидно, что существует некая закономерность для получения полиноминальных коэффициентов.
Если мы берем одно слагаемое, то коэффициенты в любой степени дают 1. Единицы составят бесконечную прямую.. Если представить, что мы видим лишь сторону треугольника Паскаля, а сам треугольник перпендикулярен направлению нашего взгляда, то, повернув его на 90 градусов, мы получим треугольник Паскаля.
Представим, что видна лишь одна грань пирамиды - треугольник Паскаля. Мысленно повернув этот треугольник, мы увидим пирамиду Паскаля. Точно также пирамида Паскаля - всего лишь одна «сторона» гиперпирамиды, а гиперпирамида - «сторона» гиперпирамиды большей размерности. Так можно продолжать бесконечно: каждая предыдущая пирамида будет являться частным случаем следующей гиперпирамиды. И коэффициенты разложения степеней п слагаемых будут рекуррентно связаны с соответствующими коэффициентами для п-1 слагаемых.
Обобщенным треугольником Паскаля (V-треугольником) называем [32] треугольную таблицу, элементы которой удовлетворяют следующим рекуррентным соотношениям: с граничными условиями К(0,0) = V0;V(n,k) = 0, если тт(п,к,п - к) 0 . Все элементы с фиксированным (равным п) первым индексом составляют п-строку, а с фиксированным (равным к) вторым индексом -к-столбец V-треугольника. Число V0, стоящее в вершине (нулевой строке), оговаривается особо; во многих случаях можно считать V0 -1. Величины а k и Рп к называют весовыми коэффициентами. Если в соотношении (6) положить V0-\, а„k=j3„k=\, л 1,0 А и, тогда V{n,k) = т.е. имеем обычный треугольник Паскаля. Если считать V0=l, апЛ -1, Да = //„_,,п 1,0 к п, то имеем Г(и,) = Вк и из соотношения (6) следует рекуррентная формула в-к = в::1 + м вг1, (7) определяющая обобщенные числа Стирлинга первого рода (см. [44, С. 42]). При апЛ = 1, Впк =/лк,п 1,0 к п, имеем V(n,к) = А"к и формулу А;=АІЇ+МІАГ1, (8) для обобщенных чисел Стирлинга второго рода (см. [44, С. 42]). Треугольники, составленные из чисел В к и А"к будем называть В-, А треугольником, соответственно. При дальнейшей конкретизации, положив в выражениях (7) и (8) ці = і, і 0, получим соотношения, определяющие модули соответственно обычных чисел Стирлинга первого и второго рода. Обобщенной пирамидой Паскаля (V-пирамидой) называем [32] трехгранный пирамидальный массив, элементы которого удовлетворяют следующим рекуррентным соотношениям: VinXl) = апЛА/(п - U -1,7) + PnJkMV{n - XXI -1) + yn,kJV{n - l,kj) (9) с граничными условиями F(0 ДО) = Va; V{n, k,l) = 0, при тіп(л, k,l,n-k-l) 0. Все элементы с фиксированным (равным п) первым индексом составляют п-слой V-пирамиды. При к = 0,1 = 0ик + 1= п получаем, соответственно, правую, левую и заднюю грани V-пирамиды, каждая из которых является V-треугольником. Число V0, стоящее в вершине (нулевом слое), оговаривается особо; во многих случаях можно считать V0 =1. Величины ccnkl,finkl и Yn,k,i называют весовыми коэффициентами. Некоторые известные комбинаторные числа являются частными случаями элементов обобщенной пирамиды Паскаля. Пусть V0=l, anXl = pnkl = упХ, = 1,п 1,0 к + 1 п, тогда V(n,к,I) а из (9) имеем формулу (5), определяющую пирамиду Паскаля (рис. 2.). Если VQ=l, то при а„м=а1_1, =/31_1 г„х,=Г11- п 1,0 к + 1 п, имеем V(n, к, I) = В 1, и из соотношения (9) следует рекуррентная формула для обобщенных триномиальных коэффициентов первого рода [24]. При апМ = ак,/Зпк1 = рк,упХ, =ук,п \,Ъ к + 1 п„ имеем V(n,к,I) = A"kJ и, из соотношения (9), рекуррентную формулу для обобщенных триномиальных коэффициентов второго рода [24]. Положив в (10) и (11) ai =1,/,- = jut,i 0, / = 0, получим формулы (7) и (8), соответственно. Согласно приведенному в [32, С. 75] конструктивному описанию, B l, =B"kJ{a,j3,y) сумма всех различных произведений по п сомножителей, которые без повторений их индексов в каждом произведении выбираются по из п первых членов базы а, по / из п первых членов базы /? и по п - к -I первых членов базы у. Непосредственно из описания следует, что Вкj(ju,ju,y) = Bj k(ju,{i,y). Пусть Кар - преобразование, заключающееся в одновременной замене базы а на базу /? и базы (3 на базу а соответственно. Преобразования KaJ3 и KaJ3 определяются аналогично.
Конструктивное построение индекса релевантности на основе принципа n-мерных пирамид Паскаля
В общей теории комбинаторных чисел [44] рассматриваются отображения «-множества К„= {1, 2, ... , п) в (т + / -множество {0, 1,2, ... , т}. На множестве ЧЯ"т таких (п, т+1)-отображений задаются веса. Вес ju(D) подмножества Z c9?",, определяемый как сумма весов входящих в D отображений, называется комбинаторным числом класса отображений. Различают веса нулевого, первого и второго родов. Исходя из этой общей схемы, в [32] получены представления В к\, и A"kl.
Пусть f = {rx,r2,...rn,)- точка и-мерного пространства с натуральными значениями координат, не превосходящими п. Строим Vkl cSR" следующим образом. Полагаем, что feVkJ, если значения к из п ее координат составляют множество г(0 ={г,(а}= {1, 2, 3, ... , к}, а значение каждой из п - к остальных на единицу больше числа предшествующих ей координат из множества г(а). Совокупность этих п к, не входящих во множество Г{а), координат разбиваем по их номерам всеми возможными способами на I-множество гт ={г Р)) и (п-к-1)-множество rly)={rj-r)}. Всего в убудет точек. Точкам feVkJ присваиваем веса. Элементарным актам г(у) присваиваем веса ціг,, равные а, , /?,,. и у,п, соответственно. Веса всех возможных элементарных актов отображения составляют три матрицы весов air , Д.(, и у. . Вес точки /определим как произведение весов элементарных актов, в совокупности определяющих эту точку /л(а) = Y.
В случае задания весов нулевого рода (в каждой матрице весов элементы одинаковы) имеем При задании весов первого рода каждая матрица весов состоит из одинаковых столбцов. В этом случае /=о где суммирование осуществляется одновременно по всем композициям В случае задания весов второго рода каждая матрица весов состоит из одинаковых строк. При этом перестановок с повторениями сомножителей Д. и у, считаются различными. Если в полученных выше представлениях Вк1 и Ак1 положить аі -1, yt = juni 0,1 = 0, то имеем представления В"к и А"к, приведенные в [44]. Использование данных представлений позволяет установить новую связь обобщенных чисел Стирлинга первого и второго рода В к\, и А к\, с обобщенными триномиальными коэффициентами первого и второго рода, соответственно, и сконструировать Алгоритм 1.3 построения B lj по Вк и Алгоритм 1.4 построения , по Ак с линейной трудоемкостью. Понятие "полином разбиения" - полином от нескольких переменных, определяемый с помощью сумм по различным разбиениям его индекса -введено Е. Белл ом [67] в 1927 году. Один из таких полиномов, связанный с производными от композиции функций, Дж. Риордан (см. перевод [48]) в 1958 году назвал полиномом Белла. Эти полиномы входят в состав формулы Бруно для производных от композиции функций.
М.Л. Платонов [43] в 1975 году ввел полиномы, являющиеся обратными в алгебраическом и аналитическом смысле однородным полиномам Белла. Эти объекты О.В. Кузьмин [29] в 1990 году назвал полиномами Платонова.
Кроме формулы Бруно, однородные полиномы Белла и полиномы Платонова применяются в задачах, связанных с дискретными процессами восстановления, однородными ветвящимися процессами и другими разделами теории вероятностей и ее приложений. Однородные полиномы Белла подробно изучаются в монографиях [17, 32,44].
В монографии [17] при моделировании дискретных распределений при помощи комбинаторных полиномов показано, что структура матрицы, составленной из однородных полиномов Белла, такова, что ее столбцы содержат полную информацию о свертках любых натуральных порядков дискретного вероятностного распределения, имеющего производящую функцию При рассмотрении суммы независимых случайных величин, в которой каждое слагаемое имеет отличное от других распределение возникают так называемые расщепленные полиномы Белла. Эти полиномы являются в некотором смысле обобщением однородных полиномов Белла. Однако следует отметить, что расщепленные полиномы Белла не являются полиномами разбиений, они являются полиномами композиций.
В данной главе дан краткий обзор однородных полиномов Белла и расщепленных полиномов Белла, а также получены новые рекуррентные соотношения для этих комбинаторных полиномов. Рассмотрены полиномы Платонова, а также построены новые объекты - расщепленные полиномы Платонова. Приведено описание полиномов Каталана, тесно связанных с числами Каталана. Построен ряд алгоритмов преобразований полиномов, а также приведены таблицы расщепленных полиномов Белла и расщепленных полиномов Платонова.
Программный комплекс ppkVisual для изучения комбинаторных полиномов и обобщенных пирамид Паскаля
В данном параграфе приводится описание модуля защиты от мошенничества в системе лицензирования программного обеспечения ActivateSoft, в котором применены некоторые алгоритмы и соотношения для треугольников типа Паскаля и пирамид со схожей структурой. При анализе параметров в модуле защиты от мошенничества каждый параметр можно интерпретировать как узел в многомерной пирамиде Паскаля, а весовые коэффициенты задаются пользователем системы. Процесс получения результата в системе является, по сути, построением пути в пирамиде Паскаля. Сегодня вопрос об использовании нелицензионного программного обеспечения стоит особенно остро в связи с бурным развитием носителей информации и глобализацией компьютерных сетей, с одной стороны, и отставанием общественного осознания того факта, что программное обеспечение является таким же предметом собственности, как и материальные предметы, с другой.
Компьютерное пиратство, нелегальное копирование и распространение программного обеспечения являются одними из самых больших проблем индустрии. На сегодняшний день не существует открытых систем и механизмов, которые позволяли бы эффективно контролировать распространение и лицензирование программных продуктов.
Экономика интеллектуальной собственности разительно меняется по мере того, как затраты на распространение и воспроизведение информации сводятся к нулю. Пиратство причиняет ущерб не только производителям программного обеспечения, но и всем участникам экономической цепи - от торговых предприятий до служб поддержки и конечных пользователей.
Проблема безопасности информационных технологий возникла на пересечении двух активно развивающихся и, наверное, самых передовых в плане использования технических достижений направлений - безопасности технологий и информатизации. Сама проблема безопасности, конечно, не является новой, ведь обеспечение собственной безопасности - задача первостепенной важности для любой системы независимо от ее сложности и назначения будь то социальное образование, биологический организм или система обработки информации. Однако в условиях, когда защищаемый объект представляет собой информационную систему, или когда средства нападения имеют форму информационных воздействий, необходимо разрабатывать и применять совершенно новые технологии и методы защиты [10, 61, 62]. Современные компьютеры за последние годы приобрели гигантскую вычислительную мощь, но одновременно с этим стали гораздо проще в эксплуатации. Это означает, что пользоваться ими стало намного легче, поэтому все большее количество новых, как правило, неквалифицированных людей получает доступ к компьютерам, что приводит к снижению средней квалификации пользователей. Эта тенденция существенно облегчает задачу нарушителям, т. к. в результате "персонализации" средств вычислительной техники большинство пользователей имеют личные компьютеры и осуществляют их администрирование самостоятельно.
Современные телекоммуникационные технологии объединили локальные компьютерные сети в глобальную информационную среду. Это привело к появлению такого уникального явления как Интернет. Именно развитие Интернет вызвало всплеск интереса к проблеме информационной безопасности и поставило вопрос об обязательном наличии средств защиты у сетей и систем, подключенных к сети Интернет, независимо от характера обрабатываемой в них информации. Дело в том, что Интернет (кроме всего прочего) обеспечивает широкие возможности злоумышленникам для осуществления нарушений безопасности в глобальном масштабе. Если компьютер, который является объектом атаки, подключен к Интернет, то для атакующего не имеет большого значения, где он находится - в соседней комнате или на другом континенте.
Прогресс в области аппаратных средств сочетается с еще более бурным развитием программного обеспечения. В настоящий момент можно констатировать, что большинство систем предоставляют злоумышленникам широкие возможности для осуществления нарушений.
Несоответствие бурного развития средств обработки информации и медленной проработки теории информационной безопасности привело к появлению существенного разрыва между теоретическими моделями безопасности, оперирующими абстрактными понятиями типа объект, субъект и т. д., и реальными категориями современных информационных технологий. Такое положение является следствием отсутствия общей теории защиты информации, комплексных моделей безопасности обработки информации, описывающих механизмы действий злоумышленников в реальных системах, а также отсутствием средств, позволяющих эффективно промоделировать адекватность тех или иных решений в области безопасности.
На текущий момент очень остро стоит проблема защиты авторских прав, ведь при возрастающей роли информационных технологий последствия пиратства все ощутимее влияют на экономику. Эта проблема очень актуальна именно сейчас, так как от ее эффективного решения зависит то, насколько динамично будет развиваться индустрия информационных технологий и смежные отрасли. Экономика интеллектуальной собственности требует появления новых средств защиты и лицензирования.
Рассмотрим схему распространения программного обеспечения (см. рис. 28). В ней участвуют 3 стороны - покупатель, производитель и регистрационный сервис (посредник, который принимает платежи от покупателя). Покупатель осуществляет платеж, и при поступлении средств, регистрационный сервис отсылает регистрационный ключ.