Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы дискретной математики основная образовательная программа подготовки специалиста по специальности 010200 (010501) «Прикладная математика и информатика»

РАЗДЕЛ 4. Словарь терминов (глоссарий) Производящие функции и их применение Алгебра биномиальная отношений Композиция Ньютона бином Паскаля преобразование треугольник Разбиение Размещение с повторениями Сочетание с повторениями Формальный степенной ряд Функция производящая экспоненциальная производящая Рекуррентные уравнения Решение общее частное Уравнение однородное рекуррентное с постоянными коэффициентами характеристическое Условие начальное Фибоначчи задача Теория алгоритмов Алгоритм Оператор неограниченный минимизации ограниченный минимизации примитивной рекурсии суперпозиции Проблема алгоритмическая неразрешимая остановки распознавания нетривиального инвариантного свойства Свойство инвариантное нетривиальное Тьюринга машина Функция Аккермана вычислимая по Тьюрингу общерекурсивная примитивно-рекурсивная частично-рекурсивная Чёрча-Тьюринга тезис РАЗДЕЛ 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Производящие функции и их применение Таблица простейших производящих функций № п/п аn а(x) аe(x) 1 1 1 / (1−x) ex 2  n 1 / (1−x) ex 3 1 / n! ex − 4  n / n! ex − 5 Cn (1+x)  − 6 C n n+  −1 (1−x) − − 7  n C n n+  −1 (1−x) − − 8 n x / (1−x)2 x ex Задание 1.1. Используя бином Ньютона, вычислить: (2-)6. Решение. В формулу (a+b)n = Cnk an−kbk подставим: a = 2, b = −; n = 6, получим: (2 −)6 = C60 26 + C61 25 (−) + C62 24 (−)2 + C63 23 (−)3 + C64 22 (−)4 + + C65 21 (−)5 + C66 (−)6 = 64 – 192 + 720 – 480 + 540 – 108 + 27 = = 1351 – 780. Ответ: 1351 – 780. Задание 1.2. Не раскрывая скобок, определить коэффициент при x9 в многочлене: (1+ x)9 + (1+ x)10 + … + (1+ x)14. Решение. Искомый коэффициент равен: C99 + C109 + C119 + C129 + C139 + C149. Упростим это выражение, используя равенство: Cnk + Cnk−1 = Cn+1 k, а также тот факт, что C99 = 1 = C1010: (C1010 + C109) + C119 + C129 + C139 + C149 = (C1110 + C119) + C129 + C139 + C149 = = (C1210 + C129) + C139 + C149 = (C1310 + C139) + C149 = (C1410 + C149) = C1510 = 3003. Ответ:3003. Задание 1.3. Даны числовые последовательности: a(n) = 2n+1 и b(n) = n + 5. Составить производящие функции a(x) и b(x) этих последовательностей. В произведении a(x)b(x) найти коэффициент при x5. Решение. Так как a(n) = 2n+1 = 22n, то, воспользовавшись таблицей, найдём: a(x) = 2 / (1−2x), так как b(n) = n + 5, то b(x) = x / (1−x)2 + 5 / (1−x). Коэффициент при x5 равен k5 = аi b5-i = а0 b5 + а1 b4 + а2 b3 + а3 b2 + а4 b1 + а5 b0 = 210 + 49 + 88 + 167 + 326 + 645 = 744. Задание 1.4. Даны числовые последовательности: a(n) = 3n − 5 и b(n) = n2. Составить экспоненциальные производящие функции этих последовательностей. В произведении ae(x)be(x) найти коэффициент при x4. Решение. Так как a(n) = 3n − 5, то, воспользовавшись таблицей, найдём: ae(x) = e3x − 5ex. так как b(n) = nn, то, по свойству «изменение масштаба», имеем: be(x) = x[ЭПФ(n)] = x [x ex] = x ex (1+x). Коэффициент при x4 равен d4 / 4! = (1/4!)C4i аi b4-i = (1/4!) [C40а0 b4 + C41а1 b3 + C42а2 b2 + C43а3 b1 + C44а4 b0] = (1/4!) [1(−4)16 + 4(−2)9 + 644 + 4221 + 0] = 48 / 24 = 2. Задание 1.5. Найти формальный степенной ряд, обратный к данному ряду: аn xn = 2 + x3. Решение. Cоставим вспомогательный ряд: g(x) = 1 − (1/а0) аn xn = 1 − (1/2) (2 + x3) = − x3 / 2. Обратный ряд найти по формуле: ( аn xn)−1 = (1/ а0) (1 + g(x) + g2(x) +…) = = (1/2) (1 − x3 / 2 + x6 / 4 − x9 / 8 …) = . Задание 1.6. Выполнить дифференцирование формального степенного ряда: Cn xn. Решение. Воспользовавшись формулой: аn xn = (n+1) аn+1 xn, найдём: Cn xn = (n+1) Cn+1 xn = (n+1) xn = xn = Cn ( − n) xn . Задание 1.7. Найти числовую последовательность, производящей функцией которой является функция вида: a(x) = . Решение. Разложим данную правильную дробь в сумму простейших дробей: a(x) = 10 / (3-2x) + 5 / (3-2x)2 − 1 / (4+5x). Приведём каждую из простейших дробей к табличному виду: 10 / (3-2x) = ; 5 / (3-2x)2 = ; 1 / (4+5x) = . Воспользовавшись таблицей производящих функций, восстановим числовую последовательность: a(n) = + C n n+ 2−1 + = [+ (n+ 1)] + . Задачи для самостоятельного решения Задание 1.8. Даны числовые последовательности: an = n2 + 7 и bn = 6n−3. а) Составить их производящие функции a(x), b(x) и вычислить коэффициент при x3 в произведении a(x)  b(x); б) Составить их экспоненциальные производящие функции ae(x), be(x) и вычислить коэффициент при x2 в произведении ae(x)  be(x). Задание 1.9. Найти числовую последовательность, производящей функцией которой является функция вида: a(x) = (2x2 − 23x) / (5 − x)3. Рекуррентные уравнения Задание 2.1. Доказать, что арифметическая прогрессия an = a0 + dn, n = 0, 1, 2, …, является возвратной последовательностью. Доказательство. Так как 2an+1 = 2(a0 + d(n+1)) = (a0 + dn) + (a0 + dn + 2d) = an + an+2 , то последовательность an − решение линейного однородного рекуррентного уравнения с постоянными коэффициентами: an+2 = 2an+1 − an, а значит, она является возвратной. Задание 2.2. Найти общее решение уравнения: f(n+3) + 3 f(n+2) + 3 f(n+1) + f(n) = 0. Решение. Составим характеристическое уравнение и решим его: x3 + 3 x2 + 3 x + 1 = 0 ; (x + 1) 3 = 0; это уравнение имеет корень −1 кратности 3. Тогда, в соответствии с основной теоремой об однородных уравнениях, общее решение данного уравнения имеет вид: Ответ: a(n) = (C1 + C2 n + C3 n2)  (−1)n. Задание 2.3. Найти решение уравнения: f(n+4) = 12 f(n+3) − 22 f(n+2) − 84 f(n+1) − 49 f(n) при заданных начальных условиях: f(0) = 8, f(1) = −14; f(2) = 4; f(3) = 342. Решение. Составим характеристическое уравнение и решим его: x4 − 12x3 + 22 x2 + 84 x + 49 = 0 . Разложив левую часть на множители, получим: (x + 1) 2 (x − 7) 2 = 0; это уравнение имеет два различных корня: корень −1 кратности 2 и корень 7 кратности 2. Тогда, в соответствии с основной теоремой об однородных уравнениях, общее решение данного уравнения имеет вид: a(n) = (C1 + C2 n)  (−1)n + (C3 + C4 n)  7n. Для нахождения постоянных C1, C2, C3, C4 воспользуемся начальными условиями: 8 = f(0) = C1 + C3; −14 = f(1) = (C1 + C2)  (−1) + (C3 + C4)  7; 4= f(2) = (C1 + 2C2)  (−1)2 + (C3 + 2C4)  72; 342= f(3) = (C1 + 3C2)  (−1)3 + (C3 + 3C4)  73. В результате получена система четырёх уравнений с четырьмя неизвестными: Решая её, найдём: C1 = 10, C2 = −3, C3 = −2, C4 = 1. Подставляя найденные значения в общее решение, окончательно получим… Ответ: a(n) = (10 − 3n)  (−1)n + (n −2)  7n. Задание 2.4. Найти частное решение уравнения: f(n+2) = 2 f(n+1) + 8 f(n) + (96n − 32)  4n. Решение. 1. Составим соответствующее однородное уравнение: f(n+2) = 2 f(n+1) + 8 f(n). Выпишем для него характеристическое уравнение и найдём его корни: x2 − 2 x − 8 = 0; x1 = 4 кратности 1, x2 = −2 кратности 1. 2. В нашем случае (n) = R1 (n) n = (96n − 32)  4n, т.е.  = 4; это значение совпало с одним из корней характеристического уравнения, имеющим кратность r = 1. Частное решение ищем в виде: aч(n) = (An + B)  4n  nr = (An2 + Bn)  4n. Постоянные A и B определяем путём подстановки частного решения в исходное уравнение: [A(n+2)2 + B(n+2)]  4n+2 = 2[A(n+1)2 + B(n+1)]  4n+1 + 8[An2 + Bn]  4n + (96n − 32)  4n. Разделив обе части уравнения на множитель 4n  0 и раскрыв скобки, получим: 16An2 + 64An + 64A + 16Bn+32B = 8An2 + 16An + 8A + 8Bn+8B+ 8An2 + 8Bn + 9 n − 32. После приведения подобных уравнение примет вид: 48 An + 56A + 24B = 96n − 32. Приравнивая коэффициенты при одинаковых степенях n, найдём: n1: 48 A = 96, откуда A =2; n0: 56A + 24B = − 32, откуда B = −6. Осталось подставить найденные значения в частное решение. Ответ: aч(n) = (2n2 − 6n)  4n. Задание 2.5. Найти решение уравнения: f(n+2) = 4 f(n+1) − 4 f(n) + 2n при заданных начальных условиях: f(0) = 1, f(1) = 4. Решение. 1. Составим соответствующее однородное уравнение: f(n+2) = 4 f(n+1) − 4 f(n). Выпишем для него характеристическое уравнение и найдём его корни: x2 − 4 x + 4 = 0; x = 2 кратности 2. Общее решение однородного уравнения имеет вид: a0(n) = (C1 + C2 n)  2n. 2. В нашем случае (n) = R0 (n) n = 2n, т.е.  = 2; это значение совпало с корнем характеристического уравнения, имеющим кратность r = 2. Частное решение ищем в виде: aч(n) = A  2n  nr = An2  2n. Постоянную A определяем путём подстановки частного решения в исходное уравнение: A(n+2)2  2n+2 = 4A(n+1)2  2n+1 − 4 An2  2n + 2n. Разделив обе части уравнения на множитель 2n  0 и раскрыв скобки, получим: 4An2 + 16An + 16A = 8An2 + 16An + 8A − 4An2 + 1. После приведения подобных уравнение примет вид: 8A =1, откуда A = 1/8. 3. Общее решение ищем в виде: a(n) = a0(n) + aч(n) = (C1 + C2 n)  2n + (1/8) n2  2n. Для нахождения постоянных C1, C2 воспользуемся начальными условиями: 1 = f(0) = C1; 4 = f(1) = (C1 + C2)  2 + (1/8)  2, C2 = 7/8. Окончательно имеем: a(n) = (1 + (7/8) n)  2n + (1/8) n2  2n = (1 + (7/8) n + (1/8) n2)  2n Ответ: a(n) = (1 + (7/8) n + (1/8) n2)  2n. Задачи для самостоятельного решения Задание 2.6. Найти решение уравнения: f(n+3) +10f(n+2) +32f(n+1) + 32f(n) = 0 при заданных начальных условиях: f(0) = 1, f(1) = −1; f(2) = 0. Задание 2.7. Найти решение уравнения: f(n+2) + 2f(n+1) − 8f(n) = n2 при заданных начальных условиях: f(0) = 3, f(1) = 1. Теория алгоритмов Задание 3.1. Построить машину Тьюринга, которая к каждому слову x в алфавите А приписывает справа символ а1, т.е. перерабатывает “x” в “x а1”. Решение. Программа должна работать так: находясь в начальном состоянии, машина двигает головку вправо, ничего не изменяя на ленте до тех пор, пока головка не дойдет до конца исходной цепочки; затем она справа от исходной цепочки пишет “а1” и останавливается. %Оставаясь в начальном состоянии и не меняя ai , сдвигаемся вправо: (1) q1 ai  ai Rq1 (i=1,...,n) %Находясь в начальном состоянии и дойдя до пустого символа , заменяем его на a1 и останавливаемся (2) q1   a1 Еq0 Задание 3.2. Построить машину Тьюринга, которая у каждого слова длины  3 в алфавите А стирает три последних символа, а слова меньшей длины перерабатывает в пустое слово. Решение. % Оставаясь в начальном состоянии и не меняя ai , сдвигаемся вправо: (1) q1 ai  ai Rq1 (i=1,...,n) % Дойдя в начальном состоянии до пустого символа , сдвигаемся влево, % перейдя во II состтояние (2) q1    Lq2 % Находясь во II состоянии, меняем ai на пустой символ, сдвигаемся влево и % переходим в III состояние (3) q2 ai   Lq3 (i=1,...,n) % Находясь в III состоянии, меняем ai на пустой символ, сдвигаемся влево и % переходим в IV состояние (4) q3 ai   Lq4 (i=1,...,n) % Находясь в четвертом состоянии, меняем ai на пустой символ и останавливаемся (5) q4 ai   Lq5 (i=1,...,n) % Находясь в любом из сост. со II по IV и попав на пустой символ, останавливаемся (6) qh    Eq0 (h=2,3,4) Задание 3.3. Доказать, что не существует алгоритма, позволяющего для любых двух машин Тьюринга узнать, эквивалентны ли они. Доказательство. Фиксируем произвольную МТ М и обозначаем через М свойство МТ Т быть эквивалентной машине М. Это свойство инвариантно (т.к. любые две эквивалентные машины либо обе обладают этим свойством, либо обе не обладают) и нетривиально (т.к. существуют как машины, обладающие этим свойством, так и не обладающие). Но алгоритм, распознающий эквивалентность двух произвольных машин, позволял бы распознавать для любой машины, обладает ли она свойством М, что невозможно в силу теоремы Райса. Задание 3.4. Доказать, что функция f(x) = x! примитивно рекурсивна. Доказательство. f(0)= 0! = 1, но 1 = g(0), где g (x) = x + 1 − функция следования; f(y+1) = (y+1)  y! = g (y)  f(y), т.е. f(y+1) = h(g(y), f(y)), где h(x, y) = x  y. Таким образом, функция f(x) получена с помощью оператора примитивной рекурсии из примитивно-рекурсивных функций, а, следовательно, является примитивно-рекурсивной. Задание 3.5. Какая функция получается из функций g (x) = x и h(x, y, z) = zx с помощью схемы примитивной рекурсии? Решение. Схема примитивной рекурсии для искомой функции f(x, y) имеет вид: f(x, 0) = g(x) = x; (1) f(x, y+1) = h(x, y, f(x, y) ) = f(x, y)x. (2) Выпишем значения функции f(x, y) для y = 1, 2, 3: при y =1 : f(x, 1) = f(x, 0)x = ; при y =2 : f(x, 2) = f(x, 1)x = = ; при y =3 : f(x, 3) = f(x, 2)x = = … Можно предположить, что искомая функция имеет вид: f(x, y) = (*). С помощью метода математической индукции докажем, что наше предположение верно: при y = 1, 2, 3 формула (*) верна; предположим, что она верна при y = k: f(x, k) = ; докажем, что она будет верна при y = k + 1: f(x, k + 1) = f(x, k)x = = = − что и требовалось доказать. Ответ: f(x, y) = . Задачи для самостоятельного решения Задание 3.6. Машина Тьюринга определяется функциональной схемой, приведенной в таблице.  1 * q1 L q2 E q0 q2 1R q3 1L q2 *L q2 q3 L q1 1R q3 *R q3 Определите, в какое слово перерабатывает машина каждое из следующих слов, если она находится в начальном состоянии q1 и обозревает крайнюю правую ячейку из тех, в которых записано перерабатываемое слово. После этого постарайтесь усмотреть общую закономерность в работе машины: а) 111*111; б) 1111*11; в) 111*1 ; г) 1*11; д) 11*111; е) 11111*; ж) *1111. Задание 3.7. Доказать, что функция f(x) = x! примитивно рекурсивна. Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы. Характер изменений в программе Номер и дата протокола заседания кафедры, на котором было принято данное решение Подпись заведующего кафедрой, утверждающего внесенное изменение Подпись декана факультета (проректора по учебной работе), утверждающего данное изменение Раздел 7. Учебные занятия по дисциплине ведут: Ф.И.О., ученое звание и степень преподавателя Учебный год Факультет Специальность кандидат тех. наук, доцент Ланина Н.Р. 2007-2008 ПМПЭ 010200 Прикладная математика и информатика кандидат тех. наук, доцент Ланина Н.Р. 2010-2011 ФМОИП 010200 Прикладная математика и информатика

