Каков порядок рекуррентного соотношения ?
Рекуррентные соотношения и Мастер-теорема
Рекуррентные соотношения и оценка сложности алгоритмов.
Как будете решать?
Блок 1. Один верный вариант
Какое характеристическое уравнение соответствует линейному однородному рекуррентному соотношению ?
Характеристическое уравнение имеет корни и . Каков общий вид решения ?
Характеристическое уравнение второго порядка имеет единственный кратный корень кратности 2. Как выглядит общее решение ?
В каком случае при решении линейного неоднородного рекуррентного уравнения с правой частью возникает явление резонанса?
Дано рекуррентное уравнение , описывающее сортировку слиянием (MergeSort). Какова его асимптотическая сложность по Мастер-теореме?
Дано рекуррентное соотношение , соответствующее бинарному поиску. Какова его сложность?
Задача размера сводится к 7 подзадачам размера с объединением за время : . Какой случай Мастер-теоремы применяется?
Какое условие регулярности необходимо проверить в случае 3 Мастер-теоремы для соотношения ?
Чему равно , если последовательность задана соотношением при начальных условиях ?
Блок 2. Краткий ответ
Дано ЛОРС: . Корни характеристического уравнения . При начальных условиях , решение имеет вид . Найдите значение константы .
целое число
Найдите шестое число Фибоначчи , если .
целое число
Дано уравнение с начальным условием . Вычислите .
целое число
Характеристическое уравнение имеет вид . Какова кратность корня ?
целое число
Для соотношения найдите критический показатель .
целое число
Найдите корень характеристического уравнения для соотношения первого порядка .
целое число
Блок 3. Несколько верных вариантов
Какие из следующих рекуррентных соотношений являются линейными однородными с постоянными коэффициентами?
Отметьте все верные варианты
Рассматривается рекуррентное соотношение второго порядка с вещественными постоянными коэффициентами и . Какие утверждения о его характеристическом уравнении верны?
Отметьте все верные варианты
В каких из приведенных алгоритмов время работы описывается вторым случаем Мастер-теоремы ()?
Отметьте все верные варианты
Какие методы применяются для нахождения замкнутой формулы рекуррентных соотношений?
Отметьте все верные варианты
Дано рекуррентное уравнение . Какие утверждения о его решении верны?
Отметьте все верные варианты
Какие свойства асимптотических оценок справедливы при анализе рекурсий?
Отметьте все верные варианты
Завершение теста
Все ответы сохраняются автоматически. Нажмите для отправки на проверку.