7HKQLFLGHPRGHODUHúLVLPXODUH [600128]

7HKQLFLGHPRGHODUHúLVLPXODUH

ÍQGUXPWRUGHODERUDWRU

5RGLFDLUWHD
2008

Cuvânt înainte
7HKQLFLOHGHPRGHODUHúLVLPXODUHV-au dezvoltat în ultimele decenii într-XQULWPQHDúWHSWDW
PXOXPLWFUHúWHULLFDSDFLWLLGHFDOFXOúLDYLWH]HLsistemelor de calcul. În acest fel, utilizând
SODWIRUPHSHUIRUPDQWHSHQWUXPRGHODUHúLVLPXODUHFRVWXULOHGHSURLHFWDUHúLWHVWDUHVXQW
UHGXVHvQPRGVXEVWDQLDO
$FHDVWOXFUDUHSURSXQHFkWHYDWHPHSUDFWLFHSHQWUXDILrealizate la activitatea de laborator
DVWXGHQLORUFDUHDOHJFXUVXOGHÄ7HKQLFLGHPRGHODUHúLVLPXODUH´6WUXFWXUDPDWHULDOXOXL
XUPHD]FDSLWROHOHFXUVXOXLGH7HKQLFLGHPRGHODUHúLVLPXODUH
$FHVWvQGUXPWRUGHODERUDWRUDERUGHD]GLYHUVHWHPHGHODFHOHFDUHYL]HD]HURULOHvQ
modelaUHPRGHODUHDSURFHVHORULQGHSHQGHQWHGHWLPSXWLOL]kQGDWkWDXWRPDWHGHVWULFkWúL
UHHOH3HWULODPRGHODUHDVLVWHPHORUWHPSRUL]DWHúLDSRLSUREDELOLVWLFHFDvQILQDOVVH
DQDOL]H]HúLDOWHGRPHQLLvQFDUHSRWILXWLOL]DWHWHKQLFLOHGHPRGHODUHúLVimulare. Exemplele
úLPRGHOHOHVXQWVHOHFWDWHGLQWUHFHOHFDUHDXDSOLFDLHúLsunt utile în modelarea proceselor
legate de sistemele de calcul.
3ULQDFHDVWOXFUDUHVHvQFHDUFIDPLOLDUL]DUHDFXUVDQWXOXLFXQRLXQLOHúLFDUDFWHULVWLFLOH
tehnicilor de modelare. )LHFDUHOXFUDUHSURSXVUHFDSLWXOHD]SHVFXUWQRLXQLOHSUH]HQWDWHOD
FXUVSHDFHDWHP7HPHOHSURSXVHVHED]HD]vQSULQFLSDOSHGRXUHIHULQHELEOLRJUDILFH
Introduction to Computational Science: Modeling and Simulation for the Sciences, Angela B.
6KLIOHW *HRUJH:6KLIOHW3ULQFHWRQ8QLYHUVLW\3UHVVúLUHVSHFWLYIntroduction to
Discrete Event Systems, Christos G. Cassandras & Stephane Lafortune, Springer, 2008, a
GRXDHGLLH3HQWUXLPSOHPHQWULQu sunt indicate anumite platforme pentUXPRGHODUHúL
VLPXODUHSHQWUXDOVDODODWLWXGLQHDFXUVDQLORUselectarea diversele instrumente software care
pot fi utilizateÌQIXQFLHGHGRPHQLXOGHXWLOL]DUHDWHKQLFLORUH[LVWGLYHUVHSODWIRUPH
SURIHVLRQDOHSHQWUXPRGHODUHúLVLPXODUH'RDUvQXnele locuri sunt indicate instrumente
VRIWZDUHúLvQVSHFLDODFHVWHDVXQWGLQGRPHQLXO2SHQSource.
DomeniulGHVWXGLXÄ7HKQLFLGHPRGHODUHúLVLPXODUH´, în mod evident, permite extinderea
FXUVXOXLúLDWHPHORUSUDFWLFHSURSXVH7RWXúLvQUHDOL]DUHDDFHstui material s-DLQXWFRQWGH
SODQXOGHvQYPkQWFDUHVSHFLILFSDWUXVSUH]HFHRUHGHODERUDWRU, astfel, doar temele
FRQVLGHUDWHHVHQLDOHDXIRVWLQFOXVH
6SHUFDDFHVWPDWHULDOVILHSHGHRSDUWHXWLOúLSHGHDOWSDUWHXWLOL]DWGHFWUHVWXGHQL
0XOXPHVFSHDFHDVWFDOHVWXGHQLORUFDUHSkQDFXPDXIXUQL]DWRSLQLLúLUHDFLLYLV-a-vis de
DFHVWPDWHULDOúLSHGHDOWSDUWHVSHUFDvQFRQWLQXDUHVH[LVWHIHHGEDFNGLQSDUWHDFHORUFDUH
vOXWLOL]HD]

5RGLFDLUWHD
Noiembrie 2008

Cuprins

Cuvânt înainte…………………………………………………………………………………………………………3
Cuprins…………………………………………………………………………………………………………………..5
0RGHODUHúLVLPXODUH6FXUWDQDOL]DHURULORUvn modelare………………………………………7
1.1. Introducere………………………………………………………………………………………………..7
1.2. Tipuri de erori în modelare………………………………………………………………………….7
([HUFLLLSURSXVH………………………………………………………………………………………13
2. Analiza sistemelor………………………………………………………………………………………………15
3UH]HQWDUHDOXFUULL…………………………………………………………………………………..15
2.2. Clasificarea sistemelor………………………………………………………………………………15
2.3. Sisteme cu evenimente discrete (DES)………………………………………………………..17
6LVWHPHFXFR]LGHDúWHSWDUHTXHXHLQJV\VWHPV………………………………………….18
2.5. Probleme propuse…………………………………………………………………………………….18
0RGHOHQHWHPSRUL]DWHSHQWUXPRGHODUHD'(6([SUHVLLUHJXODWHúLDXWRPDWHGHVWUL…21
3.1. Despre lucrare………………………………………………………………………………………….21
1RLXQLXWLOL]DWH([SUHVLLUHJXODWHúLDXWRPDWH…………………………………………….21
3.3. Probleme propuse…………………………………………………………………………………….22
5HHOH3HWUL0RGHOHQHWHPSRUL]DWHSHQWUX'(6……………………………………………………..25
3UH]HQWDUHDOXFUULL…………………………………………………………………………………..25
5HHOH3HWULQHWHPSRUL]DWH5H]XPDWXOQRLXQLORUXWLOL]DWH…………………………….25
4.3. Probleme propuse…………………………………………………………………………………….28
8WLOL]DUHDDSOLFDLHL3,3(3ODWIRUP,QGHSHQGHQW3HWUL1HW(GLWRU…………………30
4.5. Probleme suplimentare utilizând PIPE………………………………………………………..31
5. Modele temporizate pentru DES…………………………………………………………………………..33
3UH]HQWDUHDOXFUULL…………………………………………………………………………………..33
5.2. AuWRPDWHúLUHHOH3HWULWHPSRUL]DWH……………………………………………………………33
5.3. Probleme propuse…………………………………………………………………………………….35
0RGHODUHDXQRUSURFHVHHFRQRPLFHXWLOL]kQGODQXUL0DUNRY………………………………….37
$QDOL]DSURFHVHORUVWRKDVWLFHXWLOL]kQGODQXUL0DUNRY…………………………………37
6.2. DTMC –6WXGLXGHFD](YROXLDSRQGHULLGHSLDD……………………………………….38
6.3. Studii propuse………………………………………………………………………………………….40
Bibliografie…………………………………………………………………………………………………………..43

1. Modelare úi simulare. Scurt analiz a erorilor în modelare
1.1. Introducere
3HSDUFXUVXOVROXLRQULLXQHLSUREOHPHGHPRGHODre care presupune calcul matematic pot
sDSU erori. Pot ILLQIOXHQDWHGH erori toate etapele parcurse în modelare – de la colectarea
datelor pân inclusiv la implementareaSHFDOFXODWRU&HLFDUHUHDOL]HD]PRGHODUHDVLVWHPHORU
trebuie sILHFRQúWLHQi de posibilitatea DSDULLHLDFHVWRU erori,úL, pe de o parte trebuie s
minimizeze LQIOXHQD erorilor iar pe de altSDUWH s evite formularea unor concluzii eronate pe
baza unor rezultateJUHúLWH În aceast lucrare sunt prezentateúLdiscutate concepte legate de
eroriúLsurse de erori. 6XQWUH]ROYDWHH[HUFLLLpentru exemplificare. De asemenea sunt
propuse,DWkWSHVHFLXQL,FkWúLODILQDO,H[HUFLLLUHFDSLWXODWLYH
1.2. Tipuri de erori în modelare1
În aceastVHFLXQHQXQHSURSXQHPVUHDOL]Po clasificare a erorilor. Vom analizaWRWXúL
diverse tipuri de erori care apar pe parcursul procesului de modelareúLvom identifica
PRGDOLWLOH cele mai eficiente de a reduce efectul acestor erori.
1.2.1. Date eronate
Pentru a colecta date de intrare, majoritatea sistemele SHFDUHOHPRGHOPXWLOL]HD]
senzori9DORULOHIXUQL]DWHGHDFHúWLVHQ]RUL sunt apoi analizateúLutilizate pentru decizii.
2ULFHGLVIXQFLRQDOLWDWHDDFHVWRUVHQ]RULGHWHUPLQGHFL]LLHURQDWH De exemplu, dac un
VHQ]RUFDUHGHWHFWHD]SUesiunea dintr-RLQVWDODLHQXIXQFLRQHD]FRUHFW, sau nu este bine
calibrat, nu va putea furniza date corecte pentru dispozitivul de control al presiunii. De
DVHPHQHDSUHFL]LDGHWHFLHLSRDWHV fie o problem.
1.2.2. Erori de modelare
Etapa de modelare poate sILHvQVRLW de erori. Persoanele implicate în procesul de
modelare pot sJUHúHDVF'DFPRGHOXOHVWHVLPSOLILFDWSUHDPXOWDWXQFLHFXDLLOHFDUH
GHVFULXVLVWHPXOQXPDLFRUHVSXQGSURFHVXOXLLQLLDOúLGHFLQXPDLFRUHVSXQGUHDOLWLL'H
exempOXORUGXO.HOYLQFHOFDUHDLQWURGXVVLVWHPXOGHPVXUDUHDWHPSHUDWXULLFXDFHODúL
nume) a propus pe la mijlocul secolului XIX un model matematicúLa calculat vârsta planetei
noastre ca fiind între 20úL40 de milioane de ani. 7RWXúL aceasta valoare este mult diferit de
cea realGHDSUR[PLOLDUGHGHDQL/RUGXO.HYLQDSUHVXSXVFD3PkQWXOVHUFHúWHGLQ
faza în care era doar o mas incandescent)úLSoarele este singura surs dHHQHUJLH7RWXúL
aceast presupunere nu este corect deoarece descompunerea elementelor radioactive din
VFRDUDWHUHVWUJHQHUHD]GHDVHPHQHDHQHUJLHWHUPLF, încetinind astfel UFLUHDSODQHWHL
7RWXúLORUGXO.HOYLQQXDSXWXWOXD în considerare aceste efecte ale UDGLRDFWLYLWLL deoarece
radioactivitatea a fost descoperit de Becquerel mai târziu, în anul 1896.