Похожие:

	Учебно-методический комплекс дисциплины опд. В. 4 Математические... Целями изучения дисциплины являются: формирование профессиональных навыков по изучению, анализу и оптимизации экономических процессов...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Учебно-методический комплекс дисциплины дс компьютерные сети и системы... Рецензенты: кандидат физико-математических наук, доцент Маренич А. С., кандидат технических наук, доцент Ланина Н. Р		Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 11 Основы коммуникативной... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 10, Опд. Ф. 12, Опд.... А. В. Прялухина, кандидат психологических наук, доцент, зав кафедрой психологии Российского государственного социального университета...		Учебно-методический комплекс дисциплины опд. Ф. 21 Методы географических... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. В 2 опд. В 1 Современный... Педагогика и методика начального образования со специализацией «Обучение информатике в начальной школе»		Учебно-методический комплекс гсэ. В 1 история математической науки... Автор программы: кандидат физ мат наук, доцент кафедры математики и мом локоть Наталья Васильевна
	Учебно-методический комплекс фтд: универсальная алгебра основная... ...		Учебно-методический комплекс дисциплины опд. Ф. 8 Религиоведение... Пащенко Л. В., к ф н., старший преподаватель кафедры связей с общественностью и лингвистики мгту
	Учебно-методический комплекс дисциплины математическая логика Основная... Автор программы: Шиманский Сергей Александрович, ст преподаватель кафедры информатики и отд		Учебно-методический комплекс дисциплины опд. Ф. 4 История религии... ...
	Учебно-методический комплекс дисциплины фтд. 1 Основы кинезиологии... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 2 Геоморфология основная... Цель дисциплины. В соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности...