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

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

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

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

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

Що таке алгоритм?

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

Жадібний алгоритм:

1. AВикористовує лише рекурсію
2. BПеребирає всі можливі розв'язки
3. CЗавжди дає оптимальний розв'язок
4. DНа кожному кроці робить локально найкращий вибір

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

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

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

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

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

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

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

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