Главная / Алгоритмы и дискретные структуры /
Комбинаторные алгоритмы для программистов / Тест 8
Комбинаторные алгоритмы для программистов - тест 8
Упражнение 1:
Номер 1
Что является решением данного рекуррентного соотношения?
Ответ:
 (1) последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется 
 (2) последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно не выполняется 
 (3) сумма членов последовательности является решением данного рекуррентного соотношения, если при подстановке этой суммы соотношение тождественно выполняется 
 (4) сумма членов последовательности является решением данного рекуррентного соотношения, если при подстановке этой суммы соотношение тождественно не выполняется 
Номер 2
Что называется общим решением рекуррентного соотношения k
-го порядка?
Ответ:
 (1) решение, которое зависит от k
произвольных постоянных С1,С2,...,Сk
и путем подбора этих постоянных можно получить любое решение данного соотношения 
 (2) решение, которое зависит от k
-произвольных постоянных и путем подбора этих постоянных можно получить любое решение данного соотношения 
 (3) решение, которое не зависит от k
произвольных постоянных С1,С2,...,Сk
и путем подбора этих постоянных можно получить любое решение данного соотношения 
 (4) решение, которое не зависит от k
-произвольных постоянных и путем подбора этих постоянных можно получить любое решение данного соотношения 
Номер 3
Какие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами?
Ответ:
 (1) рекуррентные соотношения вида
f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n)/n где a1,a2,...,ak
- некоторые числа 
 (2) рекуррентные соотношения вида
f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n)/k где a1,a2,...,ak
- некоторые числа 
 (3) рекуррентные соотношения вида
f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n) где a1,a2,...,ak
- некоторые числа 
 (4) рекуррентные соотношения вида
f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n)/(n+k) где a1,a2,...,ak
- некоторые числа 
Упражнение 2:
Номер 1
Какое уравнение является характеристическим для данного соотношения f(n+2)=a1f(n+1)+a2f(n)
?
Ответ:
 (1) кубическое уравнение вида r2=a1r+a2*r3
 
 (2) уравнение вида r2=a1r+a2/r3
 
 (3) квадратное уравнение вида r2=a1r+a2
 
 (4) квадратное уравнение вида r2=a1r+a2-a2
 
Номер 2
Какое характеристическое уравнение соответствует рекуррентному соотношению f(n)=f(n-1)+f(n-2)?
Ответ:
 (1) r2=r+1*r3
 
 (2) r2=r+1/r5
 
 (3) r2=r+1*r10
 
 (4) r2=r+1
 
Номер 3
Линейное рекуррентное соотношение с постоянными коэффициентами имеет вид f(n+k)=a1f(n+k-1)+...+anf(n)
. Какое уравнение будет для него характеристическим?
Ответ:
 (1) rk=a1rk-1+...+ak
 
 (2) rk=a1rk-1+...+ak/r
 
 (3) rk=ak
 
 (4) rk=a1rk-1
 
Упражнение 3:
Номер 1
Что называется производящей функцией для последовательности a0,a1,a2,...,
?
Ответ:
 
(1) последовательности
a0,a1,a2,...,
ставится в соответствие формальный ряд
называемый производящей функцией для данной последовательности 
 
(2) последовательности
х1,х2,...
, ставится в соответствие формальный ряд
называемый производящей функцией для данной последовательности 
 
(3) последовательности
a0x,a1,a2,...
ставится в соответствие формальный ряд
называемый производящей функцией для данной последовательности 
Номер 2
Что называется формальным рядом для последовательности a0,a1,a2,...,
?
Ответ:
 (1) производящая функция 
 
(2) для данной последовательности
a0,a1,a2,...,
, называется формальным рядом последовательности 
 (3) последовательности а0/k,а1,а2,...
для данной последовательности a0,a1,a2,...,
, называется формальным рядом последовательности 
 (4) последовательности а0x,а1,а2,...
для данной последовательности a0,a1,a2,...,
, называется формальным рядом последовательности 
Номер 3
Что означает название "формальный ряд последовательности"?
Ответ:
 (1) ряд записывается формально 
 (2) трактуется только как удобная запись данной последовательности 
 (3) ряд записывается как последовательность целых чисел 
 (4) ряд записывается как последовательность вещественных чисел