Instructori:

Modelarea sistemelor de calculModelarea sistemelor de calculCurs, anul III Calculatoare

Instructori: Prof.dr.ing. Mihai Mocanu Conf.dr.ing.Ileana NicolaeE-mail: mocanu@software.ucv.roOre curs: Joi 16:00-18:00Ore consultatie (la cerere): Joi 14:00-16:00Pagina curs: http://software.ucv.ro/~mocanu_mihai/(pe intrarea corespunztoare cursului, introducei user/pasw)

Obiectul cursuluiDomeniul distinct de studiu/cercetare al modelariisi simularii (M&S) face parte din zona disciplineloringineresti generale (management ingineresc)n Termenii modelare si simulare sunt deseori utilizati

alternativ conceptualizarea si implementarea (M&S) alternativ conceptualizarea si implementarea (M&S) sunt activitati mutual dependente ce pot fi conduseinsa si independent (de indivizi diferiti)

O definitie generala a obiectului M&S:n Modelarea si simularea (M&S) consta in utilizarea de

modele, inclusiv emulatoare, prototipuri, simulatoareetc, fie static sau in timp, pentru a dezvolta date si a le folosi apoi ca baza pentru luarea unor decizii (tehnicesau manageriale)

Locul cursului

Operations Research*

Software

Physics

Mathematics Control Theory

Artificial Intelligence

Numerical and Symbolic

ComputationGraphics &

Visualization

Systems Engineering

Computer Science

Software Engineering

Modeling & Simulation

Zone de cunostinte conexe

Fundamente necesareProgramarea calculatoarelor

Tehnici de programare

Metode numerice

Algoritmi i structuri de dateAlgoritmi i structuri de date

Teoria general a sistemelor dinamiceTeoria probabilitilor i statistica matematicProgramarea orientat pe obiecte

Medii de programare vizual

ObiectiveIntroducerea conceptelor de baz de modelare i simulare discretnsuirea metodelor analitice de modelare pentru sisteme cu cozi de ateptare i reele de coziIntroducerea tehnicilor de modelare, simulare i analiza performantelor pentru sisteme cu evenimente discrete complexe performantelor pentru sisteme cu evenimente discrete complexe Identificarea posibilitilor i limitrilor modelelor matematice, extinderea lor prin simulareUtilizarea unor pachete i biblioteci de programe specializate pentru modelare i simulareDezvoltarea abilitilor de modelare/ simulare a unui sistem nu doar prin exerciii i probleme, ci i prin realizarea unui proiect

Structura cursuluiModelarea analitic a sistemelor discreteProbabiliti i procese aleatoare (review)Teoria elementar a cozilor de ateptareReele de cozi de ateptareReele PetriReele PetriTehnici de aproximareModele de simulare pentru SEDLimbaje si medii de simulareTopici avansaten Simularea paralel si distribuitn Analiza perturbaiilor

Coninutul cursului pe largSisteme dinamicen Sisteme cu evenimente discrete (SED, SDED)Modelarea analitic a SEDn Categorii de modele i nivele de studiun Modele algebrice i logicen Modele algebrice i logicen Modele dinamice: reele Petrin Modele temporale: reele Petri temporizate

Modelarea operaional a SEDn Statistica in modelaren Lanuri i procese Markov i semi-Markov generalizate n Formalismul GSMP ca baz a modelelor de simularen Sisteme cu cozi de ateptare i reele de cozi

Coninutul cursului (cont.)Modele de simulare pentru SEDn Generarea numerelor i variabilelor aleatoaren Construcia i verificarea modelului de simularen Execuia secveniala i analiza simulrilor (ieirilor)n Validarea simulrilor. Estimatori i inferena statistica

Limbaje i medii de simulareLimbaje i medii de simularen Limbaje de simularen Construcia unui simulator. Biblioteci de componenten Metode de accelerare a execuiei simulrilor: simularea paralela

