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

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

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

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

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

1.Легка

Як працює сортування вибором?

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

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

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

Що означає, що операція виконується за час O(1)?

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

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

  1. AO(n²)
  2. BO(dn log k)
  3. CO(d(n + k))
  4. DO(n log n)
5.Середня

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

  1. AO(n)
  2. BO(log n)
  3. CO(2ⁿ)
  4. DO(n²)
6.Середня

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

  1. AНі, бо для великих n n³ менше за n²
  2. BТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  3. CНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
  4. DТак, але лише якщо n менше за 100
7.Складна

Яка з цих задач виконуваності, як відомо, розв'язна за поліноміальний час?

  1. AВиконуваність схем
  2. B3-SAT, де кожен диз'юнкт має рівно три літерали
  3. CЗагальна SAT для формул у кон'юнктивній нормальній формі
  4. D2-SAT, де кожен диз'юнкт має щонайбільше два літерали
8.Складна

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

  1. AПрактично нерозв'язні задачі не може розв'язати жоден алгоритм, а нерозв'язні лише потребують експоненційного часу
  2. BОбидва терміни означають, що задача взагалі не має алгоритму
  3. CНерозв'язні задачі належать до NP, а практично нерозв'язні — до P
  4. DДля нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний

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

  1. 1. D · Воно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
  2. 2. A · Ω (велике Омега)
  3. 3. A · Її час виконання не зростає з розміром вхідних даних
  4. 4. C · O(d(n + k))
  5. 5. A · O(n)
  6. 6. B · Так, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  7. 7. D · 2-SAT, де кожен диз'юнкт має щонайбільше два літерали
  8. 8. D · Для нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний

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