База ответов ИНТУИТ

Введение в схемы, автоматы и алгоритмы

<<- Назад к вопросам

Постройте минимальные УБДР для функцииf(x1, x2, x3, x4)= (x1 ∧ x2) ∨ ( x3 ∧ x4)относительно двух упорядочений переменных:
  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
  • Определите сложности этих двух схем.

    (Отметьте один правильный вариант ответа.)

    Варианты ответа
    (a) - 4, (b) - 5
    (a) - 6, (b) - 7
    (a) - 6, (b) - 6
    (a) - 5, (b) - 6
    (a) - 4, (b) - 6(Верный ответ)
    Похожие вопросы
    Постройте минимальные УБДР для функции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.
  • Определите сложности этих двух схем.
    Пусть задана линейная программа P со входными переменными X1, X2, X3:
  • Y = ¬X1;
  • Z = ¬X2;
  • U = ¬X3;
  • V = X1 ∧ X2;
  • Z = Y ∧ Z;
  • W= Y ∧ X2;
  • Z = Z ∧ W ;
  • V = V ∧ U ;
  • Z = Z ∨ V.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?
    Пусть задана линейная программа P со входными переменными X1, X2, X3:
  • Y = ¬X1;
  • Z = ¬X2;
  • U = ¬X3;
  • Y = Y ∧ X2;
  • W = X2 ∧ X3;
  • Y = Y ∧ U;
  • Y = W ∨ Y ;
  • Z = Z ∨ Y.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?
    Пусть задана линейная программа P со входными переменными X1, X2, X3:
  • Y = X1 ∨ X2;
  • Z = X1 ∨ X3;
  • U = ¬X3;
  • Y = Y ∧ Z;
  • W = X2 ∨ X3;
  • U = X2 ∨ U;
  • Z = W ∨ Y ;
  • Z = U ∧ Y.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?
    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
    В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?
  • P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* )
  • P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )
  • P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )
  • В этих определениях участвуют следующие простые машины Тьюринга:
  • Копa – копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Пуст – не изменяет аргумент: w ⇐ w ;
  • Чист – стирает аргумент: w ⇐ ∧ ;
  • +1 – прибавляет 1 к аргументу: |x ⇐ |x+1
  • В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g2, f4), требовалась м.Т. M1, которая переводит конфигурацию вида |x1*|x2* |y в конфигурацию |y * |x1*|x2* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x1,x2).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?
  • P1 = Коп# ; par# (par* (Чист, Чист,Пуст); Зам(*,∧ ) , par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп* ); par* (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* ))
  • P2 = Коп# ; par# (par* (Чист, Чист , Пуст); Зам(*,∧ ) ; Зам(*,∧ ), par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )
  • P3 = Коп* ; par* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )
  • В этих определениях участвуют следующие простые машины Тьюринга:

  • Копa –копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Пуст - не изменяет аргумент: w ⇐ w ;
  • Чист – стирает аргумент: w ⇐ ∧ ;
  • +1 - прибавляет 1 к аргументу: |x⇐ |x+1