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