1 Introduction to Computational Science: Modeling and Simulation for the Sciences, Angela B. Shiflet &
George W. Shiflet, Princeton University Press, 2006 (Module 2.2).

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
8 1.2.3. Erori de implementare
Etapa de implementare este de asemenea supus erorilor. Un exemplu edificator în acest
sens este pierderea GHFWUH1$6$în 1999 a unei QDYHWHVSDLDOHFDUHDYHDPLVLXQHDGHD
observa planeta Marte. Dezastrul a fost cauzat de faptul c sistemele furnizate de o parte din
SURGXFWRULHUDXJkQGLWHXWLOL]kQGVLVWHPXOPHWULFúLXQLWLUHIHUHQLDOHLDUFHDODOWSDUWHD
furnizorilor de echipamenteDXWLOL]DWVLVWHPXOHQJOH]HVFGHPVXU.
1.2.4. Precizia
Erori pot sDSUúLvQetapa de calcul datorit preciziei de calcul. Vom analiza mai în
detaliu acest aspect.
Multe din limbajele de programare XWLOL]HD] reprezentarea numerelor în virgul flotant în
form H[SRQHQLDO. De exemplu un rezultat de forma 9.843600e02 însemnând 9.843600 x 102
= 984.36 = 0.98436 x 103. Numerele cu virgul flotantVXQWPHPRUDWHGHFWUHFDOFXODWRDUH
în trei SUL: prima parte pentru semn, 0 sau 1, pentru semnul + sau respectiv -, a doua parte
este mantisa (sau partea semnificativVDXIUDFLRQDU 98436 în cazul nostru,úLultima parte
este exponentulDGLF în acest caz.
1RWDLDH[SRQHQLDOVHUHSUH]LQWFDúLprodusDXQHLSDUL]HFLPDOHFXRSXWHUHGHDOXL
ex. dac a este partea zecimalúLn un întreg, nRWDLD H[SRQHQLDO aen UHSUH]LQW a x 10n.
Partea vQWUHDJ rezultat prin eliminarea virgulei din a IRUPHD] mantisa iar n UHSUH]LQW
exponentul.
Forma normalizat este dat de scrierea în care mantisa are virgulvQID primei cifre
diferite de zero: ex. 0,98436 x 103. În aceast form, toate cifrele diferite de zero sunt
semnificative ex. 98436. Pentru numere întregi cum ar fi 003 704 000 = 0.3704 x 107, cifrele
3704 sunt cifre semnificative, Iar 3 este cea mai semnificativ cifr. Pentru numerele reale, de
exemplu pentru 0,09200=0,92 x 10-1, 9 este cea mai semnificativ cifr iar 9200 sunt cifrele
semnificative (deci inclusiv 0 la final).
)RUPDúWLLQLILF în VFKLPESODVHD]YLUJXODGXSSULPDFLIU diferit de zero, astfel încât
DFHHDúL valoare este scris 9,8436 x 102.
Precizia este dat de QXPUXO de cifre semnificative. Astfel atât 003 704 000 câtúL0,09200
DXDFHHDúLSUHFL]LHDGLF
Magnitudinea indic mrimea relativ a valoriiúLeste 10 la puterea dat de exponent în
forma normalizat. Astfel 0.3704 x 107 are magnitudinea 107.
În C respectiv C++ precizia unui QXPU în virgul flotant de tipul float (adic precizie
simpl) este de 6-7 cifre zecimale pentru partea semnificativ în timp ce magnitudinea variaz
între 10-38úL1038. Tipul double XWLOL]HD] VSDLX de memorie dublu pentru memorie
comparativ cu tipul floatúLutilizând dubla precizie poate fi utilizat pentru a reprezenta 14-15
cifre semnificative iar magnitudinea poate varia intre 10-308úL10308.
ÌQWUHEUL recapitulative 1. Pentru valurile (i) 0,0004500; (ii) 230000; (iii) 0,312 s se
UH]ROYHXUPWRDUHOHSUREOHPH
a. Utilizând forma normalizat s se specifice cifrele semnificative.
b. Utilizând forma normalizat s se specifice exponentul lui 10.
c. S se specifice precizia.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
9 1.2.5. Erori absoluteúLerori relative
În cazul în care apar erori este important s existe PRGDOLWL pentru a determina
magnitudinea acestora. Eroarea absolut este dat de valoarea absolutDGLIHUHQHLGLQWUH
rezultatul calculatúLcel exact/corect. Eroarea relativ se determin prin vPSULUHD valorii
DEVROXWHDGLIHUHQHLUDSRUWDWODYDORDUHDH[DFW (presupunând c nu este zero).Eroarea relativ
VHUHSUH]LQW în general caúLSURFHQWH[RHURDUHGHVHUHSUH]LQWFDúL4%.
Deci, dac valoare corecta o notm ‚corect’úLcea calculat o notm ‚calculat’ avem:
eroarea absolut = | corect – calculat |
eroarea relativ = (eroarea absoluta) / | corect | = | corect – calculat | / | corect |
sau
eroarea relativ = (eroarea absoluta) / | corect | x 100% = | corect – calculat | / | corect | x
100%
presupunând corect .
Exemplul 1. Presupunem c un calculator are precizia 3 – FHDFHvQVHDPQF permite
reprezentarea a doar 3 cifre semnificativeúLWUXFKHD] ELLL mai SXLQ semnificativi dac sunt
mai PXOL decât 3. (Acesta este doar un exempluúLpentru a simplifica calculul s-a IFXW
aceast presupunere, în realitate calculatoarele au precizie mult mai mare).
TrunchiereaUHSUH]LQWHOLPLQDUHDELLORUPDLSXLQVHPQLILFDWLYL în afar de cei n SHUPLúL.
&DúLH[HPSlu vom calcula eroarea relativúLabsolut pentru vQPXOLUea (0,356 x
108)(0,228 x 10-3). Rezultatul exact este:
(0,356 x 108) (0,228 x 10-3) = (0,356) (0,228) (108) (10-3) = 0,081168 x 105.
În form normalizatVHRELQH[4.
'LQFDX]DOLPLWUii de precizie calculatorul va returna rezultatul 0,811 x 104.
Astfel eroarea absolut este:
| corect – calculat | = |0,81168 x 104 – 0,811 x 104| = 0,00068 x 104 =6.8
iar eroarea relativ:
(0,00068 x 104)/( 0,81168 x 104) = 0,0008378 = 0,08378%.
ÌQWUHEri recapitulative 2. Pentru valorile (i) 6,239; (ii) 0,312 s se calculeze:
a. Eroarea absolut în cazul în FDUHVHWUXFKHD]ODFLIUH
b. Eroarea relativ (e[SULPDLUH]XOWDWHOH în procente).
1.2.6. Erori round-off
În unele cazuri calculatoarele pot s URWXQMHDVF valorile în loc s le trucheze pentru a
corespunde unei precizii predefinite. Pentru ca valoarea 0,81168 x 104 s fie rotunjit cu o
precizie de 3 cifre se DQDOL]HD] valoarea celei de a patra valori – în cazul acesta 6. Dac cifra
e mai mic decât 5 se URWXQMHúWH în jos iar dac este mai mare sau egal se URWXQMHúWH în sus.
Astfel 0,81168 x 104 respectiv 0,81158 x 104 rotunjite devin 0,812 x 104 iar 0,81138 x 104
devine 0,811 x 104.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
10 ÌQWUHEULUHFDSLWXODWLYH 3. 5RWXQMLLYDORULOHFDUHXUPHD]útiind c valoarea preciziei este
2:
a. 0,93742 x 10-5 b. 0,93472 x 10-5 c. 0,93572 x 10-5
Exemplul 2. În XUPDXQHLLQVWUXFLXQLGHDWULEXLUHcum ar fi x= 1.0 / 3.0 (în programe caúL
C, C++, Java) cDOFXODWRUXOYDPHPRUDODORFDLDOXL[YDORDUHDUHDO 1/3=0,333… . $FHODúL
lucru se întâmpl pentru un program cum este Excel unde dac într-o celul s-a introdus =1/3
se va memora rezultatulvPSULULL. Dac calculatorul poate memora doar cu o precizie de 3
cifre, calculatorul va rotunji sau trunchia rezultatul la valoarea 0,333.
Eroarea round-off este dat tocmai de acest fapt –FDOFXODWRUXOQXDUHDORFDLVXILFLHQLELL
SHQWUXDPHPRUDQXPUXOUHDO în întregimeúLatunci XWLOL]HD] cel mai apropiat QXPU care
poate fi reprezentat.
1.2.7. Erori overflowúLunderflow
$FHVWHHURULVXQWGHDVHPHQHDGHWHUPLQDWHGHVSDLXOOLPLWDWde memorare cu care se
OXFUHD]'HH[HPSOXGDFVHOXFUHD]FXXQFDOFXODWRUIRDUWHPLFFDUHXWLOL]HD]GRDUELL
pentru a reprezenta un întreg, dac dorim s adunm 20480 + 16384 în PRGVXUSULQ]WRU
UH]XOWDWXOYDILXQQXPUQHJDWLYDGLF-28672. Problema apare deoarece cel mai semnificativ
bit devine 1 dat fiind transportul de pe nivelul precedent. Dar cum pentru numerele întregi
bitul cel mai semnificativ este bit de semn rezultatul este explicabil. Eroarea overflow apare
de asemenea în cazul în care se adun dou numere negative mariúLVHRELQHXQUH]XOWDW
pozitiv.
2HURDUHGHWLSRYHUIORZDFDX]DWSLHUGHUHDUDFKHWHL$ULDQHD$JHQLHL6SDLDOH(XURSHQH
în /DPDLSXLQGe 37 de secunde de la lansare sistemul de ghidare a încercat s
transforme viteza circular dintr-RYDORDUHIORDWSHGHELLîntr-XQvQWUHJGHELL
'HRDUHFHQXPUXODIRVWSUHDPDUHDUH]XOWDWRGHSúLUHDGRPHQLXOXL– o eroare overflow.
Sistemul de ghidaj a încercat sFRUHFWH]HSR]LLDGLQWU-una presupus ca fiind JUHúLW – care
oricum nu fusese atins)úLfoarte curând racheta a trebuit sVHDXWRGLVWUXJ2HURDUH
overflow dat de doar FkLYDELLDFDX]Dt pierderea unei rachete în care s-au investit zece ani
de cercetare úLúDSWHPLOLDUGHGHGRODULSHQWUXGH]YROWDUH
Erorile underflow apar când o valoare este prea mic pentru a fi reprezentat corect. De
exemplu dac un calculator permite reprezentarea unor valori de magnitudine 10-39úL
rezultatXOXQHLRSHUDLLHVWHGHmagnitudine 10-48 din cauza acestei erori rezultatul returnat va
fi 0.
1.2.8. Erori aritmetice
(URULSRWVDSDr la adunarea numerelor. Astfel dacVHUHDOL]HD]DGXQDUHDVSUH
GHRVHELUHGHvQPXOLUHWUHEXLHV se realizeze alinierea virgulei zecimale. Spre exemplu,
pentru o precizie de 3 cifre, dac se adun (0,684 x 103) + (0,950 x 10-2) avem:
0,684 x 103 = 684,0000
0,950 x 10-2 = +,0095
684,0095
/DQRUPDOL]DUHDUH]XOWDWXOXLVHRELQH[3, astfel se pierde influenta celui de-al
doilea termen 0,950 x 10-2.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
11 ÌQWUHEULUHFDSLWXODWLYH 4. Presupunem cXQFDOFXODWRUURWXQMHúWHQXPHUHOH în virgul
flotantODFLIUHVHPQLILFDWLYH&DOFXODLH[SUHVLD[2) + (0.2499 x 10-1) IU a
utiliza pentru rezultat forPDH[SRQHQLDO.
Date fiind problemele generateGHGLIHUHQDGHPDJQLWXGLQH, este de preferat s se realizeze
RSHUDLLOHDVXSUDQXPHUHORUPLFLSULPDGDWúLapoi s se combine cu cele mari. Astfel valorile
PLFLDXRúDQV se devin semnificative înainte deRSHUDLLOHFXFHOHPDUL
În mod similar, în FD]XOvQPXOLULLúLvPSULULLSHQWUXDHYLWDSLHUGHULOHGHSUHFL]LHHVWHGH
preferat sVHUHDOL]H]HWRDWHvQPXOLULOHGHODQXPUWRUvQDLQWHGHDVHvPSDULODQXPLWRU'H
exemplu, în cazul calculatorului nostru care URWXQMHúWH la 3 ELL semnificativi, calculm
expresia (x/y)z, unde x=2,41, y=9,75, z=1,54. Rezultatul lui x/y este 0,247179úLVHURWXQMHúWH
la 0,247,úLvQPXOLW cu z se RELQH (x/y)z = (0,247) (1,54) = 0,38038, sau 0,380 GXS rotunjire.
In schimb deoarece d.p.d.v. matematic [\] []\HIHFWXkQGvQPXOLUHDSULPDGDW se
RELQH (xz)/y = 3,71/9,75 = 0,380513, rotunjit la 0,381. Ultima valoare este mai apropiat de
cea corect de 0,380656…
7RWXúLGDF în FD]XOvQPXOLULORUXUPDWHGHvPSULUiVXQWúDQVHVVHSURGXFHURUL
overflow, pentru exemplu (xz)/y este de recomandat FDRSHUDLLOHs se realizeze în ordinea
LQLLDODGLF[\]
ÌQWUHEULUHFDSLWXODWLYH Presupune ca variabilele r, u, x, y,úLz sunt numere reprezentate
cu virgula flotant6FULHLXUPWRDUHDH[SUHVLHDVWIHOvQFkWVVHUHGXFHURULOHGDWHGHURXQG-
off, presupunând ca nu sunt probleme de generate de overflow sau underflow:
1.2.9. Propagarea erorilor
%XFOHOHXQXLSURJUDPLQVWUXFLXQLOHLWHUDWLYHFDUHFRQLQRSHUDLL aritmetice cu valori
exprimate în virgul flotant pot determina erori de tip round-off.
$FXPXODUHDXQRUDVWIHOGHHURULSRDWHDYHDFRQVHFLQHGH]DVWUXRDVH&DúLexemplu
VHUYHúWHVLWXDLDGLQFkQG în U]ERLXOGLQ*ROIVLVWHPHOHDQWLUDFKHW3DWULRW(ale USA) nu
au interceptat o rachet Scud cauzând moartea a GHVROGDLVLUQLUHDDSHVWH o sut în
Dharan, Arabia Saudit. Acest dezastru s-a datorat DFXPXOULL de erori. Deoarece ceasul intern
al sistemului Patriot PVXUD timpul în zeci de secunde, pentru a RELQH valorile în secunde se
vQPXOHD QXPUXO de impulsuri furnizate de ceas cu 1/10. Cum rezultatele se memorau pe 24
de ELLúLRSHUDLLOH se realizau în binar sistemul nu a putut SVWUD în întregime valorile. Astfel
fiecare zecime de secund determina o eroare de 0,000 000 095 sec. La momentul dezastrului,
sistemul patriot opera de aproximativ 100h IU întrerupere (re-boot-are)úLaceasta a cauzat un
decalaj fa de timpul real de (100hrs)(60min/hr)(60sec/min)(10 impulsuri/sec) (0.000 000
095 sec/impuls) = 0,34 sec. Pe parcursul acelei treimi de secund racheta Scoud a zburat
aproximativ 1676 metri, fiind departe de locul unde ar fi putut fi interceptat.
Exemplul 3. În PXOWHDSOLFDLL, care PRQLWRUL]HD] diferite procese la intervale constante de
timp,PRPHQWXOPVXUULLHVWHGHWHUPLQDWGHH[SUHVLLGHJHQXOt=t+dt, unde t apoi, din partea
dreapt ajunge în partea stângSHQWUXXUPWRDUHDLWHUDLH'HH[HPSOXSUHVXSXQHPF
LWHUDLD este repetat de 600 de ori, VSDLXl de stocare este limitat úL este nevoie úi de o
conversie în baza 2. Astfel pentru dt care în loc s fie de 0,1 secunde este de 0,09961=0,9961
x 10-1, pe PVXUD ce bucla se execut, eroarea propagat FUHúWe. Astfel la LWHUDLD 11 chiar dac () ÷
øöç
èæ+÷
øöç
èæ
uyxrz3

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
12 valoarea ar trebui sa fie (11)(0,09961) = 1.09571, pentru un calculator cu precizia 4, valoarea
rotunjit este 1,096, eroarea absolut este de 0,00029, iar cea relativ de aproximativ 0,026%.
'XSLWHUDLDHURDUHDUHODWLY este de 0,3128%úLeste de aproximativ 30 de ori mai mare
decât cea dinLWHUDLDDGRXD
Pentru a evita acumularea erorilor în buclele unor programe, t WUHEXLHFDOFXODWvQPXOLQG
indexul cu valoarea lui dt astfel t=i*dt. Eroarea round-off mai exist, dar efectul ei este
PLQLPL]DWGHRDUHFHQXVHDFXPXOHD]3HQWUXDVHFRPSDUD rezultatele se poate completa un
tabelúLse pot calcula valorile lui t pentru diferite valori ale indexului i utilizând ambele
formule de calcul.
În general, în LQVWUXFLXQLLWHUDWLYHHVWHUHFRPDQGDWV se evite acumularea unor valori în
virgul flotantSULQDGXQULVDXVFGHULUHSHWDWH
ÌQWUHEULUHFDSLWXODWLYH Care dintre atribuirile de mai jos sunt mai potrivite (dac exist
YUHRGLIHUHQ) într-o bucl cu indexul k avândYDORDUHDLQLLDO 1. Variabila sum a fost
LQLLDOL]DW deja la 0 înainte de bucl.
a. sum = sum + 0.00492
b. sum = 0.00492 * k
c. nu conteaz.
1.2.10. Nerespectarea SURSULHWLORU numerelor
ÎQVHFLXQHDGHVSUHHURULDULWPHWLFHDPY]XWFSURSULHWLOHQXPHUHORUQXVXQWvQGHSOLQLWH
întotdeauna în aritmetica calculatoarelor (ex. chiar dac (x/y)z =(xz)/yDPY]XWF FHOHGRX
expresii nuJHQHUHD]DFHODúLUH]XOWDW în unele cazuri în LPSOHPHQWULOHSHFDOFXODWRU$OWH
SURSULHWL nerespectate sunt asociativitatea -DGLF(a + b) + c = a + (b + c), úL (ab)c = a(bc)
– respectiv distributivitatea – adic a (b + c) = ab + ac. În cazul calculatoarelor, dac aúLb
sunt foarte mici în FRPSDUDLHFXcDWXQFLDFHVWHSURSULHWLVXQWvQFOFDWH
ÌQWUHEULUHFDSLWXODWLYH$UWDLF distributivitatea nu este respectat pentru expresiile
x(y]úL[\[]SHQWUX[ \ ] FkQGse utilizeazRPDúLQFDUHWUXQFKLD]
UH]XOWDWXOILQDOúLFHOHLQWHUPHGLDUHGXS2 cifre.
1.2.11. Compararea numerelor în virgul flotant
Datorit numeroaselor erori care pot s apar în implementarea oSHUDLLORUFXQXPHUHUHDOH
compararea numerelor reale trebuie evitat. Astfel, pentru a realiza DFHHDúL IXQFLRQDOLWDWH,
acceptând o marj de eroare, este de preferat s se IRORVHDVF expresii de genul:
„dac |x – z| < 0,001, considerm c x úL z sunt identice.”, (1)
unde 0.001 este o valoare folosit pentru a exprima GLIHUHQDDFFHSWDWGLQWUHYDORULvQ
YDORDUHDEVROXWúLfaptul cVLVWHPXOIRORVHúWHGRDUWUHLFLIUHVHPQLILFDWLYHSHQWUX
reprezentare.
ÌQWUHEULUHFDSLWXODWLYH6FULHLRH[SUHVLHVLPilar celei notate cu (1) pentru a compara
dou valori în virgul flotantGLIHUHQDDFFHSWDW fiind de 0,000 001.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
13 1.2.12. Erori de trunchiere
Am observat deja c utilizând tehnica de calcul nu pot fi memorate corect numere de
precizie infinit. $FHODúL lucru este valabilúLpentru calcularea unor expresii cu un QXPU
infinit de termeni. S consideram cazul QXPUXOXL lui Euler e la puterea x, care este definit:
…!4321321211432
+ ++×××+××+×++=nxxxxxen
x
Astfel, evaluarea expresiei e1=e, care are valoarea 2,718281828459045… este identic cu
UH]XOWDWXOHYDOXULLH[SUHVLHLGHPDLMRVXQGHx din expresia general a fost înlocuit cu 1:
…!1
43211
3211
21111 +++×××+××+×++=ne 
O PDúLQD nu poate realiza un QXPU infinit de DGXQUL de astfel de termeni. De aceea, de
exemplu,GXSGHDGXQULVHRELQHGRDUXQUH]XOWDWSDULDO$VWIHOWHUPHQXOQX
este inclus în rezultatúLQLFLXUPWRULLUH]XOWkQGRHURDUHGHWUXQFKLHUHGHDSUR[LPDWLY[
10-20.
Astfel, eroarea de trunchiere este datGHFDOFXODUHDXQXLQXPUILQLWGHRSHUDLL în locul
XQXLQXPULQILQLWGHRSHUDLLDOHXQHLVHULL
ÌQWUHEULUHFDSLWXODWLYH Pe baza calculelor se úWLH c sin(x) este datGHXUPWRDUHD
expresie:
…!7!5!3)sin(753
+ – + -=xxxxx
D&DOFXODLVLQSHQWUXVHULDWUXQFKLDW la 2 termeni.
E3UHFL]DLHURDUHDSHntru aceast aproximare.
1.3. ([HUFLLLSURSXVH

6FULHL valorile de la H[HUFLLLOH 1 – 12 în form H[SRQHQLDO normalizat.
1. 63,850 2. 29,748 3. 0,00032 4. 53,7 x 103
5. 0,496 6. 0,0000017 7. 0,009 x 10-5 8. 0,009 x 105
9. -0,82 10. -82 11. -0,00082 12. 4,4
3UHFL]DLPDJQLWXGLQHDúLprecizia pentru 0,743621 x 1025.
3UHFL]DLPDJQLWXGLQHDúLprecizia pentru 93,6 x 107.
15. Care este preciziaúLcea mai mare magnitudine care poate fi utilizat de un calculator
care permite 8 cifre semnificativeúLcea mai mare putere a lui 10 este 125?
6SHFLILFDL QXPUXO de cifre semnificative precumúLcele mai semnificative cifre pentru
H[HUFLLLOH– 21.
16. 63,850 17. 29,004 18. 0,00074
19. 103 20. 4 x 10-5 21. 0,300500

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
14 22.6SHFLILFDLPULPHDPDJQLWXGLQHDXQRUQXPHUHQRUPDOL]DWHSR]LWLYH în FD]XOFURUD
parte semnificativ are 3 cifreúLexponentul lui 10 poate varia între -5úL+5.
6SHFLILFDLPULPHDPDJQLWXGLQHDXQRUQXPHUHQRUPDOL]DWHSR]LWLYH în cazul cURUD
parte semnificativ are 7 cifreúLexponentul lui 10 poate varia între -78úL+73.
3HQWUXH[HUFLLLOH-GHWHUPLQDLDHURDUHDDEVROXWúL(b) eroarea relativDILHFUHL
valori dat fiind cVHIRORVHúWHRURWXQMLUHODGRX cifre zecimale. 'XSaceea s se determine
(c) eroarea absolutúL(d) eroarea relativ dacVHIRORVHúWHWUXQFKLHUHDGXSGRXSR]LLL
zecimale.
24. 6,239 25. 6,231 26. 1,0/3,0 memorat cu 5 cifre semnificative
D&DOFXODL9,4 x 10-5) + (3,6 x 1045HSUH]HQWDLUH]ultatul în form normalizat
exponeQial.
b. RotunMLLUH]XOWDWXOXWLOL]kQGGRDU 5 cifre semnificative.
F&DOFXODLHURDUHDDEVROXW pentru b.
G&DOFXODLHURDUHDUHODWLY pentru b.
5HSHWDLH[HUFLLXOSHQWUXH[SUHVLD[3) – (0,825 x 1028WLOL]DLFLIUH
semnificative în loc de 5 pentru punctele b, cúLd.
29. Presupunem c se executXUPWRDUHDVHFYHQ de cod: x = 6,239; x = x + x. Pentru o
PDúLQFDUHWUXQFKLD]GXSFLIUHVHPQLILFDWLYHGDLYDORULOHOXLxGXSILHFDUHLQVWUXFLune
úLeroarea relativGXSXOWLPDLQVWUXFLXQH&RPSDUDLHURDUHDFXUH]XOWDWXOGHODH[HUFLLXO
24.
D&XRDSOLFDLHGHFDOFXOHYDOXDLXUPWRDUHDH[SUHVLH
10000000000000000, + 1, -10000000000000000,
DGLF1,0 x 1016 + 1, – 1,0 x 1016.
b. Care ar trebui sa fie rezultatul?
F([SOLFDLFHV-a întâmplat.
8WLOL]kQGRDSOLFDLHGHFDOFXO (de exemplu Excel)HYDOXDLXUPWRDUHOHH[SUHVLLSHQWUX
t = 355/113, r=101/113úLs = 52/113: t – s – r – r – r, t – r – r – r – s, t – r – r – s – r, t – r – 2r
– s, t – r – s – r – r, t – 2r – r – s, t – 3r – s, t – r – s –U8WLOL]kQGFXQRúWLQHOHGHPDWHPDWLF,
FDUHVXQWYDORULOHDFHVWRUH[SUHVLL"&DUHSURSULHWDWHSURSULHWLDOJHEULFHVXQWvQFOFDWH?
3HED]DFDOFXOHORUVHúWLHFIXQFLD cos(x) este datGHXUPWRDUHDVHULHLQILQLW:
…!6!4!21)cos(642
+ – + -=xxxx
D&DOFXODLcos(2) pentru seria trunchiat la 3 termeni.
b. CDOFXODLFRVSHQWUXVHULDGH mai sus pânFkQGDSUR[LPULOHVXFFHVLYHVXQWLGHQWLFH
SHQWUXSULPHOHFLIUHVHPQLILFDWLYH'DLDFHa valoare.

2. Analiza sistemelor
3UH]HQWDUHDOXFUULL
'XSUHOXDUHDXQRUQRLXQLGHODFXUVUHIHULWRDUHODFODVLILFDUHDVLVWHPHORUvQFDGUXODFHVWHL
OXFUULVXQWSURSXVHSUREOHPHGHDQDOL]DVLVWHPHORU– se cere construirea unor diagrame de
timpúLFRPSDUDUHDHIRUWXOGHSURFHVDUHvQIXQFLHGHPRGHOXODOHV– condus de timp sau de
evenimente.
2.2. Clasificarea sistemelor
3ULPDHWDSDSURFHVXOXLGHPRGHODUHHVWHGHGLFDWDQDOL]HLSUREOHPHLVLVWHPXOXLPRGHODW
ÌQDFHDVWDHWDSGHDQDOL]VHLGHQWLILFFHOPDLSRWULYLWPRGHOILJXUDSHQWUXDGHVFULH
SUREOHPDVLVWHPXODQDOL]DW3HQWUXDLGHQWLILFDFHOPDLSRWULYLWPRGHOVHDQDOL]HD]SURFHVXO–
GDFHVWHVWDWLFVDXGLQDPLFGDFGHSLQGHGHWLPSVDXQXGDFHVWHFRQGXVGLUHFWDWGHWLPS
sau evenimente, etc.

