25. Производящие функции.

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

26. Целочисленные функции округления.

27.Иерархия.Асимптотическая аппроксимация.

28.Формула суммирования Эйлера-Маклорена.

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

где   - Бернулли числа, R_n - остаточный член. С помощью Бернулли многочленов B_n(t), В _n(0)=В _п остаточный член записывается в виде:

Для n=2sостаточный член R_2s может быть представлен с использованием чисел Бернулли:

Если производные   и  имеют одинаковые знаки и не меняют знака на [ р, т],то Э.-М. ф. играет важную роль при изучении асимптотич. разложений, в теоретико-числовых оценках, в конечных разностей исчислении. Э.-М. ф. была впервые приведена Л. Эйлером [1] в виде:   где S - сумма первых членов ряда с общим членом t(п), S=t=0 при n=0, а коэффициенты определяются рекуррентными соотношениями:

 Независимо формула была открыта позднее К. Маклореном.

29.Графы, ориентированные графы, псевдографы, мультиграфы.

Графом G(V,E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е двухэлементных подмножеств множества V (Е — множество рёбер). G(V, E) = (V;E), V^0, Е С 2V кVe G E |e| = 2. Если элементами множества Е являются упорядоченные пары (то есть Е с V х V), то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом). Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

30.Изоморфизм и гомеоморфизм графов, двудольные графы.Говорят, что два графа G\1V1,Ei) и G2(V2,E2) изоморфны (обозначается G1 ~ G2), если существует биекция h: V1—► V2, сохраняющая смежность ei = (u,v) е Ех <=> е2 = (h(u),h(v)) e E2. Пусть А = (-А, fi, П) и В = (В, П, П) — две однотипные алгебраические системы. Отображение h: А-± В называют гомоморфизмом алгебраической системы А в алгебраическую систему В, если выполняются следующие условия: 1) для любой п-арной операции ш ( ) и любых элементов 2) для любого п-арного отношения тг (n ^ 1) и любых элеэлементов следует Двудольный граф (или биграф, или чётный граф) — это граф G(V, E)y такой что множество V разбито на два непересекающихся множества V1 и V2 (Vi U V2 = V2 &V1 П V2 = 0), причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из Vi с вершиной из V2). Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит

все рёбра, соединяющие множества V\ и V2l то он называется полным двудольным графом..