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

Содержание к диссертации

Введение

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

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

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

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

1.4 Выводы 26

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

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

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

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

2.4 Выводы 62

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

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

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

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

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

3.5 Выводы 84

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

Заключение 88

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

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

Введение к работе

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

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

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

СКА появились в начале 1960-х годов и поэтапно развивались, в основном, в двух направлениях: теоретическая физика и создание искусственного интеллекта. Первым успешным примером была новаторская работа Мартина Велтмана (позднее удостоенная Нобелевской премии по физике), который в 1963 г. создал программу для символьных вычислений (для нужд физики высоких энергий), которая была названа Schoonschip. СКА первого поколения были способны выполнять символьные вычисления: интегрирование,

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна.

1. Разработан новый алгоритм генерации разбиений, отличающийся от аналогов тем, что позволяет генерировать класс ограниченных разбиений (N, M, n), где n - натуральное число, M - части разбиения, каждая из которых не превосходит N.

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

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

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

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

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

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

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

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

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

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

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

Соответствует п. 3 паспорта специальности 05.13.17 - Исследование методов и разработка средств кодирования информации в виде данных. Принципы создания языков описания данных, языков манипулирования данными, языков запросов. Разработка и исследование моделей данных и новых принципов их проектирования.

2. Алгоритм декомпозиции полиномов, основанный на генерации ограниченных разбиений, имеет временную сложность O (п²). При этом степень

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

Соответствует п. 4 паспорта специальности 05.13.17 - Исследование и разработка средств представления знаний. Принципы создания языков представления знаний, в том числе для плохо структурированных предметных областей и слабоструктурированных задач; разработка интегрированных средств представления знаний, средств представления знаний, отражающих динамику процессов, концептуальных и семиотических моделей предметных областей.

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации по теме диссертации. Материалы диссертации опубликованы в 18 работах, в том числе 4 публикации в рецензируемых журналах из перечня ВАК.

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

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

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

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

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

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

Как писал Д. Пойа [32]: «Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет - мешок». Производящие функции используются для: 1) компактной записи информации о последовательности; 2) нахождения зависимости an{n) для последовательности a(n), заданной рекуррентным соотношением. Например, для чисел Фибоначчи; 3) нахождения рекуррентного соотношения для последовательности -вид производящей функции может помочь найти формулу; 4) исследования асимптотического поведения последовательности; 5) доказательства тождеств с последовательностями; 6) решения задачи подсчета объектов в комбинаторике. Например, в доказательстве пентагональной теоремы или в задаче нахождения количества расстановок m ладей на доске п х п; 7) вычисления бесконечных сумм [33]. Начало методу производящих функций положил в середине XVIII в. английский математик А. де Муавр (A. De Moivre). Развитие данного метода продолжил знаменитый математик Л. Эйлер (L. Euler).