Figura 2.1. Procesul de modelare. De la sistem la model

ÌQILJXUDHVWHSUH]HQWDWRFODVLILFDUHDVLVWHPHORU
Astfel, pentru modelul din figura 2.1, un sistem este considerat staticGDFLHúLULOHy(t) sunt
independente de valorile dLQWUHFXWDOHLQWUULORUu(t) unde t < t pentru toate valorile lui t (u úL
ySRWILVXEIRUPGHYHFWRU. Un sistem dinamicHVWHFDUDFWHUL]DWSULQIDSWXOFLHúLULOHGHSLQG
vQJHQHUDOGHYDORULOHGLQWUHFXWDOHLQWUULORU
3HQWUXDIDFHGLIHUHQDvQWUHVLVWHPHFDUHGHSLQGGHWLPSúLFHOHFDUHQXGHSLQGGHWLPSH
QHYRLHVUVSXQGHPODXUPWRDUHDvQWUHEDUH,HúLUHDVLVWHPXOXLHVWHLGHQWLFSHQWUXWRDWH
VLWXDLLOHvQFDUHDFHOHDúLYDORULVXQWDSOLFDWHSHLQWUUL"'HRDUHFHUVSXQVXOQXSRDWHILvQ
general „da”WUHEXLHVFRQWLQXPvQvQFHUFDUHDGHDFODVLILFDVLVWHPHOH$VWIHOGDFy=g(u, t)
úLDVWIHOIXQFLDGHLHúLUHGHSLQGHGHYDULDELODGHWLPSDYHPGHDIDFHFXXQsistem care
depinde de timp$OWIHOGDFIXQFLDGHLHúLUHQXGHSLQGHGHYDULDELODGHWLPStGLVFXWP
despre un sistem independent de timp.
Conceptul de stare pentru un sistem descrie „comportamentul” acestuia la momentul de
timp t$VWIHOGDFYHFWRUXOGHLQWUDUHu(t) este complet specificat pentru orice moment de
timp t•W0 , starea sistemului la momentul t0FRQVWvQVXPDLQIRUPDLLORUGHODPRPHQWXOt0
QHFHVDUHSHQWUXDGHWHUPLQDvQPRGXQLFLHúLUHDy(t) pentru toate momentele de timp t•W0.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
16 Considerând u(t)úLy(t) YHFWRULVWDUHDYDILGHDVHPHQHDXQYHFWRUSHFDUHvOQRWPFXx(t).
Componentele vectorului x(t)DGLFx1(t), x2(t) etc. se numesc variabile de stare.

Figura 2.2. Clasificarea sistemelor1

