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