Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4
Пусть задана УБДР D=(V,E)
: V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1}
(в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0),
(v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)}
( для каждого ребра третий параметр после ; - его метка 0 или 1).
Постройте по D
эквивалентную ей сокращенную УБДР и укажите ее сложность.
вопрос
Правильный ответ:
1
3
4
5
6
Сложность вопроса
35
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Какой студент ищет данные вопросы inuit? Это же очень простые ответы
05 июл 2017
Аноним
Если бы не эти подсказки - я бы не справился c этими тестами интуит.
25 мар 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = (a ∧ b ∧ с) ∨ (¬b ∧ (b∨ c)) ? [Большая Картинка]
- # Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∧ x2) ∨ ( x3 ∧ x4) относительно двух упорядочений переменных: a) x1 < x2 < x3 < x4 иb) x1 < x3 < x2 < x4. Определите сложности этих двух схем.
- # Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 → q, q 1 → s, q 1→ p, p 0 → q, p 0 → p, s 0 → q, s 1 → p Какие из следующих трех ДКА эквивалентны M? M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F1={p, ps, pq, pqs }, Φ1> с программой Φ1: q 0 → q, q 1 → ps, p 0 → pq, p 1 → ∅, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → p, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅ M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F2={ p, ps, pq, pqs }, Φ2> с программой Φ2: q 0 → q, q 1 → ps, p 0 → pq, p 1 → q, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅ M3 = < {0, 1}, {q, p, ps, pq, ∅ }, q, F3={ ps, pq, p }, Φ3> с программой Φ3: q 0 → q, q 1 → ps, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, p 0 → pq, p 1 → ∅, ∅ 0 →∅, ∅ 1 →∅
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? 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 все
- # Пусть машина Тьюринга 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 = 4, x2 = 8 и при x1 = 1, x2 = 5, соответственно?