Степень производящих функций. Пусть задана производящая функция F(x) = I f(n)xn, тогда для производящей функции [F(x)f = = X F(n,k)x" справедливо рекуррентное выражение: и F(n,k) = (и), к = 1, п T,f(i)F(n-i,k-1), к 1. Пусть F(x) = I f(n)x" - производящая функция, у которой и 0 отсутствует свободный член (0) = 0. Композитой обыкновенной производящей функции F(x) = I f(n)xn называется функция FA(n,k), и 0 являющаяся коэффициентом производящей функции [F(x)f = = I F\n,k)xn [34]. п к Большинство известных книг и монографий, посвященных комбинаторным проблемам и производящим функциям, используют коэффициенты степеней производящих функций, однако как самостоятельный объект исследования эти коэффициенты не рассматриваются. Например, Н. Виленкин «Комбинаторика» [35] и «Популярная комбинаторика» [36], Л. Комтет (L. Comtet) «Advanced Combinatorics» [37], В. Сачков «Введение в комбинаторные методы дискретной математики» [38], Р. Стенли «Enumerative Combinatorics (vol. 2)» [39], Ф. Флажоле и Р. Сэджвик (R. Sedgewick) «Analytic Combinatorics» [40]. Поэтому актуальной является задача исследования степеней производящих функций и их свойств.

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

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

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

Решение задачи представления полиномов в виде композиции двух полиномов имеет некоторую историю. Так в 1976 г. американские ученые Д. Бартон (David R. Barton) и Р. Зиппель (Richard Zippel) показали, что декомпозиция полиномов может упростить поиск корней полиномиальных уравнений в символьном виде. При этом они указали, что многие системы символьной алгебры поддерживают декомпозицию полиномов для таких целей [65]. В 1985 г. эти же ученые предложили два алгоритма декомпозиции полиномов [66]. Первый из этих алгоритмов находил коэффициенты полиномов двух переменных, второй - полиномов одной переменной. Упрощенную версию второго алгоритма в том же году представили канадские ученые В. Алагар (V. S. Alagar) и М. Тан (M. Thanh) [67]. Их алгоритм был основан на дифференцировании исходного полинома.

В 1989 г. американские ученые Д. Козен (Dexter Kozen) и С. Ландау (Susan Landau) предложили свой алгоритм декомпозиции полиномов в совместной статье [68]. По данному алгоритму находились коэффициенты внутреннего полинома. Затем для получения коэффициентов внешнего полинома решалась система уравнений, основанная на матрице коэффициентов внутреннего полинома. Далее проводилась проверка ранее найденных коэффициентов.

В 2003 г. корейские ученые Джун-Кюн Сон (Joon-Kyung Seong) и Мен-Су Ким (Myung-Soo Kim) вместе с ученым из Израиля Г. Элбером (Gershon Elber) предложили еще один алгоритм декомпозиции полиномов [69]. Он состоял из двух частей. В первой части алгоритма по исходному полиному вычислялся внутренний полином. Затем во второй части находился внешний полином.

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

Получение системы уравнений. Пусть дан полином t . 2 3 F(x) = Y,fiXl = f1X+f2x + f3x +...+ftx . Необходимо представить F(x) в виде i=1 композиции двух полиномов А(х) и В(х), т. е. F(X) = B(A(X)), методом, основанным на разбиениях. При этом: т . А(х) = X щх1 = щх+СІ2Х + а3х + атхт , /=1 B(x)=Zbix =b1x+b2x2 +b3x3 +.. .+bsx, І=1 где сії и &г- - искомые коэффициенты; т и s - степени полиномов А(х) и В(х) соответственно (t = m-s). Данная задача имеет множество решений, в частности полином композиции можно представить следующим образом: F(x) = BJA (x% Ва(х) = аВ(х), Аа(х) = А\—\гдеаф0. Композицию производящих функций рассчитаем по формуле (1.3): №=%АА(п,к)Ь(к), к=1 где коэффициенты АА(п,к) представляются на основе композиций натурального числа п: АА(п,к) = Е aX1aX2...aXk, пкєС„ где Сп - множество всех композиций натурального числа п; пк - композиция к Х?ч=я, имеющая ровно к частей. Поскольку существует связь между /=1 композициями натурального числа и разбиениями, можно записать представление АА(п,к) на основе разбиений ( к Л АА(п,к)= X aJ1aJr2...aJl, (2.2) \LkeP„\1 j 2--Jl) п 2 п где Рп - множество всех разбиений натурального числа п; ]лк - разбиение, имеющее ровно к частей; rt - не повторяющиеся части разбиения \лк; I - число не повторяющихся частей; ; - число повторений частей гг в разбиении. Здесь в разбиении в отличие от композиции не учитывается порядок частей, поэтому в выражении (2.2) мультиномиальный коэффициент показывает, сколько существует вариантов композиций, состоящих из тех же частей разбиения. При этом справедлива следующая система уравнений \j1+J2+ — + Jl=K Ш J2 Л (2.3) [r1J1+r2j2 + --- + rlJl=n, где / к . Решение системы уравнений (2.3) есть все разбиения числа п, в которых ровно А: частей [34]. Подставив (2.2) в (1.3), получим систему из п уравнений: п I I k=1 \ikeP„\ 12---JlJ к aJ1a...a4k=fn. (2.4) Для получения системы уравнений (2.4) степени полиномов композиции должны быть известны. Для дальнейшего изложения будем предполагать, что т и s нам известны.

Учитывая, что степени полиномов ограничены, части разбиения rt не должны превышать т, т. е. rt m. Также коэффициенты Ък ограничены степенью s полинома В(х), т. е. к s. Степень t исходного полинома F(x) ограничивает значения и, т. е. n t.

Анализ (2.4) показал, что для получения системы уравнений необходимо получить все разбиения (m,s,ri), где п - число, представляемое разбиением; s - число частей разбиения, каждая из которых не превосходит т. Г. Эндрюс получил рекуррентную формулу для числа разбиений p(m,s,n): p(m,s,n)=p(m,s-1,n)+p(m-1,s,n-s). Используя эту формулу и методы построения алгоритмов комбинаторной генерации [34, 62, 71], разработаны оригинальные алгоритмы генерации и нумерации таких разбиений (см. п. 2.1 диссертационной работы).

Свойства системы уравнений. Исследуем свойства системы уравнений, которая базируется на генерации разбиений. Для этого рассмотрим композиционную формулу (1.3), на которой основаны уравнения в системе. Коэффициенты АА(п,к) можно представить в виде треугольной матрицы л2,1 л2,2 jA 3A ЛА л3,1 ЛЪ,2 л3,3 Ап,1 Ап2 Ап,3 Апп. В первом столбце данной матрицы записаны коэффициенты производящей функции А(х), во втором - коэффициенты производящей функции [A(x)f,…, в к-м столбце матрицы - коэффициенты производящей функции [ (х)] [34]. Так как степень т полинома А(х) известна, значит, число коэффициентов производящей функции А(х) равно т. Поэтому, основываясь на свойствах треугольной матрицы [34], можно сделать вывод о том, что в первом столбце будет т элементов, не равных нулю. Во втором столбце нули начнутся на (т+1)-й позиции, в третьем - на (2т+1)-й, в четвертом - на (3ш+1)-й,…, в (к-1)-м - на ((к-2)т+1)-й позиции, а в к-м -на ((к-1)т+1)-й позиции. Таким образом, формула для подсчета ненулевых коэффициентов в к-м столбце треугольной матрицы имеет вид (кт-к+1). Наглядно это можно представить следующим образом (для т = 2):

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

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

Возможности Maxima аналогичны возможностям таких систем, как Mathematica и Maple. Главное отличие Maxima заключается в том, что она является бесплатной и распространяется с открытым исходным кодом, то есть является свободным программным обеспечением (ПО). Использование свободного ПО в науке более естественно, чем использование коммерческого ПО. Это обусловлено тем, что для всех наработок свободного ПО действуют принципы открытости и общедоступности. Те же принципы применимы и к результатам научной деятельности. Таким образом, все расширения функционала Maxima и дополнительные библиотеки, созданные в ходе научного исследования, являются непосредственной частью результатов научных исследований. Такие результаты могут использоваться и распространяться пользователем без каких-либо ограничений, налагаемых лицензиями исходного ПО. В случае коммерческого ПО существуют значительные ограничения, начиная от невозможности свободно (и законно) передавать само ПО вместе с наработками и вплоть до возможных патентных исков от компании-разработчика программного обеспечения в случае распространения самодельных дополнительных библиотек к нему.

Свободное ПО также востребовано в области высшего образования. Использование для учебных нужд именно свободного ПО – это возможность для вуза, студентов и преподавателей иметь в своем распоряжении легальные копии такого ПО без существенных денежных затрат [74].

Кроме того, Maxima – единственная программа, переносимая на почти все основные операционные системы и платформы, даже на карманные компьютеры. Исходный код Maxima полностью написан на лиспе, для программирования в Maxima используется свой собственный язык, тесно интегрированный с лиспом, но больше похожий на привычные процедурные языки программирования. Работать с Maxima можно как в консольной версии программы, так и с использованием графического интерфейса (например, wxMaxima) [51]. Также для решения несложных задач есть онлайн-версия [75].

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

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

Если переменная является локальной внутри функции или блока, ее значение локально, но остальные свойства (заданные declare) глобальны. Функция local делает переменную локальной в отношении всех свойств [76].

Язык Maxima содержит все необходимые средства для разработки программ: условные инструкции, циклы, массивы. Вывод на экран осуществляется функциями: 1) display. Синтаксис вызова: display(expr1,expr2,...). Выражения из списка аргументов выводятся слева направо (сначала – само выражение, а затем после знака равенства – его значение); 2) disp. Синтаксис вызова: disp(expr1,expr2,...). Выводит на экран только значение выражения после его интерпретации; 3) grind. Синтаксис вызова: grind(expr). Осуществляет вывод в консоль Maxima аналогично disp, но в форме, удобной для ввода с клавиатуры; 67 4) print. Синтаксис вызова: print(expr1,expr2,...). Выражения expr1,expr2,... интерпретируются и выводятся последовательно в строчку (в отличие от вывода, генерируемого функцией display). Возвращает значение последнего интерпретированного выражения [77].

