Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть множество A = { (x, y) | y = x2 }, B = { 2n | n ∈ N }. Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 и sg(n) = 1 при n > 0).
Пусть множество A = { (x, y) | y = x2 }, B = { 2n | n ∈ N }.
Какие из следующих функций осуществляют сведение A ≤m B ?
(В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 и
sg(n) = 1 при n > 0).
вопрос
Правильный ответ:
f(x,y) = 2x f(x,y) = 2x+1 + sg( | x2 – sqr(y)2 |) f(x,y) = 4 + sg( | x2 – y |) f(x,y) = 2x + | x2 – y | f(x,y) = 1 + sg(| x2 – y |) Сложность вопроса
83
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Очень сложные тесты
04 авг 2018
Аноним
Экзамен прошёл на зачёт.
01 янв 2016
Аноним
Спасибо за ответы по интуит.
12 ноя 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # [Большая Картинка] Какую булеву функцию реализует эта логическая схема в вершине a ?
- # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { ww | w = b2anb , n > 0 }, L2 = { b2anb | n > 0 }, L3 = { (ab)nanb | n > 0 }.
- # Пусть заданы три функции: 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] ?
- # Пусть функция F(x) задана примитивной рекурсией R(1, h(y,z)), где h(y,z) = [2z+1/z]Чему равно значение F(3)?
- # Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1, с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст ); if Больше21 then par#( Пуст, Умн ) else par#( Пуст, Сум ) endif; Зам(#, *); Выб33. Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 4, x2 = 8 и при x1 = 1, x2 = 5, соответственно?