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

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

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

Що таке мемоізація?

1. AНаписання коментарів біля кожного рядка коду
2. BЗвільнення пам'яті після повернення з функції
3. CЗбереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
4. DАвтоматичне перетворення рекурсії на рівносильний цикл, щоб стек викликів не був потрібен

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

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

1. AO(V × E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V + E)

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

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

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

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

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

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