Free Printable ТОИ. Вычислимые функции

1.

Определить результат выражения при x=2, y=4, если схема примитивной рекурсии имеет вид:

f\left(x,0\right)\ =\ S\left(Z\left(x\right)\right)

f\left(x,\ y+1\right)\ =\ Mult\left(Add\left(x,\ S\left(y\right)\right),f\left(x,y\right)\right)

a)

360

b)

720

c)

5040

d)

240

2.

Чему равен двоичный логарифм значения функции $f\left(x\right)\ =\ Power\left(Mult\left(4,x\right),Power\left(x,2\right)\right)$
при x = 4?

a)

128

b)

64

c)

32

d)

$2^{64}$

3.

Схема примитивной рекурсии имеет вид
$P\left(0\right)=1$
$P\left(x+1\right)\ =\ Mult\left(P\left(x\right),Mult\left(Add\left(x,2\right),Add\left(x,2\right)\right)\right)$ Вычислите значения функции P(1), P(2) и P(3).

a)

$P\left(1\right)=4,\ P\left(2\right)=36,P\left(3\right)=576$

b)

$P\left(1\right)=9,P\left(2\right)=144,P\left(3\right)=3600$

c)

$P\left(1\right)=1,P\left(2\right)=4,P\left(3\right)=36$

d)

$P\left(1\right)=9,P\left(2\right)=81,P\left(3\right)=729$

4.

Схема примитивной рекурсии имеет вид:

$P\left(0\right)=0$ $P\left(x+1\right)=Add\left(P\left(x\right),S\left(Add\left(x,x\right)\right)\right)$

Найдите P(7).

a)

49

b)

64

c)

36

d)

42

5.

Представьте функцию, используя операцию суперпозиции.
$f\left(x,y\right)=x^2+5y+1$

a)

$f\left(x,y\right)=S\left(Add\left(Power\left(x,2\right),Mult\left(5,y\right)\right)\right)$

b)

$f\left(x,y\right)=S\left(Add\left(Mult\left(x,x\right),Mult\left(5,y\right)\right)\right)$

c)

$f\left(x,y\right)=S\left(Add\left(Power\left(x,2\right),Mult\left(5,x\right)\right)\right)$

d)

$f\left(x,y\right)=Add\left(Mult\left(x,x\right),S\left(Add\left(5,y\right)\right)\right)$

6.

Определите функцию, вычисляемую схемой примитивной рекурсии.
$P\left(0\right)=1$ $P\left(x+1\right)=Mult\left(P\left(x\right),Mult\left(S\left(x\right),3\right)\right)$

a)

$P\left(n\right)=3\cdot6\cdot9\cdot12\cdot...\cdot\left(3n\right)$

b)

$P\left(n\right)=3\cdot6\cdot9\cdot12\cdot...\cdot\left(3n+3\right)$

c)

$P\left(n\right)=6\cdot9\cdot12\cdot15\cdot...\cdot\left(3n\right)$

d)

$P\left(n\right)=6\cdot9\cdot12\cdot15\cdot...\cdot\left(3n+3\right)$

7.

В каких случаях значение функции, заданной с помощью оператора минимизации, не существует? $f\left(x\right)=\mu_y\left(Power\left(y,3\right)=x\right)$

a)

$f\left(8\right)$

b)

$f\left(1000\right)$

c)

$f\left(510\right)$

d)

$f\left(512\right)$

e)

$f\left(728\right)$

8.

Найти сумму тех значений x из промежутка [0; 100] для которых существуют значения функции f(x), заданной оператором минимизации. $f\left(x\right)=\mu_y\left(Power\left(y,4\right)=x\right)$

a)

98

b)

99

c)

1300

d)

385

9.

Найти значение функции f(x), заданной схемой примитивной рекурсии
$f\left(0\right)=1$

$f\left(x+1\right)=Mult\left(Mult\left(Add\left(2,S\left(x\right)\right),3\right),f\left(x\right)\right)$ при x=3.

a)

1620

b)

540

c)

29160

d)

648

10.

Дана схема примитивной рекурсии:
$f\left(0\right)=0$
$f\left(x+1\right)=Add\left(Power\left(S\left(x\right),S\left(x\right)\right),f\left(x\right)\right)$
Определите 10-е ненулевое слагаемое суммы f(x), вычисляемой данной схемой примитивной рекурсии.

a)

$10^{10}$

b)

$9^9$

c)

$11^{11}$

d)

$12^{12}$

11.

$t\left(x\right)=\mu_y\left(Mult\left(y,y\right)=x\right)$ Рассмотрите действие оператора минимизации. Какую функцию он вычисляет?

a)

$t\left(x\right)\ =\ x^2$

b)

$t\left(x\right)=\frac{x}{2}$

c)

$t\left(x,y\right)=\frac{x}{y^2}$

d)

$t\left(x,y\right)=\frac{y^2}{x}$

e)

$t\left(x\right)=\sqrt{x}$

12.

Дан оператор минимизации $t\left(x\right)=\mu_y\left(Add\left(S\left(y\right),y\right)=x\right)$
Определите, какую функцию он вычисляет?

a)

$t\left(x\right)=2x+1$

b)

$t\left(x\right)=2x-1$

c)

$t\left(x\right)=\frac{x+1}{2}$

d)

$t\left(x\right)=\frac{x}{2}-1$

e)

$t\left(x\right)=\frac{x-1}{2}$

13.

Некоторую функцию можно вычислить используя конечное число операций суперпозиции, примитивной рекурсии и минимизации и следующий набор базовых функций

P = { Z(x), S(x), Iⁿ_m(x₁, x₂,…, x_n), Add(x, y), Mult(x, y) }.

К какому классу ее можно отнести?

a)

примитивно-рекурсивных

b)

общерекурсивных

c)

частично-рекурсивных

d)

частичных

14.

Выберите верные утверждения.Используемые обозначения:
$P_{выч}-\ класс\ вычислимых\ функций$
$P_р-\ класс\ общерекурсивных\ функций$
$P_{чр}-класс\ частично-рекурсивных\ функций$
$P_{пр}-класс\ примитивно-рекурсивных\ функций$

a)

Функции в классе $P_{пр}$ всюду определены.

b)

Класс $P_{пр}$ полностью входит в класс $P_{чр}$

c)

Всюду определенные функции класса $P_{чр}$ образуют класс $P_р$

d)

$P_{выч}=P_{чр}$

15.

$t\left(x\right)=\mu_y\left(Mult\left(y,3\right)=x\right)$ Какова область определения функции t(x), заданной оператором минимизации

a)

целые неотрицательные числа, кратные 3

b)

натуральные числа, кратные 3

c)

натуральные числа, большие 3

d)

натуральные числа, больше либо равные 3

ТОИ. Вычислимые функции

Total questions: 15

Worksheet time: 35mins

Similar Resources on Wayground