Главная / Алгоритмы и дискретные структуры /
Классические и квантовые вычисления / Тест 1
Номер 3
Ответ:
Классические и квантовые вычисления - тест 1
Упражнение 1:
Номер 1
Ответ:
Номер 1
Однозначно определенная совокупность инструкций по преобразованию исходных данных в результат - это:
Ответ:
(1) вычислительная задача
(2) алгоритм
(3) функция
Номер 2
Ответ:
Условием строгой формулировки вычислительной задачи является наличие:
Ответ:
(1) способа кодировки входных данных
(2) внешнего алфавита
(3) ни один из перечисленных
Если кодировки переводятся друг в друга при помощи полиномального алгоритма, то они:
Ответ:
(1) разумны
(2) неразумны
(3) эквивалентны
Упражнение 2:
Номер 1
Ответ:
Номер 1
В наборедля задания машины Тьюринга выполняется условие:
Ответ:
(1) 
(2) 
- некоторый элемент 
- некоторый элемент
(3) 
- некоторая функция из 
- некоторая функция из
Номер 2
Ответ:
В наборе
Ответ:
(1) множеством состояний управляющего устройства
(2) алфавитом
(3) внешним алфавитом
Номер 3
Ответ:
Множество состояний управляющего устройства в наборе
Ответ:
(1) 
(2)
(3) 
Упражнение 3:
Номер 1
Ответ:
Номер 1
Состояние машины Тьюринга задается тройкой, где бесконечное слово в алфавите
Ответ:
(1) 
(2) 
(3) 
Номер 2
Ответ:
Для задания состояния машины Тьюринга обязательным является указание:
Ответ:
(1) бесконечного слова в алфавите
(2) неотрицательного целого числа
(3) состояния управляющего устройства
(4) ничего из перечисленного
Номер 3
Ответ:
Условием остановки машины Тьюринга, находящейся в состоянии
Ответ:
(1) 
(2) функция переходов на паре 
не определена
не определена
(3) 
Упражнение 4:
Номер 1
Ответ:
Номер 1
Выберите неверное утверждение:
Ответ:
(1) функция 
, вычисляемая машиной Тьюринга, не определена на входах, на которых машина не останавливается
, вычисляемая машиной Тьюринга, не определена на входах, на которых машина не останавливается
(2) любая машина Тьюринга вычисляет ровно одну функцию
(3) любая машина Тьюринга вычисляет заранее определенное количество функций
Номер 2
Ответ:
Частичная функцияиз
в
Ответ:
(1) если существует машина Тьюринга 
, для которой 
, для которой
(2) если существует машина Тьюринга , для которой 
, для которой
(3) всегда
Номер 3
Ответ:
Континуум - это:
Ответ:
(1) мощность множества машин Тьюринга
(2) мощность множества функций
(3) счетное множество
Упражнение 5:
Номер 1
Ответ:
Номер 1
Условием разрешимости предиката является:
Ответ:
(1) характеристическая функция равна 0
(2) характеристическая функция вычислима
(3) характеристическая функция равна 1
Номер 2
Ответ:
Время работы машины Тьюринга определяется:
Ответ:
(1) максимальным (по всем входам) количеством тактов, которое проработает до остановки
до остановки
(2) положением головки при вычислениях на входах
(3) нет верного ответа
Номер 3
Ответ:
Важнейшими ресурсами, требующимися машине Тьюринга для вычислений, является:
Ответ:
(1) память 
(2) объем вычислений 
(3) время 
Упражнение 6:
Номер 1
Ответ:
Номер 1
Тезисом Черча является утверждение:
Ответ:
(1) каждая машина Тьюринга вычисляет частичную функцию из в
вычисляет частичную функцию из в
(2) предикат от нескольких переменных разрешим, если его характеристическая функция вычислима
(3) любой алгоритм может быть реализован машиной Тьюринга
Номер 2
Ответ:
Функцияявляется функцией полиномиального роста, если для некоторой константы
при достаточно больших
выполняется неравенство:
Ответ:
(1) 
(2) 
(3) 
Номер 3
Ответ:
Если характеристическая функция предиката вычислима на машине Тьюринга, то
Ответ:
(1) предикат на множестве 
принадлежит классу 
на множестве принадлежит классу
(2) предикат на множестве принадлежит классу 
на множестве принадлежит классу
(3) предикат на множестве принадлежит классам и
на множестве принадлежит классам и
Упражнение 7:
Номер 1
Ответ:
Номер 1
Схема является формулой, если:
Ответ:
(1) имеются ссылки на другие части формулы
(2) каждая вспомогательная переменная используется в правой части присваиваний только один раз
(3) результатом вычисления является 
Номер 2
Ответ:
Вершины входной степени 0 ориентированного ациклического графа помечаются:
Ответ:
(1) исходными переменными
(2) числами, указывающими номера аргументов
(3) переменными, описывающими результат работы схемы
Номер 3
Ответ:
Полный стандартный базис образуют булевы функции:
Ответ:
(1) отрицание, конъюнкция
(2) отрицание, дизъюнкция, эквивалентность
(3) отрицание, дизъюнкция, конъюнкция
Упражнение 8:
Номер 1
Ответ:
Номер 1
Дизъюнктивной нормальной форме (ДНФ) соответствует:
Ответ:
(1) дизъюнкция конъюнкций литералов
(2) конъюнкция дизъюнкций литералов
(3) отрицание дизъюнкций литералов
(4) нет верного ответа
Номер 2
Ответ:
Выберите верное утверждение:
Ответ:
(1) количество присваиваний в схеме называется ее размером
(2) схемная сложность функции в базисе 
- это максимальный размер схемы в базисе , вычисляющей функцию
в базисе - это максимальный размер схемы в базисе , вычисляющей функцию
(3) переход от одного полного конечного базиса к другому полному конечному базису не меняет схемную сложность
Номер 3
Ответ:
Строка таблицы вычисления:
Ответ:
(1) задает схемную сложность на -том такте
-том такте
(2) задает состояние машины Тьюринга после тактов работы
тактов работы
(3) определяет размер схемы