tabele de decizie

7
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

Upload: paraoanu-nela

Post on 05-Feb-2018

265 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Tabele de Decizie

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

Page 2: Tabele de Decizie

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

Page 3: Tabele de Decizie

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:

Page 4: Tabele de Decizie

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.

Page 5: Tabele de Decizie

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.

Page 6: Tabele de Decizie

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)

Page 7: Tabele de Decizie

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