← Все тренажёры Рекуррентные соотношения и Мастер-теорема

Рекуррентные соотношения и Мастер-теорема

Рекуррентные соотношения и оценка сложности алгоритмов.

22 задания · Рекуррентные соотношения

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Каков порядок рекуррентного соотношения an=5an−1−6an−3+n2a_n = 5a_{n-1} - 6a_{n-3} + n^2?

2

Какое характеристическое уравнение соответствует линейному однородному рекуррентному соотношению an−5an−1+6an−2=0a_n - 5a_{n-1} + 6a_{n-2} = 0?

3

Характеристическое уравнение имеет корни r1=2r_1 = 2 и r2=3r_2 = 3. Каков общий вид решения ana_n?

4

Характеристическое уравнение второго порядка имеет единственный кратный корень r1=r2=4r_1 = r_2 = 4 кратности 2. Как выглядит общее решение ana_n?

5

В каком случае при решении линейного неоднородного рекуррентного уравнения с правой частью f(n)=P(n)snf(n) = P(n) s^n возникает явление резонанса?

6

Дано рекуррентное уравнение T(n)=2T(n/2)+Θ(n)T(n) = 2 T(n/2) + \Theta(n), описывающее сортировку слиянием (MergeSort). Какова его асимптотическая сложность по Мастер-теореме?

7

Дано рекуррентное соотношение T(n)=T(n/2)+Θ(1)T(n) = T(n/2) + \Theta(1), соответствующее бинарному поиску. Какова его сложность?

8

Задача размера nn сводится к 7 подзадачам размера n/2n/2 с объединением за время Θ(n2)\Theta(n^2): T(n)=7T(n/2)+Θ(n2)T(n) = 7 T(n/2) + \Theta(n^2). Какой случай Мастер-теоремы применяется?

9

Какое условие регулярности необходимо проверить в случае 3 Мастер-теоремы для соотношения T(n)=aT(n/b)+f(n)T(n) = a T(n/b) + f(n)?

10

Чему равно a2a_2, если последовательность задана соотношением an=3an−1−2an−2a_n = 3a_{n-1} - 2a_{n-2} при начальных условиях a0=1,a1=4a_0 = 1, a_1 = 4?

Блок 2. Краткий ответ

11

Дано ЛОРС: an−4an−1+3an−2=0a_n - 4a_{n-1} + 3a_{n-2} = 0. Корни характеристического уравнения r1=1,r2=3r_1 = 1, r_2 = 3. При начальных условиях a0=10,a1=16a_0 = 10, a_1 = 16, решение имеет вид an=λ1+λ2⋅3na_n = \lambda_1 + \lambda_2 \cdot 3^n. Найдите значение константы λ2\lambda_2.

целое число

12

Найдите шестое число Фибоначчи F6F_6, если F0=0,F1=1,F2=1,F3=2,F4=3,F5=5F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5.

целое число

13

Дано уравнение an=2an−1+1a_n = 2a_{n-1} + 1 с начальным условием a0=0a_0 = 0. Вычислите a5a_5.

целое число

14

Характеристическое уравнение имеет вид r2−6r+9=0r^2 - 6r + 9 = 0. Какова кратность корня r=3r = 3?

целое число

15

Для соотношения T(n)=4T(n/2)+nT(n) = 4 T(n/2) + n найдите критический показатель log⁡ba\log_b a.

целое число

16

Найдите корень характеристического уравнения для соотношения первого порядка an=5an−1a_n = 5 a_{n-1}.

целое число

Блок 3. Несколько верных вариантов

17

Какие из следующих рекуррентных соотношений являются линейными однородными с постоянными коэффициентами?

Отметьте все верные варианты

18

Рассматривается рекуррентное соотношение второго порядка с вещественными постоянными коэффициентами и c2≠0c_2\ne0. Какие утверждения о его характеристическом уравнении r2−c1r−c2=0r^2 - c_1 r - c_2 = 0 верны?

Отметьте все верные варианты

19

В каких из приведенных алгоритмов время работы описывается вторым случаем Мастер-теоремы (T(n)=Θ(nlog⁡balog⁡k+1n)T(n) = \Theta(n^{\log_b a} \log^{k+1} n))?

Отметьте все верные варианты

20

Какие методы применяются для нахождения замкнутой формулы рекуррентных соотношений?

Отметьте все верные варианты

21

Дано рекуррентное уравнение an=2an−1+3na_n = 2a_{n-1} + 3^n. Какие утверждения о его решении верны?

Отметьте все верные варианты

22

Какие свойства асимптотических оценок справедливы при анализе рекурсий?

Отметьте все верные варианты

Завершение теста

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

Карта заданий (22)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.