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

Які три кроки алгоритму «розділяй і володарюй»?

1. AВгадати, перевірити, повторити
2. BРозділити, підкорити, об'єднати
3. CПрочитати, обчислити, записати
4. DВідсортувати, знайти, повернути

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

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

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

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

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
2. BНайкоротші шляхи між усіма парами вершин за O(V³)
3. CМінімальне кістякове дерево за O(E log V)
4. DТопологічний порядок за O(V²)

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

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

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

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

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

1. AΘ(n^{log₂ 7}), близько n^2,81
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n²)

Як класифікують задачу комівояжера?

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