6HWXOGHHFXDLLQHFHVDUHSHQWUXDGHVFULHVWULOHx(t) pentru toate momentele de timp t•W0
când se cunosc x(t0)úLIXQFLDu(t), pentru toate momentele de timp t•W0 , se numesc HFXDLLGH
stare. 6SDLXOVWULORUSHQWUXXQVLVWHPGHRELFHLQRWDWFX;HVWHIRUPDWGLQWRWDOLWDWHDVWULORU
SHFDUHVLVWHPXOOHSRDWHDYHD$VWIHOSHQWUXHFXDLLOHGHVWDUHSXWHPDYHDXUPWRDUHD
H[SUHVLHGLIHUHQLDO )),(),(()( ttutxftx= , unde x(t0)=x0 (figura 2.3).

)LJXUD,QWUULOHHFXDLLOHGHVWDUHúLIXQFLLOHGHLHúLUH

ÌQIXQFLHGHIRUPDIXQFLLOor fúLgXWLOL]DWHSHQWUXDGHWHUPLQDVWDUHDXUPWRDUHD
VLVWHPXOXLUHVSHFWLYLHúLULOHVLVWHPXOXLSXWHPVFODVLILFPVLVWHPXOFDILLQGOLQHDUVDX
neliniar2IXQFLHgVSXQHPFHVWHOLQHDUGDFúLQXPDLGDFSHQWUXIXQFLDg : U ® Y, cu u
úLvDSDULQkQGOXLU, avem g(au+bv)=ag(u)+bg(v) pentru oricare numere reale aúLb. Astfel,
despre un sistem sSXQHPFHVWHlinearGDFúLQXPDLGDFDPEHOHIXQFLLfúLgVXQWIXQFLL
lineare.

1 Introduction to Discrete Event Systems, second edition, Christos G. Cassandras & Stephane Lafortune,
Springer, 2008

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
17 3RUQLQGGHODVSDLXOVWULORUXQXLVLVWHPVHPDLSRDWHIDFHRFODVLILFDUH0RGHOXOSRDWH
avea VSDLXOVWULORUFRQWLQXX, de exemplu cazul în care X poate lua orice valoareUHDO (figura
2.4) sau poate avea VSDLXOVWULORUGLVFUHW, de exemplu cazul în care X poate lua doar valori
vQWUHJLVDXQDWXUDOHQXPUXOGHRELHFWHGHLQYHQWDUGLQWU-un depozit este întotdeauna întreg).

)LJXUD6SDLXOVWULORU6SDLXFRQWLQXXYVVSDLXGLVFUHW1

Un sistem este stohasticVDXSUREDELOLVWLFGDFFHOSXLQRYDULDELOGHLHúLUHHVWH
aleatoare. Altfel, sistemul este determinist.
'DFSHQWUXXQVLVWHPVXQWGHILQLWHYDULDELOHOHGHLQWUDUHúLFHOHGHLHúLUHGRDUODLQWHUYDOH
discreWHGHWLPSVLVWHPXOVHQXPHúWHsistem cu timp discretDOWIHOHOVHQXPHúWHsistem cu
timp continuu.
ÌQSOXVGDFWUDQ]LLDGHODRVWDUHODDOWDHVWHGDWGHHYHQLPHQWHYRUELPGHVSUHsisteme
directate (conduse) de evenimente spre deosebire de sistemele directate de timp, unde
WUDQ]LLLOHVXQWVLQFURQL]DWHFXRWHPSRUL]DUHFXXQFHDVFDUHHUHVSRQVDELOGHGHFODQúDUHD
WUDQ]LLLORU Este mai greu de modelat sistemele directate de evenimente; evenimentele pot fi
comparate prin analogie cu întreruperile pentru sistemele de calcul.
2.3. Sisteme cu evenimente discrete (DES)
Prin Sistem cu Evenimente Discrete (DES – Discrete Event System)vQHOHJHPXQVLVWHP
FDUHvQGHSOLQHúWHVLPXOWDQXUPWRDUHOHFRQGLLL
DVSDLXOVWULORUHVWHRPXOLPHGLVFUHWLDU
(bPHFDQLVPXOGHGHFODQúDUHDWUDQ]LLLORUHVWHGHterminat de evenimente.
'HFL'(6HVWHXQVLVWHPGLUHFWDWGHHYHQLPHQWúLFDUHDUHXQVSDLXODOVWULORUGLVFUHW
(YROXLDGHODRVWDUHODDOWDVHUHDOL]HD]GRDUODDSDULLDXQXLHYHQLPHQWH[VWULOHXQei

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
18 PDúLQLSRWILH[^212))`^,'/(%86<'2:1`úLVWULOHODUkQGXOORUSRWILGLYL]DWH
LDUHYHQLPHQWHOHSRWILDSVDUHDXQXLEXWRQVHOHFWDUHDXQHLFRPHQ]LHWF
2.46LVWHPHFXFR]LGHDúWHSWDUHTXHXHLQJV\VWHPV
6XQWWUHLHOHPHQWHGHED]FDUHGHILQHVFRFRDGGHDúWHSWDUH
· HQWLWLOHFDUHµDúWHDSW¶VDXFOLHQLLRDPHQLvQVWDLDGHDXWREXVPHVDMHvQPHGLXOGH
FRPXQLFDUHWUDQ]DFLLH[HFXWDWHSH3&SURGXVHSDULDOILQLVDWHPDúLQLSHúRVHD
avioane la decolare…);
· UHVXUVHOHSHQWUXFDUHVHDúWHDSWVDXservereDXWREX]HYkQ]WRULvQPDJD]LQFDQDOH
de comunicare, procesoare, periferice, utilaje, semafoare…
· VSDLXOGHDúWHSWDUHúLUXOVDXFRDGDGHDúWHSWDUHVWDLLGHDúWHSWDUHGHSR]LWHEXIIHU-
e…).
0RWLYDLDXWLOL]ULLVLVWHPHORUFXFR]LGHDúWHSWDUHHGDWGHOLPLWDUHDUHVXUVHORUFDUH
QHFHVLWDORFDUHDDFHVWRUDvQPRGHFKLWDELO$VWIHOHQHYRLHFDDUHVXUVHOHVILHFRUHFWúL
HILFLHQWDORFDWHSHQWUXWRLFOLHQLLEFOLHQLLVILHVHUYLLFFRVWXOGHSURLHFWDUHúL
PHQWHQDQDVILHDFFHSWDELO6LVWHPHOHFXFR]LGHDúWHSWDUHVXQWFDUDFWHUL]DWHSULQOXQJLPHD
FR]LLOXQJLPHDúLUXOXL–QXPUXOPD[LPGHFOLHQLvQDúWHSWDUHúLUHJXODFR]LL– ex. FIFO etc.
În figura 2.5 este reprezentat XQVLVWHPFDUHSURFHVHD]FRPSRQHQWHFXGRXVHUYHUHúL
úLFXGRXFR]LGHDúWHSWDUHFHDGLQSDUWHDVWkQJGHFDSDFLWDWHLQILQLWLDUFHDGLQWUH
VHUYHUHFXXQEXIIHUSHQWUXFRPSRQHQWHDGRXDFRDGDYkQGFDSDFLWDWHDFDSDFLWDWHDILLQG
GDWLQFOXVLYGHFRPSRQHQWDvQOXFUXODVHUYHUXO.

Figura 2.5. 6LVWHPFXFRDGGHDúWHSWDUH

