Главная /
Введение в схемы, автоматы и алгоритмы /
Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∧ x2) ∨ ( x3 ∧ x4) относительно двух упорядочений переменных: a) x1 < x2 < x3 < x4 иb) x1 < x3 < x2 < x4. Определите сложности этих двух схем.
Постройте минимальные УБДР для функции
f(x1, x2, x3, x4)= (x1 ∧ x2) ∨ ( x3 ∧ x4)
относительно двух упорядочений переменных:
a) x1 < x2 < x3 < x4
и b) x1 < x3 < x2 < x4
.
Определите сложности этих двух схем.
вопрос
x1 < x2 < x3 < x4
иx1 < x3 < x2 < x4
.Правильный ответ:
(a) - 5, (b) - 6
(a) - 4, (b) - 6
(a) - 4, (b) - 5
(a) - 6, (b) - 6
(a) - 6, (b) - 7
Сложность вопроса
83
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Спасибо за сайт
22 авг 2018
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, [Большая Картинка] Какой из следующих языков распознает автомат A ?
- # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a → 1, 0 a → 2, 0 b → 0, 1 a → 2, 1 b → 1, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a → q1, q1 b → q0, q1 a → q2, q2 b → q1 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную z. Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x произведение x · y? [Большая Картинка]
- # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +2 ? [Большая Картинка]
- # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x2 ?