ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
Амурский гуманитарно-педагогический государственный университет
УТВЕРЖДАЮ
Зав. кафедрой
__________/ /
«______»___________200 г.
Контрольно-измерительные материалы
По дисциплине Теория алгоритмов
для студентов 4 - 5 курсов специальности 050202 «Информатика» со специализацией «Информационные системы в бухгалтерии и аудите»
365 –КИМ – ХХХХХХХ2007
Вариант 1
Уровень 1
1. Укажите, какое свойство не является характерным для понятия алгоритма:
А) Дискретность;
В) Детерминированность;
С) Элементарность шагов;
D) Последовательность шагов;
Е) Результативность.
2. Заключительным состоянием головки в машине Тьюринга является состояние:
А) q0;
B) q1;
C) q2;
D) qn.
3. Укажите запись, которая не может командой машины Тьюринга:
А) 3q1®3q1R;
B) 3q0®3q0R;
C) ^q1®3q0.
4. Тезис Чёрча заключается в следующем:
А) Любая задача, которая решается при помощи машины Тьюринга, может быть решена нормальным алгоритмом Маркова;
В) Любая задача, для которой существует алгоритм, может быть решена при помощи машины Тьюринга;
С) Любая задача может быть решена при помощи машины Тьюринга.
5. Функция f(x1,x2,…,xn) построена при помощи примитивной рекурсии из функций g(x1,x2,…,xn-1) и h(x1,x2,…,xn+1), если выполняются следующие условия:
А) f(x1,x2,…,xn-1)= g(x1,x2,…,xn-1) и f(x1,x2,…,xn+1)= h(x1,x2,…,xn+1);
B) f(x1,x2,…,xn-1,0)= g(x1,x2,…,xn-1) и f(x1,x2,…,k,0)= h(x1,x2,…,k,0);
C) f(x1,x2,…,xn-1,0)= g(x1,x2,…,xn-1) и f(x1,x2,…,xn,k+1)= h(x1,x2,…,k,f(x1,…,xn-1,k)).
6. Укажите функцию, которая не является основной (исходной) функцией:
А) e(x) = x;
B) s(x) = x + 1;
C) I23(x,y,z) =y.
7. Функция f(x1,x2,…,xn) называется примитивно рекурсивной, если:
А) найдутся такие функции h(x1,x2,…,xk), g1(x1,x2,…,xn), …, gk(x1,x2,…,xn), что f(x1,x2,…,xn)=h(g1(x1,x2,…,xn), …, gk(x1,x2,…,xn));
B) она построена при помощи конечного числа примитивных рекурсий из основных функций;
С) она построена при помощи конечного числа подстановок и примитивных рекурсий из основных функций;
D) она построена при помощи конечного числа подстановок и примитивных рекурсий из основных функций и применения m-операторов.
8. Класс вычислимых по Тьюрингу функций совпадает с классом:
А) примитивно рекурсивных функций;
В) частично рекурсивных функций;
С) всех числовых функций.
9. К базовым алгоритмам цифровой обработки информации сложности порядка n3 относятся:
А) базовые арифметические операции:
В) умножение вектора на скаляр;
С) умножение матрицы на вектор-столбец;
D) умножение матриц.
10. Укажите, какая из формул не является формулой подстановки в нормальной схеме алгоритма Маркова:
А) ab®ba;
B) ab®×ab;
C) baab.
Уровень 2
1. Укажите, какая характерная черта алгоритма не указана в вопросе 1 уровня 1.
2. Будет ли данная функция частично рекурсивной: f(x)=s(s(x))?
3. Продолжите утверждение: Проблема переводимости является алгоритмически…
4. Будет ли функция f(x,y) = x + y вычислимой по Тьюрингу?
Уровень 3
1. Составьте машину Тьюринга, которая в каждом числе 1 заменяет на 2.
2. Задайте функцию f(x) = x + 3 при помощи примитивной рекурсии.
Вариант 2
Уровень 1
1. Укажите, какое свойство не является характерным для понятия алгоритма:
А) Дискретность;
В) Конечность;
С) Элементарность шагов;
D) Массовость
Е) Результативность.
2. Начальным состоянием головки в машине Тьюринга является состояние:
А) q0;
B) q1;
C) q2;
D) qn.
3. Укажите запись, которая не может быть командой машины Тьюринга:
А) 5q0®5q1L;
B) 3q1®3q0;
C) ^q1®3q0R.
4. Тезис Чёрча заключается в следующем:
А) Любая задача, для которой существует алгоритм, может быть решена при помощи машины Тьюринга;
В) Любая задача, которая решается при помощи машины Тьюринга, может быть решена нормальным алгоритмом Маркова;
С) Любая задача может быть решена при помощи машины Поста.
5. Функция f(x1,x2,…,xn) построена при помощи примитивной рекурсии из функций g(x1,x2,…,xn-1) и h(x1,x2,…,xn+1), если выполняются следующие условия:
А) f(x1,x2,…,xn-1,0)= g(x1,x2,…,xn-1) и f(x1,x2,…,xn,k+1)= h(x1,x2,…,k,f(x1,…,xn-1,k))
B) f(x1,x2,…,xn-1,0)= g(x1,x2,…,xn-1) и f(x1,x2,…,k,0)= h(x1,x2,…,k,0);
C) f(x1,x2,…,xn-1,0)= g(x1,x2,…,xn-1) и f(x1,x2,…,xn+1)= h(x1,x2,…,xn+1);
6. Укажите функцию, которая не является основной (исходной) функцией:
А) O(x) = 0;
B) s(x) = x + 1;
C) E23(x,y,z) =y+z.
7. Функция f(x1,x2,…,xn) называется частично-рекурсивной, если:
А) найдутся такие функции h(x1,x2,…,xk), g1(x1,x2,…,xn), …, gk(x1,x2,…,xn), что f(x1,x2,…,xn)=h(g1(x1,x2,…,xn), …, gk(x1,x2,…,xn));
B) она построена при помощи конечного числа примитивных рекурсий из основных функций;
С) она построена при помощи конечного числа подстановок и примитивных рекурсий из основных функций;
D) она построена при помощи конечного числа подстановок и примитивных рекурсий из основных функций и применения m-операторов.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.