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

Яка нотація описує верхню межу зростання?

1. AВелике Тета
2. BМале омега
3. CВелике Омега
4. DВелике O

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

1. A2 секунди
2. B8 секунд
3. C1 секунду
4. D4 секунди

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

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AПошук у глибину (DFS)
2. BАлгоритм Дейкстри
3. CУ всіх випадках потрібен алгоритм Беллмана–Форда
4. DАлгоритм Краскала

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

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

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

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

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

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