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

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

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

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

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

1.Легка

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

  1. A12 секунд
  2. B3 секунди
  3. C6 секунд
  4. D9 секунд
2.Легка

Що таке алгоритм?

  1. AБудь-яка комп'ютерна програма з графічним інтерфейсом
  2. BСкінченна послідовність чітко визначених кроків, що розв'язує задачу
  3. CМова програмування, призначена для запису математичних формул
  4. DСтруктура даних, що зберігає числа
3.Легка

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

  1. A8 секунд
  2. B1 секунду
  3. C4 секунди
  4. D2 секунди
4.Середня

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

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

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

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

Чому динамічне програмування не дає реального пришвидшення для сортування злиттям?

  1. AСортування злиттям уже має складність O(n)
  2. BДинамічне програмування працює лише на задачах про графи, а не на масивах
  3. CЙого підзадачі не перекриваються, тож нічого використати повторно
  4. DСортування злиттям не має рекурсивної структури
7.Складна

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

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

Що встановила теорема Кука–Левіна?

  1. AПроблема зупинки нерозв'язна
  2. BКожну задачу з NP можна розв'язати за експоненційний час
  3. CP не дорівнює NP
  4. DЗадача виконуваності булевих формул (SAT) є NP-повною

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

  1. 1. C · 6 секунд
  2. 2. B · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  3. 3. C · 4 секунди
  4. 4. D · Жадібний використовує 3 монети; оптимум — 2
  5. 5. C · Близько log₂ n
  6. 6. C · Його підзадачі не перекриваються, тож нічого використати повторно
  7. 7. D · Кожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
  8. 8. D · Задача виконуваності булевих формул (SAT) є NP-повною

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