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

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

1. AΘ (велике Тета)
2. Bo (мале o)
3. CO (велике O)
4. DΩ (велике Омега)

Що з наведеного зростає найповільніше зі збільшенням n?

1. AO(n²)
2. BO(n)
3. CO(n log n)
4. DO(log n)

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

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

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

1. AO(n log n)
2. BO(n)
3. CO(n²)
4. DO(2ⁿ)

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

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

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

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

Яке твердження про позначення «мале o» правильне?

1. A2n = o(n), бо 2n зростає повільно
2. Bn = o(n²), але n не є o(n)
3. Cn² = o(n)
4. Dn = o(n), бо кожна функція є «мале o» від самої себе

Проблема зупинки показує, що:

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