ÌQDFHDVWOXFUDUHFXDMXWRUXOXQRUSUREOHPHYRPHYLGHQLDGLIHUHQGLQWUHSURFHVHOH
conduse de evenimente úi cele conduse de timp.
2.5. Probleme propuse
8QVLVWHPGHFDOFXOGLVSXQHGHGRXSURFHVRDUH31 respectiv P2FDUHIXQFLRQHD]vQ
paralel. Procesul prin care se atribuie task-urile poate fi descris în timp discret astfel: a(t), t=0,
1, 2, … , unde a(t)=1GDFHVWHWULPLVXQWDVNODPRPHQWXOt, respectiv, a(t)=0GDFQXV-a
trimis nici un task la momentul t respectiv. Presupunem ca procesul este specificat pentru
intervalul t=0, 1, …, 10 DVWIHO^`6LVWHPXOGHFDOFXOIRORVHúWH
XUPWRDUHDUHJXOSHQtru atribuirea task-ului sosit:DOWHUQHD]vQWUHFHOHGRXSURFHVRDUH
primul task fiind atribuit procesorului P1 (cel de-al doilea pentru P2XUPWRUXOSHQWUX31, etc.).
6HSUHVXSXQHFGDFXQWDVNVRVHúWHODRULFDUHGLQWUHSURFHVRDUHúi procesorul este ocupat,
task-XOYDVWDvQúLUXOFRDGDGHDúWHSWDUHDSURFHVRUXOXLcozile dHDúWHSWDUHau capacitate
LQILQLW7LPSXOGHSURFHVDUHDOOXL31 DOWHUQHD]vQWUHXQLWLGHWLPSúLRXQLWDWHGHWLPS
XQLWLGHWLPSSHQWUXSULPXOWDVNH[HFXWDWRXQLWDWHGHWLPSSHQWUXDOGRLOHDWDVNHWFvQ
timp ce pentru procesorul P2 timpXOGHSURFHVDUHHVWHGHXQLWLGHWLPSúLUPkQHFRQVWDQW
Fie y(t)QXPUXOWRWDOGHFOLHQLFDUHDXSOHFDWGHODVLVWHPODPRPHQWXOt, si x1(t) respectiv
x2(t) OXQJLPLOHúLUXULORUGHDúWHSWDUHDOHFHORUGRXSURFHVRDUH31 respectiv P2 (inclusiv task-ul

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
19 vQOXFUX'DFPDLPXOWHHYHQLPHQWHVHSURGXFODPRPHQWXOt valoarea acestor variabile este
GHWHUPLQDWFKLDULPHGLDWGXSFHDXORFHYHQLPHQWHOH
D'HVHQDLRGLDJUDPGHWLPSSHQWUXLQWHUYDOXOt=0, 1, …, 10 LQGLFkQGH[DFWVRVLULOHVúL
SOHFULOHSúWLLQGFODPRPHQWXOLQLLDOFKLDUvQDLQWHGHVRVLUHDSULPXOXLWDVNSHQWUX
SURFHVDUHYDORULOHFR]LORUGHDúWHSWDUHVXQWx1(0)= x2(0)= y(0)=0.
E&RQVWUXLLXQWDEHOFXYDORULOHSHQWUXx1(t), x2(t) si y(t) pentru intervalul t=0, 1, …, 10.
(c3UHVXSXQHPGHDFXPvQFRORFVHOXFUHD]SHGRPHQLXOGHWLPSFRQWLQXX6RVLULOHDX
loc la momentele de timp 0.1, 0.7, 2.2, 5.2 si 9.9. Timpul de procesare pentru P1 DOWHUQHD]
vQWUHúLvQWLPSFHSHQWUXSURFHVXO32 timpul de procesare este de 2.0XQLWLGHWLPS
&RQVLGHUPXQPRGHOFRQGXVGHHYHQLPHQWHFXPXOLPHDHYHQLPHQWHORUE={s, p1, p2} unde s
UHSUH]LQWVRVLUHDXQXLWDVNpiUHSUH]LQWSOHFULGHOD3iL &RQVWUXLLXQWDEHOFX
valorile lui x1(k), x2(k), y(k) si t(k) unde x1(k), x2(k), y(k) sunt OXQJLPLOHúLUXULORUGHDúWHSWDUH
DOHFHORUGRXSURFHVRDUH31, P2VLQXPUXOFXPXODWGHSOHFULGXSFHDDYXWORFHYHQLPHQWXO
k, iar t(k) este momentul în care evenimentul kDDYXWORF'DFDXORFGRXHYHQLPHQWHvQ
DFHODúLWLPSSUHVXSXQHPFSOHFDUHDDUHORFvQDLQWHDVRVLULL&RPSDUDLQXPUXOGH
DFWXDOL]ULQHFHVDUHSHQWUXDFHVWPRGHOFRPSDUDWLYFXFHOFRQGXVGHWLPSFXSDúLGH
PDJQLWXGLQHDXQLWLGHWLPS

5HOXDLSUREOHPDLQkQGFRQWGHcâte una din XUPWRDUHOHGRXUHJXOLGHalocare a
task-XULORUVHSVWUHD]SUHVXSXQHUHDFGDFDXORFGRXHYHQLPHQWHvQDFHODúLWLPS
plecarea are loc înaintea sosirii):
(a) Task-XULOHVHDORFSURFHVRUXOXL31DWkWWLPSFkWúLUXOOXL31GHDúWHSWDUHHVWHPDLPLF
sau egal cu 2, altfel task-ul este alocat lui P2.
E$ORFDUHDVHIDFHSURFHVRUXOXLFXFHOPDLVFXUWúLUGHDúWHSWDUHvQFD]GHHJDOLWDWHWDVN-
ul este alocat lui P2.

8QSURFHVVLPSOXGHSURGXFLHSUHVXSXQHH[LVWHQWDGRXPDúLQL01 si M2úLDXQXL
URERWFDUHPXWFRPSRQHQWHOHIinalizate de M1 la M23HQWUXQLFLXQDGLQWUHPDúLQLQXH[LVW
EXIIHU$VWIHOGDFRFRPSRQHQWHVWHDGXVOD01FkWWLPSDFHDVWDHVWHRFXSDWFRPSRQHQWD
HVWHUHVSLQV3HGHDOWSDUWHGDFURERWXOWUDQVSRUWRSLHVDOD02 în timp ce M2 este
RFXSDWURERWXODúWHDSWSkQFkQG02SRDWHSUHOXDFRPSRQHQW'XSFHFRPSRQHQWDHVWH
SUHOXDWGH02URERWXODUHQHYRLHGHWLPSSHQWUXDSXWHDSUHOXDRDOWSLHVGHODPDúLQD01.
Astfel, M1SRDWHILIRUDWVSVWUH]HRFRPSRQHQWILQDOL]DWúLVQXSUHLDDOWFRPSRQHQW
vQOXFUXSkQFkQGURERWXOHVWHGLQQRXGLVSRQLELO
6WULOHOXL01, M2 si respectiv a robotului sunt descrise de x1, x2úLx33UHVXSXQkQGF
timpul de procesare a M1 este 0.5s, a M2HVWHVúLURERWXODUHQHYRLHGHVVWUDQVSRUWHR
piesGHOD01 la M2UHVSHFWLYDUHQHYRLHGHVVVHvQWRDUFGHOD02 la M1. De asemenea
SUHVXSXQHPFVRVLUHDFRPSRQHQWHORUOD01HVWHSURJUDPDWODúLV
D,GHQWLILFDLWRDWHYDORULOHSRVLELOHVWULOHSRVLELOHSHFDUHOHSRWDYea x1, x2 si x3.
E'HILQLLPXOLPHDHYHQLPHQWHORUEFXQXPUXOFHOPDLPLFGHHYHQLPHQWHSHQWUX
sistem.
F3HQWUXLQWHUYDOXO>@VFRQVWUXLLXQWDEHOFXYDORULOHOXLx1(k), x2(k), x3(k)úLt(k),
unde x1(k), x2(k)úL x3(k)VXQWVWULOHPDúLQLOor M1, M2úLDURERWXOXLGXSFHHYHQLPHQWXOk a

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
20 avut loc, k=1, 2, . . ., úLt(k) este momentul în care evenimentul kDDYXWORF'DFGRX
HYHQLPHQWHDXORFVLPXOWDQSUHVXSXQHPFDvQWRWGHDXQDSULPDGDWVHILQDOL]HD]R
FRPSRQHQWúLDSRLYLQHRDOWDQRX
G,GHQWLILFDLWRDWHVWULOHvQFDUHPDúLQDM1HVWHIRUDWVDúWHSWHSkQFkQGURERWXO
vQGHSUWHD]RFRPSRQHQWILQDOL]DWGHPDúLQDM1.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
21 3. Modele netemporizate pentru modelarea DES. Expresii
UHJXODWHúLDXWRPDWHGHVWUL
3.1. Despre lucrare
Pe SDUFXUVXODFHVWHLOXFUULYRUILUHOXDWHXQHOHQRLXQLGHODFXUVUHIHULWRDUHODPRGHOH
independente de timp care pot fi utilizate în modelarea sistemelor cu evenimente discrete
(Discrete Event Systems – DES)ÌQFDGUXODFHVWHLOXFUULVXQWSURSXVHSUREOHPe care
XWLOL]HD]WHRULDDXWRPDWHORUFXVWULILQLWHLDUvQOXFUDUHDXUPWRDUHYRUILXWLOL]DWHUHHOH3HWUL
3.2. 1RLXQLXWLOL]DWH([SUHVLLUHJXODWHúLDXWRPDWH
'LQWHRULDDXWRPDWHORUFXVWULILQLWHSHQWUXPRGHODUHDQHWHPSRUL]DWD'(6VHXWLOL]HD]
uUPWRDUHOHQRLXQL
· 'DFQRWPFXEPXOLPHDevenimentelorDVRFLDWHXQXLSURFHVVLVWHPúLFRQVLGHUP
DFHDVWPXOLPHXQalfabetDWXQFLVHFYHQHGHHYHQLPHQWHIRUPHD]cuvinteúLUXUL2
VHFYHQGHFXYLQWHIRUPDWHSHED]DDOIDEHWXOXLVHQXPHúWHlimbaj. Un limbaj regulat se
FRQVWUXLHúWHXWLOL]kQGRSHUDLLDVRFLDWHúLUXULORUFRQFDWHQDUHPDUFDWSULQDOWXUDUHIU
RSHUDWRUUHXQLXQHQRWDWFXRSHUDWRUXO* al lui Kleene (notat cu A*úLGHILQLWPDLMRV
unde HVWHúLUXOYLG
· 1 , },{,1 0
0*³ = = =-¥
=nvaloriletoatepentruAAAsiAundeAAnn
nne 
· 3HQWUXGHVFULHUHDúLUXULORUGHHYHQLPHQWHVHIRORVHVFexpresii regulate úLRSHUDLLOH
DVRFLDWHúLUXULORUSUHFL]DWHPDLVXVH[concatenareaHYHQLPHQWHORUúLVHQRWH]FX
reuniunea HYHQLPHQWHORUúLVHQRWH]FXúLoperatorul * al lui.OHHQH*, etc).
· Un DXWRPDWFXVWULILQLWHHVWHXQGLVSR]LWLYFDSDELOVJHQHUH]HXQOLPEDMSHED]D
unor reguli. Este definit de
· PXOLPHDHYHQLPHQWHORUDOIDEHWILQLWE,
· PXOLPHDILQLWDVWULORUX,
· RIXQFLHGHWUDQ]LLHf,
· VWDUHDLQLLDOx0,úL
· FPXOLPHDVWULORUILQDOH
8QúLUHVWHUHFXQRVFXWGHXQDXWRPDWFXVWULILQLWH (E, X, f, x0, F)GDFFDX]HD]R
VHFYHQGHWUDQ]LLLGHODx0ODRVWDUHILQDOx din F7RDWHúLUXULOHFXDFHVWHSURSULHWL
IRUPHD]OLPEDMXOUHFXQRVFXWGH(E, X, f, x0, F)([LVWvQWRWGHDXQDXQDXWRPDWFXVWULILQLWH
FDUHVJHQHUH]HXQOLPEDMUHJXODW

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
22 · ÌQILJXUDHVWHUHSUH]HQWDWGLDJUDPDGHWUDQ]LLHDVWULORUSHQWUXXQDXWRPDWFX
VWULILQLWH

)LJXUD$XWRPDWFXVWULILQLWH([HPSOX

Pentru automatul din figura 3.1 elementele setului (E, X, f, x0, F) care descriu automatul cu
VWULILQLWHsunt:
( ^`
X ={0, 1},
I I I I 
x0 =0VWDUHDLQLLDOPDUFDWFXRVJHDW,
F={1} (În cazul acesta starea 1 esteGXEOXvQFHUFXLWSHQWUXDfi identificaWFDúLVWare
ILQDO),
([SUHVLDUHJXODWFDUHGHVFULHGLDJUDPDGLQILJXUaHVWH
$FHDVWH[SUHVLH
UHSUH]LQWOLPEDMXO/ ^«`DGLFWRDWHúLUXULOHvQFDUHGXS
VDXXUPHD]vQWRWGHDXQD
· 0RGHOXOXQXLDXWRPDWFXVWULILQLWHSRDWHILUHVWUkQVXWLOL]kQGagregareaVWULORU
HFKLYDOHQWHúLvQORFXLUHDORUFXXQDHFKLYDOHQWIUDVHSLHUGHQLFLRLQIRUPDLHAstfel,
GDFDFHODúLúLURDUHFDUHDSOLFDWDWkWGLQVWDUHDxFkWúLGin yvQWRWGHDXQDGXFHODPXOLPHDGH
VWULILQDOHF atunci xúLySRWILFRQVLGHUDWHVWULHFKLYDOHQWH7UHEXLHREVHUYDWFGRX
VWULXQDILQDOúLXQDQX–QXYRUSXWHDILHFKLYDOHQWHúLGDFf(x,e) =yúLf(y,e)=x pt.
orice eveniment e, atunci xúLy echivalente.
· 3HQWUXDIRORVLXQDXWRPDWFDúLPRGHOLQGHSHQGHQWGHWLPSSHQWUXPRGHODUHD'(6
SUHVXSXQHPFEúLXVXQWPXOLPLQXPUDELOHHOLPLQPVSHFLILFDLLOHGHPXOLPHILQLW
pentru FúLLQWURGXFHPGHILQLUHDXQRUPXOLPLGHHYHQLPHQWHSRVLELOH G(x) pentru fiecare
stare x. Modelul rezultat (E, X, G, f, x0, F) este utilizat cu denumirea automat de stare. Setul
care descrie un automat de stare este format din:
E PXOLPHDGHHYHQLPHQWHQXPUDELOH
XVSDLXOVWULORUQXPUDELOH
[PXOLPHDHYenimentelor ‘posibile’ din starea x, x Î;Í E
f IXQFLDGHWUDQ]LLHf: X´E® XGHILQLWvQx doar pentru e Î[
x0VWDUHDLQLLDOx0 Î X.
3.3. Probleme propuse
)LHDOIDEHWXO( ^g`*VLLFHOSXLQR

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
23 (a) expresieUHJXODWDOLPEDMului LSHQWUXFDUHILHFDUHúLUFRQLQHFHOSXLQXQ
(b) expresieUHJXODWDlimbajului L SHQWUXFDUHILHFDUHúLUFRQLQHH[DFWGRL
(c) expresieUHJXODWDlimbajului L SHQWUXFDUHILHFDUHúLUFRQLQHFHOSXLQGRL
GvQFGRX expresii diferite pentru (c).

)LHDOIDEHWXO( ^`3HQWUXILHFDUHGLQSHUHFKLOHFDUHXUPHD]HYDOXDLHFKLYDOHQD
expresiilor. Astfel, ILHGHPRQVWUDLFUHSUH]LQWDFHODúLOLPEDMILHvQFD]FRQWUDULQGLFDLXQ
FXYkQWFDUHDSDULQHXQXLOLPEDMúLQXDSDULQHFHOXLODOW
D





E

 

F
 

G







)LHWUHLOLPEDMH///FX/FDUHQXFRQLQHúLUXOYLG$UWDLFGDF/ //È
L3, atunci L2 = L1* L3.

4. Pe bD]DDOIDEHWXOXL( ^g`VVHFRQVWUXLDVFFkWHXQDXWRPDWFXVWULILQLWHFDUHV
UHFXQRDVF
DOLPEDMXO^ggg}.
EOLPEDMXOUHSUH]HQWDWSULQ
g.
FOLPEDMXOUHSUH]HQWDWSULQ


3RUQLQGGHODDOIDEHWXOOLPELLHQJOH]HVVHFRQVWUXLDVFXQDXWRPDWFXVWULILQLWH, sau
un automat de stare,FDUHVUHFXQRDVFFXYLQWHOHmanúLwoman. ,GHQWLILFDLWRDWHHOHPHQWHOH
VHWXOXLFDUHGHVFULXDXWRPDWXOFXVWULILQLWHUHVSHFWLYDXWRPDWXOGHVWDUHUHSUH]HQWDW

*VLLH[SUHVLDUHJXODWSHQWUXOLPEDMXOUHFXQRVFXWGHXUPWRUXODXWRPDWFXVWULILQLWH

Figura 3.2 . $XWRPDWXOFXVWULILQLWHSHQWUXSUREOHPD

8QFLIUXSHQWUXXQVHLIHVWHSURLHFWDWXWLOL]kQGGRDUFLIUHOHúL&RPELQDLDFDUH
GHVFKLGHVHLIXOFRQVWGLQH[DFWFLIUe, dintre care ultimele 2 identice (doi de 1, sau doi de 0).

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
24 'DFFRPELQDLDQXHVWHFRUHFWVHGHFODQúHD]DODUPD&RQVWUXLLXQDXWRPDWFXVWULILQLWH
FDUHVGHVFULHSURFHVXOGHGHVFKLGHUHDVHLIXOXL

8. Un sistem de calcul XWLOL]HD]GRXSURFHVRDUH3UHVSHFWLY3FDUHIXQFLRQHD]vQ
SDUDOHO/XQJLPHDWRWDODFR]LORUGHDúWHSWDUHLQFOX]kQGHOHPHQWXOSURFHVDWGHVHUYHUSHQWUX
3HVWH. LDUSHQWUX3HVWH. 6LVWHPXOSULPHúWHGRXWLSXULGHMRE-XUL-úL--RE-
urile de tip J1 sunt procesaWHOD3úLFHOHGHWLS-WUHEXLHSURFHVDWHOD3&kQGXQMREHVWH
SURFHVDWHOSUVHúWHVLVWHPXO'DFFRDGDGHDúWHSWDUHHVWHSOLQODVRVLUHDXQXLMREDWXQFL
DFHOMREHVWHUHVSLQV/XQJLPHDFR]LORUHVWHQRWDWFX[úLUHVSHFWLY['HILQLLXQDXWRPat
de stare (E, X, G, f, x0, FSHQWUXVLVWHPúLFRQVWUXLLGLDJUDPDVWULORULQGLFkQGWRDWH
evenimentele posibile.

5HHOH3HWUL0RGHOHQHWHPSRUL]DWHSHQWUX'(6
3UH]HQWDUHDOXFUULL
3HSDUFXUVXODFHVWHLOXFUULYRUILUHOXDWHXQHOHQRLXQLGHODFXUVUHIHULWRDUHODUHHOHOH3HWUL
FDUHSRWILXWLOL]DWHSHQWUXPRGHODUHDQHWHPSRUL]DWDsistemelor cu evenimente discrete
(DES)/DILQDOXOOXFUULLVXQWSURSXVHSUREOHPHXWLOL]kQGUHHOH3HWUL
5HHOH3HWULQHWHPSRUL]DWH5H]XPDWXOQRLXQLORUXWLOLzate
· 5HHOHOH3HWULSRWILIRORVLWHSHQWUXPRGHODUHDQHWHPSRUL]DWD'(63HQWUXGHILQLUHD
5HHOHORU3HWUL53VHXWLOL]HD]
± PXOLPHDILQLWDORFDLLORU (places) piÎP,
± PXOLPHDILQLWDWUDQ]LLLORU (transitions) tjÎT,
± PXOLPHDDUFXULORURULHQWDte AVXEPXOLPHDPXOLPLL(P´T)È(T´P) úL
± RIXQFLHGHJUHXWDWHSRQGHUHw(pi, tj) sau w(tj, pi) DVRFLDWILHFUXLDUF; IXQFLDw fiind
GHILQLWDVWIHOw: A®{ 1, 2, 3, …}.
7UDQ]LLLOHFRUHVSXQGevenimentelorLDUORFDLLOHGHLQWUDUHDOHXQHLWUDQ]Lii sunt asociate
FRQGLLLORUFDUHWUHEXLHvQGHSOLQLWHSHQWUXFDWUDQ]LLDHYHQLPHQWXOVDLEORF

)LJXUD([HPSOXGHUHHD3HWULPDUFDW

3HQWUXUHHDXD3HWULGLQILJXUDVHSRWLGHQWLILFD
± ORFDLLFRQGLLL P ={p1, p2}
± WUDQ]LLLHYHQLPHQWH T ={t1}
± arcuri A ={(p1,t1), (t1,p2)}
± SRQGHULJUHXWL w(p1,t1 úLZW1,p2)=1
± LQWUULLHúLUL I(t1)= {p1}úL O(t1)= {p2}
· &RPSRUWDPHQWXOGLQDPLFDOUHHOHORU3HWULHVWHGHVFULVFXDMXWRUXOXQRUjetoane sau
marcaje WRNHQSODVDWHvQORFDLLOHFDUHSHUPLWUHDOL]DUHDWUDQ]LLLORUORFDLLOHp1 úLS2 din
ILJXUDDXGRXUHVSHFWLYXQMHWRQ$FWLYDUHDúLDSRLGHFODQúDUHDXQHLWUDQ]LLLFDX]HD]
ÄPXWDUHD´MHWRDQHORU6WDUHDXQHLUHHOH3HWULHVWHGHVFULVGHXQYHFWRU>x(p1), x(p2), …,
x(pn)], unde x(pi)HVWHQXPUXOGHMHWRDQHSUH]HQWHvQORFDLDpi.
)XQFLDGHmarcare xHVWHGHILQLWx : P ® {0, 1, 2, …}. t1 p1 p2

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
26 $VWIHOSHQWUXUHHDXD3HWULGLQILJXUDVWDUHDUHSUH]HQWDWHVWHGDWGHQXPUXOGH
jetoane GLQORFDLLx=[2, 1]YDORDUHDSHQWUXORFDLDp1LDUYDORDUHDSHQWUXORFDLDp2.
· 2UHHD3HWULPDUFDWHVWHGHVFULVGHVHWXO37$Z[0), unde
± P ±PXOLPHDILQLWDORFDLLORUpi Î P
± T ±PXOLPHDILQLWDWUDQ]LLLORUti Î T
± A ±PXOLPHDDUFXULORUVXEPXOLPHDPXOLPLL(P´T)È(T´P)
± w ±IXQFLDGHSRQGHUHw: A ® {1, 2, 3, ¼}
– x0 –PDUFDUHDLQLLDO
· 2WUDQ]LLHHVWHYDOLGDWGDFx(pi)³w(pi, tj) QXPUXOGHMHWRDQHDORFDLHLGHLQWUDUH
este mai mare sau egal decât ponderea conexiunii dHODORFDLHODWUDQ]LLDDQDOL]DW pentru
WRDWHORFDLLOHGHLQWUDUHDOHWUDQ]LLHLDQDOL]DWH) pentru toate pi ÎI(ti)ÌQUHHDXDGLQILJXUD
WUDQ]LLDt1HVWHYDOLGDWGHRDUHFHvQORFDLDp1VLQJXUDORFDLHGHLQWUDUHVXQWFHOSXLQ
jetoane (cel pXLQSRQGHUHDFRQH[LXQLL(pi, tj)).
· &kQGRWUDQ]LLHHVWHYDOLGDWHDSRDWHVVHGHFODQúH]HILUHFHHDFHGHWHUPLQ
schimbarea marcajului (úLLPSOLFLWDVWULL
· 3HQWUXRUHHD3HWULGHVFULVGH(P, T, A, w, x0)VHGHILQHúWHIXQFLDGHWUDQ]LLHD
VWUilor fSHQWUXWUDQ]LLDtj ÎT, f:{1, 2, …}n ´ T ® {1, 2, …}nGDFúLQXPDLGDF
(a) x(pi)³w(pi, tj)SHQWUXWRDWHORFDLLOHpi Î I(tj)úL
EGDFf(x, tj)HVWHGHILQLWDWXQFLVWDELOLPx’ =f(x, tj) unde
x’(pi) = x(pi) – w(pi, tj) + w(tj, pi) , i=1, …, n.

