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

         

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


Производящая функция последовательности {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. Содержание  Назад  Вперед




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