Алгоритмические исследования комбинаторных чисел и полиномов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Баранчук, Антон Леонидович

• Баранчук, Антон Леонидович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Баранчук, Антон Леонидович

Введение

Глава 1. Треугольники и пирамиды типа Паскаля

1.1. Сечения в треугольниках типа Паскаля

1.2.Многомерные пирамиды Паскаля 24 1.3.Обобщенный треугольник и обобщенная пирамида Паскаля 35 1.4. Алгоритмы взаимных преобразований

Глава 2. Комбинаторные полиномы

2.1. Однородные полиномы Белла '

2.2. Расщепленные полиномы Белла

2.3. Полиномы Платонова

2.4. Расщепленные полиномы Платонова

2.5. Полиномы Каталана

2.6. Алгоритмы взаимных преобразований

Глава 3. Практические приложения

3.1. Конструктивное построение индекса релевантности на основе принципа n-мерных пирамид Паскаля

3.2. Модуль защиты от мошенничества в системе лицензирования программного обеспечения на основе механизма активации

Введение диссертации (часть автореферата) на тему «Алгоритмические исследования комбинаторных чисел и полиномов»

В настоящее время в связи с развитием современных компьютерных и информационных технологий и близких к ним разделов науки существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности [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].

Частными случаями обобщенной пирамиды Паскаля являются многие комбинаторные объекты, в частности это: обобщенные числа Стирлинга В"к и В"к и обобщенные триномиальные коэффициенты В"/ и

A'h первого и второго рода, соответственно, обобщенные числа Фибоначчи и Трибоначчи, числа Эйлера, присоединенные числа JIaxa, и многие другие [48, 50, 79], в том числе комбинаторные полиномы. Изучение определенным образом заданных сечений и частей обобщенной пирамиды Паскаля позволяет строить новые соотношения между известными объектами, переносить свойства одних объектов на другие, а также строить конструктивные алгоритмы взаимных преобразований.

Различные, чаще всего ортогональные, полиномы комбинаторного характера широко применяются в ряде разделов математики и ее приложений (см., например, [8, 49, 56, 65, 66, 70, 74, 75, 76, 78, 81]). Понятие «полином разбиения» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса -введено Беллом [67, 68]. Один из таких полиномов, связанный с производными от композиции функций, Риордан [48, 49] назвал полиномом Белла.

МЛ. Платонов [44] для получения явной формы обращения формулы Бруно ввел 5-полиномы, являющиеся, в алгебраическом и аналитическом смысле, обратными однородным ^-полиномам Белла. Эти объекты О.В. Кузьмин [30] назвал полиномами Платонова.

