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