(distribuita), tehnici de gradientAplicaii ale modelarii i simulrii pentru:n Sisteme cu cozi de ateptare i reele de cozin Sisteme de calcul i reele de calculatoare n Sisteme i reele de comunicaii

Referine bibliograficeBanks J., Carson J.S., Nelson A., Nicol D., Discrete-Event System Simulation, 3rd Ed., Prentice-Hall, 2000Cassandras C.G., Discrete Event Systems: Modeling and Performance Analysis, Irwin & Aksen, Boston, 1993Lazowska E.D., Zahorjan J., Scott-Graham G., Sevcik K. Lazowska E.D., Zahorjan J., Scott-Graham G., Sevcik K. C.: Quantitative System Performance - Computer System Analysis Using Queueing Network Models, 1984Sadiku M., Ilyas M.: Simulation of Local Area Networks, CRC Press, 1995Mocanu M., Principii, concepte i instrumente de modelare i simulare in studiul sistemelor dinamice discrete, Ed. Sitech, 2004

NotareaSe face in PV (pct. virtuale, max.100) repartizate astfel: 20% teme practice periodice proiect (P) 20% evaluare continua a activit ii de laborator (L) 20% teste de evaluare (T) 40% examen scris final (E) 40% examen scris final (E)Trebuie s obinei minim 50% din punctaj - minim 10p la

fiecare dintre formele de evaluare pe parcursul semestrului, pentru a putea lua examenul din prima sesiune.

La examenul final, trebuie s ob ine i minim 50% din punctaj (20p) pentru a promova.

Nota reflect curba lui Gauss aplicat punctajului final.

Capitolul I

Sisteme dinamice cu evenimente Sisteme dinamice cu evenimente discrete

Sisteme dinamice: Aspecte calitative

Se are n vedere dezvoltarea de tehnici de proiectare, analiz, control, msurare de performane, bazate pe unele metode i criterii Definiii:Definiii:n un sistem const din componente in interaciunen un sistem este complet descris de funcia asociat,

pe care o ndeplinete prezumptiv [Cas93]n modelul - o reprezentare abstract (o schem, un

set de ecuaii etc.) replicnd, cu un anumit grad de acuratee, comportarea sistemului nsui

Un model matematic general< X, T, U, f, Y, g, R >, unde:

X este mulimea strilor;T este timpul (continuu sau discret);U este domeniul intrrilor admise;f : XxTxUxTX, funcia de tranziie a strilor;f : XxTxUxTX, funcia de tranziie a strilor;Y este domeniul de ieire;g : XxTY este funcia de ieire;R : UxTU este funcia de admisibilitate a intrrii (datorata sau nu unei reacii a sistemului).

Variabile msurabilevariabile de intrare variabile in timp: {u1(t), u2(t), ...}variabile de ieire modificate de sistem ca rspuns: {y1(t), y2(t), ...}.

Daca:u(t) = [u (t), u (t), ..., u (t)]Tu(t) = [u1(t), u2(t), ..., um(t)]Ty(t) = [y1(t), y2(t), ..., yn(t)]T

Modelul matematic general al sistemului, din punct devedere intrare-ieire, este:

y(t) = g(u(t)) = [g1(u1(t), u2(t), ..., um(t)), g2(u1(t), u2(t),..., um(t)),..., gn(u1(t), u2(t), ..., um(t))]T

Clasificarea sistemelor (1)sisteme statice in care toate relaiilefuncionale intrare-ieire pe care le putemconstrui sunt descrise simplu prin ecuaiialgebrice, in care ieirea y(t) este, pentru orice t,independenta de valorile trecute ale intrrii u(t),independenta de valorile trecute ale intrrii u(t),t

