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