Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…
Пусть машина Тьюринга 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 = 2, x2 = 7
и при x1 = 3, x2 = 5
, соответственно?
вопрос
Выбin
– выбирает i
-ый аргумент из n
аргументов: x1*…*xi*…*xn ⇐ xi
,Большеij
- выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn
i
-ый аргумент xi
больше j
-ого аргумента xj
, иначе выдает 1,Правильный ответ:
9 и 8
9 и 15
14 и 8
14 и 15
ни один из предыдущих ответов не подходит
Сложность вопроса
68
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Я преподаватель! Тотчас сотрите сайт и ответы с интуит. Пожалуйста
14 апр 2017
Аноним
Это было сложно
22 ноя 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана логическая схема S=(V, E) : V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∨),g(∨),h(∨), i(∧), k(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, d), (a, g), (b, e), (b, f), (b, g), (c, f), (d, h), (e, h), (f,k), (g,i), (h, i), (i, k) }. Какую булеву функцию реализует схема S=(V, E) в вершине k? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)
- # Пусть язык L в алфавите {a, b}, состоит из всех слов, которые начинаются на aa и содержат число символов a кратное 3, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = aaa, h(1) = ba, h(2) = ε Какие из следующих трех слов принадлежат прообразу h-1(L) языка L при гомоморфизме h? W1 = 21112, W2 = 20101012, W3 = 00211011
- # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +2 ? [Большая Картинка]
- # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный корень из x, т.е. функцию [ x 1/2]? [Большая Картинка]
- # Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф: \begin{array}{lll} q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Л q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П \end{array} В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?