Тестирование при организации текущего контроля

При желании эту таблицу можно продолжать сколько угодно. Полученная бесконечная последовательность

, , , …, , , …

называется последовательностью или рядом Фибоначчи, а ее члены - числами Фибоначчи.

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

Рекуррентными последовательностями являются, например, арифметические и геометрические прогрессии:

, , , …, , …

, , , …, , …

В этих последовательностях и соответственно.

Последовательность называется рекуррентной (возвратной) последовательностью порядка , если существует формула, по которой член последовательности вычисляется по k предыдущим членам . Такая формула называется рекуррентным соотношением или рекуррентным уравнением порядка . Естественно, что при этом должны быть известны (заданы) и начальные члены .

Так, формула является рекуррентным соотношением порядка 2. Положив, например, , получим рекуррентную последовательность

1, 2, 3, 5, 16, …

Формула - рекуррентное соотношение третьего порядка.

Для дальнейших рассуждений необходимо уметь произвольное рекуррентное соотношение записывать в виде общей формулы

.

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

Например, формула означает, что , а правило состоит в последовательном выполнении двух действий - возведения в квадрат и вычитания.

Решения рекуррентного соотношения. Согласно определению рекуррентной последовательности k-го порядка с заданными начальными членами ее член выражается через ; - через и т.д. Подобным образом можно постепенно вычислить любой член последовательности. Однако часто необходимо знать только какой-то отдельный конкретный член последовательности, обычно с достаточно большим номером. Подобный способ его вычисления является весьма нерациональным. В этих случаях удобно знать формулу n-го (общего) члена последовательности, т.е. функцию , с помощью которой по номеру n непосредственно вычисляется n-ый член. Образно говоря, можно считать своеобразным «паспортом» или «визитной карточкой» последовательности. Поэтому целесообразно дать определение.

Пусть последовательность задана рекуррентным соотношением k-го порядка. Функция , называется решением рекуррентного соотношения, если при подстановке выражения в это соотношение оно оказывается справедливым для каждого .

Чтобы установить, является ли функция - решением рекуррентного соотношения -го порядка, приходится подставлять в это соотношение и , ..., , ; будем называть такой процесс алгоритмом проверки решения.

Покажем, например, что функция является решением рекуррентного соотношения .

Согласно алгоритму проверки решения находим , , , . Поэтому

=.

С помощью формулы можно найти любой член последовательности 13, 23, …, n3, …, задаваемой данным рекуррентным соотношением.

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

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

Иными словами, математическое выражение является общим решением рекуррентного соотношения -го порядка, если выполняются условия:

1) оно зависит от k произвольных постоянных ;

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

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

Действительно, . Поэтому

.

,

.

Найдем значения , при которых получается частное решение соотношения , являющееся формулой -ого члена ряда Фибоначчи. Для этого ряда , . Поэтому находятся из системы

, ,

, .

Откуда .

Полученная формула называется формулой Бине.

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

1) находится общее решение рекуррентного соотношения;

2) выбираются значения и подставляются в общее решение;

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

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

Начальные члены последовательности будем называть также начальными значениями (условиями) частного решения, т.е. функции .

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

Однородные линейные рекуррентные соотношения с постоянными коэффициентами. Последовательность

(1)

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

. (2)

Соотношение (2) называется при этом однородным линейным рекуррентным соотношением порядка k.

Из этого определения следует, что соотношение (1), задающее при , последовательность Фибоначчи, - однородное линейное рекуррентное соотношение второго порядка, а сама эта последовательность - однородная линейная рекуррентная последовательность второго порядка.

Докажем на примере задачи, что арифметическая и геометрическая прогрессии являются однородными линейными последовательностями.

Решение. Пусть - разность арифметической прогрессии. Тогда , и, следовательно, . Отсюда . Поэтому из (1.1) при следует, что арифметическая прогрессия является однородной линейной рекуррентной последовательностью второго порядка.

