Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.
(a) x := x+1, (b) x := 0, (c) x := y.
Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.(a) если x < y то P1 иначе P2 конец,(b) если x = y то P1 иначе P2 конец.,(c) x := 0.
Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?P1: x := y+1; z:= x + 1; если x < z то y := z иначе y:=x конецP2: x := y+1; v:= x +1; если x = z то y := v всеP3: x := y+1; u:= z +1; пока u < z +1 делай y := z; u := u+1 все
Пусть
П+ - это построенная в лекции программа, которая вычисляет функцию
Ф+(x,y) = x+y в переменной
x, используя одну рабочую переменную
zКакие из следующих структурированных программ
П1,
П2,
П3 вычисляют в переменной
x ее квадрат
x · x ?
Пусть
П+ - это построенная в лекции программа, которая вычисляет функцию
Ф+(x,y) = x+y в переменной
x, используя одну рабочую переменную
zКакие из следующих структурированных программ
П1,
П2,
П3 вычисляют в переменной
x квадратный трехчлен
p(x)= x2 +2x +2 ?
В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M43 ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})P1: q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П ,P2: : q <a, b, c, | > → q < a, b , c, | > П , s < a , b, |, d > → s < a , b, |, | > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q <a, b, ∧, ∧> → s < a , b, ∧, ∧ > Л , s < a , b, ∧, | > → s < a , b, ∧, ∧ > Л,P3: : q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q <a, b, ∧, | > → q < a, b, ∧, ∧ > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,
В доказательстве теоремы 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, ∧> П.
Пусть
П× - это программа, которая вычисляет функцию
Ф× (x,y) = x·y в переменной
x, используя две рабочих переменных
z и
i Какие из следующих структурированных программ
П1,
П2,
П3 вычисляют в переменной x целую часть частного
[ x/y] (пусть при
y=0 результат равен
0)?
Пусть
П× - это программа, которая вычисляет функцию
Ф× (x,y) = x·y в переменной
x, используя две рабочих переменных
z и
i Какие из следующих структурированных программ
П1,
П2,
П3 вычисляют в переменной
x двоичный логарифм от
x, т.е. функцию
[ log2( x)]?
Пусть
П× - это программа, которая вычисляет функцию
Ф× (x,y) = x·y в переменной
x, используя две рабочих переменных
z и
i Какие из следующих структурированных программ
П1,
П2,
П3 вычисляют в переменной
x квадратный корень из
x, т.е. функцию
[ x 1/2]?