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