Ноу Інти, лекція, обчислення функцій на послідовностях

Індуктивні функції на послідовність у вирішенні питань індуктивні розширення

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

довжини n. За допомогою знака позначимо операцію приписування нового елемента праворуч до послідовності (її називають також конкатенацией):

Нехай f (S) - деяка функція на безлічі послідовностей, наприклад, сума елементів послідовності. Функція називається індуктивної, якщо при додаванні нового елемента до послідовності нове значення функції можна обчислити, знаючи тільки старе значення функції і доданий елемент. На математичній мові функція

де W - безліч всіх послідовностей, складених з елементів деякої множини X. індуктивності, якщо існує функція G від двох аргументів

така, що для будь-якої послідовності S з W і будь-якого елемента a з X значення функції f на послідовності S. до якої доданий елемент a. обчислюється за допомогою функції G:

Функція G по парі (y, a). де y - старе значення функції f на послідовності S і a - елемент, доданий до послідовності, обчислює нове значення y. рівне значенню функції f на новій послідовності.

У прикладі з сумою елементів послідовності функція G дорівнює сумі елементів y і a:

(Тобто функція f дорівнює композиції відображень F і P. f = P * F.) Відображення P зазвичай називають проекцією безлічі Z на Y.

Як побудувати індуктивне розширення функції f. Це творчий момент, готового рецепту на всі випадки не існує. Неформальний рецепт наступний: треба зрозуміти, якої інформації не вистачає для того, щоб вміти обчислювати нове значення функції на послідовності при додаванні до послідовності нового елемента. Цю інформацію треба зберігати додатково до значення функції. Звідси і з'явився термін розширення: обчислюється більш складна, розширена, функція. щоб по ній потім відновити вихідну. Як правило, значенням індуктивного розширення F є пара (y, h). де y - значення вихідної функції f. а h - деяка додаткова інформація. що дозволяє Переобчислювати значення y при додаванні нового елемента до послідовності. Таким чином, безліч Z значень індуктивного розширення

найчастіше є безліччю пар (y, h). тобто декартових твором:

Ми бачимо, що для обчислення нового значення похідної потрібно знати старе значення похідної, а також старе значення многочлена. Отже, додатково до значення похідної многочлена треба зберігати ще значення самого многочлена. Таким чином, індуктивним розширенням функції. рівній похідною многочлена в точці t. є пара (значення похідної, значення многочлена):

Нове значення похідної обчислюється за наведеною вище формулою через старе значення похідної і старе значення многочлена. Після цього обчислюється нове значення многочлена за схемою Горнера.

Випишемо алгоритм обчислення похідної многочлена.

Інший приклад неіндуктівний функції - це середнє арифметичне значення елементів послідовності. Індуктивним розширенням є пара (сума елементів послідовності, довжина послідовності):

Легко бачити, що функція F індуктивності. При відомому значенні функції F не складає труднощів обчислити вихідну функцію:

Отже, в кожному конкретному випадку при обчисленні неіндуктівний функції f треба придумати її індуктивний розширення F і в програмі обчислювати спочатку індуктивне розширення F. а потім за значенням F обчислювати необхідне значення вихідної функції f.