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

Який алгоритм сортування багаторазово міняє місцями сусідні елементи, що стоять у неправильному порядку?

1. AСортування злиттям
2. BШвидке сортування (quicksort)
3. CСортування бульбашкою
4. DПірамідальне сортування

Який клас складності зростає найшвидше для великих n?

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

Що таке алгоритм повного перебору?

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

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

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

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

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

1. AΩ(n)
2. BΩ(log n)
3. CΩ(n log n)
4. DΩ(n²)

Алгоритм динамічного програмування Гелда–Карпа точно розв'язує задачу комівояжера. Який його час виконання для n міст?

1. AO(n² 2ⁿ)
2. BO(2^n²)
3. CO(n³)
4. DO(n!)

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

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