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

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

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

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

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

1.Легка

Що описує час виконання алгоритму в найгіршому випадку?

  1. AОчікуваний час на випадкових вхідних даних розміру n
  2. BЧас на повільному комп'ютері
  3. CЧас на найменших вхідних даних
  4. DМаксимальний час на всіх вхідних даних розміру n
2.Легка

Що означає f(n) = Θ(g(n))?

  1. Af завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
  2. Bf зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
  3. Cf зростає строго швидше, ніж g
  4. Df зростає строго повільніше, ніж g
3.Легка

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

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

Як алгоритм Прима будує мінімальне кістякове дерево?

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

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

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

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

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

Яке визначення класу NP правильне?

  1. AЗадачі, які неможливо розв'язати за поліноміальний час
  2. BЗадачі, що не є поліноміальними
  3. CЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката
  4. DЗадачі, які не може розв'язати жоден алгоритм

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

  1. 1. D · Максимальний час на всіх вхідних даних розміру n
  2. 2. B · f зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
  3. 3. A · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  4. 4. B · O(n³)
  5. 5. A · Він вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
  6. 6. D · Так, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  7. 7. C · X належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
  8. 8. C · Задачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката

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