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

Бесплатный лист заданий для печати по теме «Алгоритмы и сложность»: 8 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

Для преподавателей: можно бесплатно печатать, копировать и использовать на занятиях. Каждый новый лист содержит новые значения и собственные ответы. Будем благодарны за ссылку на ExamProblems на странице вашего курса.

Имя: ____________________   Дата: ____________

1.Лёгкая

Какое из этих времён работы полиномиально?

  1. AO(n!)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(2ⁿ)
2.Лёгкая

Какой класс сложности растёт быстрее всех при больших n?

  1. AO(n log n)
  2. BO(n³)
  3. CO(2ⁿ)
  4. DO(n²)
3.Лёгкая

Какая нотация описывает верхнюю границу роста?

  1. AO-большое
  2. BОмега-малое
  3. CОмега-большое
  4. DТета-большое
4.Средняя

Что означает, что задача обладает оптимальной подструктурой?

  1. AОптимальное решение можно построить из оптимальных решений её подзадач
  2. BУ задачи ровно одно оптимальное решение, общее для всех подзадач
  3. CЗадачу можно решить за постоянное время
  4. DВсе подзадачи одного размера
5.Средняя

Почему динамическое программирование не даёт реального ускорения для сортировки слиянием?

  1. AУ сортировки слиянием нет рекурсивной структуры
  2. BДинамическое программирование работает только на задачах о графах, но не на массивах
  3. CСортировка слиянием уже работает за O(n)
  4. DЕё подзадачи не перекрываются, поэтому нечего использовать повторно
6.Средняя

Каково решение рекуррентного соотношения T(n) = 2T(n/2) + O(1)?

  1. AO(n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n log n)
7.Сложная

Какое утверждение о P и NP верно?

  1. AКаждая задача из P также принадлежит NP
  2. BNP означает «неполиномиальный» (not polynomial)
  3. CРешения задач NP невозможно быстро проверить
  4. DДоказано, что P ≠ NP
8.Сложная

Принадлежит ли 22n классу O(2ⁿ)?

  1. AНет, потому что 22n растёт медленнее 2ⁿ
  2. BНет, потому что 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ растёт неограниченно
  3. CДа, потому что постоянные множители в показателе в O большом всегда игнорируются
  4. DДа, потому что обе функции экспоненциальны

Ответы

  1. 1. C · O(n³)
  2. 2. C · O(2ⁿ)
  3. 3. A · O-большое
  4. 4. A · Оптимальное решение можно построить из оптимальных решений её подзадач
  5. 5. D · Её подзадачи не перекрываются, поэтому нечего использовать повторно
  6. 6. A · O(n)
  7. 7. A · Каждая задача из P также принадлежит NP
  8. 8. B · Нет, потому что 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ растёт неограниченно

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.