A) Розробка нових мов програмування B) Аналіз ресурсів, необхідних для вирішення обчислювальних задач C) Психологічні аспекти взаємодії людини та комп'ютера D) Апаратний дизайн для комп'ютерів
A) Нотація Big O B) Двійковий код C) Римські цифри D) Грецькі літери
A) БПП B) NP C) PSPACE D) EXP
A) Розвідувальний B) Експоненціальний час C) Розширений D) Експерт
A) Проблема P vs NP B) Паралельні обчислення C) Квантові алгоритми D) NP-повнота
A) NP-повний B) ЕКСКЛЮЗИВ C) БПП D) P
A) ЕКСПРЕС B) NP-повний C) PSPACE D) BQP
A) Щоб будувати суперкомп'ютери B) Створювати швидші комп'ютери C) Щоб згенерувати випадкові числа D) Класифікувати обчислювальні задачі на основі притаманної їм складності
A) Проблема, пов'язана з апаратним забезпеченням комп'ютерів. B) Теоретичне питання, яке не має вирішення. C) Математичне рівняння, яке неможливо розв'язати. D) Завдання, яке вирішується комп'ютером за допомогою алгоритму.
A) Набір усіх малих літер B) Двійковий алфавіт {0, 1} C) Набір символів ASCII D) Шістнадцяткова система
A) Кодування за допомогою природної мови B) Не потрібне жодне кодування C) Конкретний вибір способу кодування вхідних даних D) Використання лише десяткової системи числення
A) Пошук найкоротшого шляху в графі. B) Визначення кількості вершин у графі. C) Обчислення максимального потоку в мережі. D) Визначення, чи є заданий граф зв'язним, чи ні.
A) Визначення, чи є два графи ізоморфними. B) Задача про комерційного мандрівника. C) Перевірка, чи є граф двочастковим. D) Визначення, чи є число простим.
A) Байти B) Символи C) Біти D) Слова
A) Рання форма апаратного забезпечення комп'ютера. B) Практична технологія обчислень. C) Пристрій для маніпулювання фізичними об'єктами. D) Теоретична модель загальних обчислень.
A) Теорема Кука-Левіна. B) Неповні теореми Геделя. C) Теорема P проти NP. D) Теза Черча-Тюрінга.
A) Машина Тюрінга з ймовірнісними перетвореннями. B) Детермінована машина Тюрінга. C) Квантова машина Тюрінга. D) Недетермінована машина Тюрінга.
A) Вони обмежені поліноміальним часом. B) Вони працюють детерміновано. C) Вони потребують фізичної реалізації. D) Вони використовують випадкові біти для обчислень.
A) Аксіоми складності Блума B) Аксіоми, що стосуються проблеми P проти NP C) Аксіоми повноти Тюрінга D) Теорема Кука-Левіна
A) Складність ланцюга B) Складність квантової заплутаності C) Складність комунікації D) Складність дерева рішень
A) Складність комунікації B) Часова складність C) Складність схеми D) Просторова складність
A) Амортизований аналіз B) Найкращий сценарій складності C) Середній сценарій складності D) Найгірший сценарій складності
A) NP B) EXPTIME C) PSPACE D) FP
A) Теорема Савіча B) Теорема Кука-Лівіна C) Теорема про ієрархію часу D) Проблема P проти NP
A) P B) EXPTIME C) NP D) Усі
A) Теорема про ієрархію часу B) Теорема Кука-Левіна C) Теорема про ієрархію просторів D) Теорема Савіча
A) NC B) BPP C) QMA D) AC
A) QMA B) AC C) BPP D) RP
A) QMA B) NC C) IP D) BPP
A) NC B) #P C) RP D) BPP
A) Редукція з лінійною часовою складністю. B) Редукція з логарифмічною часовою складністю. C) Редукція з експоненціальною часовою складністю. D) Редукція з поліноміальною часовою складністю.
A) NP B) BQP C) PP D) co-NP
A) co-P не дорівнюватиме co-NP B) NP не дорівнюватиме co-NP C) co-P дорівнюватиме co-NP D) P не дорівнюватиме NP
A) NC B) PP C) NL D) L
A) BQP B) PP C) PH D) MA
A) Безперервні динамічні системи та диференціальні рівняння. B) Автомати з кінцевим числом станів. C) Обробка цифрових сигналів. D) Ймовірнісні алгоритми.
A) Неперервні функції. B) Квантові стани. C) Булеві вирази. D) Дискретні графи.
A) Юріс Хартманіс B) Річард Е. Стірнс C) Алан Тьюрінг D) Габріель Лам
A) 1965 B) 1936 C) 1950 D) 1945
A) Юріс Хартманіс B) Едмондс C) Габріель Лам D) Леонід Левін
A) Борис Трахтенброт B) Хісао Ямада C) Джон Майхілл D) Реймонд Смаллян
A) Елементарні множини B) Обчислення в режимі реального часу C) Метрики складності D) Лінійно обмежені автомати
A) Борис Трахтенброт B) Джон Майхілл C) Хісао Ямада D) Реймонд Смаллян
A) 1956 B) 1955 C) 1971 D) 1960
A) "Функція сигналізації" B) "Машина Тюрінга" C) "Обчислювальна складність" D) "Поліноміальний час"
A) 1971 B) 1967 C) 1972 D) 1965
A) 15 B) 10 C) 30 D) 21
A) Ґарі, Майкл Р.; Джонсон, Девід С. B) Дауні, Род; Феллоуз, Майкл C) Арора, Санджів; Барак, Боаз D) Вуппулурі, Шьям; Дорія, Франсіско А.
A) Вуппулурі, Ш'ям; Дорія, Франсіско А. B) Кук, Стівен; Фортнов, Ленс C) Дауні, Род; Феллоуз, Майкл D) Пападимітріу, Христос; Сіпсер, Майкл
A) Мертенс, Стефан B) Кук, Стівен C) Халіль, Хатем; Юлері, Дана D) Фортнов, Ленс; Гомер, Стівен
A) Хрістос Пападимітріу B) Санджів Арора C) Майкл Сіпсер D) Боаз Барак
A) Майкл Р. Герей; Девід С. Джонсон B) Хрістос Пападимітріу C) Санджів Арора; Боаз Барак D) Одед Гольдрейх
A) Санджів Арора; Боаз Барак B) Хрістос Пападимітріу C) Одед Гольдрейх D) Майкл Р. Герей; Девід С. Джонсон |