Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть машина Тьюринга 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 Больше12 then par#( Пуст, Сум ) else par#( Пуст, Умн ) endif;
Зам(#, *); Выб33.
Какие результаты она получит на входных данных вида |x1 * |x2
при x1 = 3, x2 = 6 и при x1 = 2, x2 = 6
, соответственно?
вопрос
Выбin
– выбирает i
-ый аргумент из n
аргументов: x1*…*xi*…*xn ⇐ xi
,Большеij
- выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn
i
-ый аргумент xi
больше j
-ого аргумента xj
, иначе выдает 1,Правильный ответ:
9 и 8
18 и 12
9 и 12
18 и 8
ни один из предыдущих ответов не подходит
Сложность вопроса
53
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Спасибо за гдз по интуит.
05 май 2018
Аноним
Это очень простой решебник intuit.
15 фев 2018
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q - начальное, а p – заключительное состояние. Какие из следующих программ могут быть использованы в качестве программы для M24 ? (В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |}) P1: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, |, c, ∧> → q <a, ∧ , c, ∧> П , s <∧, ∧, ∧, ∧> → p <∧, ∧ , ∧, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,P2: q <a, |, c, d> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, ∧, c, |> → q <a, ∧ , c, ∧> П , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,P3: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, b, c, ∧> → s <a, ∧ , c, ∧> Л , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П.
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? 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; v:= u+1; пока x < v делай если y < x то y := y+1; u := u+1 иначе x := x +1 конец все начинает работу в состоянии σ : σ(x) =0, σ(y) =2, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1 она завершит свою работу?
- # Пусть структурированная программа P: x:= y+1; v:= u+1; пока x < v делай если y < x то y := y+1 иначе x := x +1; u := u+1 конец все начинает работу в состоянии σ : σ(x) = 2, σ(y) =3, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1она завершит свою работу?
- # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результат равен 0)? [Большая Картинка]