Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть структурированная программа P: x:= y+1; y := u+1; v := z+1; если x < v то если x = y то z := y+1 иначе z := x конец иначе z :=x +1 конец начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1
Пусть структурированная программа
P:
x:= y+1; y := u+1; v := z+1;
если x < v то
если x = y то
z := y+1
иначе z := x
конец
иначе z :=x +1
конец
начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?
вопрос
Правильный ответ:
σ1(x) = 4, σ1(y) = 5, σ1(z) = 6, σ(u) = 4, σ(v) =6 σ1(x) = 4, σ1(y) = 5, σ1(z) = 5, σ(u) = 4, σ(v) =6 σ1(x) = 4, σ1(y) = 5, σ1(z) = 4, σ(u) = 4, σ(v) =6 σ1(x) = 4, σ1(y) = 5, σ1(z) = 4, σ(u) = 4, σ(v) = 5
ни в одном из вышеуказанных
Сложность вопроса
93
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Если бы не эти ответы - я бы не осилил c этими тестами интуит.
24 мар 2020
Аноним
Экзамен сдал на 4 с минусом.!!!
15 ноя 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе бесконечности множества ее результатов: Minf = {n | множество значений ФПn,y (x) бесконечно}. Какие из следующих функций сводят Mh0 к Minf ? f1(n) = номер программы: ' x:= 0; Пn ; y:= x '. f2(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn '. (здесь переменная xn не входит в Пn )f3(n) = номер программы: 'y:= x; x:= 0; Пn ; y:= y+1'.
- # Пусть задана логическая схема 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)
- # Какие из следующих УБДР являются сокращенными? [Большая Картинка]
- # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x2 ?
- # Пусть 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