Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результа
Пусть П×
- это программа, которая вычисляет функцию Ф× (x,y) = x·y
в переменной x
, используя две рабочих переменных z
и i
Какие из следующих структурированных программ П1
, П2
, П3
вычисляют в переменной x целую часть частного [ x/y]
(пусть при y=0
результат равен 0
)?
вопрос
Правильный ответ:
только
П1
только
П2
только
П3
П1
и П2
П1
и П3
П2
и П3
все
Сложность вопроса
69
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Какой человек ищет эти ответы с интуитом? Это же очень просты вопросы
02 фев 2020
Аноним
Зачёт защитил. Лечу пить отмечать 4 за тест интуит
30 мар 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В теореме 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 (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: V = X ∧ V; f = ¬Y; Y = ¬Y; V = ¬V; g = ¬Z; Z = ¬Z; Y = ¬Y; e = X ∧ V; Z = Y ∧Z; Z = ¬Z; k = ¬e; Z = Z ∧V; Y = Y ∧ Z; h = f ∧ g; V = X ∧ V; Z = Y ∧ V; i = h ∧ V; V = ¬V; Z = V ∨ Z . Z = h ∨ k. Z = Z ∧ V.
- # Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∧ x2) ∨ ( x3 ∧ x4) относительно двух упорядочений переменных: a) x1 < x2 < x3 < x4 иb) x1 < x3 < x2 < x4. Определите сложности этих двух схем.
- # Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {S}, ΦA > с программой ΦA: { Q a → R, Q b → P, P b → P, P a → R, R a → Q, R b → S, S a → R, S b → S} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = bab, h(1) = aba, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)? С1 = < {0, 1}, { Q, P, R, S }, 0, F1={S}, Φ1>, С2 = < {0, 1}, { Q, R, S }, 0, F2={ S }, Φ2>, С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ S }, Φ3>, где программы заданы в следующих таблицах. [Большая Картинка]
- # Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧k w или w∧k q ∧ (k > 0) переведут в конфигурацию q'w ? (В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l1, r1 , l2 , r2, l3, r3, l4) P1: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 a→ l2 a Л, l2 ∧→ q'∧ П, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н. P2: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 ∧→ l2∧ П, l2 *→ l3∧ Л, l3 ∧→ l3∧ Л, l3 a→ q'a Н, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н. P3: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 ∧→ l2∧ П, l2 *→ l3∧ Л, l3 ∧→ l3∧ Л, l3 a→ l4 a Л, l4 a→ l4 a Л, l4 ∧→ q'∧ П, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н.