Робочий аркуш «Алгоритми та складність» з відповідями

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

Новий робочий аркушТренуватися онлайн з підказками

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

Ім’я: ____________________   Дата: ____________

1.Легка

Яка часова складність лінійного пошуку в невідсортованому масиві з n елементів (у найгіршому випадку)?

  1. AO(n²)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
2.Легка

Задачу зазвичай називають практично розв'язною (tractable), якщо:

  1. AВона не має розв'язку
  2. BЇї можна розв'язати за сталий час
  3. CЇї можна розв'язати за поліноміальний час
  4. DЇї можна розв'язати лише перебором усіх можливостей
3.Легка

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

  1. AБлизько n
  2. BБлизько n / 2
  3. CБлизько log₂ n
  4. DБлизько n²
4.Середня

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

  1. AЖадібний використовує 2 монети; оптимум — 2
  2. BЖадібний використовує 4 монети; оптимум — 3
  3. CЖадібний використовує 3 монети; оптимум — 3
  4. DЖадібний використовує 3 монети; оптимум — 2
5.Середня

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

  1. AОбрати заявку, що починається найраніше
  2. BСпершу обрати найкоротшу заявку
  3. CОбрати заявку, що закінчується найраніше, а потім повторити із сумісними
  4. DСпершу обрати заявку з найменшою кількістю перекриттів, а потім повторити із сумісними
6.Середня

Який розв'язок рекурентного співвідношення T(n) = 2T(n/2) + O(1)?

  1. AO(n²)
  2. BO(n)
  3. CO(n log n)
  4. DO(log n)
7.Складна

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

  1. AУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час
  2. BПроблема зупинки стала б розв'язною
  3. CЛише ця одна задача перейшла б до P
  4. DКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
8.Складна

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

  1. AЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
  2. BЇї завжди можна розв'язати за O(V + E)
  3. CВона нерозв'язна
  4. DЦе NP-складна задача

Ключ відповідей

  1. 1. D · O(n)
  2. 2. C · Її можна розв'язати за поліноміальний час
  3. 3. C · Близько log₂ n
  4. 4. D · Жадібний використовує 3 монети; оптимум — 2
  5. 5. C · Обрати заявку, що закінчується найраніше, а потім повторити із сумісними
  6. 6. B · O(n)
  7. 7. D · Кожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
  8. 8. D · Це NP-складна задача

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.