игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Введение в схемы, автоматы и алгоритмы / Тест 3

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

Упражнение 1:
Номер 1 

files
Какую булеву функцию реализует эта диаграмма?
(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)

Ответ:

 (1) (00011101) 

 (2) (01010101) 

 (3) (01011001) 

 (4) (01010001) 

 (5) (01011101) 

Номер 2 

files
Какую булеву функцию реализует эта диаграмма?
(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)

Ответ:

 (1) (01010111) 

 (2) (01010101) 

 (3) (01011011) 

 (4) (01010011) 

 (5) (01011101) 

Номер 3 

files
Какую булеву функцию реализует эта диаграмма?
(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)

Ответ:

 (1) (01011101) 

 (2) (01010111) 

 (3) (01011011) 

 (4) (01000111) 

 (5) (01011101) 

Упражнение 2:
Номер 1 

files
Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Ответ:

 (1) (X1 ∧ X3) ∨ (X2 ∧¬X3) 

 (2) (X1 ∧ ¬X2 ∧ X3) ∨ (X2 ∧ X3)) 

 (3) (X1 ∨ X2) ∧(X2 ∧X3) 

 (4) (X1 ∧ X3) ∨ (X2∧ X3) 

 (5) ¬X2 ∧ X3  

 (6) (X1 ∧ X3) ∨ (¬X1 ∧¬X2 ∧ X3) 

Номер 2 
files
Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Ответ:

 (1) (X1 ∧ X3) ∨ (X2 ∧¬X3) 

 (2) (X1 ∧ ¬X2 ∧ X3) ∨ (X2 ∧ X3)) 

 (3) (X1 ∨ X2) ∧(X2 ∧X3) 

 (4) (X1 ∧ X3) ∨ (X2∧ X3) 

 (5) X2 ∧ ¬X3  

 (6) (X2 ∧ ¬X3) ∨ (X1 ∧¬X2 ∧ X3) 

Номер 3 

files
Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Ответ:

 (1) (X1 ∧ X3) ∨ (¬X2 ∧¬X3) 

 (2) (X1 ∧ ¬X2 ∧ X3) ∨ (X2 ∧ X3)) 

 (3) (X1 ∨ X2) ∧(¬X2 ∧¬X3) 

 (4) (X1 ∧ X3) ∨ (X2∧ X3) 

 (5) (¬X2 ∧ ¬X3 ) ∨ (X1 ∧ X2 ∧ X3) 

 (6) (¬X2 ∧ X3) ∨ (¬X1 ∧¬X2 ∧ ¬X3) 

Упражнение 3:
Номер 1 
 
Какие из следующих УБДР являются сокращенными? 

files

Ответ:

 (1) только D1 

 (2) только D2 

 (3) только D3 

 (4) D1 и D2 

 (5) D2 и D3 

 (6) D1 и D3 

 (7) все 

Номер 2 
 
Какие из следующих УБДР являются сокращенными? 

files

Ответ:

 (1) только D1 

 (2) только D2 

 (3) только D3 

 (4) D1 и D2 

 (5) D2 и D3 

 (6) D1 и D3 

 (7) все 

Номер 3 
 
Какие из следующих УБДР являются сокращенными? 
files

Ответ:

 (1) только D1 

 (2) только D2 

 (3) только D3 

 (4) D1 и D2 

 (5) D2 и D3 

 (6) D1 и D3 

 (7) все 

Упражнение 4:
Номер 1 

Пусть задана УБДР D=(V,E): V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), v9(w), 0, 1} (в скобках после имени вершины указана переменная, которой она помечена),
E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 1), (v2, v5; 0), (v3, v4; 1), (v3, v6; 0), (v4, v7; 1), 
(v4, v8; 0), (v5, v8; 1), (v5, v9; 0), (v6, v8; 1), (v6, v9; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), 
(v8, 1; 1), (v9, 0; 0), (v9, 1; 1) } ( для каждого ребра третий параметр после ; - его метка 0 или 1).
Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.

Ответ:

 (1) 1 

 (2) 3 

 (3) 4 

 (4) 5 

 (5) 6 

Номер 2 
 Пусть задана УБДР 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) 1 

 (2) 3 

 (3) 4 

 (4) 5 

 (5) 6 

Номер 3 
 Пусть задана УБДР 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; 1), (v8, 1; 0)} ( для каждого ребра третий параметр после ; - его метка 0 или 1).
Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.

Ответ:

 (1) 1 

 (2) 3 

 (3) 4 

 (4) 5 

 (5) 6 

Упражнение 5:
Номер 1 
 Постройте минимальные УБДР для функции
f(x1, x2, x3, x4)= (x1 ∧ x2) +( x3 ∧ x4)
относительно двух упорядочений переменных:

  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
    • 
Определите сложности этих двух схем.

    Ответ:

     (1) (a) - 7, (b) - 8 

     (2) (a) - 6, (b) - 6 

     (3) (a) - 5, (b) - 6 

     (4) (a) - 6, (b) - 7 

     (5) (a) - 7, (b) - 7 

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

  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
    • 
Определите сложности этих двух схем.

    Ответ:

     (1) (a) - 5, (b) - 6 

     (2) (a) - 4, (b) - 6 

     (3) (a) - 4, (b) - 5 

     (4) (a) - 6, (b) - 6 

     (5) (a) - 6, (b) - 7 

    Номер 3 
     Постройте минимальные УБДР для функции
f(x1, x2, x3, x4)= (x1 ∨ x2) + ( x3 ∨ x4)
относительно двух упорядочений переменных:

  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
    • 
Определите сложности этих двух схем.

    Ответ:

     (1) (a) - 6, (b) - 7 

     (2) (a) - 6, (b) - 6 

     (3) (a) - 5, (b) - 6 

     (4) (a) - 5, (b) - 7 

     (5) (a) - 7, (b) - 7 

    Упражнение 6:
    Номер 1 
    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

    Ответ:

     (1) 10 

     (2) 8 

     (3) 9 

     (4) 11 

     (5) 7 

    Номер 2 
    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

    Ответ:

     (1) 10 

     (2) 8 

     (3) 9 

     (4) 11 

     (5) 7 

    Номер 3 
    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

    Ответ:

     (1) 10 

     (2) 8 

     (3) 9 

     (4) 7 

     (5) 6 



    Главная / Алгоритмы и дискретные структуры / Введение в схемы, автоматы и алгоритмы / Тест 3