Из (2) при получаем -ый член геометрической прогрессии. Поэтому геометрическая прогрессия является однородной линейной рекуррентной последовательностью первого порядка.

Решение однородного линейного рекуррентного соотношения. Рассмотрим свойства решений однородного линейного рекуррентного соотношения k-го порядка.

Теорема 1. Пусть , …, - частные решения рекуррентного соотношения (2) k-го порядка и - произвольные числа. Тогда

(3)

- общее решение рекуррентного соотношения (2).

Теорема 2. Если - корень алгебраического уравнения

, (4)

то функция является частным решением рекуррентного соотношения

.

Уравнение (4) называется характеристическим уравнением однородного линейного рекуррентного соотношения (2).

Теорема 3. Если характеристическое уравнение (4) однородного линейного рекуррентного соотношения (2) имеет различных корней , то общее решение этого соотношения имеет вид

. (5)

Найдём на примере общее решение однородного линейного соотношения и частное решение, соответствующее начальным условиям .

Составим характеристическое уравнение . Оно имеет корни , . Поэтому общее решение этого рекуррентного соотношения имеет вид .

Найдем частное решение, соответствующее начальным условиям . Для этого необходимо решить систему Эта система имеет решение . Поэтому частное решение, соответствующее заданным начальным условиям, есть.

Пусть характеристическое уравнение (4) имеет два комплексных корня, которые являются сопряженными числами . Из комплексных решений , рекуррентного соотношения (2) можно составить его действительные решения. Для этого комплексные числа представим в тригонометрической форме:

, ,

где , . Тогда

,

.

По теореме 1

,

- решения рекуррентного соотношения (2), а, значит,

- также решение этого соотношения. Поэтому в общем решении (5) слагаемые, соответствующие комплексным сопряженным корням характеристического уравнения, можно заменить полученной суммой.

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

Рассмотрим рекуррентное соотношение

.

Его характеристическое уравнение есть , т.е. , имеющее трехкратный корень: . Если воспользоваться формулой (5), то получим решение, зависящее только от одной постоянной:

.

Поэтому очевидно, что не для любых a, b и c можно выбрать начальные значения , и .

Но можно проверить, что кроме решения , решениями рассматриваемого соотношения будут и . Действительно,

,

.

Подставляя эти значения в наше рекуррентное соотношение, соответственно получим:

,

.

Зная три частных решения рекуррентного соотношения, его общее решение можно записать так:

.

Теорема 4. Пусть характеристическое уравнение (4) однородного линейного рекуррентного соотношения (2) имеет только k-кратный корень . Тогда общее решение рекуррентного соотношения имеет вид

.

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

,

,

………………………………………………….

можно получить действительных решений:

, , …, ;

, , …, .

Это позволяет записать общее решение в следующем виде:

Найдём на примере общее решение рекуррентного соотношения

четвертого порядка.

Характеристическое уравнение или имеет двукратные корни и . Поскольку , общее решение рекуррентного соотношения записывается в виде

.

В общем случае характеристическое уравнение может иметь корни - кратности , кратности , и т.д., кратности , . Тогда в общем решении соответствующего рекуррентного соотношения каждому корню отвечает слагаемое вида

, ,

а само общее решение есть сумма таких слагаемых.

Решение неоднородных линейных рекуррентных соотношений. Последовательность называется неоднородной линейной рекуррентной последовательностью порядка , если существуют натуральное число , числа () и функция такие, что

, (6)

При этом каждое из чисел может быть как действительным, так и комплексным. Рекуррентное соотношение (6) называется неоднородным линейным рекуррентным соотношением порядка k.

Рекуррентное соотношение

(7)

называется однородным линейным рекуррентным соотношением, ассоциированным с соотношением (6).

Отыскание общего решения неоднородного линейного рекуррентного соотношения основано на теоремах.