· (VWHvQWRWGHDXQDSRVLELOVVHRELQRUHHD3HWULGLQWU-XQDXWRPDWFXVWULILQLWH'HúL
UHHOHOH3HWULVXQWPRGHOHFXFDUHVHOXFUHD]PDLJUHXGDWRULWFRPSOH[LWLLHOHSRWIL
utilizate pentru modelarea unor DES mult mai generale/ample.
· Arborele de acoperire poate fi utilizat pentru rezolvarea multor problemelor
IXQFLRQDOHGHED]OHJDWHGHPRGHODUHDLQGHSHQGHQWGHWLPSD'(6FXPDUILDFRSHULUHD
GHOLPLWDUHDúLFRQVHUYDUHD3HQWUXXQ'(6FXPXOLPHDVWULORUILQLWDUERUHOHGHDFRSHULUH
devine arbore de accesibilitate.

)LJXUD([HPSOXGHUHHD3HWULPDUFDW

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
27 Figurii 4.2 SUH]LQW graful unei UHHOH3HWUL(SDUWHDVWkQJ) úLarborele de acoperire
FRUHVSXQ]WRUîQSDUWHDGUHDSW).
Pentru descrierea arborelui de acoperire se utilizeD]XUPWRDUHOHQRLXQL
– QRGUGFLQ-SULPXOQRGFRUHVSXQ]WRUVWULLLQLLDOH
– nod terminal -QRGGLQFDUHQLFLRWUDQ]LLHQXPDLSRDWHILGHFODQúDW
– nod duplicat -LGHQWLFFXXQDOWXOH[LVWHQWvQDUERUHVSUHFDUHGXFHOLQLDvQWUHUXSW
– dominaQDQRGXULORU -GDF[ >[S1), x(p2), …, x(pn@úL\ >\S1), y(p2), …, y(pn)] sunt 2
VWULQRGXULDOHDUERUHOXLGHDFRSHULUH[GRPLQSH y (scris x >d\GDFVXQWvQGHSOLQLWH
FRQGLLLOH
(a) x(pi) ³ y(piSHQWUXWRLL «Q
(b) x(pi) > y(piPFDUSHQWUXFkLYDL «Q
De exemplu [1, 0, 2, 0] >d [1, 0, 1, 0]GHRDUHFHORFDLDDWUHLDvQSULPDVWDUHGRPLQDQW
SULQQXPUXOGHMHWRDQHGRPLQDGRXDVWDUHFDUHDUHWRWSHQWUXORFDLDDWUHLDGRDUXQMHWRQ
– simbolul , marcaj pentru infinit într-RUHHDQHPUJLQLW>@®>@, când
PDUFDMXODUFUHúWHODLQILQLW
· Algoritmul de realizare a arborelui de acoperire este descris în continuare:
– Pasul 1 – se LQLLDOL]HD]x=x0VWDUHDLQLLDO,
– Pasul 2 – pentru fiecare nod nou se HYDOXHD]IXQFLDGHWUDQ]LLHf(x,tj)SHQWUXWRLtj ÎT,
– Pasul 2.1 –GDFf(x,tj)HVWHQHGHILQLWSHQWUXWRLtj ÎT QLFLRWUDQ]LLHQXHYDOLGDW
atunci x e nod terminal,
– Pasul 2.2 –GDFf(x,tj)HVWHGHILQLWSHQWUXXQLLtj ÎT atunci se FUHHD]QRGQRX
pentru x'= f(x,tj) apoi,
± Pasul 2.2.1 ±GDFx(pi pentru uneleORFDLL pi, se atribuieSHQWUXDFHOHORFDLL
x'(pi ,
– Pasul 2.2.2 –GDFH[LVWXQQRGy pe calea de la nodul x0 la x astfel încât x' >d
y se atribuie x'(pi pentru toateORFDLLOH pi la care x'(pi) >d y(pi),
± Pasul 2.2.3 ± altfel se atribuie x'= f(x,tj),
– Pasul 3 –GDFWRDWHQRGXULOHQRLVXQWRULGXSOLFDWHRULWHUPLQDOHVWRS
$VWIHOUH]XOWXQDUERUHILQLWGHDFRSHULUHSHQWUXUHHDXD3HWUL.
· OUHHD3HWULVHQXPHúWHYLDELO (live(-QHVVGDFLQGLIHUHQWGHPDUFDMXOFDUHDIRVW
atins din x0HVWHSRVLELOFDvQFRQWLQXDUHVVHH[HFXWHRULFHWUDQ]LLHDUHHOHL.
· 2UHHD3HWULSHQWUXDILPUJLQLWQXWUHEXLHVFRQLQDOWIHOUHHDXDDUHXQVSDLX
LQILQLWDOVWULORU
· 2UHHD3HWULHVWHSHUVLVWHQWGDFSHQWUXRULFDUHWUDQ]LLLYDOLGDWHIDSWXOFXQDVH
GHFODQúHD]QXGHWHUPLQLQYDOLGDUHDFHOHLGHDGRXDGDFGRXWUDQ]LLLVXQWYDOLGDWHGH
DFHODúLVHWGHFRQGLLL
· O stare x este DFFHVLELO (reachable) într-RUHHD3HWULGLQx0GDFH[LVWRVHFYHQGH
WUDQ]LLLFDUHvQFHSvQx0DVWIHOvQFkWVWDUHDUHHOHLVGHYLQODXQPRPHQWGDWx.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
28 · O stare y este DFRSHULW (coverable) pornind din x0, GDFH[LVW o secYHQGHWUDQ]LLL
care încep în x0 astfel încât starea devine la un moment dat xúLîn plus x(pi) ³y(pi) pentru
toate i=1, ¼, nDGLFSHUPLWHúLYDOLGDUHDWUDQ]LLLORUdin acea stare).
4.3. Probleme propuse

)LHRUHHD3HWULGHVFULVGH
P={p1, p2, p3, p4},
T={t1, t2, t3},
A= {(p1, t1), (p1, t3), (p2, t2), (p3, t2), (p3, t3), (p4, t3), (t1, p2), (t1, p3), (t2, p2), (t2, p4)},
iar ponderile asociate acestor arcuri sunt 1.
(a) RHSUH]HQWDLUHHDXD3HWULDVRFLDW
(b) Fie x0=[2, 0, 0, 1]VWDUHDLQLLDO,GHQWLILFDLSHQWUXILHFDUHGLQWUHWUDQ]LLLOHUHHOHLGDF
VXQWYDOLGDWHGDFVHSRWGHFODQúDúLGDFGDLQGLFDLFDUHDUILVWULOHXUPWRDUH
F5HSUH]HQWDLDUERUHOHGHDFRSHULUHSHQWUXDFHDVWUHHD

)LHRUHHD3HWULGHVFULVGH
P={p1, p2, p3},
T={t1, t2, t3},
A= {(p1, t1), (p1, t3), (p2, t1), (p2, t2), (p3, t3), (t1, p2), (t1, p3), (t2, p3), (t3, p1), (t3, p2)},
LDUSRQGHULOHDVRFLDWHDFHVWRUDUFXULVXQWH[FHSLHw(p1, t1)=2.
DUHSUH]HQWDLUHHDXD3HWULDVRFLDW
(b) Fie x0 >@VWDUHDLQLLDO,GHQWLILFDLSHQWUXILHFDUHGLQWUHWUDQ]LLLOHUHHOHLGDF
VXQWYDOLGDWHúLGDFGDLQGLFDLFDUHDUILVWDUHDXUPWRDUH
(c) Fie x0 >@VWDUHDLQLLDO$UWDLFvQQLFLRRSHUDLHFDUHXUPHD]vQUHHDXD3HWUL
WUDQ]LLDW1 nu poate avea loc.
(d) Fie x0 >@RDOWVWDUHDLQLLDO$UWDLFvQSDúLLFDUHXUPHD]vQUHHDXD3HWULRUL
DSDUHXQEORFDMDGLFQXVHPDLSRDWHUHDOL]DQLFLRWUDQ]LLHRULVHUHYLQHvQVWDUHDLQLLDO[0.
(e) PentUXSXQFWXOGUHSUH]HQWDLDUERUHOHGHDFRSHULUHúLDQDOL]DLDUERUHOHSHQWUXDFHOHDúL
GHPRQVWUDLL

3. )LHUHHDXD3HWULGHPDLMRVFXPDUFDMXOLQLLDO[0=[1, 1, 0, 2].
D'XSFHVHGHFODQúHD]GRXWUDQ]LLLJVLLRVWDUHSHQWUXFDUHWRDWHWUDQ]LLLOHVXQW
moarte.
E3UHVXSXQHPFGRULPVDSOLFPXUPWRDUHDVHFYHQGHGHFODQúDUHW3, t1, t3, t1, ¼).
$UWDLFQXVHSRDWHUHSHWDDFHDVWVHFYHQODLQILQLW
F,GHQWLILFDLVWDUHD[sUH]XOWDWvQXUPDVHFYHQHLGHGHFODQúDUHW1, t2, t3, t3, t3).

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
29

Figura 4.35HHDXD3HWULSHQWUXSUREOHPD

D'XSFHVHGHFODQúHD]GRXWUDQ]LLLJVLLRVWDUHSHQWUXFDUHWRDWHWUDQ]LLLOHVXQW
moarte.
E3UHVXSXQHPFGRULPVDSOLFPXUPWRDUHDVHFYHQGHGHFODQúDre (t3, t1, t3, t1, ¼).
$UWDLFQXVHSRDWHUHSHWDDFHDVWVHFYHQODLQILQLW
F,GHQWLILFDLVWDUHD[sUH]XOWDWvQXUPDVHFYHQHLGHGHFODQúDUHW1, t2, t3, t3, t3).

