Главная / Алгоритмы и дискретные структуры /
Основы дискретной математики / Тест 6
Основы дискретной математики - тест 6
Упражнение 1:
Номер 1
Пусть задана система H-формул
F={ (X∧ Y∧ Z) → U, (V∧ Z)→X, (V∧ Z)→Y, (U∧ W)→ V, (U∧X)→ W }
.
Какие из следующих H-формул являются следствиями системы F
?
A) (V∧ Z)→ W
B) (X∧ Y∧ Z) → V
C) (X∧ Y∧ Z) → W
Ответ:
 (1) только A
 
 (2) только B
 
 (3) только C
 
 (4) A
и B
 
 (5) A
и C
 
 (6) все 
Номер 2
Пусть задана система H-формул
F={ (X∧ Y) → Z , (V∧ Z)→X, (V∧ Z)→Y, (Z ∧V)→ U, (U∧X)→ W }.
Какие из следующих H-формул являются следствиями системы F
?
A) (V∧ Z)→ W
, B) (X∧ Y) → W
, C) (X∧ Y∧ Z) → W
Ответ:
 (1) только A
 
 (2) только B
 
 (3) только C
 
 (4) A
и B
 
 (5) A
и C
 
 (6) все 
Номер 3
Пусть задана система H-формул
F={ (X∧ Y∧ Z) → U, V→X, (V∧ Z)→Y, (U∧V)→W, W→ T, (U∧X)→V}
.
Какие из следующих H-формул являются следствиями системы F
?
A) (V∧ Z)→ W
, B) (X∧ Y∧ Z) → W
, C) (X∧ U ∧ Z) → T
Ответ:
 (1) только A
 
 (2) только B
 
 (3) только C
 
 (4) A
и B
 
 (5) A
и C
 
 (6) все 
Упражнение 2:
Номер 1
Используя алгоритм ЗАМЫКАНИЕ(X,F)
, вычислить замыкание Cl(X,F)
набора исходных продуктов X = { b,f }
с помощью следующей системы технологических процессов F
:
a,b,c → d;
b,c,d → a;
g,b → e;
e,f → c;
f,e →d;
b,f → g.
Ответ:
 (1) {b, f, g, e}
 
 (2) {b, f, g, e, c}
 
 (3) {a, b, f, g, e, c}
 
 (4) {a, b, f, g, e, c,d}
 
 (5) {a, g, e, c,d}
 
Номер 2
Используя алгоритм ЗАМЫКАНИЕ(X,F)
, вычислить замыкание Cl(X,F)
набора исходных продуктов X = { e, f }
с помощью следующей системы технологических процессов F
:
a,b,c → d;
c, f → b ;
g,b → k;
e,f → c;
a,f,e → d;
b,f → g.
Ответ:
 (1) {b, f, g, e}
 
 (2) {b, f, g, e, c}
 
 (3) { b, f, g, e, c, k}
 
 (4) {a, b, f, g, e, c,d, k}
 
 (5) { b, c, g, k}
 
Номер 3
Используя алгоритм ЗАМЫКАНИЕ(X,F)
, вычислить замыкание Cl(X,F)
набора исходных продуктов X = {b, c, f }
с помощью следующей системы технологических процессов F
:
a ,b, c → h;
e, d → a ;
g ,b → e;
e, f → c;
c, f → d;
b, f → g.
Ответ:
 (1) {b, c, f, g, e}
 
 (2) {b, c, d, f, g, e}
 
 (3) {a, b, c , d, f, g, e }
 
 (4) {a, b, c, d, e, f, g, h}
 
 (5) {a, d, e, g, h}
 
Упражнение 3:
Номер 1
Каковы будут структуры данных СЧЕТ
и СПИСОК
после этапа инициализации алгоритма БыстроеЗамыкание
для следующей системы технологических процессов F
:
a ,b, c → d ;
b, d → a ;
c,b → a;
a,d → b;
a,b,d → c;
b → a
.
A: B: C:
СЧЕТ = [3, 3, 3, 2, 1, 2] СЧЕТ = [ 2, 3, 3, 2, 1, 2] СЧЕТ = [3, 2, 3, 2, 1, 2]
СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1, 2, 3, 4,5,6)
СПИСОК[b] = (2, 3, 6) CПИСОК[b] = (2, 3, 6) СПИСОК[b] = (1, 2, 3, 4, 6)
СПИСОК[c] = (1,3, 4) СПИСОК[c] = (1,3,4) СПИСОК[c] = (1,2,3,4,5)
СПИСОК[d] = (1, 2, 3, 6) СПИСОК[d] = (1,2,5,6) СПИСОК[d] = (1,2,3,6)
Ответ:
 (1) A
 
 (2) B
 
 (3) C
 
 (4) все ошибочны 
