Информатика и выч. техника \ Информатика

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

8.         Класс вычислимых по Тьюрингу функций образует:

А)        счетное множество;

В)        несчетное множество;

С)        конечное множество.

9.         К базовым алгоритмам цифровой обработки информации сложности порядка n2 относятся:

А)        базовые арифметические операции:

В)        умножение вектора на скаляр;

С)        умножение матрицы на вектор-столбец;

D)        умножение матриц.

10.       Укажите заключительную формулу подстановки в нормальной схеме алгоритма Маркова:

А)        ab®ba;

B)        ab®×ab;

C)        ®ab.

Уровень 2

1.         Укажите, какая характерная черта алгоритма не указана в вопросе 1 уровня 1.

2.         Будет ли данная функция частично рекурсивной: f(x)=s(О(x))?

3.         Продолжите утверждение: Проблема самоприменимости является алгоритмически…

4.         Будет ли функция f(x,y) = x×y вычислимой по Тьюрингу?

Уровень 3

1.         Составьте машину Тьюринга, которая в конце каждого числа дописывает цифру 3.

2.         Задайте функцию f(x) = 3x при помощи примитивной рекурсии.

Вариант 3

Уровень 1

1.         Укажите, какое свойство не является характерным для понятия алгоритма:

А)        Конечность;

В)        Детерминированность;

С)        Элементарность;

D)        Массовость:

С)        Результативность.

2.         В начальный момент времени головка находится над:

А)        первым непустым символом слова С;

В)        последним непустым символом слова С;

С)        первым пустым символом перед словом С;

D)        первым пустым символом после слова С.

3.         Укажите запись, которая не может командой машины Тьюринга:

А)        3q1®^q1R;

B)        1q0®1q0L;

C)        ^q1®3q1R.

4.         Тезис Чёрча заключается в следующем:

А)        Любая задача, которая может быть решена при помощи машины Тьюринга, может быть решена при помощи машины Поста.

В)        Любая задача, которая решается при помощи машины Тьюринга, может быть решена нормальным алгоритмом Маркова;

С)        Любая задача, для которой существует алгоритм, может быть решена при помощи машины Тьюринга;

5.         Функция f(x1,x2,…,xn) построена при помощи примитивной рекурсии из функций g(x1,x2,…,xn-1) и h(x1,x2,…,xn+1), если выполняются следующие условия:

А)        f(x1,x2,…,0)= g(x1,x2,…,0) и 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,…,xn,k+1)= h(x1,x2,…,k,f(x1,…,xn-1,k));

C)        f(x1,x2,…,xn-1,0)= g(x1,x2,…,xn-1) и f(x1,x2,…,k,0)= h(x1,x2,…,k,f(x1,…,xn-1)).

6.         Укажите функцию, которая не является основной (исходной) функцией:

А)        O(x) = 0;

B)        e(x) = x;

C)        I11(x) =x.

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)        она построена при помощи конечного числа примитивных рекурсий из основных функций;

С)        она построена при помощи конечного числа примитивных рекурсий и применения m-операторов.

8.         Множество всех числовых функций:

А)        конечно;

В)        счетное;

С)        несчетное.

9.         К базовым алгоритмам цифровой обработки информации сложности порядка 1 относятся:

А)        базовые арифметические операции:

В)        умножение вектора на скаляр;

С)        умножение матрицы на вектор-столбец;

D)        умножение матриц.

10.       Укажите обычную формулу подстановки в нормальной схеме алгоритма Маркова:

А)        ab®ba;

B)        ab®×ab;

C)        ®×ab.

Уровень 2

1.         Укажите, какая характерная черта алгоритма не указана в вопросе 1 уровня 1

2.         Будет ли данная функция частично рекурсивной: f(x)=s(s(0(x)))?

3.         Продолжите утверждение: Проблема применимости является алгоритмически…

4.         Будет ли функция f(x) = 2x вычислимой по Тьюрингу?

Уровень 3

1.         Составьте машину Тьюринга, которая каждое число умножает на 10.

2.         Задайте функцию f(x;y) = x + y при помощи примитивной рекурсии.

№

1

2

3

4

5

6

7

8

9

10

1

2

3

4

1

D

A

B

B

C

A

C

B

D

C

массовость

да

нераз-решима

да

2

B

B

A

A

A

C

D

A

C

B

детерминиро-ванность

да

нераз-решима

да

3

A

A

B

C

B

B

A

C

A

A

дискретность

да

нераз-решима

да

Вес каждого задания уровня 1 – 1 балл.

Вес каждого задания уровня 2 – 2 балла.

Вес каждого задания уровня 3 – 3 балла

Максимальное количество баллов  - 24.

Таблица перевода тестового балла в пятибалльную шкалу:

Отметка

Процент выполненных заданий

Количество набранных баллов

3

40 - 50%

10-12

4

51-70%

13-17

5

71-100%

18-24

Для получения отметки 5 требуется выполнить от 71% до 100% всех заданий, но среди верно выполненных должно быть одно из заданий 3 уровня.

Скачать файл