игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 11

Основы теории вычислимых функций - тест 11

Упражнение 1:
Номер 1 
 Операция:

h(x1,x2,…,xk,0) = f(x1,x2,…,xk,)
h(x1,x2,…,xk,y+1) = g(x1,x2,…,xk,y,h(x1,x2,…,xk,y))

называется:

Ответ:

 (1) рекурентностью 

 (2) рекурсией 

 (3) итерацией 

Номер 2 
Функции, получаемые с помощью операций подстановки и рекурсии из константы 0, операции прибавления единицы k штук k-местных функций math называют:

Ответ:

 (1) базово рекурсивной 

 (2) примитивно рекурсивной 

 (3) универсально рекурсивной 

Номер 3 
Функция fn(x)=fn-1(x)+x:

Ответ:

 (1) рекурсивна 

 (2) не рекурсивна 

 (3) совершенна 

Упражнение 2:
Номер 1 
Функция f(xn)=f(xn-1)+x:

Ответ:

 (1) рекурсивна 

 (2) не рекурсивна 

 (3) несовершенна 

Номер 2 
Функция f(x,0)=x, f(x,y+1)=f(x,y)+1:

Ответ:

 (1) рекурсивна 

 (2) не рекурсивна 

 (3) линейна 

Номер 3 
Сложение чисел x, y  math реализует рекурсия:

Ответ:

 (1) s(x,0)=x, s(x,y+1)=s(x, y)+1 

 (2) s(x,0)=0, s(x,y+1)=s(x, y)  

 (3) s(x,x)=0, s(x,y)=1 

Упражнение 3:
Номер 1 
Умножение чисел x, y math реализует рекурсия:

Ответ:

 (1) p(x,0)=0, p(x, y)=s(x, y)*x 

 (2) p(x,0)=0, p(x,y+1)=p(x, y)+x 

 (3) p(x,x)=0, p(x,y)=p(y,x) 

Номер 2 
Множество является примитивно рекурсивной, если его характеристическая функция:

Ответ:

 (1) примитивно рекурсивна 

 (2) частично рекурсивна 

 (3) равна нулю 

Номер 3 
Примитивно рекурсивно для примитивно рекурсивных операндов:

Ответ:

 (1) перечисление 

 (2) объединение 

 (3) декартово произведение 

Упражнение 4:
Номер 1 
Примитивно рекурсивно для примитивно рекурсивных операндов:

Ответ:

 (1) дополнение 

 (2) декартово произведение 

 (3) характеристическая функция 

 (4) инверсия 

Номер 2 
Примитивно рекурсивно свойство:

Ответ:

 (1) x=y 

 (2) x2=y2 

 (3) x>y+sin(x) 

Номер 3 
Примитивно рекурсивно свойство:

Ответ:

 (1) x>y 

 (2) math 

 (3) x=x+6 

Упражнение 5:
Номер 1 
Формула х+1 mod n = [if x+1=n then 0 else x+1] :

Ответ:

 (1) прибавляет единицу по модулю n 

 (2) находит остаток от деления x на n 

 (3) округляет x 

Номер 2 
Рекурсия 0 mod n=0, (x+1) mod n=(x mod n)+1 mod n определяет:

Ответ:

 (1) x mod n 

 (2) n mod x 

 (3) НОД(x,y)  

Номер 3 
Если свойство R(x,y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:

Ответ:

 (1) math 

 (2) math 

 (3) math 

Упражнение 6:
Номер 1 
Если свойство R(x, y) - примитивно рекурсивно, то примитивно  рекурсивно и свойство:

Ответ:

 (1) math 

 (2) math 

 (3) math 

Номер 2 
Функция f примитивна рекурсивна, если одновременно выполнено:

Ответ:

 (1) график f примитивно рекурсивен 

 (2) значения f ограничены сверху примитивно рекурсивной функцией g 

 (3) D(f), E(f) - перечислимы 

Номер 3 
Выводящие из класса примитивно рекурсивных функций схемы рекурсии:

Ответ:

 (1) не существует 

 (2) существует 

 (3) не определены 

Упражнение 7:
Номер 1 
Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное время:

Ответ:

 (1) примитивно рекурсивна 

 (2) возвратно рекурсивна 

 (3) Тьюрингова 

Номер 2 
Функции, вычисляемые программой с полным ветвлением и циклом "для", но без циклов "пока":

Ответ:

 (1) примитивно рекурсивны 

 (2) не примитивно рекурсивны 

 (3) просты 

Номер 3 
Частично рекурсивны функции, получаемые из базисных с помощью:

Ответ:

 (1) подстановки 

 (2) примитивной рекурсии 

 (3) итерации 

Упражнение 8:
Номер 1 
Частично рекурсивны функции получаемые из базисных с помощью:

Ответ:

 (1) минимизации 

 (2) характеристической 

 (3) суперпозиции 

Номер 2 
Частично рекурсивная и всюду определенная функция называется:

Ответ:

 (1) общерекурсивной 

 (2) определенно рекурсивной 

 (3) совершенно рекурсивной 

 (4) эквивалентностью 

Номер 3 
Всякая частично рекурсивная функция:

Ответ:

 (1) вычислима на машине Тьюринга 

 (2) представима в виде f(x)=xf(x - 1)  

 (3) регулярна 



Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 11