Алгоритмы и программный модуль получения явных выражений коэффициентов производящих функций тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Перминова Мария Юрьевна

• Перминова Мария Юрьевна
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Перминова Мария Юрьевна

Введение

1 Современное состояние проблемы получения явных выражений коэффициентов производящих функций

1.1 Производящие функции и их степени

1.2 Метод нахождения явных выражений коэффициентов производящих функций

1.3 Обзор возможностей систем компьютерной алгебры для работы с производящими функциями

1.4 Выводы

2 Алгоритмическое обеспечение модуля получения явных выражений коэффициентов производящих функций

2.1 Алгоритмы рекурсивной генерации ограниченных разбиений натурального числа

2.2 Алгоритм декомпозиции полиномов, основанный на генерации разбиений

2.3 Алгоритм получения явных выражений коэффициентов производящих функций

2.4 Выводы

3 Программная реализация алгоритмов

3.1 Выбор средства реализации

3.2 Структура программного модуля

3.3 Программный модуль получения явных выражений коэффициентов композиции производящих функций в Maxima

3.4 Пример работы программного модуля получения явных выражений коэффициентов композиции производящих функций

3.5 Выводы

4 Внедрение результатов диссертационной работы

Заключение

Список использованных источников

Приложение А Акты внедрения

Приложение Б Схемы алгоритмов

Приложение В Пример синтаксического дерева

Приложение Г Примеры записей из базы операций и композит

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

Введение

Актуальность темы. Система компьютерной алгебры (СКА, англ. computer algebra system - CAS) представляет собой тип программного средства, предназначенного для обработки математических выражений в аналитической (символьной) форме [1].

В настоящее время СКА широко используются в различных областях: от естественных наук (математика, физика, химия и т. д.), инженерных и теоретических расчетов, математического моделирования до анализа звука и изображений [2-5].

Аналитические вычисления являются неотъемлемой частью научных исследований. На выполнение и реализацию таких вычислений тратится большое количество времени. При этом требуется достаточно высокая точность. Именно здесь приходят на помощь системы компьютерной алгебры, являющиеся практически единственным средством решения задач, требующих больших затрат ручных вычислений и чувствительных к потере точности при численном счёте на компьютере. Поэтому системы компьютерной алгебры востребованы среди ученых, преподавателей, аспирантов и студентов [6].

СКА как отдельное направление программного обеспечения появились в начале 60-х годов XX века и развивались в двух совершенно разных областях: теоретическая физика и искусственный интеллект. Первым успешным примером была разработка в 1963 г. Мартином Велтманом (Martinus J. G. Veltman) программы Schoonschip, ориентированной на символьное решение проблем в области физики высоких энергий [1].

В бывшем СССР большой вклад в развитие систем символьной математики внесла школа академика В. М. Глушкова. В конце 70-х годов XX века были созданы малые инженерные ЭВМ класса «Мир», способные выполнять аналитические вычисления даже на аппаратном уровне. Был

разработан и успешно применялся язык символьных вычислений «Аналитик». Эти работы появились слишком рано для своего времени и не соответствовали линии развития советской вычислительной техники в те годы. Поэтому компьютеры «Мир» отошли на задний план, а затем этот класс компьютеров прекратил свое существование и развитие.

В отрыве от мировой науки и крупных источников финансирования работы советских ученых (за исключением некоторых теоретических) в области компьютерной алгебры оказались малоэффективными -отечественных систем компьютерной алгебры для персональных компьютеров, доведенных до серийного производства и мировой известности, так и не было создано [7].

Системы компьютерной алгебры были разработаны западными учеными. СКА первого поколения (Reduce, Macsyma, MathLab, Scratchpad, SAC-1, muMATH, Derive) были способны выполнять символьные вычисления: интегрирование, дифференцирование, факторизацию. В СКА второго поколения (Mathematica, Maple, Sage) к символьным вычислениям были добавлены поддержка численных вычислений с произвольной точностью, развитые пользовательские интерфейсы и визуализация данных. В СКА третьего поколения (Axiom, Magma, MuPAD) появилась возможность решения задач для любых математических объектов, допускающих алгебраическое описание. Например, группы, кольца, поля и т. п. Также СКА этого поколения позволяли пользователям описывать новые алгебраические объекты [8].

Значительное расширение возможностей систем компьютерной алгебры и их адаптация к решаемым конкретными пользователями задачам достигаются за счёт пакетов расширения систем. Эти пакеты (нередко и библиотеки) пишутся на собственном языке программирования той или иной СКА, что делает возможным их подготовку обычными пользователями [6].

В настоящее время исследования в области систем компьютерной алгебры продолжаются в трёх направлениях: возможности по решению всё

более широких задач, простота использования и скорость работы [8]. К первому указанному направлению относится развитие преобразующих процедур и процедур управления преобразованиями, в том числе развитие операций над производящими функциями.

Производящие функции являются мощным инструментом решения задач комбинаторики, теории чисел, алгебры, статистики, теории вероятности, математической физики, анализа алгоритмов и др. [9-11].

Впервые в середине XVIII в. метод производящих функций использовал английский математик А. де Муавр (A. De Moivre) для решения рекуррентных уравнений. Во второй половине XVIII в. Л. Эйлер (L. Euler) развил методы использования производящих функций для решения задач, связанных с изучением разбиений [12]. Существенный вклад в изучение методов решения математических задач на основе использования производящих функций в XX веке внесли Э. Белл (E. T. Bell), Дж. Риордан (J. F. Riordan), Н. Виленкин, Г. Вильф (H. S. Wilf), Г. Егорычев, Дж. Эндрюс (G. E. Andrews), В. Сачков, Ф. Флажоле (Ph. Flajolet), Р. Стенли (R. P. Stanley) [13].

Одной из важнейших задач, которые решают производящие функции, является получение явных выражений членов числовых последовательностей, применяемых в задачах комбинаторики, статистики, математической физики. В настоящее время решение этой задачи в СКА носит существенно ограниченный характер [23]. С другой стороны, разработан новый метод нахождения явных выражений коэффициентов производящих функций, основанный на использовании коэффициентов степеней производящих функций [13], позволяющий существенно расширить нахождение явных выражений коэффициентов производящих функций для операций композиции, обращения и др. Поэтому актуальной является задача создания алгоритмов и программного обеспечения систем компьютерной алгебры для получения явных выражений коэффициентов производящих функций.

Цели и задачи исследования. Целью диссертационной работы является развитие алгоритмов и программного обеспечения систем компьютерной

алгебры для получения явных выражений коэффициентов производящих функций.

Задачи исследования.

1. Провести анализ возможностей систем компьютерной алгебры для работы с производящими функциями, выявить достоинства и недостатки систем компьютерной алгебры по работе с производящими функциями.

