Разделив обе части уравнения на множитель 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. В нашем случае u(n) = R0 (n) ln = 2n, т. е. l = 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) + 32 f(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)
%Находясь в начальном состоянии и дойдя до пустого символа l, заменяем его на a1 и останавливаемся
(2) q1 l ® a1 Еq0
Задание 3.2. Построить машину Тьюринга, которая у каждого слова длины ³ 3 в алфавите А стирает три последних символа, а слова меньшей длины перерабатывает в пустое слово.
Решение.
% Оставаясь в начальном состоянии и не меняя ai, сдвигаемся вправо:
(1) q1 ai ® ai Rq1 (i=1,...,n)
% Дойдя в начальном состоянии до пустого символа l, сдвигаемся влево,
% перейдя во II состтояние
(2) q1 l ® l Lq2
% Находясь во II состоянии, меняем ai на пустой символ, сдвигаемся влево и
% переходим в III состояние
(3) q2 ai ® l Lq3 (i=1,...,n)
% Находясь в III состоянии, меняем ai на пустой символ, сдвигаемся влево и
% переходим в IV состояние
(4) q3 ai ® l Lq4 (i=1,...,n)
% Находясь в четвертом состоянии, меняем ai на пустой символ и останавливаемся
(5) q4 ai ® l Lq5 (i=1,...,n)
% Находясь в любом из сост. со II по IV и попав на пустой символ, останавливаемся
(6) qh l ® l Eq0 (h=2,3,4)
Задание 3.3. Доказать, что не существует алгоритма, позволяющего для любых двух машин Тьюринга узнать, эквивалентны ли они.
Доказательство. Фиксируем произвольную МТ М и обозначаем через aМ свойство МТ Т быть эквивалентной машине М. Это свойство инвариантно (т. к. любые две эквивалентные машины либо обе обладают этим свойством, либо обе не обладают) и нетривиально (т. к. существуют как машины, обладающие этим свойством, так и не обладающие). Но алгоритм, распознающий эквивалентность двух произвольных машин, позволял бы распознавать для любой машины, обладает ли она свойством aМ, что невозможно в силу теоремы Райса.
Задание 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. Машина Тьюринга определяется функциональной схемой, приведенной в таблице.
l | 1 | * | |
q1 | lL q2 | lE q0 | |
q2 | 1R q3 | 1L q2 | *L q2 |
q3 | lL 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 Прикладная математика и информатика |
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)