Теорема 5. Сумма любого решения неоднородного линейного рекуррентного соотношения (6) и любого решения ассоциированного с ним однородного рекуррентного соотношения (7) есть решение неоднородного соотношения (6).

Теорема 6. Разность любых двух решений неоднородного линейного рекуррентного соотношения (6) есть решение ассоциированного с ним однородного рекуррентного соотношения (7).

Из этих теорем вытекает

Теорема 7. Общее решение неоднородного линейного рекуррентного соотношения (6) есть сумма любого частного решения данного неоднородного соотношения и общего решения ассоциированного с ним однородного рекуррентного соотношения (7).

Иными словами, если - некоторое частное решение неоднородного линейного рекуррентного соотношения (6), а - общее решение ассоциированного с ним однородного соотношения (7), то

- общее решение неоднородного линейного рекуррентного соотношения (6).

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

1?. Пусть . Возможны следующие случаи:

а) Число не является корнем характеристического уравнения

.

Подставляя в уравнение (6), получим

.

Отсюда , значит, искомое частное решение имеет вид

.

б) Число является простым корнем характеристического уравнения. Подстановка в уравнение (6) дает

.

Отсюда

.

Из этого равенства, учитывая , получим

.

Следовательно, , поэтому

при .

в) Число является r-кратым корнем характеристического уравнения . В этом случае частное решение находится аналогичным образом в виде .

2?. Пусть - многочлен степени от переменной . Возможны следующие случаи:

а) Число 1 не является корнем характеристического уравнения. Тогда . Частное решение находится в виде . Подстановка многочленов , …, в уравнение (6) дает , т.е.

.

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

б) Число 1 является корнем характеристического уравнения и поэтому . Частное решение аналогичным способом находится в виде , где - кратность корня .

3?. Если , - частные решения линейных неоднородных рекуррентных соотношений

,

соответственно, то - частное решение рекуррентного соотношения

.

Найдём общее решение неоднородного линейного рекуррентного соотношения второго порядка:

а) ;

б) ;

в) ;

г) ;

д) .

Все заданные неоднородные рекуррентные соотношения имеют одно и тоже ассоциированное с ними однородное рекуррентное соотношение . Его характеристическое уравнение или обладает корнями и . Значит, общее решение ассоциированного соотношения

.

Для каждого из данных неоднородных соотношений найдем его частное решение и запишем общее решение.

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

.

б) Характеристическое уравнение не имеет комплексных корней, поэтому будем искать частное решение в виде . Имеем

или

.

Используя формулы приведения, получим

или

.

Полученное равенство должно тождественно выполняться при всех . При и соответственно имеем

, .

Откуда , . Таким образом, общее решение неоднородного соотношения выглядит так

.

в) Поскольку 2 - корень характеристического уравнения, частное решение неоднородного соотношения можно представить в виде . Тогда

.

Отсюда , т.е. .

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

.

г) Коэффициент является многочленом от , 1 не является корнем характеристического многочлена. Частное решение ищется в виде . Имеем

или

.

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

.

д) Общее решение получаем из решений пунктов а) и в)

.

Неоднородные рекуррентные соотношения и суммирование. Рассмотрим использование неоднородных линейных рекуррентных соотношений при вычислении конечных сумм.

Вычислить суммы:

а) ;

б) ;

в) .

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

а) Частное решение неоднородного соотношения имеет вид

.

Подставляя его в рекуррентное соотношение, после преобразований получим:

.

Откуда , , , . Таким образом, общее решение неоднородного соотношения -

.

Так как , то и искомая сумма .

б) Здесь частное решение , поэтому общее имеет вид

.

в) Число 3 не является корнем характеристического уравнения, поэтому частное решение ищется в виде . Подставим его в рекуррентное соотношение: . Отсюда , и значит, общее решение неоднородного рекуррентного соотношения запишется так . Поскольку , то и . Искомая сумма . Этот же результат можно получить с помощью формулы для вычисления суммы членов геометрической прогрессии (первый член и знаменатель прогрессии равны 3).

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

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