2. Провести анализ метода получения явных выражений коэффициентов производящих функций и разработать алгоритм автоматизации вычисления указанных выражений коэффициентов.

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

4. Разработать и исследовать алгоритм декомпозиции полиномов, основанный на генерации ограниченных разбиений.

5. Разработать программный модуль получения явных выражений коэффициентов композиции производящих функций.

Объект исследования. Объектом исследования являются системы компьютерной алгебры.

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

Методы исследования. В работе использовались методы: метод, основанный на применении производящих функций; комбинаторной генерации; декомпозиции полиномов; анализа алгоритмов; объектно-ориентированного программирования.

Научная новизна полученных результатов.

1. Разработан новый алгоритм генерации разбиений, отличающийся от аналогов тем, что позволяет генерировать класс ограниченных разбиений

(Я, М, п), где п - натуральное число, М - части разбиения, каждая из которых не превосходит N.

2. Разработан оригинальный алгоритм декомпозиции полиномов, отличающийся от известных алгоритмов тем, что основан на генерации ограниченных разбиений.

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

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

Алгоритм декомпозиции полиномов обеспечивает решение полиномиальных уравнений и вычисление значений полиномов (для полиномов больших степеней). Данный алгоритм позволил сформулировать подход к представлению решений системы интегро-дифференциальных уравнений композицией производящих функций при моделировании нелинейных импульсных динамических систем.

Алгоритм получения явных выражений коэффициентов производящих функций расширяет возможности СКА по работе с производящими функциями за счет базы композит и операций, связанных с поиском композиции производящих функций.

Разработанный программный модуль позволяет в автоматизированном режиме решать задачи комбинаторики, алгебры, теории чисел, статистики, математической физики и др. Это обеспечивает ускорение выполнения математических преобразований и уменьшение числа ошибок.

Также полученное с использованием программного модуля явное выражение коэффициентов производящей функции позволяет расширить базу

энциклопедии целочисленных последовательностей OEIS [41]. Данными этой энциклопедии пользуются как любители, так и специалисты в математике, комбинаторике, теории чисел, теории игр, физике, химии, биологии, информатике.

Положения, выносимые на защиту.

1. Временная сложность алгоритма последовательной генерации ограниченных разбиений натурального числа имеет логарифмический вид O(alnn+b), где a и b - некоторые константы. Временная сложность

алгоритмов нумерации и генерации разбиения по номеру имеет вид, близкий к линейному. Соответствует п. 3 паспорта специальности 05.13.17.

2. Алгоритм декомпозиции полиномов, основанный на генерации

ограниченных разбиений, имеет временную сложность O (n2 ). При этом

степень полинома должна представлять собой произведение двух множителей. Соответствует п. 4 паспорта специальности 05.13.17.

3. Новый алгоритм позволяет получать явные выражения коэффициентов производящих функций. Исходная производящая функция должна быть представлена композицией или производящими функциями, композиты которых есть в базе. Соответствует п. 14 паспорта специальности 05.13.17.

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

Внедрение результатов работы. Полученные результаты диссертационной работы внедрены в онлайн-энциклопедию целочисленных последовательностей OEIS. Зарегистрирована 1 новая последовательность (A210460) и добавлена 1 оригинальная формула (A039834). Получено свидетельство Объединенного фонда электронных ресурсов «Наука и

образование» о регистрации программного модуля № 22861. Результаты диссертационной работы использованы в ходе выполнения научно-исследовательских работ: «Моделирование адаптивных энергонасыщенных объектов с применением методов производящих функций и методов самоорганизации моделей» № 8.2571.2014 в ФГБОУ ВО «ТУСУР», реализуемой в рамках базовой части государственного задания в сфере научной деятельности (2014 г.); «Разработка перспективных алгоритмов защиты информации» (2015-2017 гг.), выполняемую совместно с ООО «Удостоверяющий центр Сибири».

Результаты диссертационной работы внедрены в учебный процесс ФГБОУ ВО «ТУСУР» на факультете электронной техники - дисциплина «Компьютерные технологии в научных исследованиях» направление подготовки 11.04.04 «Электроника и наноэлектроника» (магистратура).

Личный вклад автора. Постановка цели и задач научного исследования осуществлялась научным руководителем. Часть опубликованных работ написана в соавторстве с научным руководителем. Автором самостоятельно разработаны алгоритм рекурсивной генерации ограниченных разбиений натурального числа, алгоритм декомпозиции полиномов, основанный на генерации разбиений, алгоритм, основанный на методе [13], позволяющий получить явные выражения коэффициентов производящих функций, а также программный модуль получения явных выражений коэффициентов композиции производящих функций.

Апробация работы. Основные результаты диссертационной работы докладывались на следующих конференциях:

1. Двадцатая международная конференция «Математика. Компьютер. Образование» (февраль 2013 г., Пущинский центр биологических исследований РАН, г. Пущино).

2. Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР» (май 2013-2015 гг., ТУСУР, г. Томск).

3. Международная научно-методическая конференция «Современное образование» (январь 2013-2015 гг., ТУСУР, г. Томск).

4. VII Международная научно-практическая конференция «Информационные процессы и технологии «Информатика - 2014» (апрель 2014 г., СевНТУ, г. Севастополь).

5. XII Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (ноябрь 2014 г., ТПУ, г. Томск).

Публикации по теме диссертации. Основные результаты диссертационного исследования опубликованы в 18 работах, в том числе 4 публикации в рецензируемых журналах из перечня ВАК [14-17], 11 публикаций в тезисах и материалах конференций [18-28], новая последовательность A210460 [29] и оригинальная формула A039834 [30] в онлайн-энциклопедии OEIS, получено свидетельство Объединенного фонда электронных ресурсов «Наука и образование» о регистрации программного модуля № 22861.

Объем и структура работы. Диссертация состоит из введения, четырёх глав основной части, заключения, списка литературы и четырёх приложений. Общий объем диссертации 113 страниц. Список литературы включает 82 наименования, в том числе 1 8 работ автора по теме диссертации.

Работа выполнена в рамках государственного задания Министерства образования и науки РФ, проект № 8.8184.2017/8.9 «Методология создания систем энергогенерирующих и энергопреобразующих устройств для наземных и бортовых комплексов наземного, космического и подводного базирования».

1 Современное состояние проблемы получения явных выражений коэффициентов производящих функций

1.1 Производящие функции и их степени

Производящие функции. Пусть /0,/2... - произвольная (бесконечная) последовательность чисел. Производящей функцией Е(х) для этой последовательности называется выражение вида

/о + /х + /2 X2 + .

или, в сокращённой записи,

ж

Е /пХп.

п=0

