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

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

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

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

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

1.Легка

Яке позначення описує нижню межу зростання?

  1. AO (велике O)
  2. BΩ (велике Омега)
  3. Co (мале o)
  4. DΘ (велике Тета)
2.Легка

Просторова складність вимірює:

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

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

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

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

  1. AСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  2. BСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
  3. CРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
  4. DСортування вставками має складність O(n log n) у найгіршому випадку
5.Середня

Що означає, що задача має оптимальну підструктуру?

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

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

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

Які дві речі треба показати, щоб довести, що задача розпізнавання X є NP-повною?

  1. AX не має поліноміального алгоритму, і X розв'язна
  2. BX належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
  3. CX належить до P, і X зводиться до SAT
  4. DX зводиться до задачі з P, і X належить до NP
8.Складна

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

  1. AТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
  2. BW — число, тому час експоненційний відносно кількості бітів, використаних для запису W
  3. CТому що n завжди мале
  4. DТому що він працює лише для W = 0

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

  1. 1. B · Ω (велике Омега)
  2. 2. A · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  3. 3. B · Її можна розв'язати за поліноміальний час
  4. 4. A · Сортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  5. 5. C · Оптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  6. 6. D · O(d(n + k))
  7. 7. B · X належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
  8. 8. B · W — число, тому час експоненційний відносно кількості бітів, використаних для запису W

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