,

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

получило специальное название - производящая функция для последовательности чисел .

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

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

.

В действительности это выражение совсем не обязательно является функцией в привычном понимании этого слова. Более того, сумма ряда может вообще не иметь смысла. Поэтому, вообще говоря, бессмысленно говорить и о значении производящей функции в некоторой точке . Единственная точка, в которой всегда можно указать значение производящей функции ; в ней . В связи со сказанным, наряду с термином «производящая функция» в литературе по комбинаторике часто используется термин «формальный степенной ряд».

Пусть даны две производящие функции

и .

Суммой производящих функций и называется производящая функция

(1)

или, кратко,

.

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

(2)

Или .

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

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

Теорема 1. Пусть даны производящие функции и , причем . Тогда существует такая производящая функция =, что

() () = (3)

Следствие. Пусть свободный член ряда отличен от нуля. Тогда существует единственный формальный степенной ряд такой, что .

Для производящих функций и с нулевым свободным членом определена операция замены переменной. А именно, производящая функция

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

Производной производящей функции

называется производящая функция

, (4)

а интегралом - функция

. (5)

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

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

,

,

(формула интегрирования по частям).

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

Экспоненциальные производящие функции. Наряду с обычными производящими функциями в комбинаторике часто используются экспоненциальные производящие функции. Так для последовательности называют выражение

, (6)

где является формальным символом.

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

,

.

Степенные ряды. Напомним некоторые необходимые сведения о степенных рядах, известные из курса математического анализа.

Ряд

, (7)

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

. (8)

Если придать некоторое значение, то степенной ряд превратится в числовой ряд, который может либо сходиться, либо расходиться. Так, например, в точке имеем числовой ряд . Отсюда, в частности следует, что степенной ряд всегда сходится, по крайней мере, в одной точке.

Множество всех , при которых ряд сходится, называется областью сходимости ряда. Сумма степенного ряда (7) является функцией, заданной на области его сходимости: , где . При этом говорят, что ряд (7) сходится к функции .

Основная теорема о сходимости степенных рядов формулируется так. Для любого степенного ряда (7) существует такое число (в частности, ), что ряд абсолютно сходится при и расходится при . При и ряд может как сходиться, так и расходиться. Число называется радиусом сходимости ряда (7), а интервал - его интервалом сходимости (при ).

Пусть - сумма степенного ряда (7) с положительным радиусом сходимости . Тогда

(9)

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

Дифференцирование и интегрирование степенных рядов основывается на теореме. Пусть при , где - радиус сходимости этого ряда. Тогда функция непрерывна и дифференцируема в интервале сходимости и

(10)

. (11)

При этом оба полученных ряда имеют тот же радиус сходимости , что и ряд .

Применяя эту теорему к функции , представленной сходящимся степенным рядом (2.4.7), путем последовательного дифференцирования получим:

,

,

и т.д.

Подставив в полученные равенства , найдем , , , …, , … Отсюда однозначно находим коэффициенты ряда

, (12)

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

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

,

который называется рядом Тейлора в точке . При этот ряд называется рядом Маклорена.

Если функции и разложены в степенные ряды

при ,

при ,

то ряды , также сходятся при , где .

В курсе математического анализа доказывается, что при

, (13)

, (14)

(15)

Следовательно, - обычные производящие функции для последовательностей

1, 1, , , …; 0, 1, 0, , 0, , …; 1, 0, , 0, , 0, …

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

1, 1, …, 1, …; 0, 1, 0, -1, 0, 1, 0, -1, …; 1, 0, -1, 0, 1, 0, -1, …

соответственно.

Заменяя в (13) на , получим производящую функцию

Отсюда и из (13) следует, что

,

Ряд Ньютона. Как было отмечено ранее, И.Ньютон обобщил формулу разложения бинома для любого действительного показателя, т.е. рассмотрел разложение функции , где - любое действительное число, не обязательно натуральное.

Теорема 2. Для любого действительного значения при имеет место разложение

. (16)

Ряд (16) называется при этом рядом Ньютона.

Следствие 1. При , где n - натуральное число, формула (2.4.16) принимает вид .

В самом деле, при все производные порядка выше, чем , тождественно равны нулю.

Следствие 2. При формула (16) принимает вид

Если положить придем к соотношению

(18)

Заменяя в последнем равенстве на , получим

(19)

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

Следствие 3. При , где n - натуральное число, формула (16) принимает вид

(20)

или

Мы учли, что , и обе части равенства (20) умножили на .

Опять положив и , соответственно получим

(21)

(22)

Из (22) при получим еще одну полезную формулу

(23)

Как было сказано, применяя к известным рядам допустимые операции, можно строить новые производящие функции и соответствующие им последовательности. Заменяя, например, в (18) и (19) на соответственно получим

, (24)

(25)

Заметим, что ряд (25) можно было получить и путем почленного перемножения разложений (18), (19).

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

(26)

Приведем, наконец, еще два степенных ряда, которые получаются из (16) при , и , :

(27)

(28)

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

.

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

или

.

Приравнивая коэффициенты при в левой и правой частях этого равенства, получим обобщение свойства 6? обычных биномиальных коэффициентов:

.

По понятным причинам, как только мы начнем рассматривать сумму биномиальных коэффициентов ряда Ньютона, придется учитывать сходимость этого ряда. Так, при рассматриваемый ряд сходится тогда и только тогда, когда , а его сумма равна , т.е. , . При ряд Ньютона сходится тогда и только тогда, когда , а его сумма равна 0 при и 1 при , т.е. , , где - символ Кронекера.

Если , то , поэтому .

2.3 Тесты по теме «Рекуррентные последовательности и производящие функции» в курсе «Дискретная математика»

1. Найдите пятый член числовой последовательности .

Ответ: . (Решение : =)

2. Укажите формулу общего члена числовой последовательности

1, , , , …

а) , б) , в) , г) .

(Решение: , , , ).

3. Найдите шестой член последовательности, заданной рекуррентным соотношением , если , , .

Ответ: 36.

(Решение:

, , ).

4. Среди рекуррентных соотношений

а) ,

б) ,

в) ,

г)

укажите:

1) линейные однородные соотношения первого порядка (б),

2) линейные однородные соотношения второго порядка (г),

3) соотношения, не являющиеся однородными (в),

4) линейные неоднородные рекуррентные соотношения (а).

5. Общее решение однородного линейного рекуррентного соотношения второго порядка имеет вид . Какие корни имеет его характеристическое уравнение:

а) действительные различные,

б) два совпавших действительных корня,

в) комплексные сопряженные,

г) другой ответ.

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

.

6. Среди линейных однородных рекуррентных соотношений

а) ,

б) ,

в) ,

г)

выберите соотношение, имеющее общее решение

.

(Решение: , , , , представив комплексные числа в тригонометрической форме, получим общее решение

для последовательности )

7. Среди линейных однородных рекуррентных соотношений

а) ,

б) ,

в) ,

г)

выберите соотношение, имеющее общее решение

.

(Решение: , , ,

8. Какой из последовательностей

а) 1, 1, …, 1, …;

б) 1, 2, …, n, …;

в) 1, -1, 1, -1, …

г) 1, -2, …, , …

соответствует производящая функция

?

(Решение: Для любого действительного значения при имеет место разложение

. )

9. Какой из последовательностей

а) 1, 1, …, 1, …;

б) 1, 2, …, n, …;

в) 1, -1, 1, -1, …

г) 1, -2, …, , …

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

?

(Решение: если степень - чётное число, то 1, если - нечётное, то -1.)

10. Укажите производящую функцию последовательности при начальных условиях , .

а) , б) , в) , г) .

