Теорія обчислювальної складності - тест
- 1. Теорія обчислювальної складності - це розділ теоретичної інформатики, який зосереджується на класифікації обчислювальних проблем на основі їхньої складності та кількості необхідних ресурсів, таких як час і простір. Вона має справу з розумінням ефективності алгоритмів, аналізом можливості розв'язання задач на різних типах машин та визначенням обмежень обчислювальних потужностей. Вивчаючи теорію обчислювальної складності, дослідники прагнуть дослідити межі обчислень і визначити можливості та обмеження комп'ютерів у розв'язанні різних типів задач.
На чому зосереджена теорія обчислювальної складності?
A) Апаратний дизайн для комп'ютерів
B) Психологічні аспекти взаємодії людини та комп'ютера
C) Розробка нових мов програмування
D) Аналіз ресурсів, необхідних для вирішення обчислювальних задач
- 2. Яка нотація зазвичай використовується для позначення складності алгоритмів?
A) Нотація Big O
B) Двійковий код
C) Римські цифри
D) Грецькі літери
- 3. До якого класу складності відносяться задачі прийняття рішень, які можна ефективно перевірити?
A) NP
B) БПП
C) EXP
D) PSPACE
- 4. Яка основна мета теорії обчислювальної складності?
A) Щоб будувати суперкомп'ютери
B) Створювати швидші комп'ютери
C) Класифікувати обчислювальні задачі на основі притаманної їм складності
D) Щоб згенерувати випадкові числа
- 5. Який клас складності представляє найскладніші проблеми в НП?
A) P
B) БПП
C) NP-повний
D) ЕКСКЛЮЗИВ
- 6. З чим пов'язана теорема Кука-Левіна в теорії обчислювальної складності?
A) Паралельні обчислення
B) Проблема P vs NP
C) Квантові алгоритми
D) NP-повнота
- 7. Що означає "EXP" в теорії обчислювальної складності?
A) Експоненціальний час
B) Розширений
C) Розвідувальний
D) Експерт
- 8. Який клас складності використовується для класифікації задач, які можуть бути вирішені квантовим комп'ютером за поліноміальний час?
A) PSPACE
B) ЕКСПРЕС
C) BQP
D) NP-повний
|