Как в условных выражениях, так и в циклах вместо простых операторов можно писать составные операторы, т. е. блоки. Стандартный блок имеет вид: block([r,s,t],r:l,s:r+l,t:s+l,x:t,t t);

Сначала идет список локальных переменных блока (глобальные переменные с теми же именами никак не связаны с этими локальными переменными). Список локальных переменных может быть пустым. Далее идет набор операторов. Упрощенный блок имеет вид: (х:1,х:х+2,а:х); Обычно в циклах и в условных выражениях применяют именно эту форму блока. Значением блока является значение последнего из его операторов. Внутри данного блока допускаются оператор перехода на метку и оператор return [77].

Условная инструкция if имеет следующий синтаксис: if условие then выражение! else выражение2 При этом инструкция if возвращает значение одного из двух выражений. Например, присвоить переменной m максимум из двух переменных a и b можно двумя способами: if а b then m:a else m:t или m: if a b then a else b Синтаксис цикла for следующий [78]: for переменная: начальное_значение step шаг [thru, while, unless] конечное_значение do выражение Ключевые слова thru, while, unless указывают на способ завершения цикла: по достижении переменной цикла значения конечное значение; пока выполняется условие конечное значение; пока не будет достигнуто условие конечное значение [77]. Пример: for i:2 step 2 thru 100 do print(і)$ Любые части этой конструкции (step, thru) можно опускать. При нормальном завершении цикла возвращаемая величина - атом. Принудительный выход из цикла осуществляется при помощи оператора return, который может возвращать произвольное значение.