Заключение

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

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

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

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

Одной из причин этого является отсутствие в образовательных учреждениях простых в использовании программных пакетов для создания предметно-ориентированных тестов. Большинство имеющихся оболочек позволяет реализовать тест в текстовом виде. Принято считать, что такие оболочки не могут использоваться для создания полноценных тестов по математике и дисциплинам естественно-научного цикла, где, как правило, необходим встроенный в программу формульный редактор. Блок eAuthor, используемого при выполнении дипломной работы программного пакета «eLearning Office 3000», предназначенного для создания дистанционных электронных учебных курсов, также, к сожалению, не позволяет использовать редактор математических формул.

В дипломной работе при создании тестов по избранной теме удалось выявить особенности фактического учебного материала, усвоение которого может быть проверено с помощью тестов, созданных на базе программной оболочки, предназначенной для гуманитарных дисциплин и не имеющей математического редактора. Тем самым было показано, что соответствующий выбор заданий для текущего контроля и форм их представления позволяет использовать Конструктор в среде «eLearning Office 3000» и для создания тестов по математике. Разработанные в ходе выполнения работы тесты могут быть использованы при организации текущего и рубежного контроля в курсе «Дискретная математика» на факультете информатики университета. Кроме того, полученные результаты могут быть полезны при создании тестов на базе подобных оболочек и проведении последующего тестирования по другим математическим курсам.

Библиографический список

1. Аванесов В.С. Композиция тестовых заданий. - М.: АДЕПТ, 1998.

2. Аванесов В.С. Тесты в социологическом исследовании. - М.: Наука, 1982.

3. Аванесов В.С. Теоретические основы разработки заданий в тестовой форме. - М., 1995.

4. Аванесов В.С. Формы тестовых заданий. - М.: МИСиС ,1991.

5. Агапонов С.В. и др. Средства дистанционного обучения. Методика, технология, инструментарий. / Под ред. З.О. Джалиашвили. - СПБ.:БХВ - Петербург, 2003.

6. Азевич А.И. Тестируем контрольные работы. // Математика в школе. - 2000. - №8.

7. Акимова М.К. Интеллектуальные тесты // Психология индивидуальных различий. - М.: Изд-во МГУ, 1996.

8. Аллахвердиева Д.Т. Опыт применения тестов для дидактической экспертизы обучения // Высшее образование в России. - 1993. - №2.

9. Анастази А., Урбина С. Психологическое тестирование. - М.: ПИТЕР, 2003.

10. Андерсон Дж.А. Дискретная математика. - М.: Изд. Дом «Вильямс», 2003.

11. Анисимов П.Ф., Сосонко А.Е. Управление качеством среднего профессионального образования. - Казань: ИСПО, 2001.

12. Айнштейн В.Г., Гольцова И.Г. Об адекватности экзаменационных оценок//Высшее образование в России. - 1993. - №3.

13. Беспалько В.П. Слагаемые педагогической технологии. - М.: Педагогика, 1989

14. Буравлев А.И., Переверзев В.Ю. Методы подсчёта индивидуальных баллов при математическом моделировании процесса педагогического тестирования // СПО. - 2001. - №4.

15. Вербицкий А.А. Активное обучение в высшей школе: контекстный подход. - М.: Высш. шк., 1991.

16. Вигдорчик Б.Н., Гулидов И.Н., Шатун А.Н. Совершенствование программ для безмашинного контроля знаний // Реферативная информация. Отдел научной информации НИИВШ. М., 1976.

17. Виленкин Н Я. Комбинаторика. - М.: Наука, 1969.

18. Гаврилов Г.И., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учебное пособие. - 3-е изд., перераб. - М.: ФИЗМАТЛИТ, 2004.

19. Гильбух Ю.З. Актуальные вопросы валидации психологических тестов / Вопросы психологии, N 5. - M. : Педагогика, 1978.

20. Глазков Ю.А. Централизованное тестирование школьников // Математика в школе. - 2000. - №1.

21. Горбачева В.И. Критериально-ориентированное тестирование как средство диагностики умственного развития школьников: Дисс. Канд. психол. наук. - М., 1987.

22. Гулидов И.Н., Шатун А.Н. Методика конструирования тестов. - М., 2003.

23. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. - М.: Наука, 1977.

24. Ивашина А.С., Свиридова Т.С. Тестовый контроль знаний // Специалист. - 1997. - №12.

25. Кларин М.В. Инновационные модели обучения в зарубежных педагогического поиска. - М., 1994.

26. Клековкин Г.А., Перминов Е.А. Дискретная математика. Часть II. Рекуррентные соотношения и производящие функции: Учебн. пособие для студентов пед. университетов и институтов. - Самара: СФ МГПУ, 2005.

27. Комбинаторный анализ. Задачи и упражнения / Под ред. К. А. Рыбникова - М.: Наука, 1982.

28. Корсак К. О качестве систем педагогических измерений // Народное образование. - 2002. - №4.

29. Крамор В.С. О совершенствовании методов обучения математики. - М.: Просвещение, 1978.

30. Куклин В.Ж., Мешалкин В.И., Наводнов В.Г., Савельев Б.А. О компьютерной технологии оценки качества знаний//Высшее образование в России. - 1993. - №3.

31. Ландо С.К. Лекции о производящих функциях. - М.: МЦНМО, 2004.

32. Лузик Э.В., Чернилевский Д.В. Определение результатов обучения на основе системы программно-целевого управления // СПО. - 2000. - №9.

33. Майоров А.Н. Тесты школьных достижений: конструирование, проведение, использование. - СПб.: Образование и культура, 1996.

34. Маркушевич А.И. Возвратные последовательности. - М.: Наука, 1983. - (Популярные лекции по математике).

35. Педагогика: Учебное пособие для студентов пед. ВУЗов и пед. коледжей / Под ред. П.И. Пидкасистого. - М.: Российское педагогическое агенство, 1996.

36. Садовничий В.А. Компьютерная система проверки знаний студентов // Высшее образование в России. - 1994. - №3.

37. Сачков В.Н. Введение в комбинаторные методы дискретной математики. - М.: МЦНМО, 2004.

38. Симонов В.Л. Новая философия оценки степени обученности личности // Специалист. - 2000. - №4.

39. Смирнов С.Д. Педагогика и психология высшего образования: От деятельности к личности: Уч. пособие. - М., 1995.

40. Сосонко А.Е. Контроль учебной деятельности студентов в средних учебных заведениях с применением рейтинговой системы. - М., 1998.

41. Талызина К.Ф. Нормирование познавательной деятельности младших школьников. - М.: Просвещение, 1988.

42. Тихомиров В., Рубин Ю., Самойлов В., Шевченко К. Информационные технологии для будущих экономистов // Высшее образование в России. - 1999. - №1.

43. Филиппов В.М. Об активизации самостоятельной работы студентов высших учебных заведений // Высшее образование сегодня. - 2003. - №2.

44. Хубаев Г. О построении шкалы оценок в системах тестирования // Высшее образование в России. - 1996. - №1.

45. Челышкова М.Б. Теория и практика конструирования педагогических тестов. - М.: ЛОГОС, 2002.

46. Чередов И.М. Формы учебной работы в средней школе. - М.: Просвещение, 1988.

47. Щапов А., Тихомирова Н., Ершиков С., Лобова Т. Тестовый контроль в системе рейтинга // Высшее образование в России. - 1995. -№3.

48. Эрдниев П.М., Эрдниев Б.П. Укрупнение дидактических единиц в обучении математике. - М.: Просвещение, 1986.

Яблонский С.В. Введение в дискретную математику: Учебное пособие для вузов. - М.: Высшая школа, 2003.

Размещено на Allbest