Номер 2
Каковы будут структуры данных СЧЕТ
и СПИСОК
после этапа инициализации алгоритма БыстроеЗамыкание
для следующей системы технологических процессов F
:
a, c → d ;
a, b, d → c ;
c,b → a;
a,c → b;
a,d → c;
b,d → a
.
A: B: C:
СЧЕТ = [2, 3, 2, 2, 2, 2] СЧЕТ = [ 2, 3, 2, 2, 2, 2] СЧЕТ = [2,3, 2, 2, 2, 2]
СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1,2,3, 4,5,6)
СПИСОК[b] = (2, 3, 6) CПИСОК[b] = (2, 3, 6) СПИСОК[b] = (2, 3,4, 6)
СПИСОК[c] = (1,3, 4) СПИСОК[c] = (1,3,4) СПИСОК[c] = (1,2,3,4,5)
СПИСОК[d] = (1, 2,5,6) СПИСОК[d] = (2,5,6) СПИСОК[d] = (1,2,5,6)
Ответ:
 (1) A
 
 (2) B
 
 (3) C
 
 (4) все ошибочны 
Номер 3
Каковы будут структуры данных СЧЕТ
и СПИСОК
после этапа инициализации алгоритма БыстроеЗамыкание
для следующей системы технологических процессов F
:
a, c, d → b
;a, b, d → c
;c,b,d → a
;a,c → b
;a → c
;b,d → a
.
A: B: C:
СЧЕТ = [3, 2, 2, 2, 3,1] СЧЕТ = [3, 2, 2, 2, 2,1] СЧЕТ = [3, 2, 2, 2, 3,1]
СПИСОК[a] = (1,2, 3, 4,5) СПИСОК[a] = (1,4,5) СПИСОК[a] = (1,4,5)
СПИСОК[b] = (1, 2, 3, 4, 5,6) CПИСОК[b] = (1, 2, 3, 5) СПИСОК[b] = (1, 2, 3, 5,6)
СПИСОК[c] = (1,3,5) СПИСОК[c] = (1,3) СПИСОК[c] = (1,3)
СПИСОК[d] = (1,2,4,5) СПИСОК[d] = (2,4,5) СПИСОК[d] = (2,4,5)
Ответ:
 (1) A
 
 (2) B
 
 (3) C
 
 (4) все ошибочны 
Упражнение 4:
Номер 1
Используя алгоритм БыстроеЗамыкание
, вычислить замыкание
для набора исходных продуктов X = { c,d}
и следующей системы технологических процессов F
:
a, b, d → h
;a, c, d, g → f
; d, g → b
; e, f → c
;b, k → a
;d, c → k
;h, d, c → b
;h, d → g
;c, d, k → h
.
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению a
.
Ответ:
 (1) 2 
 (2) 3 
 (3) 4 
 (4) 5 
 (5) 6 
 (6) получить a
нельзя 
Номер 2
Используя алгоритм БыстроеЗамыкание
, вычислить замыкание
для набора исходных продуктов X = {a,b}
и следующей системы технологических процессов F
:
a, b → h
; a, b, c, g → f
; a, g → c
; e, f → c
; b, k → d
; a, h → k
; h, d, c → e
;h, b → g
; d, k → c
.
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e
.
Ответ:
 (1) 2 
 (2) 3 
 (3) 4 
 (4) 5 
 (5) 6 
 (6) получить e
нельзя 
Номер 3
Используя алгоритм БыстроеЗамыкание
, вычислить замыкание
для набора исходных продуктов X = {c, d}
и следующей системы технологических процессов F
:
a, b → h
; a, b, c, g → f
; d, g → a
; . d, f → k
; b, k → d
;c, f, k → h
;h, d, c → e
;c, d → g
;c, d → f
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e
.
Ответ:
 (1) 2 
 (2) 3 
 (3) 4 
 (4) 5 
 (5) 6 
 (6) получить e
нельзя