Переменная х является формальной, поэтому нельзя сказать, чему равно «значение Дх0) производящей функции F в точке х0». По этой же причине сумма ряда / + /х + /2х2 +... смысла не имеет. При этом можно найти значение производящей функции в нуле, то есть ^0) = /0. Таким образом, производящая функция представляет последовательность чисел в виде ряда по степеням формальной переменной (формальный степенной ряд) [31].

Производящие функции подразделяются на следующие классы: полиномы, рациональные производящие функции, производящие функции логарифма, радикалы, тригонометрические производящие функции, гиперболические производящие функции, производящие функции на основе

ех.

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

Как писал Д. Пойа [32]: «Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много

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

1) компактной записи информации о последовательности;

2) нахождения зависимости ап(п) для последовательности а(п), заданной рекуррентным соотношением. Например, для чисел Фибоначчи;

3) нахождения рекуррентного соотношения для последовательности -вид производящей функции может помочь найти формулу;

4) исследования асимптотического поведения последовательности;

5) доказательства тождеств с последовательностями;

6) решения задачи подсчета объектов в комбинаторике. Например, в доказательстве пентагональной теоремы или в задаче нахождения количества расстановок т ладей на доске п х п;

7) вычисления бесконечных сумм [33].

Начало методу производящих функций положил в середине XVIII в. английский математик А. де Муавр (А. De Могуге). Развитие данного метода продолжил знаменитый математик Л. Эйлер Euler).

Степень производящих функций. Пусть задана производящая

функция Р(х) = X I(п)хп , тогда для производящей функции [Р(х)]к =

п>0

= X Р(п,к)хп справедливо рекуррентное выражение:

п>0

Р (п, к) =

I (п), к = 1,

п

X I(ОР(п - /, к -1), к > 1.

I=0

Пусть Р(х) = X I(п)хп - производящая функция, у которой

п>0

отсутствует свободный член I (0) = 0. Композитой обыкновенной производящей функции Р(х) = X I(п)хп называется функция РА (п, к),

п>0

<

являющаяся коэффициентом производящей функции [ F( x) ]k =

= I FЛ(n,k)xn [34].

n>k

Большинство известных книг и монографий, посвященных комбинаторным проблемам и производящим функциям, используют коэффициенты степеней производящих функций, однако как самостоятельный объект исследования эти коэффициенты не рассматриваются. Например, Н. Виленкин «Комбинаторика» [35] и «Популярная комбинаторика» [36], Л. Комтет (L. Comtet) «Advanced Combinatorics» [37], В. Сачков «Введение в комбинаторные методы дискретной математики» [38], Р. Стенли «Enumerative Combinatorics (vol. 2)» [39], Ф. Флажоле и Р. Сэджвик (R. Sedgewick) «Analytic Combinatorics» [40]. Поэтому актуальной является задача исследования степеней производящих функций и их свойств.

1.2 Метод нахождения явных выражений коэффициентов производящих функций

Одной из задач, в ходе решения которой используются степени производящих функций, является задача нахождения явных выражений коэффициентов производящих функций. В настоящее время разработан метод нахождения явных выражений коэффициентов производящих функций, основанный на использовании коэффициентов степеней производящих функций [13].

Для нахождения явных выражений коэффициентов производящих функций необходимо знать композиты простых производящих функций и операции над композитами.

Основные операции и правила получения композит [13].

1. Пусть имеется производящая функция А(х) = X а(п)хп, её

п>0

композита АЛ (п, к) и константа а:

• Производящая функция Р (х) = аА( х) будет иметь композиту

Р л (п, к) = акАл (п, к). (1.1)

• Производящая функция Р(х) = А(ах) будет иметь композиту

Р л (п, к) = а пАл (п, к ).

2. Пусть имеется производящая функция Р(х) = XI(п)хп и известно

п>0

выражение для коэффициентов Р(п, к) производящей функции [Р(х)]к. Тогда композита функции хР( х) будет иметь вид

РЛ (п,к) = Р(п - к, к). (1.2)

3. Пусть имеется производящая функция В(х) = X Ь(п)хп

п>0

и [В(х)]к = X В(п, к)хп .

п>0

Тогда производящая функция Р(х) = А(х)В(х) будет иметь композиту

РЛ(п, к) = XX АЛ(г, к)В(п - г, к).

г =к

4. Пусть имеется производящая функция х) = X Я(п)хп и композита

п>0

СЛ (п, к) .

Тогда производящая функция Р (х) = А( х) + С(х) будет иметь композиту

РЛ(п, к) = АЛ(п,к) + X X АЛ(г,у)СЛ(п - г,к - j) + СЛ(п,к).

к-1^ ^п - к+у

j=^ у

Л/, лл^ VI, , ^Л,

г=у

5. Для вычисления композиции производящих функций Р(х) = В (А( х)) будет верно выражение:

n А

f(n) = X ЛА(n,k)b(k), f(0) = b(0), (1.3)

k=1

когда F(x) = X f (n)xn .

n>0

6. Пусть имеется производящая функция R(x) = Xr(n)xn и её

n >0

композита R A (n, k).

Тогда производящая функция F (x) = R ( Л( x)) будет иметь композиту

F A (n, m) = ХЛА (n, k) Ra (k, m).

k =m

При нахождении явных выражений коэффициентов k-ой степени производящих функций полученное выражение должно быть максимально простым. Поэтому в нем должно присутствовать минимальное число сумм. Рассмотрим данное утверждение на примере производящих функций, представленных полиномами.

n к

Пусть An(x) = X akx - полином; [Л (x)]к = X ЛА(n, k)xn - k-ая степень

k=1 n>k

полинома Лп (x); An (x)) - целое число, обозначающее количество сумм в закрытом выражении коэффициентов ЛА(n, k) k-ой степени полинома; D((x):Bp(x),Gl(x),...,Fr(x)) - множество всех декомпозиций полинома Лп(x), где B (x),G(x),F(x) - полиномы порядковp, l и r соответственно. Необходимо представить полином таким образом, чтобы Лп (x)) ^ min на множестве D( Л (x)).

Используя операции сложения, умножения и композиции производящих функций, оценим Лn (x)) следующим образом:

1. ju( Лп (x)) = ju((ax + bx2)k ) = 0.

2. j( Лп (x)) = n - 2.

3. j( Лп (x)) = jj(Bp (x) + Gt (x)) = 2 + jj(Bp (x)) + j(Gi (x)).

4. М(Ап (х)) = М(Вр (х)-С (х)) = 1 + М(Вр (х)) + М(С1 (х)).

