Введение в схемы, автоматы и алгоритмы - тест 8

Упражнение 1:

---

Номер 1

Пусть заданы три функции:
f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2
Какую функцию F(x1,x2) задает выражение
[f;[g;I21, I21], I21 , [h; I22 ]] ?

Ответ:

---

Номер 2

Пусть заданы три функции:
f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2
Какую функцию F(x1,x2) задает выражение
[f; [h; I21 ] [g; [h; I22 ], I22], I22] ?

Ответ:

---

Номер 3

Пусть заданы три функции:
f(x,y,z) = xy +z, g(x,y) = 2x - y, h(x) =2x2
Какую функцию F(x1,x2) задает выражение
[g; [f; I22 , I22 , I21 ], [h;[s1; I22 ]] ?

Ответ:

---

Упражнение 2:

---

Номер 1

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x2  + x?

Ответ:

---

Номер 2

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x2 ?

Ответ:

---

Номер 3

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2 ?

Ответ:

---

Упражнение 3:

---

Номер 1

Обозначим через minus(x,y) функцию "усеченного" вычитания,
равную  (x – y)  при x ≥ y  и  0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0]  задает  функцию    (целая часть квадратного корня из x) ?

Ответ:

---

Номер 2

Обозначим через minus(x,y) функцию "усеченного" вычитания,
равную  (x – y)  при x ≥ y  и  0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0]  задает  функцию  F(x) = [ log2 (x+1) ]  (целая часть двоичного логарифма x+1) ?

Ответ:

---

Номер 3

Обозначим через minus(x,y) функцию "усеченного" вычитания,
равную  (x – y)  при x ≥ y  и  0 – в противном случае. Для какой из следующих функций f(x,y, i) выражение μi [ f(x,y,i)= 0]  задает  функцию  F(x,y) = [ y/x ]  (целая часть частного от деления y на x) ?

Ответ:

---

Упражнение 4:

---

Номер 1

Пусть функция  F(x) задана примитивной рекурсией
R(1, h(y,z)),  где h(y,z) = [2z/z2]Чему равно значение F(5)?

Ответ:

---

Номер 2

Пусть функция  F(x) задана примитивной рекурсией
R(1, h(y,z)),  где h(y,z) = [2z/z]Чему равно значение F(5)?

Ответ:

---

Номер 3

Пусть функция  F(x) задана примитивной рекурсией
R(1, h(y,z)),  где h(y,z) = [2z+1/z]Чему равно значение F(3)?

Ответ:

---

Упражнение 5:

---

Номер 1

Пусть функция  rm(x, y) = y mod x  равна остатку от деления y на x  ( rm(0,y)=y), а функция p(n) принимает значение 1, если число  n простое, и равна 0 для составных n  (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа  x?

Ответ:

---

Номер 2

Пусть функция  rm(x, y) = y mod x  равна остатку от деления y на x  ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа  x,  отличных от 1 и самого x?

Ответ:

---

Номер 3

Пусть функция  rm(x, y) = y mod x  равна остатку от деления y на x  ( rm(0,y)=y), а функция p(n) принимает значение 1, если число  n простое, и равна 0 для составных n  (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет при x >1 число mp(x), равное произведению  различных простых делителей числа  x? Например, mp(2)=mp(4)=mp(8) =2, mp(12)=2x3=6, … (Пусть mp(0)=mp(1)=1).

Ответ:

---

Упражнение 6:

---

Номер 1

Пусть c2(x, y) = 2x(2y+1) -1  - это функция нумерации пар, а 
c21(z) и c22(z)   - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех  z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и  yРассмотрим функцию F(x), заданную равенствами:
F(0) = 1, F(1) = 1, F(y+2) = F(y) + F(y+1) . Положим  G(y) = c2(F(y), F(y+1))Так как
F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность GОпределите, какая из следующих примитивных рекурсий задает G

Ответ:

---

Номер 2

Пусть c2(x, y) = 2x(2y+1) -1  - это функция нумерации пар, а 
c21(z) и c22(z)   - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех  z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и  y.  Рассмотрим функцию F(x), заданную равенствами:
F(0) = 1, F(1) = 2, F(y+2) = F(y) × F(y+1). Положим  G(y) = c2(F(y), F(y+1)).  Так как
F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.

Ответ:

---

Номер 3

Пусть c2(x, y) = 2x(2y+1) -1  - это функция нумерации пар, а 
c21(z) и c22(z)   - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех  z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и  y.  Рассмотрим функцию F(x), заданную равенствами:
F(0) = 0, F(1) = 1, F(y+2) = F(y) + F(y+1) +1. Положим  G(y) = c2(F(y), F(y+1)).  Так как
F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.

Ответ:

---