Контрольная переменная цикла - локальная внутри цикла, поэтому её изменение в цикле не влияет на контекст (даже при наличии вне цикла переменной с тем же именем) [77]. Синтаксис цикла while следующий: while условие do выражение В качестве условий можно использовать операторы сравнения , , =, =, =, # и логические операторы and, or, not [79]. Наряду с простейшим способом задания функции, Maxima допускает создание функции в виде последовательности операторов: f(x):=(exprl, expr2,..., exprn); Значение, возвращаемое функцией - значение последнего выражения exprn. Чтобы использовать оператор return и изменять возвращаемое значение в зависимости от логики работы функции, следует применять конструкцию block, например: f(х) := block ([], exprl, ..., if (а 10) then return (a), . . ., exprn); При a 10 выполняется оператор return и функция возвращает значение a, в противном случае - значение выражения exprn. Формальные параметры функции или блока - локальные и являются видимыми только внутри них. Кроме того, при задании функции можно объявить локальные переменные (в квадратных скобках в начале объявления функции или блока) [77].

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

Сначала объявляется переменная filesearchmaxima. Она указывает списки каталогов для поиска файлов функциями load, demo и некоторыми другими функциями Maxima. В данном случае к каталогам, которые заданы в Maxima по умолчанию, добавляется один пользовательский каталог, путь которого указан в квадратных скобках. Далее функцией load загружаются обе части программного модуля: Lib и Decomposition. Затем вызывается главная функция AllFunc(F(x)), где F(x) - производящая функция в синтаксисе Maxima. Результатом работы AllFunc(F(x)) является закрытый вид выражений коэффициентов/ ).

