Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть множество A = { (x2, y2) | x ∈ N , y ∈ N }, B = { n3 | n ∈ N }. Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(x) обозначает целую часть квадратного корня из x, sg(0) =0 и sg(n) = 1 при n > 0).
Пусть множество A = { (x2, y2) | x ∈ N , y ∈ N }, B = { n3 | n ∈ N }
.
Какие из следующих функций осуществляют сведение A ≤m B
?
(В выражениях ниже sqr(x)
обозначает целую часть квадратного корня из x, sg(0) =0
и
sg(n) = 1
при n > 0
).
вопрос
Правильный ответ:
f(x,y) = x3y3
f(x,y) = (x+2)3 + sg( x2 – sqr(x)2 ) + sg( y2 – sqr(y)2 )
f(x,y) = 8 + sg( x2 – sqr(x)2 + y2 –sqr(y)2 )
f(x,y) = sqr(x)3 sqr(y)3
f(x,y) = (sqr(x) + sqr(y))3
Сложность вопроса
79
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Гранд мерси за ответы по intiut'у.
11 июн 2017
Аноним
Кто находит данные вопросы с интуитом? Это же изи
20 дек 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabbabab, V= babbbabba, U= ababaaab
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конецP2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конецP3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все
- # Пусть структурированная программа P: x:= y+1; z := x+1; x := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии σ : σ(x) =3, σ(y) =5, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?
- # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +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) = 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