Clasificarea sistemelor (2)sisteme invariante in timp: rspunsulintrare-ieire nu depinde de momentulaplicrii intrrii (daca u(t) y(t), atunciu(t+t) y(t+t), "tT);sisteme variabile in timp: rspunsulintrare-ieire depinde de momentul aplicriiintrrii (daca u(t) y1(t), atunci u(t+t) y2(t+t), cu y1(t) y2(t+t) pentru t,tT)

Stare sistemIeirea unui sistem nu este ntotdeauna aceeai atunci cnd se aplic aceeai intrareSimpla observare a ieirii y(t) atunci cnd Simpla observare a ieirii y(t) atunci cnd intrarea u(t) este complet specificat nu conduce la predicia ieirii viitoareDeci starea sistemului difer!

Clasificarea sistemelor (3)Introducerea noiunii de stare este

important pentru nelegerea corect aechilibrului intre influenta factorilor externii interni in rspunsul unui sistem.i interni in rspunsul unui sistem.

Numrul strilor poate fi finit, numrabilsau infinit :

- sisteme cu stri discrete;- sisteme cu stri continue.

Clasificarea sistemelor (4)Nu doar numrul strilor influeneaz

capacitatea de predicie a comportriiviitoare a sistemului pentru o intrare data.

- sisteme deterministe: ieirile sunt- sisteme deterministe: ieirile suntdeterminate complet de stare, intrri imomentul aplicrii;

- sisteme stochastice: cel puin una dintreieiri este variabila aleatoare.

Clasificarea sistemelor (rev.)SISTEME

STATICE DINAMICE

VARIANTE INTIMP

INVARIANTEIN TIMP

LINIARE NELINIARE

CU STARICONTINUE

CU STARIDISCRETE

CONDUSE DETIMP

CONDUSE DEEVENIMENTE

DETERMINISTE STOCHASTICE

Sisteme dinamice cu evenimente discrete

SDED - sistemele dinamice cu evenimente discreteExemple:

Obiect de studiu:

Exemple:liniile de fabricaie/de asamblare reelele de calculatoare i de comunicaiisistemele de dirijare a traficului aerianprocesele de business (supermarket) etc.

Elemente distinctive ale SDEDSisteme artificiale - create de noile tehnologiiSisteme dinamice - prin natura evoluiei interne Starea lor se schimba la momente discrete de timp i nu continuu ca n cazul sistemelor fizice timp i nu continuu ca n cazul sistemelor fizice Evoluia n timp - depinde de interaciunea complexa a momentelor de apariie a diferitelor tipuri de evenimenteNu pot fi descrise prin ecuaii difereniale, cu derivate pariale sau cu diferene finite

SDED - definiiiSisteme dinamice al cror spaiu de stri estediscret i ale cror traiectorii de stare suntconstante pe poriuniMomentele de timp la care tranziiile survin, ca iMomentele de timp la care tranziiile survin, ca itranziiile n sine sunt n general impredictibileTranziiile de stare se numesc evenimenteAcestea dirijeaz mecanismul tranziiilor de stareSDED se deosebesc profund de sistemele cueantionare, obinute prin discretizarea timpului

discrete - privind timpul de referina i spaiul strilor

natura lor discontinu nu mpiedica analiza prin aproximare continua (ex. prin modele de difuzie)

SDED - proprieti

asincrone - raportate la evenimente, nu la timp nedeterministe - generative i capabile de alegeri

interne dei perturbri neplanificate, defectri i cderi

sunt inerente, modelarea determinista este posibila (prin algebra min-max sau reelele Petri)

gradul de complexitate i dimensiunile lor sunt mari:numrul de stri ale unui SDED explodeaz

combinatorialenumerarea strilor duce la sarcini computaionale

inadecvate

SDED proprieti (cont.)

inadecvate sunt modulare - compuse din componente cvasi-

independente pot fi aplicate metode de decompoziie i agregare pot fi echipate cu mijloace de control i comunicare

Modelarea analitica Simularea

Metodologii de studiu:

DE CE studiem un sistem?Scopurin Proiectaren Msurare i controln mbuntire

ModalitiModalitin Studiul sistemului realw Prezint avantajul exactitii obiectului de studiu

n Uneori imposibil, deoarece:w Sistemul real nu existaw Studiul sistemului real poate fi distructiv, periculos

sau costa prea mult

DE CE recurgem la modele?Este necesar ca orice experiment s aib o baz,

dar uneori realitatea nu este construit(absena sistemului real)(absena sistemului real)

alteori realitatea nu este disponibil(lipsa accesului la sistemul real)

Studiul modelelorDe obicei uor, rapid, ieftin, sigur fa de studiul sistemului realPermite ncercarea unor idei i ipotezeSimpla construcie a unui model este instructiv indiferent de utilizarea sa indiferent de utilizarea saValiditatea unui model are in vedere:n similaritatea cu sistemul realn nivelul de detaliu

Numai ea poate garanta concluzii corecte prin studiul modelului in locul sistemului real

Definiii: modelare i modelUn proces de modelare este o etapa preliminara necesara in studiul oricrui sistem, pentru:n calcul analiticn simulare

Un model:Un model:n este o reprezentare abstracta a unui sistemn nu doar o reprezentare a unui sistem - ci i o

simplificare a san totui suficient de detaliata, ca sa permit, prin

studiul sau, concluzii valide asupra sistemului

Modelarea in studiul sistemelor

Tipuri de modeleModele fizice (iconice)n Planuri, scheme, schie necesare in multe domeniin De tip manechin (phantom) in medicinan De tip virtual reality sau augmented reality in

domenii de nalta tehnologie (simulatoare de zbor)domenii de nalta tehnologie (simulatoare de zbor)

Modele matematice (logice)n Aproximeaz modul de operare al unui sistemn Deseori reprezentate printr-un software adecvatn Execuia programului permite ncercri, obinerea de

rezultate, studiul comportamentului modelului

Modelarea predictivEste o modelare in absenta realitii

Exemple:

a) Construcia unei caroserii care trebuie sa satisfac anumite criterii de greutate, rezistenta, geometrice, tehnologicerezistenta, geometrice, tehnologice