Рассмотрим данный пример более подробно. Исходная производящая функция F(x) равняется sin(x)+sin(x)A2. F{x) записана в синтаксисе Maxima, ошибок нет. Поэтому далее осуществляется семантический анализ F(x). Раскладываем F(x) в ряд Тейлора функцией taylor и получаем: 2 х3 х4 Х5 2х6 х7 х8 х9 2х10 При этом нулевой член равен 1. То есть семантический анализ прошел успешно. Далее осуществляется проверка, есть ли F(x) в базе. Функция CompareWithBase возвращает «false», GetNumbsInBase возвращает пустой список [], следовательно, функция GetListCompos возвращает -1. Это означает, что F{x) отсутствует в базе.

На следующем шаге осуществляется проверка, можно ли представить F{x) композицией полиномов. Вызывается функция SolvelnNumbnew, которая вызывает функцию SearchDegrees. Она возвращает пустой список [], так как в полиноме присутствует функция sin(x). Поэтому функция SolvelnNumbnew возвращает -1, что означает, что F{x) не может быть представлена композицией полиномов.

Далее F(x) необходимо разбить на элементарные составляющие. Вызывается функция treebuilding. Результат работы функции -синтаксическое дерево (рис. 3.3).

Дерево, представленное на рис. 3.3, представляет собой список L=[+,[A,[sin,x],2],[sin,x]]. Далее по списку L функцией ListSubExp формируется список подвыражений: ListSubExpFunc возвращает список с исходной производящей функцией [sin(x)A2+sin(x)], так как F{x) имеет вид, отличный от funcl(fimc2(x)). PrintE(list) возвращает список подвыражений Luniq = = [8ІП(Х)Л2+8ІП(Х),8ІП(Х),8ІП(Х)Л2,8ІП(Х)]. Таким образом, функция ListSubExp возвращает список ListLL = = [8ІП(Х)Л2+8ІП(Х),8ІП(Х),8ІП(Х)Л2,8ІП(Х)]. Рисунок 3.3 - Синтаксическое дерево sin(jc) + sin(jc)2 На следующем шаге функция ComposYavn проверяет вид внешней функции В{х) композиции F(x) = B(A(x)). Так как В{х) не является тригонометрической, гиперболической, логарифмической функцией или функцией квадратного корня, то ComposYavn возвращает -1. После этого вызывается функция GetListSubexps: RepeatSubExp возвращает R = [sin(x)]; Replace возвращает функцию F{x) после замены в ней повторяющихся подвыражений Ri, то есть хЛ2+х.

Таким образом, GetListSubexps возвращает список [sin(x),x 2+x]. После того, как найдены внешняя и внутренняя функции, их композиты находятся в базе Lib. Это осуществляет функция GetNumbsInBase(F(x)). В случае с sin(x) она возвращает [8], с x 2+x – [18, 24]. Далее по номерам функция GetListCompos возвращает сами композиты:

Далее получаем явное выражение коэффициентов композиции производящих функций. Вызывается функция Superposition(A(x),B(x)). Входными параметрами для неё служат композиты, которые вернула функция GetListCompos. На выходе получаем список с двумя формулами f(n). Функция ChooseForm оставляет формулу с наименьшим количеством переменных. Таким образом, получаем: lp+lj (2i-k)" (-1) 1 На рисунках 3.4 и 3.5 показаны примеры работы модуля в Maxima. Рисунок 3.4 – Примеры работы программного модуля по нахождению явных выражений коэффициентов композиции производящих функций

В случаях, когда явное выражение коэффициентов композиции производящей функции не будет найдено, будет показано одно из следующих сообщений (рис. 3.5). Рисунок 3.5 – Примеры работы программного модуля, когда явное выражение коэффициентов композиции производящей функции не найдено

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

На основе алгоритма, базирующегося на методе [13], разработана структура программного модуля получения явных выражений коэффициентов композиции производящих функций. Для программной реализации модуля выбрана система компьютерной алгебры Maxima. Главными её преимуществами являются: бесплатность, распространение с открытым исходным кодом и переносимость на основные операционные системы. Для программирования в Maxima используется свой собственный язык, тесно интегрированный с лиспом, но больше похожий на привычные процедурные языки программирования.

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