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