Алгоритмы, структуры данных

       

Описание метода


Производящая функция последовательности {an}, n>=0 – формальный степенной ряд:

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

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

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


где i – номер итерации

t – функция преобразования переменной v, принадлежащая множеству T

Vi-1 – значения переменных, полученные на предыдущей итерации

Vi – значения переменных, полученные на текущей итерации

Производящие функции (или выражения для vi) достаточно просто можно получить для присваиваний вида:

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

Пользуясь методикой из [2] каждый оператор присваивания вида

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


где Fv(z) – производящая функция для переменной v

FV – множество производящих функций для переменных, принадлежащих множеству V

G – некоторая алгебраическая функция

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

Для каждого из слагаемых существует следующий выбор:

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

  2. Производящую функцию нельзя получить непосредственно. Например, ai - bi. В этом случае, необходимо подставить выражения для всех переменных (ai и bi), а затем найти производящую функцию для последовательности, которую генерирует это выражение при изменении i от 0 до бесконечности.

  3. Производящую функцию нельзя получить непосредственно (как в случае 2), но выражения для ai и bi (см. случай 2) невозможно получить без знания выражения для vi+1. В этом случае предлагаемый метод не работает.

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

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

Найдем производящую функцию для данной последовательности

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



для c1 = 1:
(*)


для c1 <> 1:


2. Линейная комбинация переменных


где k – номер переменной (переменные с номерами меньше k изменились в текущей итерации, с номером большим k – будут изменены позднее)
Применяя манипуляции, подобные использованным в предыдущем пункте, можно получить следующий результат:

Отсюда можно получить выражение для Vk(z), а из него – выражение для vki.
3. Многочлен от переменных, выражения для которых имеют вид (*)

Метод, применяемый в предыдущих примерах здесь не сработает, поэтому необходимо выполнить подстановку выражений для vji в данную формулу, что приведет к появлению многочлена от i:

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

Отсюда можно получить производящие функции для in:
i1:


i2:

и так далее.

Таким образом, производящая функция для vki будет иметь вид:


где ri – коэффициент при in в R(i), а Ii(z) – производящая функция для in.

Содержание раздела