Теория алгоритмов. Контрольно-измерительные материалы

Страницы работы

Содержание работы

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Амурский гуманитарно-педагогический государственный университет

УТВЕРЖДАЮ                    

Зав. кафедрой                      

__________/ /

«______»___________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-операторов.

Похожие материалы

Информация о работе

Предмет:
Информатика
Тип:
Методические указания и пособия
Размер файла:
67 Kb
Скачали:
0