b) Studiul performantei unui algoritm in ipoteza implementrii pe o arhitectura inc inexistenta (dar posibila)

c) Experimentarea unor medicamente ce trebuie sa aib unele proprieti speciale

Modelarea restrictivEste modelarea in condiiile restriciilor de acces la un sistem real existent

Exemple:

a) Nu putem opri o reea de calculatoare ce monitorizeaz a) Nu putem opri o reea de calculatoare ce monitorizeaz o centrala nucleara in scopul efecturii de experimente

b) Nu putem opri procese de fabricaie ritmice pentru a experimenta noi metode de management

c) Nu putem perturba circulaia pe o artera aglomerata pentru a decide in ce msura, de exemplu, schimbarea unor reguli de trafic (viteza, prioritatea) este benefica

Studiul modelelor logiceDaca un sistem este destul de simplu, i modelul este simplu, pot fi aplicate metode matematice tradiionalePermit obinerea de rezultate exacte:n Aparatul matematic integro-diferenialn Teoria ateptrii (cozi i reele de cozi)n Teoria ateptrii (cozi i reele de cozi)n Programare liniara

Sistemele complexe pot fi uneori reprezentate de modele analitice simple, validen Presupunerile simplificatoare pstreaz validitatea?

Cel mai adesea, un sistem complex necesit un model complex, metodele analitice nu se aplic ce facem?

Simularea pe calculatorIn sens larg, se refera la metode de studiu ce pp. n evaluare numerica a unor modele de sistemn utilizarea unui model software pentru a mima operaii/

caracteristici sistem, in timpPoate fi validata de studiul modelelor simple, pentru care este disponibila i o soluie analiticapentru care este disponibila i o soluie analiticaPotenial ridicat in studiul modelelor complexeSimularea este foarte utila in studiul unor sisteme complexe, unde nu se ntrevede soluia analiticaFundamente teoretice ale modelelor de simulare:n automatele de stare (stohastice) n procesele semi-Markov generalizate (GSMP)

