Тест 1.
1. Свойство алгоритма «детерминированность» это :
а) последовательное построение величин;
б) система величин однозначно определяется системой
величин, полученных на предыдущем шаге;
c) получение результата.
2. Любая примитивно рекурсивная функция всюду определена?
а) да
б) нет
с) не любая
3. Какую функцию можно получить, многократно применяя оператор суперпозиции к функции следования и нуль-функции?
а) нулевую;
б) константную;
с) нулевую от n-переменных.
4. Может ли в машине Тьюринга быть команда q0ai→q0aj?
а) да
б) нет
с) не во всех.
5. Сколько вхождений имеет слово аа в слово аааа?
а) 1
б) 2
с) 3
Ключи к тесту.
1 | 2 | 3 | 4 | 5 |
б | а | Б | б | с |
Тест 2
1. Множество, для которого существует алгоритм, позволяющий определить, принадлежит ли некоторый элемент данному множеству, называется
a) перечислимым
b) разрешимым
c) конечным
d) бесконечным
2. Команда для машины Поста записывается в следующем формате (n – номер текущей команды, m – номер следующей команды, k – указание о выполняемом действии):
a) k n m
b) n m k
c) m k n
d) n k m
3. Информация, хранящаяся на ленте машины Тьюринга, закодирована знаками
a) двоичного алфавита
b) внутреннего алфавита
c) внешнего алфавита
d) латинского алфавита
4. В нормальном алгоритме Маркова дана система подстановок в алфавите Х={x, y,z}:
. Преобразуйте с помощью этой системы слово xxxyyyzzz
a) xxy
b) yxz
c) xyz
d) yxzz
5. Открытие того, что алгоритмы и исчисления имеют формальные задания, и что эти формальные задания (точнее, некоторые их записи) сами могут служить объектами алгоритмических и исчислительных преобразований, сделал
a) А. Черч
b)
c) Э. Пост
d)
6. Неразрешимость проблемы разрешения для логики предикатов первого порядка установил
a) Э. Пост
b) А. Чёрч
c)
d)
7. Проблема определения по двум произвольным заданным алгоритмам, будут ли они выдавать одинаковые выходные результаты на любых исходных данных, называется
a) проблема останова
b) проблема тотальности
c) проблема эквивалентности алгоритмов
d) десятая проблема Гильберта
Ключи к тесту.
1 | 2 | 3 | 4 | 5 | 6 | 7 |
b | d | c | d | a | b | c |
