"Продвинутые" алгоритмы для школьников

Упражнение 1:

Номер 1

Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами носит название

Ответ:

(1) модульное программирование

(2) динамическое программирование

(3) комплексное программирование

Номер 2

Какие принципы включаются в динамическое программирование?

Ответ:

(1) оптимальная подструктура

(2) перекрывающиеся подзадачи

(3) контекстные модули

Номер 3

Центральным результатом теории динамического программирования следует считать

Ответ:

(1) уравнение Беллмана

(2) алгоритм Флойда

(3) теорему Кронекера-Капелли

Упражнение 2:

Номер 1

Идея о том, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи, лежит в основе концепции

Ответ:

(1) оптимальной подструктуры

(2) модульного программирования

(3) поиска вершинного покрытия

Номер 2

К составным частям оптимальной подструктуры следует отнести

Ответ:

(1) разбиение задачи на подзадачи меньшего размера

(2) нахождение оптимального решения подзадачи рекурсивно

(3) использование полученного решения подзадач для конструирования решения исходной задачи

Номер 3

Если нужно найти n!, то тривиальной задачей может быть

Ответ:

(1) 1! = 1

(2) 0!=1

(3) (n-1)!

Упражнение 3:

Номер 1

Подзадачи, которые используются для решения некоторого количества задач большего размера, носят название

Ответ:

(1) динамические подзадачи

(2) перекрывающиеся подзадачи

(3) контекстные подзадачи

Номер 2

Из приведенных ниже записей выделите варианты применения перекрывающихся задач:

Ответ:

(1) симплекс-метод

(2) NP-модулирование

(3) вычисление чисел Фибоначчи

Номер 3

Сохранение решений перекрывающихся подзадач носит название

Ответ:

(1) стаффинг

(2) кэширование

(3) импликация

Упражнение 4:

Номер 1

Для чего в динамическом программировании используется кэширование?

Ответ:

(1) для вычисления рекурсивных зависимостей

(2) для сохранения решений подзадач

(3) для вычисления по рекуррентным формулам

Номер 2

Граф подзадач для вычисления чисел Фибоначчи является

Ответ:

(1) модификативным

(2) ациклическим

(3) когнитивным

Номер 3

Из приведенных ниже записей выделите тип графа подзадач для вычисления чисел Фибоначчи:

Ответ:

(1) комплексный

(2) ациклический

(3) приоритетный

Упражнение 5:

Номер 1

Из приведенных ниже записей выделите типы динамического программирования:

Ответ:

(1) нисходящее программирование

(2) циклическое программирование

(3) модульное программирование

Номер 2

К типам динамического программирования следует отнести

Ответ:

(1) ациклическое программирование

(2) контейнерное программирование

(3) восходящее программирование

Номер 3

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

Ответ:

(1) циклическое и ациклическое программирование

(2) восходящее и нисходящее программирование

(3) модульное и потоковое программирование

Упражнение 6:

Номер 1

Граф взаимосвязей переменных в динамическом программировании представляет собой

Ответ:

(1) путь

(2) контейнер

(3) матрицу

Номер 2

Несериальное динамическое программирование рассматривает целевую функцию

Ответ:

(1) как статическую функцию

(2) как рекурсивно вычислимую функцию

(3) как модификативную константную функцию

Номер 3

Эффективность несериального динамического программирования зависит

Ответ:

(1) от метода поиска остовного дерева графа соответствия

(2) от структуры графа взаимосвязей переменных

(3) от типа данных и количества вершин графа смежности

Упражнение 7:

Номер 1

Из приведенных ниже записей выделите классические задачи динамического программирования:

Ответ:

(1) задача о наибольшей общей последовательности

(2) задача о перекрывающихся стеках

(3) задача о редакционном расстоянии

Номер 2

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

Ответ:

(1) задача о порядке перемножения матриц

(2) задача последовательного принятия решения

(3) задача о выборе траектории

Номер 3

К классическим задачам динамического программирования следует отнести

Ответ:

(1) задачу об использовании рабочей силы

(2) задачу о ранце

(3) задачу поиска кратчайшего пути в сети

Упражнение 8:

Номер 1

Для каких из приведенных ниже задач применимы методы динамического программирования?

Ответ:

(1) алгоритм Флойда-Уоршелла

(2) поиск максимального независимого множества вершин в дереве

(3) вычисление чисел Фибоначчи

Номер 2

Какое рекуррентное соотношение задает последовательность чисел Фибоначчи?

Ответ:

(1) F_n+1=F_n+F_n-1

(2) F_n=F_n-1+F_n+1

(3) F_n-1=F_n+1+F_n

Номер 3

Каким образом можно выразить числа Фибоначчи через многочлены Чебышева?

Ответ:

(1) F_n+1=(-i)ⁿT_n(-i)

(2) F_n+1=T_n

(3) F_n+1=(-i)ⁿT_n

Упражнение 9:

Номер 1

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным

Ответ:

(1) среднему арифметическому индексов

(2) наибольшему общему делителю индексов

(3) сумме индексов

Номер 2

Последовательность чисел Фибоначчи является частным случаем

Ответ:

(1) контекстной последовательности

(2) возвратной последовательности

(3) модульной последовательности

Номер 3

Характеристический многочлен возвратной последовательности чисел Фибоначчи имеет вид

Ответ:

(1) x²-x-1

(2) x²-1

(3) 2x-x²

Упражнение 10:

Номер 1

Отношения чисел Фибоначчи F_n+1/F_n являются

Ответ:

(1) дробями золотого сечения

(2) индексами характеристического многочлена

(3) наибольшими индексами матрицы совместимости

Номер 2

Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются

Ответ:

(1) числами матрицы инцидентности

(2) числами Фибоначчи

(3) числами модулей графа корректности

Номер 3

Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы

Ответ:

(1) всегда является числом Фибоначчи

(2) никогда не является числом Фибоначчи

(3) может являться числом Фибоначчи

Упражнение 11:

Номер 1

Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом

Ответ:

(1) 10

(2) 40

(3) 60

Номер 2

Последняя пара цифр чисел Фибоначчи образует последовательность с периодом

Ответ:

(1) 120

(2) 270

(3) 300

Номер 3

Последняя  тройка цифр чисел Фибоначчи образует последовательность с периодом

Ответ:

(1) 1500

(2) 2000

(3) 3500

Упражнение 12:

Номер 1

Если никакие две вершины множества вершин графа не соединены ребром, то такое множество носит название

Ответ:

(1) независимое

(2) висячее

(3) свободное

Номер 2

Задача о независимом множестве эффективно решается методом динамического программирования, если рассматриваемый граф является

Ответ:

(1) деревом

(2) контейнером

(3) гиперграфом

Номер 3

Задача о независимом множестве является

Ответ:

(1) циклической

(2) симплексной

(3) NP-полной

"Продвинутые" алгоритмы для школьников - тест 7