Acurateea simulrilorPrin simulare nu se obin rspunsuri exacte, doar aproximaii, estimri; totui:n Aceasta nu este o problema specifica, ci una generala

pentru multe alte metode de studiun Erorile pot fi limitate, prin verificare si validare (V&V)n Erorile pot fi limitate, prin verificare si validare (V&V)n Verificarea si validarea sunt compuse din proceduri

integrate in dezvoltarea modelului (de simulare)Ceea ce trebuie evitat este obinerea ieirilor aleatoare (RIRO) din simulri stochastice, prin:n Proiectarea i analiza statistic a experimentelor de

simularen Controlul zgomotului, replicabilitii, eantionrii

secveniale, tehnicilor de reducere a variantei

Verificarea i validarea simulrilorVerificarea simulrii consta in principal in compararea modelului conceptual cu codul programatMetode de verificare a unei simulri: n Compararea modelului implementat cu alte modele, att la nivel

de structura interna cat si de intrare/ ieiren Testarea la nivel de sistem, subsistem sau componente pentru

ndeplinirea cerinelor sau specificaiilor documentate

Validarea unei simulri consta in analiza corespondentei intre model si sistemul realMetode de validare a unei simulri:n Examinarea atenta a ieirilor modelului in condiiile variabilitii

cat mai mari a intrrilor, si compararea cu datele de observaien Execuia repetata a modelului programat

Diversitatea metodelor de simulareCel mai adesea, simularea are loc pentru starea stabila, dupa eliminarea regimurilor tranzitoriiMetode statice vs. dinamicen Ce rol joaca timpul in model?

Metode continue vs. discreteMetode continue vs. discreten starea se poate schimba continuu, sau tranziiile de

stare apar doar la momente discrete in timp?Metode deterministe vs. stochasticen este evoluia sistemului sigura sau exista elemente

de incertitudine?

Majoritatea modelelor operaionale sunt: dinamice, discrete i stochastice

Ex.de simulare manual: estimarea nr.p prin aruncarea acului (Buffon)

Se arunc un ac de lungime L pe o masa cu Se arunc un ac de lungime L pe o masa cu dungi d- echidistante (d >L)P (acul sa taie o linie) = (2*L)/(p*d)Se repet experimentul de un numr mare de ori i se determina R = raportul intre nr. traversrilor i nr. aruncrilorSe estimeaz p prin (2*L)/(R*d)

JustificareAcul poate ateriza in poziii diferite (fig.1)

Orice poziie intre 2 linii se caracterizeaz prin:n Distanta captului acului (interior) fata de cea mai

apropiata linie de deasupra sa (y): 0 < y < dapropiata linie de deasupra sa (y): 0 < y < d

n Unghiul format cu direcia liniilor (): 0 < < p.

Fig.1 Fig.2

Justificare (cont.)Acul intersecteaz linia dac y < Lsin

Perechea (, y) determin in mod unic poziia acului (fr a ine cont de translaii)

Spaiul de eantionare:

Justificare (cont.)

Probabilitatea ca acul sa intersecteze

o linie:

Dup efectuarea calculelor:pp

q=

==

dAdlaturideuluidreptunghiariaLycurbasubdeariaP

:,)sin(

ConcluziiProblema acului (Buffon) pare banal, dar aduce in atenie unele caracteristici de simulare importante:

n Execuia in vederea estimrii unei mrimi dificil de calculat exact (in 1733)

n Factorul aleator, ce face ca estimatorul sa nu fie exactn Factorul aleator, ce face ca estimatorul sa nu fie exactn Posibilitatea estimrii erorii estimatoruluin Replicarea (mai mult=mai bine) pentru reducerea eroriin Eantionarea secveniala pentru controlul erorii repet

aruncarea pana cnd eroarea estimatorului este destul de mica

n Reducerea varianei (crucea Buffon sau tehnica Fox)w n esen, artificii ca rotirea mesei pe care este

aruncat acul pot elimina imperfeciunea aruncrilor