Алгоритмы и сложность: лист заданий с ответами

Доступ к элементу массива по индексу занимает:

1. AO(1)
2. BO(n²)
3. CO(n)
4. DO(log n)

Задачу обычно называют практически разрешимой (tractable), если:

1. AЕё можно решить за постоянное время
2. BЕё можно решить только перебором всех возможностей
3. CЕё можно решить за полиномиальное время
4. DУ неё нет решения

Что такое алгоритм полного перебора (brute force)?

1. AАлгоритм, работающий на многих процессорах
2. BАлгоритм, перебирающий все возможные кандидаты в решения
3. CАлгоритм, угадывающий ответ случайным образом
4. DАлгоритм, который всегда использует рекурсию

Какое утверждение о рекурсивной функции без достижимого базового случая верно?

1. AОна работает за время O(1)
2. BКомпилятор всегда превращает её в цикл, который безопасно завершается
3. CОна автоматически возвращает 0
4. DОна продолжает вызывать себя, пока не переполнится стек вызовов

При монетах 1, 3 и 4 и сумме 6 сколько монет использует жадный метод «сначала самая крупная монета» по сравнению с оптимумом?

1. AЖадный метод использует 3 монеты; оптимум — 3
2. BЖадный метод использует 2 монеты; оптимум — 2
3. CЖадный метод использует 3 монеты; оптимум — 2
4. DЖадный метод использует 4 монеты; оптимум — 3

Какова временна́я сложность стандартного алгоритма динамического программирования для наибольшей общей подпоследовательности строк длиной m и n?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn)
4. DO(mn log n)

Как соотносятся n! и 2ⁿ при больших n?

1. An! растёт быстрее 2ⁿ
2. Bn! есть O(n²)
3. C2ⁿ растёт быстрее n!
4. DОни растут с одинаковой скоростью

Проблема остановки показывает, что:

1. AКаждая программа в конце концов останавливается
2. BНикакой алгоритм не может для каждой программы и входных данных определить, остановится ли она
3. CНекоторые программы работают быстрее на более быстрых компьютерах, поэтому остановка зависит от оборудования
4. DЦиклов следует избегать