| Date post: | 05-Oct-2015 |
| Category: |
Documents |
| Upload: | duta-alexandru |
| View: | 223 times |
| Download: | 0 times |
BDD
Se consider un sistem cu 6 componente binare Se cere: reprezentarea diagramei de decizie binar (BDD), cunoscnd urmtoarele
trasee minimale T1={A, B} T2={C, D} T3={A, E, F}
A
Datele problemei: T1={A, B} T2={C, D} T3={A, E, F}
Dac A=1, traseele devin: T1={B} T2={C, D} T3={E, F}
Dac A=0, traseele devin: T1={A, B} T2={C, D} T3={A, E, F}
T1 i T3 nu se pot realiza fr A, rmne numai T2: T2={C, D}
Aleg s ncep cu nodul A pentru c apare n mai multe trasee
Dac A e realizat, traseul T1 se va realiza atunci cnd se realizeaz i B
Dac A=1, traseele devin: T1={A, B} T2={C, D} T3={A, E, F}
C
A
Pe partea cu A=0, a rmas un singur traseu ncep cu nodul C:
C=1 traseul T2={C, D} devine T2={D} C=0:
Traseul T2 ={C, D} nu se mai poate realiza, Pt c nu mai exist alte trasee realizabile, rezult starea sistemului trece n zero
C
A
0
Pe partea cu A=0, a rmas un singur traseu ncep cu nodul C:
C=1 traseul T2={C, D} devine T2={D} C=0:
Traseul T2 ={C, D} nu se mai poate realiza, Pt c nu mai exist alte trasee realizabile, rezult starea sistemului trece n zero
C
A
Pe partea cu C=1, a rmas un singur traseu i anume T2 Continui cu nodul D:
D=1: traseul T2={D} se realizeaz, rezult starea sistemului trecee n 1 D=0:
Traseul T2 ={D} nu se mai poate realiza Nu mai exist alte trasee, posibile rezult starea sistemului trece n 0
0 D
0 1
C
A
Pentru partea cu A=0, am epuizat de reprezentat toate traseele Continum pe partea cu A=1: Observm c traseul T1 ={B} se realizeaz odat cu realizarea lui B, aadar se alege ca nod urmtor, nodul B Nodul B:
B=1 traseul T1={B} se realizeaz, rezult starea sistemului trece n 1
B=0: traseul T1 ={B} nu se mai poate realiza Traseele T2 i T3 se pot realiza n continuare i pe ramura B=0
0
D
0 1
C
A
Pentru partea cu A=0, am epuizat de reprezentat toate traseele Continum pe partea cu A=1: Observm c traseul T1 ={B} se realizeaz odat cu realizarea lui B, aadar se alege ca nod urmtor, nodul B Nodul B:
B=1 traseul T1={B} se realizeaz, rezult starea sistemului trece n 1
B=0: traseul T1 ={B} nu se mai poate realiza Traseele T2 i T3 se pot realiza n continuare i pe ramura B=0
0
D
0 1
B
1
C
A
Pt B=0, rmn posibile urmtoarele trasee: T2={C, D} T3={E, F} Aleg nodul E:
E=1 Traseul T3={E, F}, devine T3={F} Traseul T2={C, D} rmne nemodificat
E=0: Traseul T3={E, F} nu se mai poate realiza Traseul T2={C, D} rmne nemodificat
0
D
0 1
B
1
E
C
A
Continum pe ramura E=0: Aleg nodul C:
C=1 Traseul T2={C, D} devine T2={D}
C=0: Traseul T2={C, D} nu se mai poate realiza
0
D
0 1
B
1 E
C
C
A
Continum pe ramura E=0: Aleg nodul C:
C=1 Traseul T2={C, D} devine T2={D}
C=0: Traseul T2={C, D} nu se mai poate realiza Cum nu exista niciun alt traseu posibil, sistemul trece n starea 0
0
D
0 1
B
1 E
C
0
C
A
Continum pe ramura C=1: Aleg nodul D:
D=1 Traseul T2={D} se realizeaz, sistemul trece n starea 1
D=0: Traseul T2={C, D} nu se mai poate realiza Cum nu exista niciun alt traseu posibil, sistemul trece n starea 0
0
D
0 1
B
1 E
C
0 D
0 1
C
A
Continum pe ramura E=1: trasee disponibile: T2={C, D} T3={F} Aleg nodul F:
F=1 Traseul T3={F} se realizeaz, sistemul trece n starea 1 Nu mai are rost reprezantarea traseului T2={C, D} , ntruct sistemul este deja n starea de succes datorit traseului T3
F=0: Traseul T3={E, F} nu se mai poate realiza Traseul T2={C, D} se poate realiza
0
D
0 1
B
1
E
C 0
D
0 1
F
1
C
A
Continum pe ramura F=0: trasee disponibile: T2={C, D} Se realizeaz traseul T2={C, D}, asemeni cazului anterior (E=0)
0 D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
Polinomul P
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
qA*pC*pD=p2*q1
!A C D
Polinomul P
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*pB=p2
A B
Polinomul P
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*pE*pF=p3*q1
A !B E F
Polinomul P
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*pE*qF*pC*pD=p4*q2
A !B E !F C D
Polinomul P
C
A
0 D
0
1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*qE*pC*pD=p3*q2
A !B !E C D
C
A
0 D
0
1
B
1
E
C
0 D
0 1
F
1
C
0 D
0 1
A !B !E C D
A !B E !F C D
A !B E F
A B
!A C D
!A C D A B
A !B E F A !B E !F C D A !B !E C D
P=qA*pC*pD+pA*pB+pA*qB*pE*pF+pA*qB*pE*qF*pC*pD+pA*qB*qE*pC*pD
C
A
0 D
0
1
B
1
E
C
0 D
0 1
F
1
C
0 D
0 1
pA*pB=p2
pA*qB*pE*pF=p3*q1
pA*qB*pE*qF*pC*pD=p4*q2
pA*qB*pE*qF*pC*pD=p4*q2
qA*pC*pD=p2*q1
Psistem =qA*pC*pD + pA*pB + pA*qB*pE*pF + pA*qB*pE*qF*pC*pD + pA*qB*qE*pC*pD
Psistem =p2*q1 + p2 + p3*q1 + p4*q2 + p3*q2
!A C D A B
A !B E F A !B E !F C D A !B !E C D
p2*q1
p2
p3*q1
p4*q2
p3*q2
qA*pC*pD pA*pB
pA*qB*pE*pF pA*qB*pE*qF*pC*pD
pA*qB*qE*pC*pD
De aici scoatem Psistem
l folosim pentru a calcula IBP (la derivare)
Pentru verificare, vom calcula Qsistem i vom verifica relaia Psistem + Qsistem =1
Psistem =p2*q1 + p2 + p3*q1 + p4*q2 + p3*q2
Pentru a rspunde cerinei, n aceast form a lui Psistem nlocuim q=1-p
Psistem =p2*(1-p)1 + p2 + p3*(1-p)1 + p4*(1-p)2 + p3*(1-p)2
Relaii utile: (1-p)2 = p2- 2 * p + 1
(1-p)3 = p3 3 * p + 3 * p2 - 1
Psistem = 2 * p2 + p3 2 * p4 - p5 + p6
Calculnd, rezult:
Putem s facem o prim verificare: pentru p=1 trebuie ca Psistem = 1
Psistem = 2 * 12 + 13 2 * 14 - 15 + 16 = 1
Sau, altfel spus, suma tuturor coeficienilor polinomului Psistem trebuie s fie egal cu 1
Dac aceast condiie nu este ndeplinit, cu
siguran exist o greeal n
determinarea lui Psistem
Polinomul Q
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
qA*qC=q2
!A !C
Polinomul Q
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
qA*pC*qD=p1*q2
!A C !D
Polinomul Q
C
A
0
D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*qE*qC=p1*q3
A !B !E !C
Polinomul Q
C
A
0 D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*qE*pC*qD=p2*q3
A !B !E C !D
Polinomul Q
C
A
0 D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*pE*qF*qC=p2*q3
A !B E !F !C
Polinomul Q
C
A
0 D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
pA*qB*pE*qF*pC*qD=p3*q3
A !B E !F C !D
Polinomul Q
C
A
0 D
0
1 B
1 E
C
0 D
0
1
F
1
C
0 D
0 1
A !B E !F C !D
!A !C
!A C !D
A !B !E !C
A !B !E C !D
A !B E !F C !D
!A !C !A C !D
A !B !E !C A !B !E C !D
A !B E !F C !D A !B E !F C !D
Q=qA*qC+qA*pC*qD+pA*qB*qE*qC+pA*qB*qE*pC*qD+ pA*qB*pE*qF*pC*qD+pA*qB*pE*qF*pC*qD
Q=q2 + p1*q2 + p1*q3 +p2*q3+ p3*q3 + p3*q3
C
A
0 D
0 1
B
1 E
C
0 D
0
1
F
1
C
0
D
0 1
pA*qB*pE*qF*pC*qD=p3*q3
qA*qC=q2
qA*pC*qD=p1*q2
pA*qB*qE*qC=p1*q3
pA*qB*qE*pC*qD=p2*q3
pA*qB*pE*qF*pC*qD=p3*q3
qA*qC qA*pC*qD
pA*qB*qE*qC pA*qB*qE*pC*qD+
pA*qB*pE*qF*pC*qD pA*qB*pE*qF*pC*qD
Polinomul Q
!A !C !A C !D
A !B !E !C A !B !E C !D
A !B E !F C !D A !B E !F C !D
q2 p1*q2 p1*q3 p2*q3 p3*q3 p3*q3
De aici scoatem Qsistem
l folosim pentru a calcula IBP (la derivare)
Q=qA*qC + qA*pC*qD + pA*qB*qE*qC + pA*qB*qE*pC*qD + pA*qB*pE*qF*pC*qD + pA*qB*pE*qF*pC*qD Q=q2 + p1*q2 + p1*q3 + p2*q3+ p3*q3 + p3*q3
T1={A, B} T2={C, D} T3={A, E, F}
C
A
0 D
0 1
B
1 E
C
0 D
0 1
F
1
C
0 D
0 1