3HQWUXGLDJUDPDGHWUDQ]LLHGHPDLMRVILJXUD4), cu E={e1, e2`GHVHQDLUHHDXD3HWUL
FRUHVSXQ]WRDUH$SRL
DLQGLFDLXQSRVLELOPDUFDMSHQWUXILHFDUHGLQFHOHVWUL
EH[LVWVWULSHQWUXFDUHQLFLRWUDQ]LLHQXHVWHYDOLGDW"

Figura 4.4'LDJUDPDGHWUDQ]LLHDVWULORUSHQWUXSUREOHPa 4.

0, 1, 2, 3, 4, 5, e1

e2
e1

e2
e1

e2
e1

e2
e1

e2
t3
t1
t4 t2 p1
p2 p3 p4

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
30 4.4. UtilizDUHDDSOLFDLHLPIPE (Platform Independent Petri Net Editor)
ÌQDFHDVWVHFLXQHGXSFHVWXGHQLLV-DXIDPLOLDUL]DWWHRUHWLFFXGLQDPLFDUHHOHORU3HWUL
XUPHD]VXWLOL]H]HSHQWUXYHULILFDUHRDSOLFDLH care permite vizualizarea VFKLPEULORUGH
VWDUHvQUHHOHOH3HWUL
Pentru aceasta s-DDOHVRDSOLFDLH2SHQ6RXUFH1 care permite rularea pe diferite sisteme de
operare.

Figura 4.5. PIPE2 (Platform Independent Petri Net Editor)

ÌQILJXUDHVWHSUH]HQWDWIHUHDVWUDDSOLFDLHi PIPE cu un exemplu de reprezentare,
H[HPSOXGLQWUHFHOHGLVSRQLELOHvQFDGUXODSOLFDLHL.ÌQDFHVWH[HPSOXWUDQ]LLLOHGLQILJXU
VXQWWHPSRUL]DWHILLQGUHSUH]HQWDWHFXDMXWRUXOXQRUGUHSWXQJKLXULLDUFHOHFRORUDWHvQURúX
sunt validate. În partea de MRVVWkQJDHVWHLQGLFDWLVWRULFXOWUDQ]LLLORU, pentru exemplul dat
GXSPDUFDMXOLQLLDODDYXWORFRGHFODQúDUHDWUDQ]LLHL7
$SOLFDLD3,3(SHUPLWHUHSUH]HQWDUHDUHHOHORU3HWULWHPSRUL]DWH (care sunt discutate în alte
OXFUULGDUúLDFHORUnetemSRUL]DWH3HQWUXDFHDVWOXFUDUHVHIRORVHVFGRDUUHHOHOH
QHWHPSRUL]DWH$SOLFDLDSHUPLWHUHSUH]HQWDUHDXQHLUHHOH3HWULúLDSRLSRDWHILYL]XDOL]DW
GLQDPLFDDFHVWHLD$VWIHOVHSRWSODVDMHWRDQHvQORFDLLOHUHSUH]HQWDWHúLSHED]DDFHVWRU
marcaje trDQ]LLLOHYDOLGDWHvúLVFKLPEFXORDUHD&XXQFOLFNSHRULFDUHGLQWUHWUDQ]LLLYDOLGDWH
VHGHFODQúHD]WUDQ]LLDLQGLFDW
$SOLFDLDSHUPLWHJHQHUDUHDPDWULFHLGHLQFLGHQúLGHDVHPHQHDDJUDIXOXLDUERUHOXLGH
acoperire cum se poate vedea în exemplul din figura 4.6. Pentru fiecare nod al grafului se
SRDWHYHGHDFDUHVXQWQRGXULOHSULQFDUHSXWHPDMXQJHvQDFHDVWDUHUHVSHFWLYFDUHVXQWVWULOH
care pot urma –vQIXQFLHGHWUDQ]LLDGHFODQúDW

1$SOLFDLD PIPE2 (Platform Independent Petri Net Editor)HVWHGLVSRQLELOSDJLQDDIRVWXOWLPDGDW
DFFHVDWvQQRLHPEULHSHKWWSSLSHVRXUFHIRUJHQHW

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
31

Figura 4.6. PIPE permite reprezentarea arborelui (graf-ului) de acoperire

$VWIHOVWDUHD6HVWHFHDFDUHDUHPDUFDMXOLQLLDO>@úLYDOLGHD]DPEHOHWUDQ]LLL7úL
7GHIDSW7HVWHvQWRWGHDXQDYDOLGDW'LQVWDUHD6VHSRDWHDMXQJHvQVWDUHD6GDFVH
GHFODQúHD]WUDQ]LLD7UHVSHFWLYvQVWDUHD6GDFVHGHFODQúHD]WUDQ]LLD7GXSFXPVH
SRDWHYHGHDúLGLQGHVFULHUHDDVRFLDWVWULL6ÌQSOXVVHSRDWHYHGHDFVWDUHD6DUH
marcajul []GHRDUHFHGHFODQúDUHDWUDQ]LLHL7LQFUHPHQWHD]QXPUXOGHPDUFDMHSHQWUX
DPEHOHORFDLLODLQILQit. .
4.5. Probleme suplimentare utilizând PIPE
1. 3HQWUXvQFHSXWLGHQWLILFDLRSLXQLOHGHHGLWDUHDUHHOHORU3HWULXWLOL]kQGDSOLFDLD3,3(
'XSDFHHDUHSUH]HQWDLRUHHD3HWULla alegere.
D3ODVDLPDUFDMHvQORFDLLOHUHHOHLúLDQDOL]DLGLQDPLFa acesteia comparând studiul
WHRUHWLFFXUH]XOWDWHOHDSOLFDLHL
E*HQHUDLJUDIXOGHDFRSHULUH$QDOL]DLUH]XOWDWXO
8WLOL]kQGSUREOHPHOHSURSXVHvQVHFLXQHDúLFRPSDUkQGUH]XOWDWHOHRELQXWHDQDOLWLF
FXFHOHJHQHUDWHGHDSOLFDLHYHULILFDLUH]XOWDWHOHRELQXWHFXDMXWRUXODSOLFDLHL3,3(

5. Modele temporizate pentru DES
5.1. Prezentarea lucrrii
3HQWUXPRGHODUHDWHPSRUL]DWDsistemelor cu evenimente discrete (DES) se pot utiliza atât
DXWRPDWHWHPSRUL]DWHFkWúLUHHOH3HWULWHPSRUL]DWH'XSUHOXDUHDXQRUQRLXQLGHODFXUV
UHIHULWRDUHODPRGHOHOHWHPSRUL]DWHvQVHFLXQHDVXQWSURSXVHSUREOHPH
5.2. $XWRPDWHúLUHHOH3HWULWHPSRUL]DWH
· 8QDXWRPDWGHVWULWHPSRUL]DWHVWHXQDXWRPDWGHVWULFDUHFRQLQHúLRVWUXFWXUGH
temporizareVWUXFWXUGHWLPS6WUXFWXUDGHWLPSHVWHRPXOLPHDOFWXLWGLQVHFYHQHFkWH
una pentru fiecare eveniment, definind GXUDWDGHYLDDHYHQLPHQWXOXLúLUHSUH]HQWkQG
LQWUDUHSHQWUXPRGHOXOWHPSRUL]DW$FHVWHLQIRUPDLLVXQWXWLOL]DWHSHQWUXDJHQHUDVHFYHQD
GHHYHQLPHQWHFDUHGHWHUPLQSDUFXUJHUHDDXWRPDWXOGHVWUL

Figura 5.1. 'LDJUDPGHWLPSFXXQHYHQLPHQWSHUPDQHQWDFWLY

3HQWUXGLDJUDPDGHWLPSGLQILJXUDDYHPXUPWRDUHOHDVSHFWHFXQRVFXWH
E={}úL[ {}SHQWUXWRL[Î X,
evenimentele sunt e1, e2« úLDXORFODPRPHQWHOHt1, t2, ¼úLVHSRWGHILQLunele
QRLXQL.
Intervalul dintre 2 evenimente consecutive VHQXPHúWH GXUDWDGHYLD definit pentru figura
5.1 astfel vk=tk – tk-1, k=1, 2, ¼ cu vkÎR+.
Evenimentul k este validat/activat la momentul tk-1ILLQGSRVLELOvQVWDUHDUHVSHFWLY. La
momentul tk HYHQLPHQWXODUHORFúLse definesc:
yk= tk-t timpul evenimentului k, sau timpul rezidual,
zk= t-tk-1 vârsta evenimentului k.
'LDJUDPDGHWLPSHVWHFRPSOHWGHILQLWGHvQúLUXLUHDWXWXURUGXUDWHORUGHYLD{v1, v2, ¼}.

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
34 · Un automat de stare temporizat se notHD] cu (;I[0, V), unde
E este PXOLPHDGHHYHQLPHQWHX este VSDLXOVWULORUQXPUDELOHx0VWDUHDLQLLDO,
[PXOLPHDHYHQLPHQWHORUµSRVLELOH¶GLQVWDUHDx, x Î;Í E,
fIXQFLDGHWUDQ]LLHf: X´E ® XGHILQLWvQX doar pentru e Î[,
V={vi: i Î E} structura de timp (de temporizare).
· Într-XQDXWRPDWGHVWULWHPSRUL]DWXQHYHQLPHQWe este validatGDFWRFPDLDDYXWORF
úLUPkQHSRVLELOvQVWDUHDXUPWRDUHVDXGDFXQDOWHYHQLPHQWDUHORFFkWWLPSe nu este
SRVLELOúLvQQRXDVWDUHe este posibil. De câte ori un eveniment este activat, timpului lui i se
DWULEXLHYDORDUHDFRUHVSXQ]WRDUHGXUDWHLGHYLDGLQVWUXFWXUDGHWLPSDVRFLDW
· Un eveniment e este invalidat/dezactivatFkQGXQDOWHYHQLPHQWDUHORFúLGHWHUPLQ
WUDQ]LLDVSUHRVWDUHXQGHeQXHVWHSRVLELO'DFXQHYHQLPHQWHVWHdezactivat atunci timpul
asociat este ignorat.
· (YHQLPHQWXOGHFODQúDWRUSHQWUXRDQXPLWVWDUHHVWHFHOFXFHDPDLPLFYDORDUHD
timpului dintre evenimentele validate.
· 3HQWUXDDQDOL]DUHHOH3HWULWHPSRUL]DWHVHLQWURGXFHVHFYHQDGHWHPSRUL]DUH vj
DVRFLDWWUDQ]LLLORUtj6HXWLOL]HD]XQQXPUSR]LWLYUHDOvj,k asociat lui tj care are
XUPWRDUHDVHPQLILFDLH: cândWUDQ]LLDtj HVWHDFWLYDWGHk RULHDQXVHGHFODQúHD]LPHGLDW
SUH]HQWkQGRvQWkU]LHUHDGHFODQúULLGDWGHvj,k; pe durata acestei întârzieri jetoanele sunt
SVWUDWHvQORFDLLOHGHLQWUDUHDOHWUDQ]LLHLtj. 1XWRDWHWUDQ]LLLOHDXvQWkU]LHULvQGHFODQúDUH
vQWkU]LHUH]HURDFHVWHWUDQ]LLLDSDULQVHWXOXLGHWUDQ]LLLFXvQWkU]LHUH]HURÎT0. Cele cu
întârzieri sunt numite WUDQ]LLLWHPSRUL]DWHÎTD, unde T= T0 È TD.
· ÌQUHSUH]HQWDUHDJUDILFWUDQ]LLLOHWHPSRUL]DWHVXQWQRWDWHFXDMXWRUXOXQRU
dreSWXQJKLXULVSUHGHRVHELUHGHFHOHQHWHPSRUL]DWHQRWDWHFXREDULDUGXUDWDGHYLDD
WUDQ]LLHLHVWHQRWDWGHRELFHLOkQJGUHSWXQJKL
· 2UHHD3HWULWHPSRUL]DWHVWHGHILQLWFXDMXWRUXOVHWXOXL37$Z[9
P –PXOLPHDILQLWDVWULORUpi Î P,
T –PXOLPHDILQLWDWUDQ]LLLORUti Î T= T0 È TD,
A –PXOLPHDDUFXULORUVXEPXOLPHDPXOLPLL(P´T)È(T´P),
w –IXQFLDGHSRQGHUHw: A ® {1, 2, 3, ¼},
x ±PDUFDUHDLQLLDO,
V ±VWUXFWXUDGHWLPSDUHHOHLPDUFDWHVHFYHQDGHWHPSRUL]DUHVÎ{vj : tjÎ TD}.

Figura 5.2. RHHD3HWULWHPSRUL]DW Exemplu

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
35
· ÌQILJXUDVHSRDWHREVHUYDWUDQ]LLDWHPSRUL]DWt2 care are o întârziere de
GHFODQúDUHviÌQDFHODúLJUDIWUDQ]LLDt1QXHVWHWHPSRUL]DW
5.3. Probleme propuse
1. 6HDQDOL]HD]XQVLVWHP'(6FDUHDUHVSDLXOVWULORU;= {x1, x2, x3`PXOLPHD
evenimentelor ( ^g}úLGLDJUDPDWUDQ]LLLORUSUH]HQWDWvQILJXUD. Se presupuneF
evenimentele sunt planificate la momentele de timp (0., 1., 2.3, 5.6),HYHQLPHQWHOHVXQW
planificate la momentele de timp (0.2, 3.1, 6.4, 9.7) iar evenimentele g sunt planificate la
momentele de timp (2.2, 5.3).

Figura 5.3. 'LDJUDPDWUDQ]LLLORUSHQWUXXQ'(6

D3UHVXSXQkQGF[1HVWHVWDUHDLQLLDOVVHFRQVWUXLDVFRGLDJUDPGHWLPSSHQWUX
seFYHQDGHHYHQLPHQWHdin intervalul [0., 10.]. Se vor indica momentele în care apar
HYHQLPHQWHWLSXOORUúLVWDUHDVLVWHPXOXLSHQWUXRULFHLQWHUYDOGLQWUHHYHQLPHQWHQX
trebuiesc reprH]HQWDWHVWULOHSHQWUXWRDWHPRPHQWHOHGHWLPS).
EÌQFHUFDLSHED]DGLDJUDPHLGHWLPSGHODSXQFWXODVHVWLPDLFDUHHVWHvQJHQHUDO
SUREDELOLWDWHDFDVLVWHPXOVILHvQVWDUHDx2.

2. RHHDXD3HWULGLQILJXUDPRGHOHD]H[HFXLDXQXLWDVN73. VLPXOWDQFXGRXWDVN-uri
VHFYHQLDOH71úL72 iar task-ul T4 comELQUH]XOWDWHOHGHOD73úL72GXSFXPVHSRDWH
observa în figura 5.4.

Figura 5.4. Sistem cu task-XULUHDOL]DWHVHULDOúLvQSDUDOHO

PresupunemFGRULPVVLPSOLILFPPRGHOXOSULQHOLPLQDUHDWUDQ]LLHLW23 astfel încât
WUDQ]LLLOHW2úLW3VSRDWSODVDXQMHWRQGLUHFWvQORFDLDp4úLvQSOXVDWULEXLQGJUHXWDWHD
arcului (p4, t4).
(a) (VWHSRVLELODFHDVWPRGLILFDUH"$UJXPHQWDLUVSXQVXO

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
36 E3HQWUXUHHDXD3HWULGLQILJXUDVFULHLXQVHWGHHFXDLLUHFXUVLYHSHQWUXPRPHQWHOH
GHGHFODQúDUHDWUDQ]LLLORU