5. М(Ап (х)) = [( Вр (О, (х)) ) = 1 + М(Вр (х)) + М(С1 (х)).

Для случая (1) закрытое выражение коэффициентов имеет вид

( к Л

а2к-пЪп~к (используя операцию (1.2) и бином Ньютона), откуда

ч п - к )

[(А (х)) = 0. Случай (1) является частным случаем (2). Для случая (2) [(А (х)) получается путем анализа [ при нахождении композит полиномов разных степеней:

[((ах + Ъх2)к ) = 0, [((ах + Ьх2 + ех3)к ) = 1, [((ах + Ъх2 + ехъ + (1хА)к) = 2, [((ах + Ъх2 + ехъ + (1хА + ях5)к) = 3. Следовательно, [((ах + Ъх2 +... + х)к) = и - 2 .

Применение случаев (3-5) позволит получить [ в границах 1 < [(А (х)) < п - 2. При этом минимальное число сумм будет при представлении полинома в виде произведения или композиции. Было выбрано представление производящей функции в виде композиции.

Метод нахождения явных выражений коэффициентов композиции производящих функций. Опишем метод нахождения явных выражений коэффициентов композиции производящих функций, которые представлены композицией [13]. Исходную производящую функцию необходимо представить в виде композиции двух функций, для каждой из которых известны коэффициенты их степеней. Используя композиционную формулу (1.3), получим явные выражения коэффициентов композиции производящих функций.

Пример получения коэффициентов производящей функции 2

х х

1 х 2 х 2 х х

X + X

Пусть дана производящая функция и (х) =------.

1 х 2 х 2 х х

Представим её в виде:

(х + х2 )

и (х) =-^--- = Г ( х + х2 ],

1 - (х + х21 - (х + х21

где функция Г (х) - числа Фибоначчи.

То есть функция и (х) представлена в виде композиции двух функций:

2 х х + х и-

1 х х

Композита х + х2 равна

( к л

2 равна

ч п - к у

(табл. 1.1). Выражение для п-го члена

х

1 х х

известно (числа Фибоначчи). Получим явное выражение

коэффициентов и(п) исходной производящей функции и(х):

и(п) = X

к=1

С ь \

К п - к у

/(к), и(0) = 1,

где / (к) - числа Фибоначчи.

Выражение, найденное для и (х), было записано в ОЕ1Б [41]. Присвоен номер А210460 [29].

Таким образом, представленный метод позволяет определять явные выражения коэффициентов производящих функций, заданных композицией [13].

п

Таблица 1.1 - Примеры производящих функций и их композит

Производящая функция Р( х) Композита Р Л (п, к)

ах + Ьх ( к Л а 2к-пЬп-к ^ п - к )

Ьх 1 - ах (п - Л П 1 ап-кЬк 1к -V

1 -V1 - 4 х 2 к ( 2 п - к -1 ^ п ^ п -1 )

ех -1 к! Г п 1 п! | к }

Полный список производящих функций и их композит в [13]

1.3 Обзор возможностей систем компьютерной алгебры для работы

с производящими функциями

Система компьютерной алгебры является одним из видов программных пакетов, который используется для работы с математическими формулами. СКА могут быть использованы для упрощения рациональных функций, коэффициентов многочленов, нахождения решения системы уравнений и для других манипуляций [42].

Современные СКА являются эффективным инструментом для решения многих математических задач, в том числе и выполнения операций над производящими функциями.

Перечислим основные задачи, возникающие при работе с производящими функциями.

Задача 1. По формуле производящей функции Р(х) найти ее коэффициенты /, /,..., /,... Например,

(1 -V1 - 4 х )

Р (х) =

f (n) = 1,1,2,5,14,42,132,429,1430,4862...

Задача 2. По списку коэффициентов f,f,...,f,... найти формулу производящей функции F (x). Например,

f (n) = 1,1,2,5,14,42,132,429,1430,4862...;

(1-V1-4 x )

F(x) = *---1.

Задача 3. По формуле производящей функции F( x) найти явный вид выражения коэффициентов f (n) = Solve (F(x), x, n) . Например,

(1-V1-4 x )

F(x) = *---1;

f (n) = (k*binomial(2*n-k-1,n-1))/n.

Задача 4. По явному виду выражения коэффициентов f (n) = Solve ( F (x), x, n) найти формулу производящей функции F ( x). Например,

f (n) = (k*binomial(2*n-k-1,n-1))/n.

(1-V1-4 x )

F(x) = *---}-.

На основе анализа энциклопедии целых последовательностей OEIS был получен список основных систем компьютерной алгебры, применяемых для работы с производящими функциями (см. табл. 1.2) [43].

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

Таблица 1.2 - Системы компьютерной алгебры

Система Разработчик Первый релиз Последняя стабильная версия

Magma University of Sydney 1993 2016 (2.22-3)

Maple Symbolic Computation Group,University of Waterloo 1984 2016 (Maple 2016)

Mathematica Wolfram Research 1988 2017 (11.1.0)

Maxima MIT Project MAC and Bill Schelteret al. 1998 2016 (5.39.0)

PARI/GP Henri Cohen, Karim Belabas, Bill Allombert et al. 1990 2016 (2.9.1)

SageMath William A. Stein 2005 2017 (7.5.1)

МаШешайса. МаШетайса является одной из универсальных математических систем, которая даёт возможность решать большое количество сложных задач, не вдаваясь в сложности программирования. В ряду себе подобных МаШетайса является одной из самых мощных и детально разработанных. С её помощью легко осуществляются численные и символьные вычисления. Сильной стороной системы, выгодно отличающей её от остальных, является двух- и трёхмерная графика, применяемая для визуализации кривых и поверхностей в трёхмерном пространстве. В среде МаШетайса содержится язык программирования современного высокого уровня с более ёмким и естественным функциональным стилем и стилем правил преобразований. Система интерактивна, то есть работает в режиме постоянного диалога с пользователем [44].

В системе МаШешайса существует пакет для работы с производящими функциями - GeneratingFunctions, содержащий инструменты для выполнения

некоторых унарных, бинарных и n-арных операций над производящими функциями. Можно легко проверить идентичность функций или последовательностей [45].

Список литературы диссертационного исследования кандидат наук Перминова Мария Юрьевна, 2017 год

Список использованных источников

1. Аладьев, В. З. Избранные системные задачи в программной среде Mathematica / В. З. Аладьев, В. А. Ваганов, Д. С. Гринь. - Х.: Олди-Плюс, 2013. - 556 с.

2. Дьяконов, В. П. Энциклопедия компьютерной алгебры / В. П. Дьяконов. - М.: ДМК Пресс, 2010. - 1264 с.: ил.

3. Cohen, J. S. Computer algebra and symbolic computation. Mathematical Methods [Электронный ресурс]. - Режим доступа: http: //www.ukma.edu.ua/~yubod/teach/compalgebra/%5BJoel_S._Cohen%5D_Co mputer_algebra_and_symboHc_comp(BookFi.org).pdf, свободный (дата обращения: 16.03.2017).

4. Афонский, А. А. Электронные измерения в нанотехнологиях и микроэлектронике [Электронный ресурс] / А. А. Афонский, В. П. Дьяконов. -Режим доступа: https://www.litres.ru/vladimir-dyakonov-2/elektronnye-izmereniya-v-nanotehnologiyah-i-mikroelektronike-6599233/, свободный (дата обращения: 19.03.2017).

5. Клименко, В. П. Современные особенности развития систем компьютерной алгебры [Электронный ресурс] / В. П. Клименко, А. Л. Ляхов, Д. Н. Гвоздик. - Режим доступа: http://cyberleninka.ru/article/n/sovremennye-osobennosti-razvitiya-sistem-kompyuternoy-algebry, свободный (дата обращения: 19.03.2017).

6. Компьютерная математика с Maxima [Электронный ресурс] // Национальный открытый университет ИНТУИТ. - Режим доступа: http://www.intuit.ru/studies/courses/3484/726/info (дата обращения: 27.03.2017).

7. Зарождение и развитие систем компьютерной алгебры // Техническая библиотека lib.qrz.ru. - Режим доступа: http://lib.qrz.ru/book/export/html/10485 (дата обращения: 27.03.2017).

8. Von zur Gathen, J. Modern Computer Algebra / J. von zur Gathen, J. Gerhard. - 3rd edition - Cambridge University Press, 2013. - 808 p.

9. Stanley, Richard P. Catalan Numbers. - Cambridge University Press, 2015. - 222 p.

10. Довгалюк, П. M. Анализ и оптимизация циклов с помощью производящих функций [Электронный ресурс] / П. M. Довгалюк. - Режим доступа: http://citforum.ru/programming/theory/cycles/, свободный (дата обращения: 27.04.2017).

11. Wilf, H. S. Generatingfunctionology / H. S. Wilf. - Academic Press, 1994. - 231 p.

12. История математики: в 3 т. / под ред. А. П. Юшкевича - M., Наука, 1972. - 496 с. - 3 т.

13. ^учинин, В. В. Степени производящих функций и их применение / В. В. ^учинин, Д. В. ^учинин. - Томск : ТУСУР, 2013. - 236 с.

14. Перминова, M. Ю. Алгоритмы рекурсивной генерации ограниченных разбиений натурального числа / M. Ю. Перминова, В. В. ^учинин // Доклады Томского государственного университета систем управления и радиоэлектроники. - 2014. - № 4(34). - С. 89-94.

15. Перминова, M. Ю. Алгоритм декомпозиции полиномов, основанный на разбиениях / M. Ю. Перминова, В. В. ^учинин, Д. В. ^учинин // Доклады Томского государственного университета систем управления и радиоэлектроники. - 2015. - № 4(38). - С. 102-107.

16. Перминова, M. Ю. Анализ алгоритма декомпозиции полиномов, основанного на разбиениях [Электронный ресурс] / M. Ю. Перминова // ^бер^тика и программирование. - 2015. - № 6. Режим доступа: http://e-notabene.ru/kp/article_17169.html (дата обращения: 20.01.2016).

17. Перминова, M. Ю. Программный модуль получения явных выражений коэффициентов производящих функций, основанных на использовании композиции // Доклады Томского государственного

университета систем управления и радиоэлектроники. - 2017. - №2 1, т. 20. - С. 65-69.

18. Перминова, М. Ю. Метод получения выражений коэффициентов композиции производящих функций / М. Ю. Перминова, В. В. Кручинин // Тезисы докладов : тез. конф., Двадцатая международная конференция «Математика. Компьютер. Образование» / Пущинский центр биологических исследований РАН. - Пущино, 2013. - 419 с.

19. Перминова, М. Ю. Нахождение закрытого выражения коэффициентов степени полинома по критерию минимума сумм / М. Ю. Перминова, В. В. Кручинин // Тезисы докладов : тез. конф., Двадцать первая международная конференция «Математика. Компьютер. Образование» / Объединенный институт ядерных исследований. - Дубна, 2014. - 383 с.

20. Перминова, М. Ю. Алгоритмы генерации одного класса разбиений натурального числа / М. Ю. Перминова, В. В. Кручинин // Тезисы докладов : тез. конф., Двадцать вторая международная конференция «Математика. Компьютер. Образование» / Пущинский центр биологических исследований РАН. - Пущино, 2015. - 460 с.

21. Перминова, М. Ю. Исследование алгоритма декомпозиции полиномов, основанного на разбиениях / М. Ю. Перминова // Тезисы докладов : тез. конф., Двадцать третья международная конференция «Математика. Компьютер. Образование» / Объединенный институт ядерных исследований. - Дубна, 2016. - С. 182.

22. Перминова, М. Ю. Проблема автоматизации получения выражений коэффициентов степеней производящих функций / М. Ю. Перминова, В. В. Кручинин // Современное образование: новые методы и технологии в организации образовательного процесса : материалы междунар. науч.-метод. конф. - Томск : ТУСУР, 2013. - С. 169-170.

23. Перминова, М. Ю. Обзор систем компьютерной алгебры для работы с производящими функциями / М. Ю. Перминова // Научная сессия

ТУСУР-2013 : материалы Всерос. научн.-технич. конф. - Томск: В-Спектр, 2013. - Ч. 2. - С. 323-325.

24. Перминова, М. Ю. Метод нахождения закрытого вида выражений коэффициентов степени полиномов / М. Ю. Перминова, В. В. Кручинин // Современное образование: актуальные проблемы профессиональной подготовки и партнерства с работодателем : материалы Междунар. науч.-метод. конф. - Томск : ТУСУР, 2014. - С. 93-94.

25. Перминова, М. Ю. Подход, основанный на разбиениях, для декомпозиции полиномов / М. Ю. Перминова // Научная сессия ТУСУР-2014 : материалы Всерос. научн.-технич. конф. - Томск: В-Спектр, 2014. - Ч. 3. -С. 13-15.

26. Перминова, М. Ю. Развитие систем компьютерной алгебры на основе методов определения коэффициентов степеней производящих функций / М. Ю. Перминова // Информационные процессы и технологии : «Информатика - 2014» : материалы VII Междунар. науч.-практ. конф. -Севастополь : ВЕБЕР, 2014. - С. 31-32.

27. Перминова, М. Ю. Гипотеза о системе уравнений для получения коэффициентов композиции полиномов / М. Ю. Перминова // Молодежь и современные информационные технологии : сб. тр. XII Междунар. науч.-прак. конф. - Томск: Изд-во ТПУ, 2014. - Т. 1 - С. 92-93.

28. Перминова, М. Ю. Алгоритм декомпозиции полиномов, основанный на разбиениях / М. Ю. Перминова // Научная сессия ТУСУР-2015 : материалы Всерос. научн.-технич. конф. - Томск: В-Спектр, 2015. - Ч. 5. -С. 312-314.

29. Expansion of x(1+x)/(1-x-2x2-2x3-x4) [Электронный ресурс] // The On-Line Encyclopedia of Integer Sequences. - Режим доступа: https://oeis.org/A210460 (дата обращения: 12.03.2014).

30. Formula for A039834 [Электронный ресурс] // The On-Line Encyclopedia of Integer Sequences. - Режим доступа: https://oeis.org/A039834 (дата обращения: 12.03.2014).

31. Ландо, С. К. Лекции о производящих функциях / С. К. Ландо. -3-е изд., испр. - М. : МЦНМО, 2007. - 144 с.

32. Пойа, Д. Математика и правдоподобные рассуждения / Д. Пойа ; перевод с англ. - 2-е изд., испр. - М.: Глав. ред. физ-мат. лит., 1975. - 464 с.

33. Производящая функция [Электронный ресурс] // Вики-конспекты университета ИТМО. - Режим доступа: http://neerc.ifmo.ru/wi-М/^ех^р?Ше=Производящая_функция (дата обращения 26.04.2016).

34. Кручинин, В. В. Комбинаторика композиций и её применение / В. В. Кручинин. - Томск : Изд-во В-Спектр, 2010. - 155 с.

35. Виленкин, Н. Я. Комбинаторика / Н. Я. Виленкин. - М.: Наука, 1969. - 328 с.

36. Виленкин, Н. Я. Популярная комбинаторика / Н. Я. Виленкин. -М.: Наука, 1975. - 208 с.

37. Comtet, L. Advanced Combinatorics, enlarged ed., Dordrecht: D. Reidel Publishing Co., 1974. - 343 p.

38. Сачков, В. Н. Введение в комбинаторные методы дискретной математики / В. Н. Сачков. - М.: Наука, 1982. - 384 с.

39. Stanley, R. P. Enumerative Combinatorics / R.P. Stanley. - vol. 2. -Cambridge University Press, 2001. - 600 p.

40. Flajolet, Ph. Analytic Combinatorics / Ph. Flajolet, R. Sedgewick. -Cambridge University Press, 2008. - 810 p.

41. Sloane, J. A. The On-Line Encyclopedia of Integer Sequences [Электронный ресурс]. - Режим доступа: https://oeis.org/.

42. Computer Algebra Systems [Электронный ресурс] // Worcester Polytechnic Institute. - Режим доступа: http://www.math.wpi.edu/IQP/BVCalcHist/calc5.html (дата обращения: 13.04.2014).

43. List of computer algebra systems [Электронный ресурс] // Wikipedia - The Free Encyclopedia. - Режим доступа:

http: //en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems (дата обращения: 13.04.2014).

44. Горский, Е. А. Системы компьютерной алгебры в обучении математике [Электронный ресурс] // Научная электронная библиотека «КиберЛенинка». - Режим доступа: http://cyberleninka.ru/article/n/sistemy-kompyuternoy-algebry-v-obuchenii-matematike (дата обращения: 23.03.2017).

45. Combinatorial Software and Databases. Generating Functions, holonomic functions [Электронный ресурс] // Fakultät für Mathematik. - Режим доступа: http://www.matumvie.ac.at/~slc/divers/software.html (дата обращения: 17.04.2014).

46. Wolfram Language & System. Documentation Center. Normal // Wolfram [Электронный ресурс]. - Режим доступа: http: //reference. wolfram. com/language/ref/Normal. html (дата обращения: 31.03.2017).

47. Wolfram Language & System. Documentation Center. SeriesCoefficient //Wolfram [Электронный ресурс]. - Режим доступа: http://reference.wolfram.com/language/ref/SeriesCoefficient.html (дата обращения: 19.04.2014).

48. Lesson 23: Power Series Expansions [Электронный ресурс] // Maplesoft. - Режим доступа: http://www.maplesoft.com/applica-tions/view.aspx?SID=3987& view=html (дата обращения: 19.04.2014).

49. Начала математического анализа в Maple [Электронный ресурс]. -Режим доступа: http: //physics. herzen. spb. ru/library/03/02/mapletut/page4. html (дата обращения: 20.04.2014).

50. Система компьютерной алгебры Maxima [Электронный ресурс]. -Режим доступа: http://maxima.sourceforge.net/ru/ (дата обращения: 23.03.2017).

51. Решение прикладных задач с помощью Maxima [Электронный ресурс] // Энциклопедия ЛУГа МИФИ. - Режим доступа: http: //lug. mephist. ru/wiki/Решение_прикладных_задач_с_помощью_Maxima (дата обращения: 22.04.2014).

52. Functions and Variables for ggf [Электронный ресурс] // Maxima, a Computer Algebra System. - Режим доступа: http://maxima.sourcefor-ge.net/docs/manual/de/maxima_49.html (дата обращения: 22.04.2014).

53. SageMath [Электронный ресурс]. - Режим доступа: http://www.sagemath.org (дата обращения: 21.02.2017).

54. Functional notation support for common calculus methods [Электронный ресурс] // SageMath Documentation. - Режим доступа: http://doc.sagemath.org/html/en/reference/calculus/sage/calculus/functional.html (дата обращения: 21.02.2017).

55. Magma Computational Algebra System [Электронный ресурс]. -Режим доступа: http://magma.maths.usyd.edu.au/magma (дата обращения: 22.04.2014).

56. Coefficients, Monomials and Terms [Электронный ресурс] // Magma. Computer. Algebra. - Режим доступа: https://magma. maths.usyd.edu. au/magma/handbook/text/226# 1970 (дата обращения: 22.03.2017).

57. PARI [Электронный ресурс]. - Режим доступа: http://pari.math.u-bordeaux.fr (дата обращения: 22.04.2014).

58. Polynomials and power series [Электронный ресурс] // PARI/GP. -Режим доступа: http : //pari .math.u-bordeaux.fr/dochtml/html .stable/Polyno-mials_and_power_series.html (дата обращения: 22.04.2014).

59. Кнут, Д. Искусство программирования. Т. 4, вып. 3: генерация всех сочетаний и разбиений / Д. Кнут : пер. с англ. - М. : ООО «И.Д. Вильямс», 2007. - 208 с.

60. Kreher, D. L. Combinatorial algorithms: Generation, Enumeration and Search / D. L. Kreher, D. S. Stinson. - Boca Raton: CRC Press, 1998. - 329 p.

61. Кручинин, В. В. Методы построения алгоритмов генерации и нумерации комбинаторных объектов на основе деревьев И/ИЛИ / В. В. Кручинин. - Томск: В-Спектр, 2007. - 200 с.

62. Кручинин, В. В. Алгоритмы генерации и нумерации композиций и разбиений натурального числа n / В. В. Кручинин // Доклады ТУСУРа. -

2008. - №2 (17). - С. 113-119.

63. Стенли, Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции / Р. Стенли. - М.: Мир,

2009. - 767 с.

64. Эндрюс, Г. Теория разбиений / Г. Эндрюс; перев. с англ. - М.: Наука. Главная редакция физико-математической литературы, 1982. - 256 с.

65. Barton, D. R. Polynomial decomposition / D. R. Barton, R. E. Zippel // Proceedings of Symposium on Symbolic and Algebraic Manipulation. - 1976. -P. 356-358.

66. Barton, D. R. Polynomial decomposition algorithms / D. R. Barton, R. E. Zippel // Journal of Symbolic Computation. - 1985. - Vol. 1, № 2. - P. 159-168.

67. Alagar, V. S. Fast polynomial decomposition algorithms / V. S. Alagar, M. Thanh // Proceedings of European Conference on Computer Algebra. - 1985. -P. 150-153.

68. Kozen, D. Polynomial decomposition algorithms / D. Kozen, S. Landau // Journal of Symbolic Computation. - 1989. - № 7. - P. 445-456.

69. Seong, J.-K. Polynomial Decomposition and Its Applications [Электронный ресурс]. / J.-K. Seong, G. Elber, M.-S. Kim. - Режим доступа: http://www.cs.utah.edu/~seong/decomposition.pdf (дата обращения: 09.07.2015).

70. Kruchinin, D. V. Application of a composition of generating functions for obtaining explicit formulas of polynomials / D. V. Kruchinin, V. V. Kruchinin // Journal of Mathematical Analysis and Applications. - 2013. - Vol. 404, № 1. -P. 161-171.

71. Кручинин, В. В. Рекурсивные композиции деревьев и их свойства / В. В. Кручинин // Доклады Томского государственного университета систем управления и радиоэлектроники. - 2007. - № 2(16). -С. 75-80.

72. OEIS - онлайн-энциклопедия целочисленных последовательностей [Электронный ресурс]. - Режим доступа: https://oeis.org/A029895 (дата обращения: 03.08.2015).

73. Кручинин, В. В. Разработка компьютерных учебных программ / В. В. Кручинин. - Томск : Изд-во Том. гос. университета, 1998. - 211 с.

74. Тарнавский, Т. Максима в науке и образовании [Электронный ресурс]. - Режим доступа: http://maxima.sourceforge.net/ru/maxima-tarnavsky-

I.html (дата обращения: 23.04.2017).

75. Online Algebra Calculator [Электронный ресурс]. - Режим доступа: http://maxima-online.org/ (дата обращения: 11.03.2016).

76. Додиер, Р. Коротко о Maxima / Р. Додиер; пер. с анг. А. Бешенова, 2007. - 16 с.

77. Чичкарёв, Е. А. Компьютерная математика с Maxima: Руководство для школьников и студентов / Е. А. Чичкарёв. - М. : ALT Linux, 2012. - 384 с. : ил. - (Библиотека ALT Linux).

78. Программирование в системе Maxima [Электронный ресурс]. -Режим доступа: http://server.179.ru/tasks/maxima/4.html (дата обращения:

II.03.2016).

79. Тихон Тарнавский. Maxima - укротитель выражений [Электронный ресурс] // Система компьютерной алгебры Maxima. - Режим доступа: http: //maxima. sourceforge. net/ru/maxima-tarnavsky-3. html (дата обращения: 11.03.2016).

80. Программный модуль получения явных выражений коэффициентов производящих функций, основанных на использовании композиции : свидетельство о регистрации электронного ресурса № 22861 / Перминова М. Ю.; организация-разработчик: ТУСУР. Зарегистрировано в Объединенном фонде электронных ресурсов «Наука и образование» 07.06.2017.

81. Стариков, В. И. Применение производящих функций для расчета колебательно-вращательных энергий радикала CH2 = Use of generating

functions in calculations of rovibrational energies of the CH2 radical /

B. И. Стариков, С. Н. Михайленко // Оптика атмосферы и океана. - [б. м.]: Институт оптики атмосферы им. В. Е. Зуева СО РАН, 1992. - Т. 5, № 09. -

C. 947-955.

82. Starikov, V. I. Expansion of the generating-function approach for nonrigid X2Y-type molecules by means of the Borel-type summation [Электронный ресурс] / V. I. Starikov, S. N. Mikhailenko // Journal of Physics B: Atomic, Molecular and Optical Physics. - 2000. - № 33. - P. 2141-2152. - Title screen. -Доступ по договору с организацией-держателем ресурса. - Режим доступа: http://iopscience.iop.org/0953-4075/33/11/314?fromSearchPage=true (дата

обращения: 27.09.2017).

Приложение А Акты внедрения

«УТВЕРЖДАЮ» Декан факультета электронной техники ТУСУР,

[01ГРТГТ т- ц

/,(/-* А.И. Воронин «Л^/» 2017 г.

Акт

о внедрении результатов кандидатской диссертационной работы Перминовой Марии Юрьевны в учебный процесс

Комиссией в составе: Легостаев Н.С., к.т.н., профессор, зам. зав. каф. промышленной электроники (ПрЭ) по учебно-методической работе; Орликов Л.Н., Д.т.н., профессор каф. электронных приборов (ЭП); Чистоедова И.А., к.т.н., доцент каф. физической электроники (ФЭ)

составлен настоящий акт о том, что результаты диссертационной работы Перминовой М.Ю. использованы в учебном процессе при выполнении лабораторных работ на факультете электронной техники ТУСУР в виде модуля получения явных выражений коэффициентов производящих функций, основанных на использовании композиции, по дисциплине «Компьютерные технологии в научных исследованиях». Использование программного модуля позволяет повысить качество обучения студентов.

факультета электронной техники

д.т.н., профессор каф. ЭП

к.т.н., профессор, зам. зав. каф. ПрЭ по учебно-методической работе

Н.С. Легостаев

Л.Н. Орликов

к.т.н., доцент каф. ФЭ

И.А. Чистоедова

АКТ

об использовании результатов кандидатской диссертационной работы Перминовой Марии Юрьевны

«Алгоритмы и программный модуль получения явных выражений коэффициентов производящих функций»

Настоящим актом подтверждается использование при выполнении гос. задания Министерства образования и науки РФ на выполнение НИР в 20142015 гг. на тему «Моделирование адаптивных энергонасыщенных объектов с применением методов производящих функций и методов самоорганизации моделей» (номер государственной регистрации НИР: 114102840081) в рамках проекта № 8.2571.2014 следующих результатов диссертационной работы Перминовой М. Ю.: алгоритма декомпозиции полиномов, основанного на генерации разбиений; алгоритма получения явных выражений коэффициентов производящих функций; программного модуля получения явных выражений коэффициентов композиции производящих функций.

Использование указанных результатов позволило сформулировать подход к созданию алгоритмов представления экспериментальных данных в виде композиции производящих функций.

д.т.н., профессор кафедры ПрЭ ТУСУР 7 Кобзев

к.т.н., доцент кафедры ПрЭ ТУСУР ¿„-..-»./и^ Ю. Н. Тановицкий

федеральное государственное бкщжетное научное учреждение

ИНСТИТУТ УПРАВЛЕНИЯ ОБРАЗОВАНИЕМ РОССИЙСКОЙ АКАДЕМИИ

ОБРАЗОВАНИЯ

СВИДЕТЕЛЬСТВО О РЕГИСТРАЦИИ ЭЛЕН РОЕМОГО РЕСУРСА

№22861

Настоящее свидетельство выдано на электронный ресурс, отвечающий требованиям новизны и приоритетности:

Программный модуль получения явных выражении коэффициентов производящих функций, основанных на использовании композиции

Дата регистрации: 07 июня 2017 года

Автор: Перминова М.Ю. С

организация-разработчик: ФГБОУ ВО «Томский государственный университет

систем управления и радиоэлектроники»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ОБЪЕДИНЕННЫЙ ФОНД ЭЛЕКТРОННЫХ РЕСУРСОВ "НАУКА и ОБРАЗОВАНИЕ"

(основан в 1991 году)

Директор ФГБНУ ИУО РАО,

С. Неустроев

доктор экономических наук

Руководитель ОФЭРНи®, по

раоотник науки и техники Ро,реии

Галкийа

/ч

^ Удостоверяющий

t

центр Сибири

634009, г. Томск, пр-т Ленина, 110 ИНН/КПП/ОГРН 7017311494/701701001 /1127017020767

Общество с ограниченной ответственностью «Удостоверяющий центр Сибири»

тел: факс: e-mail: http://

(382 2)900-111 (382 2) 900-111 [e-mail] www.udcs.ru

АКТ

об использовании результатов кандидатской диссертационной работы Перминовой Марии Юрьевны «Алгоритмы и программный модуль получения явных выражений коэффициентов

производящих функций»

Настоящим актом подтверждается использование при выполнении НИР в 20152017 гг. на тему «Разработка перспективных алгоритмов защиты информации» следующих результатов диссертационной работы Перминовой М. Ю.: алгоритмов генерации и нумерации класса разбиений натурального числа "п" с заданными ограничениями на части.

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

Директор ООО «УЦ Сибири»

ерфильев А.В./

Приложение Б Схемы алгоритмов

Рисунок Б.1 - Схема First

Рисунок Б.2 - Схема Next

раг^[]] := рагй[] + 1

Рисунок Б.3 - Схема алгоритма Шгапк

Рисунок Б.4 - Схема алгоритма Rank

Рисунок Б.5 - Схема алгоритма Ое1ВесотроБШоп

Приложение В Пример синтаксического дерева

Приложение Г Примеры записей из базы операций и композит

Сотроз^а_х2х2хЗ (п, к) : =Ьп.пот1а1 (2*к, п-к) ;

В табличном виде композита представляется треугольником. Треугольник композиты данной производящей функции:

1

2 1 1 4 1 0 6 6 1 0 4 15 8 1 0 1 20 28 10 1 0 0 15 56 45 12 1

/* f (х)=х/(1-х)-хЛ3 - рациональная производящая функция */ Composita_Pascalmx3(n,k):= sum (

binomial(k,j)*binomial(n-3*(k-j)-1,j-1)* (-1)Л (k-j) j,ceiling ((3*k-n+l}/3),k ) +(-1)~k*kron_delta(n,3*k);

Треугольник композиты:

1

1 1 0 2 1 1 1 3 1 1 2 3 4 1 1 4 4 6 5 1 1 4 9 8 10 6 1

/* f(x)=ln(l+x) - производящая функция логарифма */ Composita_ln(n,k):=stirlingl(n,k)*k 1/n!;

Треугольник композиты:

1

-1/2 1 1/3 -1 1

-1/4 11/12

1/5 -5/6 7/4

137/180 -15/8

-7/10 29/15 -7/2

1/6

-3/2

17/6

1/7

-2 1

-5/2 1 25/6 -3 1

/* f(x)=(1-sqrt(l-4x))/2 - радикал */

CompositaCatalan(n,k):=k/n*Composita_Pascal(2*n-k,n); Треугольник композиты:

14 14 42 42 132 132 90

2 2 1 5 5 3 1

9 4 1 28 14 5 1 48 20 6 1

/* f(x)=arcsin (x) - тригонометрическая производящая функция */ Composita_arcsin(n, k): = ((-1) Л (n-k)+l)/2*kl * sum ( (

sum (

(2-Ai*stirlingl (i+k, k) * binomial (j+k-1, i+k-1) ) / (i+k) ! , i,0,j)

)*(-1)л((3*j)/2)*binomial ( (n-2)/2, (n-j-k)/2), j,0,n-k);

1

1

1

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

0

1/6

0

3/40 0

0 8/45

5/112 0 37/120

1/3

0

0

1/2

0

0

2/3

0

0 1

5/6 0 1

Треугольник композиты:

0

1/5040

1/120

0

0

2/45

1/6

0

13/120

0

1/3

0

0

1/2

0

0

2/3

0 1 0 1 5/6 0 1

Треугольник композиты:

1/2 2

1/6 2 3

1/24 4/3 9/2

1/120 2/3 9/2 8

1

4 1 5 1

1/720

4/15 27/8 32/3 25/2 6 1

1

1

1

1

1

1

1

1

1

1

1

/* формула композиты производящей функции f (х)=ах+ЬхЛ2 */ Compositaab(n, k, a, b):=binomial(k,n-k)*аЛ(2*k-n)*ЬЛ(n-k);

/* формула композиты производящей функции f(x)=sin(x) */ Compositasin(n,k):=

(1+ (-1)A(n-k))*2Л(-k) * sum (

(-1)Л((n+k)/2-i)*binomial(k,i)*(2*i-k) Лп/п! , i,0,floor(k/2)

);

/* формула, композиты произведения производящих функций F(x) и В (х) */ Composita_Product2(F_,В_,п,k):=(sum(F_(i,k)*B_(n-i,k),i,k,n));