Свойства однородных ^-полиномов Ъешт A(n,k,g) и сопряженных им 5-полиномов Платонова B(n,k,g) изучались в работах В.Д. Жукова, О.В. Кузьмина, О.В. Леоновой, M.JI. Платонова, Б.И. Селиванова [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 таблиц.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Баранчук, Антон Леонидович

Основные результаты главы опубликованы в работах [85, 86, 89-91, 94-96].

Заключение

Полученные в диссертации результаты имеют теоретическое значение для развития теории комбинаторных чисел класса отображений, а также практическое применение при решении прикладных задач перечислительной комбинаторики.

Результаты, полученные в диссертации, использовались при чтении специальных курсов по перечислительной комбинаторике и комбинаторным методам теории вероятностей для студентов института математики, экономики и информатики ИГУ и могут быть использованы в курсе лекций по дискретной математике.

Список литературы диссертационного исследования кандидат физико-математических наук Баранчук, Антон Леонидович, 2005 год

1. Айгнер М. Комбинаторная теория. М: Мир, 1982.

2. Алгоритмические исследования в комбинаторике. М.: Наука, 1978.

3. Андерсон, Джеймс А. Дискретная математика и комбинаторика. М: Вильяме, 2003.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — СПб.: Вилиямс, 2000.

6. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: ФИЗМАТЛИТ, 2004.

7. Бондаренко Б.А. Обобщенные треугольники и пирамиды Паскаля, их фрактали, графы и приложения. Ташкент: Фан, 1990.

8. Бондаренко JI.H. Многочлены композиций и обобщенные многочлены Эйлера // Труды V Международной конференции «Дискретные модели в теории управляющих систем» (Ратмино, 2629 мая 2003г.). М.: Изд. отдел факультета ВМиК МГУ, 2003. -С.13-15.

9. Браславский П.И., Вовк Е.А., Маслов М.Ю. Фасетная организация интернет-каталога и автоматическая жанровая классификация документов // http://company.Yandex.ru/articles/article8.html

10. Ю.Венбо Мао. Современная криптография: теория и практика. СПб.: Вилиямс, 2005.

11. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989

12. Гасфилд Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. СПб.: Невский диалект; БХВ - Петербург, 2003.

13. Генри С. Уоррен, мл. Алгоритмические трюки для программистов. СПб.: Вилиямс, 2000.

14. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. -М.: Мир, 1998.

15. Гудман С., Хидетниеми С. Ввведение в разработку и анализ алгоритмов. М.: Мир, 1981.

16. Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука, 1990.

17. Докин В.Н., Жуков В.Д., Колокольникова Н.А., Кузьмин О.В., Платонов M.JI. Комбинаторные числа и полиномы в моделях дискретных распределений. Иркутск: Изд-во Иркут. ун-та, 1990.

18. Докин В.Н. О треугольной схеме развития популяций // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1977. - Вып. 41. - С. 104-161.

19. Жуков В.Д. Рекуррентные формулы для обобщенных А- и В-полиномов // Исследования по геомагнетизму, аэрономии и физике Солнца. -М.: Наука, 1983. Вып. 66. - С. 192-197.

20. Жуков В.Д. Производящий определитель // Асимптотические и перечислительные задачи комбинаторного анализа. Красноярск: Изд-во Краснояр. ун-та. 1976. - С. 47-58.

21. Кнут Д., Искусство программирования, т. 1. Основные алгоритмы. -СПб.: Вильяме, 2000.

22. Кнут Д. Искусство программирования для ЭВМ, т. 2. Получисленные алгоритмы. — СПб.: Вильяме, 2000.

23. Кнут Д. Искусство программирования для ЭВМ, т. 3. Сортировка и поиск. — СПб.: Вильяме, 2000.

24. Колокольникова Н.А., Кузьмин О.В. Обобщения триномиальных коэффициентов // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. - Вып.63. - С. 60-67.

25. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.:МЦНМО, 1999.

26. Коробов Н.М. Специальные полиномы и их приложения. Диофантовы приближения. // Математические записки, 1996. Т.2 -С. 77-79.

27. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

28. Кувырков П.П., Темников Ф.Е. Комбинаторные системы. М.: Энергия, 1975.

29. Кузьмин О.В. Взаимные преобразования некоторых полиномов разбиений // Алгоритмические и комбинаторные вопросы дискретных систем и ЭВМ. Иркутск: Иркут. ун-т, 1990. - С.71-79.

30. Кузьмин О.В. Построение обобщенных А- и В-полиномов в пространстве отображений // Методы дискретного анализа в теории графов и сложности. Новосибирск: ИМ СО РАН, 1992. - Вып.52. -С. 66-76.

31. Кузьмин О.В. Рекуррентные соотношения и перечислительные интерпретации некоторых комбинаторных чисел и полиномов // Дискретная математика. 1994. - Т. 6, вып. 3. - С. 39-49.

32. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. -Новосибирск: Наука, 2000.

33. Кузьмин О.В., Леонова О.В. О полиномах Тушара // Асимптотические и перечислительные задачи комбинаторного анализа. Иркутск: Иркут. ун-т, 1997. - С.101-109.

34. Кузьмин О.В., Леонова О.В. Полиномы Тушара и им квазиортогональные // Оптимизация, управление, интеллект. -1999. -Вып. 3.-С. 218-227.

35. Кузьмин О.В., Леонова О.В. Полиномы Тушара и их приложения // Дискретная математика. 2000. - Том 12, вып. 3. - С.60-71.

36. Кузьмин О.В., Леонова О.В. Некоторые свойства полиномов Тушара // Мат. VII межд. семинара «Дискретная математика и ее