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