Figura 5.5. 5HHD3HWULWHPSRUL]DW

F6VHUHSHWHSUREOHPDESHQWUXPRGHOXOPRGLILFDW&DUHHVWHGLIHUHQDvQDFHVWFD]"

6. Modelarea unor procese economice utilizând ODQXUL0DUNRY
6.1. Analiza proceselor stohastice utilL]kQGODQXUL0DUNRY

AFHDVWOXFUDUHDGUHVHD]DSOLFDLLOHPRGHOULLúLVLPXOriiÌQOXFUDUHVHDQDOL]HD] un
exemplu de utilizare a /DQXUL0DUNRY vQGRPHQLXOSURJQR]HLGHPDUNHWLQJ/DQXULOH
Markov sunt modele cDUHSHUPLWPRGHODUHDVWRKDVWLF. Chiar dDFVHIRORVHúWHXQPRGHO
VLPSOLILFDWVFRSXOHVWHVVXEOLQLHPXWLOLWDWHDPRGHOULL
ÌQDFHDVWOXFUDUHXWLOL]PGRDUODQXUL0DUNRYvQWLPSFRQWLQXX– DTMC (Discrete Time
Markov Chain) pentru studiul de caz.
Prin lDQ0DUNRYVHvQHOHJHRVHFYHQ de variabile aleatoare X1, X2, X3, … care au
proprietatea lui Markov. Proprietatea lui MarkovSRDWHILH[SULPDWvQPDLPXOWHPRGXUL
„GDWDILLQGVWDUHDSUH]HQWDVWDUHDYLLWRDUHúLVWDUHDWUHFXWVXQWLQGHSHQGHQWH´ sau „starea
XUPWRDUHHVWHGHWHUPLQDWGHVWDUHDFXUHQW´.
Toate valorile XiSRVLELOHIRUPHD]PXOLPHDVWULORU6GHQXPLWVSDLXOVWULORU. De
exemplu, simplificat, starea vremii poate fi: însorit, (cer acoperit) noros, ploaie. În figurile 6.1
este reprezentat graful orientat, tabelul de corespoQGHQúLVWDUHDLQLLDO

Figura 6.1. Modelare simpliILFDWSHQWUXSURJQR]PHWHR0DWULFHDWUDQ]LLLORUúLYHFWRUXOLQLLDO

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
38 /DQXULOH0DUNRYVXQWGHVFULVHFXDMXWRUXOJUDI-urilor orientate. Pe arce pot fi notate
SUREDELOLWLOHGHWUDQ]LLH.
PUREDELOLWLOHGHWUDQ]LLHsunt descrise cu o PDWULFHDWUDQ]LLLORUÌQDFHDVWPDWULFHD
WUDQ]LLLORUVXPDLQWUULORUSHFRORDQHUkQGXUL .
6HPDLGHILQHúWHYHFWRUXOLQLLDO sau GLVWULEXLDLQLLDO care este starea la momentul 0, în
cazul figurii 6.1 este vectorul de jos.
$úDFXPVSHFLILFQXPHOHDTMC (Discrete Time Markov Chain)FRQVLGHULQWHUYDOHGH
timp discret. (H[ODLQWHUYDOHGHWLPSW).
DTMC sunt caracterizate cu ajutorul unei matrice a WUDQ]LLLORUSHQWUXXQSDVGLDJUDPD
WUDQ]LLLORU (matricea P, dimensiuni NxN cu elementele pij – UHSUH]LQWSUREDELOLWDWHDWUDQ]LLHL
din starea i in starea j, intr-un pas). DXSnSDúL, SULQPXOWLSOLFDUHDPDWULFHLFXHDvQVúLFkQG
n tinde la infinit RELQHPPDWULFHDVWDLRQDU. În cazul figurii 6.1 matULFHD3HVWHGDWOD
mijlocul figurii.
(YLGHQWH[HPSOXOGLQILJXUDLJQRUDOLIDFWRULFOLPDWLFLFDUHLQIOXHQHD]SURJQR]D
YUHPLLFXUHQLLGHDHUHWF
0102030405060
1 2 3 4 5 6
zileprocenteinsorit noros ploaie

)LJXUD(YROXLDGXSSDúLDH[HPSOXOXLGLQILJXUD

)LJXUDSUH]LQWHYROXLDUH]XOWDWHOHSURFHVXOXLGHHYDOXDUHVXFFHVLYDSURJQR]HLSHQWUX
exemplul din figura 6.1. Vectorul LQLLDODIRVWvQPXOLWFXPDWULFHDWUDQ]LLLORUSHQWUXDRELQH
HYDOXDUHDSHQWUXSULPD]LúLDSRLUH]XOWDWXORELQXWILLQGGLQQRXvQPXOLWFXPDWULFHD
tran]LLLORUSHQWUXDRELQHHYDOXDUHDSHQWUX]LXDDGRXDHWF'LVWULEXLDVWDLRQDUDUHWRDWH
FHOHWUHLSUREDELOLWL.
6.2. DTMC – Studiu de caz. (YROXLDSRQGHULLGHSLDD1

ÌQDFHDVWVHFLXQHHVWHSUH]HQWDWXQVWXGLXGHFD]SHQWUXRDQDOL]DHYROXLHLSRQGHULLGH
SLDDXQRUSURGXVHFRQFXUHQLDOH

1&5DLX-Suciu, F. Luban, D. Hîncu, M. Sarchiz, Modelarea si simularea proceselor economice, Ed.
DidaFWLFúLSHGDJRJLF%ucuresti, 1997

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
39 ÌQDFHVWVWXGLXGHFD]VHSUHVXSXQHFDYHPWUHLSURGXVHFRQFXUHQWHGHSHSLDDSURGXVHORU
cosmetice pentru copii. Cele trei produse le vom identifica cu C1, C2 respectiv C3. Cota de
SLDDILHFUXLSrodus este 35% pentru produsul C1, 45% pentru produsul C2, úLUHVSHFWLY
20% pentru produsul C3.
&RHILFLHQWXOGHILGHOLWDWHGHODROXQODDOWDHVWHFRQVWDQWúLDQXPH% dintre
FXPSUWRULLDFWXDOLDLSURGXVXOXL&UPkQILGHOLDFHVWXLSURGXV%UPkQ fideli
produsului C2 respectiv 75%UPkQILGHOLSURGXVXOXL&&HLODOLFXPSUWRULVHUHRULHQWHD]
VSUHFHOHODOWHSURGXVHGLVSRQLELOHGXSFXPVHSRDWHREVHUYDvQWDEHOXO

7DEHOXO5HRULHQWULDOHFOLHQLORU

5HRULHQWUL Produs
µSUVLW¶
C1 C2 C3
C1 – 20 25
C2 15 – 20
C3 10 15 –

&RQVLGHUkQGFRQVWDQWHSUREDELOLWLOHGHWUDQ]LLHVHDQDOL]HD]HYROXLDSRQGHULLGHSLDD
FHORUWUHLSURGXVHSHQWUXúDVHOXQL
3HED]DDFHVWXLVWXGLXVHSRWIDFHHYDOXULDOHHYROXLHLúLDVWIHOSRWILstabilite politici
manageriale potrivite pentru fiecare produs în parte la firma la care este produs/distribuit.
$VWIHOVHúWLX
3RQGHUHDSHSLDDDSURGXVH (ODXQPRPHQWGDWLQLLDO –DGLFFRWDGHSLDLQLLDO
5H]XOWDWHOHXQXLVRQGDMGHSLD(dLQFDUHVUH]XOWHRSLXQHDFXPSUWRULORUSHQWUX
XUPWRDUHOHSHULRDGHGHWLPS –DGLFPDWULFHDGHUHRULHQWDUHDFOLHQLORU
MRGHODUHFXODQXUL0DUNRYXWLOL]HD]PDWULFHDVWRKDVWLF (matricea de reorientare a
FOLHQLORUvQFDUHV-DXLQVHUDWSUREDELOLWLOHFHORUILGHOLúLGLVWULEXLDLQLLDODGLFFRWDGH
SLDLQLLDO
(WDSHOHVXQWXUPWRDUHOH
VHFRQVWUXLHúWHPDWULFHDSUREDELOLWLORUSHED]DFRHILFLHQLORUGHILGHOLWDWHúLDWDEHOXOXL
GHUHRULHQWDUHÌQDFHDVWPDWULFHWRDWHYDORULOHVXQWSR]LWLYHúLVXPDORUHGDF
XWLOL]PSURFHQWSHQWUXILHFDUHOLQLH
÷÷÷
øö
ççç
èæ
=
75.015.010.020.065.015.025.020.055.0
P
2. VHVFULHGLVWULEXLDLQLLDOVXEIRUPDXQXLYHFWRUXOOLQLHIRUPDWGLQFRWDGHSLDLQLLDO
( )20.045.035.0=a
VHGHWHUPLQFRWDGHSLDGXSSULPDSHULRDGvQPXOLQGGLVWULEXLDLQLLDOFXPDWULFHD
SUREDELOLWLORU$FHVWUH]XOWDWYDvQORFXLGLVWULEXLDLQLLDOvQFDOFXOXOFRWHLGHSLDSHQWUXDO
GRLOHDLQWHUYDOGHWLPS6HFRQWLQXSHQWUXWRWLQWHUYDOXODQDOL]DW

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
40 Astfel pentru acest exemplu avemGXSROXQ:
( )3275.03925.028.0=´Pa
,DUGXSGRXOXQL
( )3941.03602.02455.0=´´PPa
ÌQILQDOVHRELQH

00.10.20.30.40.5
M1 M2 M3 M4 M5 M6 M7
Momente de timpPonderi pe piataC1 C2 C3

)LJXUD(YROXLDpentruOXQLDFRWHLGHSLDXWLOL]kQGODQXUL0DUNRY

3HED]DDFHVWRUFRWHVHSRDWHGHFLGHUHGXFHUHDGHSUHSHQWUXSURGXVHOH&úL&SHQWUXD
FUHúWHYkQ]ULOHVDXGDFQXVHSRDWHVHUHQXQODGHVIDFHUHDORU
6.3. Studii propuse
8WLOL]kQGHWDSHOHGHVFULVHvQVHFLXQHDDQWHULRDUVVHIDFRDQDOL]DHYROXLHLSHSLD
DWUHLSURGXVHúWLLQGXUPWRDUHOH
• produsul P1,FRQFXUHQWFX3úL3SURGXVHVLPLODUH
• GXSXQVWXGLXGHPDUNHWLQJDXUH]XOWDWXUPWRDUHOH
ƒ ILUPDGHLQHRSRQGHUHGHGLQSLD
• FRPSDUDWLYFXúLUHVSHFWLYFRQFXUHQD
ƒ H[LVWRUHODWLYVWDELOLWDWHDSUHIHULQHORUFRQVXPDWRULORU
• 80% din FHLFHDXDFKL]LLRQDW3YRUFRQWLQXDV-ODFKL]LLRQH]HSW3
úL3SURSRULDFXPSUULORUILGHOLILLQGGHUHVSHFWLY
• UHRULHQWULOHVXQWvQWDEHOXO.
3UHVXSXQkQGFQXDSDUPRGLILFULSHSLDVHGRUHúWHFXQRDúWHUHDHYROXLHLSRQGHULLGH
piDDFHORUSURGXVHSHQWUXXUPWRDUHOHPRPHQWHGHWLPS'HDVHPHQHDVHSUHVXSXQH
FRQVWDQWQXPUXOGHSURGXVHúLQXPUXOGHFRQVXPDWRUL PURSXQHLVROXLLSHQWUXSURGXFWRUL

7HKQLFLGHPRGHODUHúLVLPXODUH–ÌQGUXPWRUGHODERUDWRU
41
Tabelul 6.25HRULHQWULDOHFOLHQLORU

5HRULHQWUL Produs
µSUVLW¶
P1 P2 P3
P1 – 10 % 10 %
P2 35 % – 15 %
P3 10 % 15 % –

2. 3UHVXSXQHPFSHRSLDVXQWWLSXULGHFDOFXODWRDUH3&3&3&6HúWLX
XUPWRDUHOH
ƒ FRWDGHSDUWLFLSDUHvQWRWDOXOSLHHLúL
ƒ GLQVRQGDMHOHHIHFWXDWHDXUH]XOWDWFOLHQLILGHOL
• 65% pentru PC1, 75% pentru PC2, úLSHQWUX3&
• FHLODOLFOLHQLVHUHRULHQWHD]FRQIRUPWDEHOXOXL6.3.

Tabelul 6.35HRULHQWULDOHFOLHQLORU pentru problema 2.

5HRULHQWUL Produs
µSUVLW¶
P1 P2 P3
P1 – 15 20
P2 15 – 10
P3 5 10 –

SHFHUHVDQDOL]DLHYROXLDSRQGHULLSHSLDDSURGXVHlor pentru minim 3 luni
SUHVXSXQkQGFRQVWDQWHSUREDELOLWLOHGHWUDQ]LLH. Care ar fi propunerile d-YRDVWUSHQWUXD
îmbXQWLVLWXDLDFHORUFDUHSLHUGGLQSRQGHUHDGHSLD?

Bibliografie
Discrete Event Systems: Modeling and Performance Analysis, Christos G. Cassandras,
Richard D Irwin, 1993.
Modelarea úi simularea proceselor economice, M. Stoica, I. Ionita, M. Botezatu, Ed.
Economica, Bucureúti, 1997.
Modelarea úi simularea proceselor economice, &5DLX-Suciu, F. Luban, D. Hîncu, M.
Sarchiz, Ed. 'LGDFWLFúLSHGDJRJLF%ucuresti, 1997.
$SOLFDLLDOHUHHOHORU3HWULvQVWXGLHUHDVLVWHPHORUFXHYHQLPHQWHGLVFUHWH, Octavian
3VWUYDQX0LKDHOD0DWFRYVFKL&ULVWLDQ0DKXOHD(GLWXUD*K$6$&+,.
Introduction to Computational Science: Modeling and Simulation for the Sciences, Angela
B. Shiflet & George W. Shiflet, Princeton University Press, 2006.
Introduction to Discrete Event Systems, second edition, Christos G. Cassandras &
Stephane Lafortune, Springer, 2008.