tabele de decizie
TRANSCRIPT
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 1/7
B az ele informaticii
e
conomice
3.6.
T,l'nnr,nnEDEcrzm
llxe4l,
[Pov88]
Tabela de decizie este un nou mod de reprezentare
a
unui
algoritn,
permilind
formalizarea
gi
sintetizarea
proceselor
complexe
de
prelucrare
a
datelor
precum
gi
verificarea
corectitudinii 1or.
Tabela
de decizie reprezint6
un instrument
util
de
comunicare
intre
persoanele
care
particip[
la realizarea unui
proiect
de sistem informatic.
Cu
ajutorul
tabelelor de decizie
este
posibild
analiza
proceselor
complexe
de
decizie
qi
evidentierea eventualelor ambiguiteJi.
in
esent[ un
proces
de decizie este determinat de
condilii
qi
acliuni
in rela$e
unele cu altele.
Legarea rmei anumite
situalii,
catacteizatd
prin
realizirile
concrete ale
factorilor
de
influenfl,
de
o
anumiti
variantii
de adoptat
se
va
numi
regzld
penfu
cel ce ia decizia.
Definifia
3.4.
O
tabeld de decizic
(TD)
asociati
unui
proces
de
prelucrare
P
este un tablou
bidimensional
(cu
dubl6
inhare) avind
forma
prezentatl
in figura
J.Z- llnqe:
C,,i
=Sn
sunt condiliile
(situatiile
semnificative) ale
procesului
P;
aieste
condifii
sunt
variabile logice,
fiecare
condilie
C;
putAnd
si
ia v;
(vi
>
2) valori
logice
altemative;
Aj
,
i
=
l,m sunt
acfiunile
posibile
(programele
de ac$uni) ale
procesului
P,
care
se
iau
cend
conditiile
indeplinesc anumite
sisteme de
valori;
Rk,
k
=
W
sunt
regulile
ce
precizeazi
acliunile
ce se execute
pentru
sistemul de valori asociat conditiilor,
Se
noteazi
TD
=
TD
(n,
m;
M.
Se observd cd numirul maxim
posibil
de reguli
distincte
ale
unei tabele de decizie este:
N=
7E
vi
(3.4)
Deoarcce
u>2
+
N>-2".
70
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 2/7
Algoritmi
7l
Conditii
Actiuni
Figura
3.2
In consecinld,
tabela
de decizie
este
o
matrice
de
forma
(n
+
m)
x
M,
pimele
n
linii
reprezentdnd
condiiiile gi
urmdtoarele
m rcprezcntdnd,
acliunile;
cele
M
coloane
ale
matricei
reprezintii
regulile.
Existe
doud
tipuri
de
reguli
de
decizie:AND gi
OR.
Regula
R*
se nume$te
regul[
de
tip
AND
dacl
legltura
dintre
valorile
conditiilor
este:
C11
AND
Czr
AND
... AND
C6
9i
se
numegte
de
tip
OR
dactr
crk
oR c2k
oR
...
oR c"k.
Definifia
3.5.
O
tabelS
de decizie
care
conline
toate regulile
posibile
(M=
fr';
se llrume1te
tabeld
de
decizie
cu intrdri
complete.
in
descrierea
proceselor
de
prelucrare
a informafiilor
tabelele
de
decizie nu
sunt intotdeauna
complete.
De exemplu,
dac6
tabela
are
M
regali,
M
<
l{,
tabela
nu
are
intriri
complete gi
deci nu
este
complete; penfu
a
o transforma
intr-o
tabela
complete
.dg..u
regulilor
care lipsesc
se identifici
cu o noui
reguli (re
gtla
M
+
1)
denwnt|
regula
ELSE,
carc
se
atafeazE
tabelei.
Dacd pentru
regula
ELSE
nu
este
asociati
o
aclinne
atunci
la aceaste
regul[
se
asociazi
acfiunea.E
=
etoare,
Deci,
c6nd
se
conskuiesc
tabele
de decizie,
acestea
trebuie
s[
fie
comnlete:
mrmai
astfel
se
pot
descrie ptocesele
complete
de
prelucrare,
cerinli
ce
se i-p.ute
oricirui
algoriua
de
calcul.
Rl
R2
RM
\-l
c"
Crr
Czt
Cnr
Crz
Czz
C,.2
Intrtui
condilii
Crv
Czu
CnM
A1
/\2
;
Inberi
acfiuni
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 3/7
B azel e infor
n aticii
economice
Definilia
3.6.
Tabela
de
decizie
TD
(n,
m; r11)
se numegte
cl intrdri
limitate
dacd
Vi
eI,n,v7:2.in
acest
caz se
iau
ca intrdri
ale
condiliilor
valorile:
D
(Ci:
TRUE)
9iN(C;=FALSE).
Dacl
existd
i eln
,incet
v,> 2
tabela
se nume$t
e ct
inbdri etinse.
Observafie.
Orice tabeld de
decizie cu
intriri
extinse
este echivalentd
cu
o
anumitd tabeli
de decizie cu
inheri
limitate.
Tabela cu
intriri
limitate
obfinutl prin
transformare
are acelaqi numil
de
reguli
ca
gi
cea inifiali,
dar
un
numdr
de condifii
mult
mai
mare.
REDUCERI,A
TABELEI
DE DECIZIF,
Dacd
mai multe reguli
distincte ale
tabelei
conduc
la
ac,tiuni
identice,
atunci
in
anumite condilii
tabela de
decizie
este
redundantd,
adici
acele reguli
se
pot
reduce
la una singurd.
Sd
presupunem
cl
existi ur reguli
pentru
care
intrdrile
condiliilor
C,,
j
+ i
(
i
fixat)
sunt
identice,
iar
condilia
C;
ia
in
fiecare
reguli
una
din
cele
v;
valori
logice
altemative,
adice inherile
condiliilor in cele
v1
reguli
diferd mrmai
prin
valorile
pe
care
le
ia
condi$a
C1; atunci
cele
v; reguli se reduc
la
o
singuri
reguli
pentru
caxe
condiJia C;
ia
valoarea
convenlionall
"indiferent",
notatd
"-".
Aceaste
opemlie,
efectuati penku
toate
seturile de reguli redondante
se nume$te
operafia
de
reducere
a tabelei de
decizie; iar tabela rezultante
se
nume$te tdrela
redusd.
Delinifia 3.7.
Regula
fu
din tabela
cu
intreri fimitate
se nuneSte
elementard
daciC**"-", Vi
el,n
qi
se
mrmegte
corzp usd
dacd ll
e
p,
incat
C,o:
',-,'.
Observalie.
Daci
regula
compusi
Rp
are
r inhiri
aceasta
conline 2'
reguli
elementare.
Definilia 3.8.
O
tabeli
de
decizie
este ambigud
daci
existd
regulile compuse
Rp
qi
Rl
cu
ft
+
/ incit Rp .\
&
+
4, adici
regulile
compuse
au cel
pulin
o reguld
elementara
comune.
o
Dacd Ro
a
R, +
A,
9i
A2 * A1,
atwrci
Rr
$i
&
sunt
contrailictorii
(cele
dou6
reguli
compuse conlin
rcguli elementare
contradictorii);
r
DacI
Rk a,
Rt
+ A,
gi
A1
:
A1, atwrci
Rp
gi
.R1
srmt
rcdundante
(cele
doui
reguli
compuse
conlin
reguli
elementare redundante).
Exemplu.
Sl
analiz6m tabela de decizie redus6:
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 4/7
Algoritni
73
R7
R6
,
R3 Ra
R:
R6
1
LI
Cz
Cj
c4
t/t/Nnr
N1{DD
ND
DtlD/{
NN
DD
D
-D
N
a2
./42
12
.42
^2
ta2
1
ObservSm
cA
Rl
este
independentl
de toate
celelalte
reguli deoarece
pe
linia
condiliei C1
arem
(D),
iar
toate
celelalte
reguli au
(l[).
Existl
6
perechi
de reguli
dependente:
1)
(Rz,Rr)
conlin
in
comun
regula
elementare
(NDDD);
2)
(Rz,
&)
conlin
in
comun regula
elementarl
(/{DDM);
3)
(Rr,
R)
conlin
in comun
regula
elementarI
(NDDll);
4)
(R3,
R
)
conlin
in comun
regula elementard
(lfDND),
5)
(&,
&)
confin
in
comun
regulile
elementare
(l{XDif)
Ei
(1f1VNN);
6)
(&,
&)
conlin
in
comun
regula
elementarl
(tr'DDtr)
Numdrul
total
de
reguli ce
ar
rezulta
din
cele 4 condilii
este
2a
=
16'
Tabela
conline 23
+
2
+
2
+
22
+
2
+
2
+
|
+
|
=
22 regoli,
din
care
7 sunt
comune,
deci in tabeia
existd
15
reguli
din
16
posibile.
Rezulti
ci:
- tabela
este incomPleti;
-
tabela
este ambigu6;
-
toate
ambiguitlfile
sunt
redundanle'
ALGoRTTMUL
DE
coNsrRUIRx'
A
TABELEI
DE
DECIZIE
cu
INrR.i.Rr
COMPLETE.
Presupunem
ci fiecare
din cele
n condifi,
C;,
|
<
i
<
n, are
vi
altemative;
se
accepte
ordinea
de scriere
pe
verticali
Cr,
Cz, .", C".
Pasul
1.
Se calculeazE
M
:
N
/
v1, cu 1{ dat
de
(3.4).
Se
scrie
pe
linie
in
drephrl condiliei
Cr de Nr ori
fiecare
din
cele
vr valori
logice ale
condiliei;
r€zulte
N
valori
logice
ale
conditiei
Cr,
fiecare
din
valori
repetandu-se
in
gmpe
de Nl.
Pasul
2.
Pentru
i
:
2,3, ...,
n
se calculeaz5
ivi
:
Ni-.. Iv6
pe
linia
lui
Ci
se
vor scrie sub
fiecare
din
grupele
de
valori
constante ale
condiliei
C- r
de ?{i
ori,
fiecare
din
cele
vr valori ale condiliei
Ci'
Se
obsewi
ci
]r',
:
I,
adic6
ultima
condilie
va
avea
repetate de
un numar
de
ori
valorile
sale
in aceea$i
ordine.
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 5/7
74
Bazel e
inform
qt
icii
economice
Notd.
O interesantl
aplicare
a
tabelelor
de
decizie
se
poate
realiza
in
studiul
fi
elaborarea
legislaJiei.
O lege
juridica
se referi
de obicei
la un
anumit
domeniu'
Prevederile
legii
sunt
exprimate
prin
referiri
la materii
(o
materie
poate
fi
interpretata
ca
o
condilie
cu
mai
multe
valori
logice
descrisi
prin
termeni)'
incleplinirea
unui
sistem
de condilii
referitoare
la
materii
conduce
la
o
actiune
juridicd. Deci, o
lege poate
fr
descrisd compact
cu
ajutorul
unei
tabele de
decizie'
Aceast6
tabe16
poate
fi
redusA
-
se va
asigura
astfel
conciziwlea
legii'
Stabilirea
regulilor
redundante
gi
ambigue
conduce
la
stabilirea
corectitudinii
legii; se
pot
astfel
elimina,
in
faza de
elaborare,
eventualele
prevederi
contradictodi
ale legilor.
Penku
a exemplifica
conceptul
de tabelI
de decizie
se
prezint4
doui
aplicalii'
in
care
regulile
de
decizie
vor fi
de tipul
AND.
l.
Sistemul
de
credite
transferabile
(ECTS,)
a
fost introdus
la Facultatea
de
$tiinle
Economice
a
universitllii
"Transilvania"
din
Bragov
incepand
cu anul
universitar
1998-1999.
Prevederile extrase
din
regulament
care
aclioneazi
la
trecerea
din anul
I in
anul II sunt:
a)
inscrierea
in
anul
tr este
condilionati
de oblinerea
a minim
40
p'c';
b)
promovarea
anului
I
este
condilionata
de ob,rmerea
a
60
p'c';
c)
punctele
de
credit
alocate
ciclului
I
(prirnii
2 ani de studiu)
trebuie
obiinute
in
maxim
3
ani,
in caz
contrar
studentul
este
exmatriculat;
d)in
cazul
unui
concediu
medical
mai
mare de 30
de
zile
de
activitate
didacticd
pe
semestru,
prevederea de
la
punctul a)
se
reduce la
30
p.c',
urmdnd
ca
in
anul II
studenhrl
s6-qi
completeze
studiile,
oblindnd
cel
pulin
50
p.c.
pentm
a
promova,
astfel
incAt
perioada de 3 ani
s6 nu fie
dep69it6.
Din analiza
acestor
prevederi,
se deduc
urmitoarele
condilii:
C1
-
numdrul
de
puncte de
credite
oblinute
in
anul
I: <
30,
[30,
40)'
[40,
60)' >
60
(4
valori);
C:
-
dac6
are
concediul
medical
mai
mare
de 30
zile
de activitate
didactici
pe
semestru:
D,
N
(2
valori);
C:
-
dac4
a fost
2 ani in
anul I:
D,
N
(2
valori)'
Acfiunile
sunt:
Ar
-
studentul
este
declarat
promovat
gi
este
inscris in
anul tr;
A2
-
studenhrl
este
inscris
in anul
II;
A:
-
studentr:l
rlm6ne
in
anul
I
(prelungire
de
gcolaritate);
Aa
-
studentul
este
exmatriculat.
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 6/7
Rr R,
&
R4
& &
Rz R3
Re
R1s .R11
R12
R13
Rla
R15
R16
cl
Cz
>60 >60 >60 >60 >40 >40
>40
>40
>30 >30
>30 >30
<30
<30 <30
<30
D D N t/ D D ]/ N D D,I/ N D D N
]/
D N D 1f D N
D,IT D
1T D t/
D N D il
.all
Algoritmi
Tabela de decizie
cu
intrlri
complete
va
avea
16 reguli.
Aplicdnd
algoritrnul
de
construire
a tabelei de decizie
cu intrdri complete,
se obline:
Observalie.
S-au
notat
doui
valori
ale
condiliei
Cr astfel:
[30,
40) cu
">
30"
qi
[40,
60)
cu
"
> 40".
Tabela
redusd
este:
R1
R2
&
D
& &
Rt
Lt
\'2
r-3
>60
>40 >30
>30 >30
<30 <30
DffN
-DNDtl
A1 t72 A2
A3 ra3
2, Algoritmal de
interclasme
a tei
ftgierc
Se
consideri trei fiqiere
secvenfiale
FA, FB, FC,
avand
aceea$i
structure
qi
sortate dupd
valorile unui
camp
cheie
(cheia
de
sortare) K. Sd
se
construiascd
tabela de decizie
asociatd
procesului
de prelucrare
carc
realizruazA
interclasarea
acestor
fl$iere.
in
urma
procesului
de
interclasare
rezultd un
fiqier
FD
avind
inregiskdrile
sortate dupd acelagi
criteriu.
Din
studiul
problemei
rezulta urmAtoarele condilii
(cu
intriri limitate):
C1
-
incepuhrl
procedurii;
C2
-
s-a
terrdnat
fiqierul
FA
(EOF (FA));
C3
-
s-a
terminat
fifierul
FB
(EOF (FB));
Ca
-
s-a terninat
fiqierul
FC
(EOF (FC));
C5
-
cheia inregistrlrii
SA
este mai
mici decit
a
inregisterii
SB
(KA
<
KB);
C6
-
cheia
inregistrhrii
SA
este mai mici
decdt a inregistrerii
SC
(I(A
<
KC);
C7
-
cheia inregistrdrii
SB este mai micd
decdt a inregistrarii SC
(KB
<
KC).
Acliunile sunt:
I
I
-
scrierea
inregisbnrii
SA
in
FD;
t)
7/21/2019 Tabele de Decizie
http://slidepdf.com/reader/full/tabele-de-decizie 7/7
B az ele
informaticii
e
c onomice
lz
-
citirea fiqierului
FA;
13
-
scrierea
iffegistrlrii
SB
in
FD;
lq
-
citirea fi$ierului
FB;
l5
-
scrierea inregisherii
SC
in FD;
16
-
citirea
fiqierului FC;
Ar
-
reluarea
examindrii tabelei;
As
-
incheierea
procedurii.
Algorituul de
interclasare
este
cel
gene€l
$i
constd
in:
Pasul
1.
Cithea
simultani a
celor trei fi;iere.
Pasul 2.
Din tripletul
(SA,
SB,
SC) se alege
inregistrarea cu cea
mai
mici valoare
qi
aceasta
va fi scrisd
in
fiqierul rezultat
FD.
Pasul
3. Tripletul
este reflcut
prin
citirea
urmitoarei
inregistrlri
din
figierul ce
confne
ultima
inregistoare
scdse in
FD.
Pasul
4. Dupi ce s-a
atins sfArgitul
unui
fi9ier,
procesul
continu6
pentru
celelalte
figiere
rimase'
Pasul
5.
in
momentul
in
care se
depisteazi
5i
sfirqitul
celui
de-al
doilea
frqier,
articolele
rimase
in cel de-al
fieilea
vor
fi
transferate in FD.
Tabela
de decizie
obtinutd
este:
76
Rl
R2 R3
&
Rs
& &
Rs Rq
R1s
R11
R12 R13
R1a
Ll
Cz
Cs
Co,
Cs
Ct
D
N N N
1{ .If
N I{ TT N
il ]V 1{
N
-TT.I{N?{NNNDDNDDD
-NNN1{IVDD]fND-ITDD
-
N Ntr
D D
trl{?/l{
D D ?{ D
- D N - D
t/
-D-l{Dnr
DilDN
.112
.413
tt5
76
118
*rr********+,t*
Pr Pz Pz
P+
Pz
Pt
Pz
.P4
Pt
Pq
Pz Pz Pt
Ps