Главная / Алгоритмы и дискретные структуры /
Введение в схемы, автоматы и алгоритмы / Тест 8
Введение в схемы, автоматы и алгоритмы - тест 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 ]]
?
Ответ:
 (1) 2x12 + 2x22 +x1
 
 (2) 3x12 + 2x22 +x2
 
 (3) 2x12 x2 + 2x22
 
 (4) 3x12 + 2x22
 
 (5) ни одну из выше перечисленных 
Номер 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]
?
Ответ:
 (1) 6x12 + 2x22 x1+x2
 
 (2) 2x12 x2+ 4x22 +x2
 
 (3) 2x12 x2 (2x2 +1) +x2
 
 (4) 4x12 x22+ 4 x12 x2+x2
 
 (5) ни одну из выше перечисленных 
Номер 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 ]]
?
Ответ:
 (1) 2x1 - 4x2 -2
 
 (2) 2x1 x2 - 4x2 -2
 
 (3) 4x12 - 4x2 -1
 
 (4) 2x1 - 2x2 -2
 
 (5) ни одну из выше перечисленных 
Упражнение 2:
Номер 1
Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x2 + x
?
Ответ:
 (1) R( 0, [+; [s1 ; [+; I21, I21]], I22 ])
 
 (2) R( 0, [+; [+; [s1 ; I21], [s1 ; I21]], I22 ])
 
 (3) R( 0, [+; [+; [s1 ; I21], I21], I22 ])
 
 (4) R( 0, [+; [+;[+; [s1 ; I21], [s1 ; I21]], [+;I21, I21]], [+;I22 , I22]])
 
 (5) ни одно из выше перечисленных 
Номер 2
Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x2
?
Ответ:
 (1) R( 0, [+; [s1 ; [+; I21, I21]], I22 ])
 
 (2) R( 0, [+; [+; [s1 ; I21], [s1 ; I21]], I22 ])
 
 (3) [s1 ; R( 0, [+; [+; [s1 ; I21], I21], I22 ])]
 
 (4) R( 0, [+; [+;[+; [s1 ; I21], [s1 ; I21]], [+;I21, I21]], [+;I22 , I22]])
 
 (5) ни одно из выше перечисленных 
Номер 3
Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2
?
Ответ:
 (1) R( 1, [+; [s1 ;[ s1 ;[ s1 ;[+; I21, I21]]]], I22 ])
 
 (2) R( 1, [+; [+; [s1 ; I21], [s1 ; I21]], I22 ])
 
 (3) [s1 ; R( 0, [+; [+; [s1 ; I21], I21], I22 ])]
 
 (4) R( 1, [+; [+;[+; [s1 ; I21], [s1 ; I21]], [+;I21, I21]], [+;I22 , I22]])
 
 (5) ни одно из выше перечисленных 
Упражнение 3:
Номер 1
Обозначим через minus(x,y)
функцию "усеченного" вычитания,
равную (x – y)
при x ≥ y и 0
– в противном случае. Для какой из следующих функций f(x,y)
выражение μy [ f(x,y)= 0]
задает функцию (целая часть квадратного корня из x
) ?
Ответ:
 (1) f(x,y) = minus(y2, x)
 
 (2) f(x,y) = minus(x,y2)
 
 (3) f(x,y) = minus((x+1),y2)
 
 (4) f(x,y) = minus((x+1),(y+1)2)
 
 (5) f(x,y) = minus(x,(y+1)2)
 
Номер 2
Обозначим через minus(x,y)
функцию "усеченного" вычитания,
равную (x – y)
при x ≥ y
и 0
– в противном случае. Для какой из следующих функций f(x,y)
выражение μy [ f(x,y)= 0]
задает функцию F(x) = [ log2 (x+1) ]
(целая часть двоичного логарифма x+1
) ?
Ответ:
 (1) f(x,y) = minus(2y, x+1)
 
 (2) f(x,y) = minus(x+2, 2(y+1))
 
 (3) f(x,y) = minus(x+2, 2y)
 
 (4) f(x,y) = minus(x+1, 2y)
 
 (5) f(x,y) = minus(x+1, 2(y+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) ?
Ответ:
 (1) f(x,y) = minus(y, ix)
 
 (2) f(x,y) = minus(y+1, i(x+1))
 
 (3) f(x,y) = minus(y, (i+1)x)
 
 (4) f(x,y) = minus(y+1, ix)
 
 (5) f(x,y) = minus(y+1, (i+1)x)
 
Упражнение 4:
Номер 1
Пусть функция F(x)
задана примитивной рекурсией
R(1, h(y,z)), где h(y,z) = [2z/z2]
Чему равно значение F(5)
?
Ответ:
 (1) 1 
 (2) 2 
 (3) 4 
 (4) 8 
 (5) 3 
 (6) ни одному из выше перечисленных 
Номер 2
Пусть функция F(x)
задана примитивной рекурсией
R(1, h(y,z))
, где h(y,z) = [2z/z]
Чему равно значение F(5)
?
Ответ:
 (1) 1 
 (2) 3 
 (3) 8 
 (4) 4 
 (5) 2 
 (6) ни одному из выше перечисленных 
Номер 3
Пусть функция F(x)
задана примитивной рекурсией
R(1, h(y,z))
, где h(y,z) = [2z+1/z]
Чему равно значение F(3)
?
Ответ:
 (1) 2 
 (2) 16 
 (3) 8 
 (4) 64 
 (5) 32 
 (6) ни одному из выше перечисленных 
Упражнение 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
?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
 (5) ни одно из выше перечисленных 
Номер 2
Пусть функция rm(x, y) = y mod x
равна остатку от деления y
на x
( rm(0,y)=y )
Какое из следующих выражений определяет число dn(x)
различных делителей числа x
, отличных от 1
и самого x
?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
 (5) ни одно из выше перечисленных 
Номер 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
).
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
 (5) ни одно из выше перечисленных 
Упражнение 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
Ответ:
 (1) R( 5, [c2; [c21; I22], [+; [c21; I22], [c22; I22]]) 
 (2) R( 1, [c2; [c22; I22], [+; [c21; I21], [c22; I22]]) 
 (3) R( 2, [c2; [c22; I22], [+; [c21; I21], [c22; I22]]) 
 (4) R( 5, [c2; [c22; I22], [+; [c21; I22], [c22; I22]]) 
 (5) ни одна из выше перечисленных 
Номер 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
.
Ответ:
 (1) R( 9, [c2; [c21; I22], [×; [c21; I22], [c22; I22]]) 
 (2) R( 9, [c2; [c22; I22], [×; [c21; I22], [c22; I22]]) 
 (3) R( 2, [c2; [c22; I22], [×; [c21; I21], [c22; I22]]) 
 (4) R( 2, [c2; [c22; I22], [×; [c21; I21], [c22; I22]]) 
 (5) ни одна из выше перечисленных 
Номер 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
.
Ответ:
 (1) R( 2, [c2; [c21; I22], [+; [c21; I22], [s;[c22; I22]]]) 
 (2) R( 1, [c2; [c22; I22], [+; [c21; I21], [c22; I22]]) 
 (3) R( 2, [c2; [c22; I22], [s; [+; [c21; I22], [c22; I22]]]) 
 (4) R( 1, [c2; [c22; I22], [+; [c21; I22], [s; [c22; I22]]]) 
 (5) ни одна из выше перечисленных