All Coursesas

Instructori:

Modelarea sistemelor de calculModelarea sistemelor de calculCurs, anul III Calculatoare

Instructori: Prof.dr.ing. Mihai Mocanu Conf.dr.ing.Ileana NicolaeE-mail: [email protected] curs: Joi 16:00-18:00Ore consultatie (la cerere): Joi 14:00-16:00Pagina curs: http://software.ucv.ro/~mocanu_mihai/(pe intrarea corespunzătoare cursului, introduceţi user/pasw)

mailto:[email protected]

http://software.ucv.ro/~mocanu_mihai/

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 probabilităţilor şi statistica matematicăProgramarea orientată pe obiecte

Medii de programare vizuală

ObiectiveIntroducerea conceptelor de bază de modelare şi simulare discretăÎnsuşirea metodelor analitice de modelare pentru sisteme cu cozi de aşteptare şi reţele de coziIntroducerea tehnicilor de modelare, simulare şi analiza performantelor pentru sisteme cu evenimente discrete complexe performantelor pentru sisteme cu evenimente discrete complexe Identificarea posibilităţilor şi limitărilor modelelor matematice, extinderea lor prin simulareUtilizarea unor pachete şi biblioteci de programe specializate pentru modelare şi simulareDezvoltarea abilităţilor de modelare/ simulare a unui sistem nu doar prin exerciţii şi probleme, ci şi prin realizarea unui proiect

Structura cursuluiModelarea analitică a sistemelor discreteProbabilităţi şi procese aleatoare (review)Teoria elementară a cozilor de aşteptareReţele de cozi de aşteptareReţele PetriReţele PetriTehnici de aproximareModele de simulare pentru SEDLimbaje si medii de simulareTopici avansaten Simularea paralelă si distribuităn Analiza perturbaţiilor

Conţinutul 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: reţele Petrin Modele temporale: reţele Petri temporizate

Modelarea operaţională a SEDn Statistica in modelaren Lanţuri şi procese Markov şi semi-Markov generalizate n Formalismul GSMP ca bază a modelelor de simularen Sisteme cu cozi de aşteptare şi reţele de cozi

Conţinutul cursului (cont.)Modele de simulare pentru SEDn Generarea numerelor şi variabilelor aleatoaren Construcţia şi verificarea modelului de simularen Execuţia secvenţiala şi analiza simulărilor (ieşirilor)n Validarea simulărilor. Estimatori şi inferenţa statistica

Limbaje şi medii de simulareLimbaje şi medii de simularen Limbaje de simularen Construcţia unui simulator. Biblioteci de componenten Metode de accelerare a execuţiei simulărilor: simularea paralela

(distribuita), tehnici de gradientAplicaţii ale modelarii şi simulării pentru:n Sisteme cu cozi de aşteptare şi reţele de cozin Sisteme de calcul şi reţele de calculatoare n Sisteme şi reţele de comunicaţii

Referințe 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ă obţineţi 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, măsurare de performanţe, bazate pe unele metode şi criterii Definiţii:Definiţii:n un sistem constă din “componente” in interacţiunen un sistem este complet descris de “funcţia” asociată,

pe care o îndeplineşte prezumptiv [Cas93]n modelul - o reprezentare abstractă (o schemă, un

set de ecuaţii etc.) replicând, cu un anumit grad de acurateţe, comportarea sistemului însuşi

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

X este mulţimea stărilor;T este timpul (continuu sau discret);U este domeniul intrărilor admise;f : XxTxUxT→X, funcţia de tranziţie a stărilor;f : XxTxUxT→X, funcţia de tranziţie a stărilor;Y este domeniul de ieşire;g : XxT→Y este funcţia de ieşire;R : UxT→U este funcţia de admisibilitate a intrării (datorata sau nu unei reacţii a sistemului).

Variabile măsurabilevariabile de intrare – variabile in timp: u1(t), u2(t), ...variabile de ieşire – modificate de sistem ca răspuns: y1(t), y2(t), ....

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

y(t) = [y1(t), y2(t), ..., yn(t)]T

Modelul matematic general al sistemului, din punct devedere intrare-ieşire, 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 relaţiilefuncţionale intrare-ieşire pe care le putemconstrui sunt descrise simplu prin ecuaţiialgebrice, in care ieşirea y(t) este, pentru orice t,independenta de valorile trecute ale intrării u(τ),independenta de valorile trecute ale intrării u(τ),τ<t;sisteme dinamice – in care relaţiile funcţionale intrare-ieşire construite sunt descrise prin ecuaţii diferenţiale, deci in care ieşirea y(t) depinde de valorile trecute ale intrării u(τ), τ<t, deci de momentul iniţierii studierii relaţiilor i/e

Clasificarea sistemelor (2)sisteme invariante in timp: răspunsulintrare-ieşire nu depinde de momentulaplicării intrării (daca u(t) ⇒ y(t), atunciu(t+τ) ⇒ y(t+τ), ∀τ∈T);sisteme variabile in timp: răspunsulintrare-ieşire depinde de momentul aplicăriiintrării (daca u(t) ⇒ y1(t), atunci u(t+τ) ⇒y2(t+τ), cu y1(t)≠ y2(t+τ) pentru t,τ∈T)

“Stare” sistemIeşirea unui sistem nu este întotdeauna aceeaşi atunci când se aplică aceeaşi intrareSimpla observare a ieşirii y(t) atunci când Simpla observare a ieşirii y(t) atunci când intrarea u(t) este complet specificată nu conduce la predicţia ieşirii viitoareDeci “starea” sistemului diferă!

Clasificarea sistemelor (3)Introducerea noţiunii de stare este

importantă pentru înţelegerea corectă aechilibrului intre influenta factorilor externişi interni in răspunsul unui sistem.şi interni in răspunsul unui sistem.

Numărul stărilor poate fi finit, numărabilsau infinit :

- sisteme cu stări discrete;- sisteme cu stări continue.

Clasificarea sistemelor (4)Nu doar numărul stărilor influenţează

capacitatea de predicţie a comportăriiviitoare a sistemului pentru o intrare data.

- sisteme deterministe: ieşirile sunt- sisteme deterministe: ieşirile suntdeterminate complet de stare, intrări şimomentul aplicării;

- sisteme stochastice: cel puţin una dintreieşiri 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 fabricaţie/de asamblare reţelele de calculatoare şi de comunicaţiisistemele de dirijare a traficului aerianprocesele de business (supermarket) etc.

Elemente distinctive ale SDEDSisteme artificiale - create de noile tehnologiiSisteme dinamice - prin natura evoluţiei 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 Evoluţia în timp - depinde de interacţiunea complexa a momentelor de apariţie a diferitelor tipuri de evenimenteNu pot fi descrise prin ecuaţii diferenţiale, cu derivate parţiale sau cu diferenţe finite

SDED - definiţiiSisteme dinamice al căror spaţiu de stări estediscret şi ale căror traiectorii de stare suntconstante pe porţiuniMomentele de timp la care tranziţiile survin, ca şiMomentele de timp la care tranziţiile survin, ca şitranziţiile în sine sunt în general impredictibileTranziţiile de stare se numesc evenimenteAcestea dirijează mecanismul tranziţiilor de stareSDED se deosebesc profund de sistemele cueşantionare, obţinute prin discretizarea timpului

• discrete - privind timpul de referinţa şi spaţiul stărilor

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

•

SDED - proprietăţi

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

interne • deşi perturbări neplanificate, defectări şi căderi

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

• gradul de complexitate şi dimensiunile lor sunt mari:Ønumărul de stări ale unui SDED “explodează”

combinatorialØenumerarea stărilor duce la sarcini computaţionale

inadecvate

SDED – proprietăţi (cont.)

inadecvate• sunt modulare - compuse din componente cvasi-

independente⇒ pot fi aplicate metode de decompoziţie şi agregare⇒ pot fi echipate cu mijloace de control şi comunicare

Modelarea analitica Simularea

Metodologii de studiu:

DE CE studiem un sistem?Scopurin Proiectaren Măsurare şi controln Îmbunătăţire

ModalităţiModalităţin Studiul sistemului realw Prezintă avantajul exactităţii 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ă(absenţa sistemului real)(absenţa sistemului real)

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

Studiul modelelorDe obicei uşor, rapid, ieftin, sigur – faţă de studiul sistemului realPermite încercarea unor idei şi ipotezeSimpla construcţie 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

Definiţii: modelare şi modelUn proces de modelare este o etapa preliminara necesara in studiul oricărui 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 totuşi 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, schiţe – 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 Execuţia programului permite încercări, obţinerea de

rezultate, studiul comportamentului modelului

Modelarea predictivăEste o modelare in absenta realităţii

Exemple:

a) Construcţia unei caroserii care trebuie sa satisfacă anumite criterii de greutate, rezistenta, geometrice, tehnologicerezistenta, geometrice, tehnologice

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

c) Experimentarea unor medicamente ce trebuie sa aibă unele proprietăţi speciale

Modelarea restrictivăEste modelarea in condiţiile restricţiilor de acces la un sistem real existent

Exemple:

a) Nu putem opri o reţea de calculatoare ce monitorizează a) Nu putem opri o reţea de calculatoare ce monitorizează o centrala nucleara in scopul efectuării de experimente

b) Nu putem opri procese de fabricaţie ritmice pentru a experimenta noi metode de management

c) Nu putem perturba circulaţia pe o artera aglomerata pentru a decide in ce măsura, 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 tradiţionalePermit obţinerea de rezultate exacte:n Aparatul matematic integro-diferenţialn Teoria aşteptării (cozi şi reţele de cozi)n Teoria aşteptării (cozi şi reţele de cozi)n Programare liniara

Sistemele complexe pot fi uneori reprezentate de modele analitice simple, validen Presupunerile simplificatoare păstrează 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 operaţii/

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

Acurateţea simulărilorPrin simulare nu se obţin răspunsuri exacte, doar aproximaţii, estimări; totuşi: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 obţinerea ieşirilor aleatoare (RIRO) din simulări stochastice, prin:n Proiectarea şi analiza statistică a experimentelor de

simularen Controlul “zgomotului”, replicabilităţii, eşantionării

secvenţiale, tehnicilor de reducere a variantei

Verificarea şi validarea simulărilorVerificarea simulării consta in principal in compararea modelului conceptual cu codul programatMetode de verificare a unei simulări: n Compararea modelului implementat cu alte modele, atât la nivel

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

îndeplinirea cerințelor sau specificațiilor documentate

Validarea unei simulări consta in analiza corespondentei intre model si sistemul realMetode de validare a unei simulări:n Examinarea atenta a ieșirilor modelului in condițiile variabilității

cat mai mari a intrărilor, si compararea cu datele de observațien Execuția 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 tranziţiile de

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

de incertitudine?

Majoritatea modelelor operaţionale sunt: dinamice, discrete şi stochastice

Ex.de simulare manuală: estimarea nr.π 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)/(π*d)Se repetă experimentul de un număr mare de ori şi se determina R = raportul intre nr. traversărilor şi nr. aruncărilorSe estimează π prin (2*L)/(R*d)

JustificareAcul poate ateriza in poziţii diferite (fig.1)

Orice poziţie intre 2 linii se caracterizează prin:n Distanta capătului 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 direcţia liniilor (θ): 0 < θ < π.

Fig.1 Fig.2

Justificare (cont.)Acul intersectează linia dacă y < L·sinθ

Perechea (θ, y) determină in mod unic poziţia acului (fără a ţine cont de translaţii)

Spaţiul de eşantionare:

Justificare (cont.)

Probabilitatea ca acul sa intersecteze

o linie:

După efectuarea calculelor:ππ

θ⋅=

==

dAdlaturideuluidreptunghiariaLycurbasubdeariaP

:,)sin(

ConcluziiProblema acului (Buffon) pare banală, dar aduce in atenţie unele caracteristici de simulare importante:

n Execuţia in vederea estimării unei mărimi 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 estimării erorii estimatoruluin Replicarea (mai mult=mai bine) pentru reducerea eroriin Eşantionarea secvenţiala pentru controlul erorii – repetă

aruncarea pana când eroarea estimatorului este “destul de mica”

n Reducerea varianţei (“crucea Buffon” sau tehnica Fox)w În esenţă, artificii ca rotirea mesei pe care este

aruncat acul pot elimina imperfecţiunea aruncărilor

Modelarea sistemelor de calculModelarea sistemelor de calcul

Fundamente matematice ale modelarii.

Curs, anul III Calculatoare

Fundamente matematice ale modelarii. Elemente de probabilităţi şi statistică

matematică.

Definiţii nonformale şi exemple

Def: Spaţiu de eşantionare (eng. sample space) , notat S: o mulţime in care fiecare element reprezintă “rezultatele” unui “experiment”

Exemple:Exemple:n S = Ban, Marca in aruncarea unei moneden S = 1, 2, …, 6 in aruncarea unui zar

Def.: Eveniment: un subset al spaţiului SExemple:

n Obţinerea unei valori dintr-o submulţime a spaţiului S (Ban, 1,2,3) in cadrul unei aruncări

Relaţii în mulţimea evenimentelorImplicaţia evenimentelor: evenimentul A implicaevenimentul B (notam A → B sau A ⊂ B) daca atunci când se produce A se produce in mod necesar şi BReuniunea evenimentelor A, B (notata A ∪ B): este evenimentul care se produce atunci când se produce cel puţin unul dintre evenimentele A, Bpuţin unul dintre evenimentele A, BIntersecţia evenimentelor A, B (notata A ∩ B): este evenimentul care se produce doar atunci când se produc ambele evenimente A, BEvenimente incompatibile: evenimentele care nu se pot produce simultanEvenimente contrare: producerea unuia înseamnă nerealizarea celorlalte

Evenimente elementare Def.: Evenimentul elementar este un element din mulţimea S

Evenimentele elementare se mai definesc ca rezultate cu valori booleene ale unor probe (experimente)Un experiment poate aduce: n fie realizarea unui anumit evenimentn fie nerealizarea sa

Există 2 evenimente speciale în mulţimea de evenimente asociate unui experiment :evenimentul sigur S = A ∪ Ā

evenimentul imposibil ∅ = A ∩ Ān Evenimentele A şi B sunt mutual exclusive daca A ∩ B = ∅

Distribuţia de probabilitate

Def.: Distribuţia de probabilitate Pr este o funcţie

definita pe evenimentele din S cu valori in R

Proprietăţi:Proprietăţi:

1. PrA ≥ 0 pentru orice eveniment A

2. PrS = 1

3. If A ∩ B = ∅ then PrA∪B = PrA + PrB

else PrA∪B = PrA + PrB – PrA ∩ B

Exemplul 1Aruncarea a doua monede:

n Spaţiu de eşantionare: S = BB, BM, MB, MM

n Oricare eveniment elementar se produce cu n Oricare eveniment elementar se produce cu

aceeaşi probabilitate: ¼ (ev. echiprobabile)

n Probabilitatea de a obţine cel puţin o data B:

PrBB, BM, MB = PrBB + PrBM + PrMB = ¾

Exemplul 2Aruncarea a doua zaruri:

n Calculam probabilitatea de a da 4 sau dublen Spaţiul de eşantionare S conţine 36 de evenimente

elementare posibile, echiprobabile (probabilitatea fiecăruia fiind 1/36)fiecăruia fiind 1/36)

n Eveniment A: sa obţinem 4 (3 evenimente elementare)n Eveniment B: sa dam duble (6 evenimente elementare)n A ∩ B: roll (2, 2)

Pr4 ori duble = = Pr4 + Prduble – Pr(2, 2)= 3/36 + 6/36 – 1/36= 8/36

Definiţii formalizateSunt necesare operaţii ca: n implicaţia & echivalenta evenimentelor

n reuniunea evenimentelor, ∪

n intersecţia evenimentelor, ∩∩

n complementaritatea evenimentelor, ¯

n incompatibilitatea evenimentelor

Mulţimea evenimentelor ataşate unui experiment formează o algebră Boole în raport cu operaţiile definite (∪, ∩ şi ¯)

Câmp de evenimenteFie S o mulţime de evenimente elementare, iar B ⊂ P(S) un sistem de submulţimi ale lui S

Dacă:1. S ∈ B;1. S ∈ B;

2. E1, E2 ∈ B ⇒ E1 ∪ E2 ∈ B; E1 ∩ E2 ∈ B; Ē1∈ B; Ē2∈ B

3. E1, E2,..., En,... ∈ B ⇒ E1 ∪ E2 ∪ ... ∪ En ∪ ... ∈ B; E1 ∩ E2 ∩ ... ∩ En ∩ ... ∈ B,

atunci B se numeşte câmp Borel de evenimente

Măsura de probabilitateDefinirea se face intr-un câmp borelian de evenimente şi are la bază sistemul de axiome al lui Kolmogorov:Axioma 1: Fiecărui eveniment elementar E din câmpul

de evenimente îi este ataşat un număr real nenegativ numit probabilitatea lui E, notat P(E)

Axioma 2: Probabilitatea evenimentului sigur S este Axioma 2: Probabilitatea evenimentului sigur S este 1, P(S)=1

Axioma 3: Dacă evenimentele E1, E2,..., En sunt incompatibile 2 câte 2, atunci P(E1 ∪ E2 ∪ ... ∪ En) = P(E1)+P(E2)+...+P(En).

Axioma de adunare extinsă: Dacă apariţia unui eveniment E e echivalentă cu apariţia evenimentelor E1, E2,..., En,... incompatibile 2 câte 2, P(E)=P(E1)+P(E2)+...+P(En)+...

Distribuţie de probabilitate discretaDef.: O distribuţie de probabilitate este discreta daca e definita

pe un spaţiu de eşantionare finit sau infinit numărabil

n Pentru orice eveniment A:PrA = Prs1 + Prs2 + … Prsn = Σs∈APrs, şi ∈ APrA = Prs1 + Prs2 + … Prsn = Σs∈APrs, şi ∈ A

Def.: O distribuţie de probabilitate este uniforma pe un spaţiu finit S

n |S| = n

n Prs = 1/|S| pentru orice eveniment elementar s ∈ SEx: Aruncarea unui zar netrucat:

n Fiecare fata are probabilitatea de apariţie 1/6

Variabile aleatoare discrete

Def.: O variabila aleatoare (discreta) X e o functie definita pe un

spaţiu de eşantionare finit/ infinit numărabil cu valori reale

n Ea asociază un număr real cu orice rezultat posibil al unui

experiment

Pentru o v.a. X şi un număr real x:

Def.: Evenimentul X = x = s ∈ S: X(s) = x

Def.: f(x) = PrX=x = Σs∈S: X(s) = xPrs se numeşte funcţia

densităţii de probabilitate a v.a. X

ExempluAruncarea unei perechi de zaruri:

Spaţiul de eşantionare S are 36 evenimente elementare posibile

Fiecare eveniment elementar s∈S este echiprobabil: Fiecare eveniment elementar s∈S este echiprobabil: Prs = 1/36

V.a. X = maximul celor doua valoriProbabilitatea ca maximul celor doua valori sa fie 3:n X asignează valoarea 3 pentru 5 din cele 36 evenimente posibile:

(1, 3), (2, 3), (3, 3), (3, 2), (3, 1)

n Deci: PrX = 3 = 5/36

V.a. şi eşantion (discret)Este o funcţie X : (Ω, B, P) → R, ce ia valori diferite în cazul unor experimente efectuate în condiţii identice, apariţia fiecărei valori fiind un eveniment incontrolabilX(ω) e valoarea reală a variabilei aleatoare, ca funcţie de experimentul sau eşantionul considerat, unde ω este eşantionul (engl."sample").O v.a. X=X(ω) determină o desfacere a evenimentului O v.a. X=X(ω) determină o desfacere a evenimentului total în evenimente incompatibile: intuitiv, pentru cazul discretizării Ω luand k valori posibile ale variabilei X(ω), notate x1, x2,..., xk, cu probabilităţile ataşate p1, p2,..., pk (p1+p2+...+pk =1), variabila aleatoare e dată sub forma:

x1 x2 ... xkX =

p1 p2 ... pk

Variabile aleatoare continuePrin analogie valorile sunt funcţii continue, de ex. peste RProbabilităţile apariţiei acestor valori sunt definite (dacaexista) de o funcţie f(x) definita pe întreaga dreapta reala

( ) xptxfdxxfxXxPx

x∀≥=≤≤ ∫ .0)(,)(2

21

Pentru orice x1, x2 a.i. x1≤x2, X este o v.a. continua iar f(x) se numeşte funcţia densităţii de probabilitateAtât v.a.discrete cat şi v.a.continue pot fi dependente sau independenten In cazul a 2 v.a. independente, X şi Y, definite ca mai sus:

P(Xi ∩ Yj) = P(Xi)∙P(Yj)

( ) xptxfdxxfxXxPx

∀≥=≤≤ ∫ .0)(,)(1

21

Distribuţii (repartiţii) continueAvând in vedere “aspectul” v.a., se definesc:

Funcţia de distribuţie sau repartiţie (c.d.f) a unei v.a. X:

F(x)=P(ω|X(ω)<x)F(x)=P(ω|X(ω)<x)Densitatea de probabilitate (p.d.f.), pentru orice A ⊂ R, prin:

P(x∈A)=∫A f(x)dx, sau f(x)=dF(x)/dx

dacă F este diferenţiabilă în x

Media, dispersia, alte momenteMedia sau valoarea aşteptată a unei v.a. este:µ = E[X] = ∫-∞

∞ xdF(x) = ∫-∞∞ xf(x)dx;

Momentul de ordinul k al v.a.:E[Xk] = ∫-∞

∞ xkdF(x) = ∫-∞∞ xkf(x)dx;

Dispersia (variabilitatea) v.a.:Dispersia (variabilitatea) v.a.:σ2 = var(X) = E[(X-E[X])2] = E[X2]-(E[X])2.Numita şi abatere medie pătratică, pentru un şir xi cu n (nr. mare) valori, ea se calculează astfel :

−

−≈

− ∑∑∑∑

====

2

11

22

11

2 11

111 n

ii

n

ii

n

ii

n

ii x

nx

nx

nx

n

Aplicatie practicaPentru 2 v.a. distribuite uniform:1. Discreta pe intervalul [1,6] (aruncarea

zarului)2. Continua in intervalul [a,b]se cere:se cere:I. Calculul mediilor şi dispersiilorII. Reprezentarea grafica a pdf şi cdfRăspunsuriI. 1. µ = 7/2; σ2 = 35/12

2. µ = (a+b)/2; σ2 = (b-a)2/12 ...

Teoreme importante: Inegalitatea lui Cebîşev

Putem avea o imagine asupra repartiţiei prin cunoaşterea mediei şi dispersiei

Inegalitatea lui Cebîşev arata cat de mari sunt probabilităţile abaterilor de la medie:probabilităţile abaterilor de la medie:

Se poate aplica atât v.a. discrete cat şi continue

2

2

)|(|εσ

εµ ≤≥−xP

Teoreme importante: Legea numerelor mari

Bernoulli: Probabilitatea ca modulul diferenţei intre frecventa relativa de aparitie a unui eveniment E şi probabilitatea p a lui E sa fie mai mic decât un ε pozitiv, arbitrar de mic, este ≈1 pentru un nr. de experimente n suficient de mare

pnP 1 11)|(| ε −≥<−

Cebîşev: Probabilitatea ca modulul diferenţei intre media aritmetica A a valorilor medii a n v.a. i.i.d. şi media aritmetica a uneia dintre v.a. să fie mai mica decât un ε pozitiv, arbitrar de mic, este ≈1 pentru n suficient de mare

np

nnP 2

1

411)|(|ε

ε −≥<−

nbAX

nP

n

ii 2

2

1

1)|1(|ε

ε −≥<−∑=

Distribuţia binomiala (Bernoulli)Se defineşte printr-un experiment Bernoulli, ce are doar doua valori:

Succes/Esec (1/0)0.3

0.4

0.5

0.6

0.7

P(X=

x)

n Succes/Esec (1/0)

0

0.1

0.2

0.3

0 1

X

P(X=

x)

pXP

pXP

−==

==

1)0(

)1(

pXE =][ )1()( ppXVar −=

Distribuţia binomiala Definita de numărul de încercări reuşite dintr-un total de n experimente Bernoulli

0.2

0.3

P(X=

x)

Sau ca suma a n variabile aleatoare de tip Bernoulli

xnxxn ppCxXPxf −−=== )1()()( npXE =][

)1()( pnpXVar −=

0

0.1

0 1 2 3 4 5 6 7 8 9 10

X

Distribuţia binomiala negativa Definita de numărul necesar de repetări ale unui experiment Bernoulli pana la obţinerea de m ori a unui eveniment legat de el (m reuşite)Sau ca o suma infinita de variabile aleatoare de tip Bernoulli, cu valori ce încep cu m, m+1, ...tip Bernoulli, cu valori ce încep cu m, m+1, ...

xmmxm ppCxXPxf )1()()( 1

1 −=== −−+

ppmXE /)1(][ −=

2/)1()( ppmXVar −=

Distribuţia geometrica

Definita de numărul de experimente Bernoulli necesar pentru a obţine primul succes

0.3

0.4

0.5

0.6

0.7

P(X=

x)

primul succes

0

0.1

0.2

0 1 2 3 4 5 6 7 8 9 10

X1)1()( −−= xppxf

pXE 1][ =

2)1()(

ppXVar −

=xpxF )1(1)( −−=

Distribuţia Poisson Definita de nr. de evenimente aleatoare ce au loc intr-un interval de timp de mărime fixa 0.1

0.2

0.3

P(X=

x)

Sau ca o limita a distribuţiei binomiale când n→∞ şi p→0

00 1 2 3 4 5 6 7 8 9 10

X

λλ −=== ex

xXPxfx

!)()(

λ=][XE λ=)( XVar

xexF λ−−= 1)(

Procese Poisson omogeneDaca numărul de evenimente apărute pana la momentul t este distribuit Poisson cu rata λtn Numărul de evenimente apărute in intervale de timp

disjuncte este independentn Timpii intre evenimente sunt independenţi şi identic

distribuiţi ca v.a. exponenţiale cu media 1/λdistribuiţi ca v.a. exponenţiale cu media 1/λn Un proces Poisson omogen este staţionar (distribuţia

nr. de evenimente depinde doar de lungimea intervalului, nu şi de punctul sau de început)

Alte proprietăţi:n Combinarea a 2 procese Poisson cu ratele λ şi µ da

un alt proces Poisson cu rata λ+µn Alegerea evenimentelor dintr-un proces Poisson cu

probabilitatea p da un proces Poisson cu rata p λ

Procese de naştere şi moarteDaca timpii intre evenimente sunt i.i.d. atunci numărul de evenimente ce apar in timp formează un proces “de naştere şi moarte” n Un proces Poisson omogen este un proces de naştere

şi moarte cu timpii intre sosiri exponenţialişi moarte cu timpii intre sosiri exponenţialin Majoritatea proceselor de sosire pot fi modelate

folosind procese de naştere şi moarten Uşor de utilizat deoarece timpii intre sosiri pot fi

obţinuţi prin eşantionare dintr-o distribuţie datan Un proces de naştere şi moarte este staţionar

Procese de sosire nestaţionare Evenimentele externe (inclusiv sosirile in sistem) pot avea rate variabile in timp, de ex.n Sosirile la un restaurant fast-food in jurul prânzuluin Traficul in “rush-hour” in oraşe sau pe autostrăzin Cererile sezoniere pentru un produs

28

n Cererile sezoniere pentru un produs

Caracterul de nestaţionaritate al sosirii trebuie păstrat in model – acest lucru este critic pentru validitatea modeluluiModelul adecvat este cel al unui proces Poisson neomogen

Distribuţia exponenţialaModelează:n Timpii intre sosiri,

când sosirile sunt complet aleatoare

n Timpii de servire ce 0.2

0.3

0.4

0.5

f(x)

n Timpii de servire ce prezintă o mare variabilitate

Este o distribuţie “fără memorie”:

0

0.1

0 2 4 6 8 10

X

β

β/1)( xexf −=

β=][XE 2)( β=XVar)()|( xfyXyxf =>+

Distribuţia normalaDescrisa de următoarele proprietăţi:n Limitele pdf la -∞ şi +∞

sunt 0n Valoarea maxima a pdf 0.15

0.3

0.45

f(x)

n Valoarea maxima a pdf este atinsa când X=μ

n Graficul pdf este simetric după μ

Distribuţia mediei unui sir de v.a. i.i.d. este normalaPentru µ=0: distribuţia normala standard

0

0.15

0 2 4 6 8 10

X

( )222

1

221)(

µσ

πσ

−−=

xexf

µ=][XE 2)( σ=XVar

Distribuţia log-normala (→Weibull)V.a. ln(X) este distribuita normalSe utilizează in modelarea mărimilor ce reprezintă

0.2

0.3

0.4

f(x)

ce reprezintă produse ale unui număr mare de mărimi aleatoare

22 2/))(ln(

21)( σµ

πσ−−= xe

xxf

2/2

][ σµ+= eXE )1()(222 −= + σσµ eeXVar

0

0.1

0 1 2 3 4 5

X

Distribuţia uniformaUtilizata in situaţii cu date echiprobabile pe un interval

1 ≤≤

2/)(][ baXE += 12/)()( 2abXVar −=

a b0

altfel 0

bx a 1)(

≤≤−= abxf

Distribuţia triangularaUtilizata in situaţii cu date puţine sau lipsan Se obţine pe baza a 2

distribuţii uniformen Sunt necesare doar 0.1

0.2

0.3

f(x)

n Sunt necesare doar minimul, maximul şi c.m.probabilă valoare

0

0.1

0 1 2 3 4 5 6 7 8 9 10

X

altfel ,0

,))((

)(2

,))((

)(2)(

=

<≤−−

−=

<≤−−

−=

bxmabmb

xb

mxaabam

axxf

2/)(][ baXE +=

12/)()( 2abXVar −=

Relatii intre distributii

Chi-SquaredDistribution

Lognormal

Distribution

Normal

Distribution

Extreme-ValueDistribution

ExponentialDistribution

GammaDistribution

ErlangDistribution

WeibullDistribution

Tema: ReferatInstalati pe calculatorul personal sau in laboratorpachetul utilitar Analysis ToolPak din Exceln Dupa instalare, comanda Data Analysis trebuie sa fie

disponibila in Excel in grupul Analysis sub tab-ul Data

Folositi aceasta comanda si/ sau alte functii Excel Folositi aceasta comanda si/ sau alte functii Excel pentru a genera multiple esantioane de numerealeatoare cu diferite distributiiReprezentati grafic distributiile obtinuteCalculati momentele (statisticile) semnificativepentru esantioanele generate; comparati-le cu cele teoretice


Generarea datelor de intrare


Generarea datelor de intrare1. Generarea numerelor aleatoare

Date de intrare in simularea dinamica discreta

Fie un SED pentru care “stim” ca timpul necesarservirii unui client este cuprins intre 10 si 20 de minute, fiind distribuit uniform (media fiind 15 minute). Cum putem determina timpii de servireai primilor 100 clienti – ca date de baza de ai primilor 100 clienti – ca date de baza de intrare pentru simularea SDED?§ Recurgand din nou la sistemul si procesul real

si la colectarea datelor§ Prin generarea automata (distributionala), cu

grija de a respecta parametrii procesului real

Colectarea datelorIn general grea, costisitoare, frustranta – in plus:n Sistemul real poate sa nu existen Datele sunt din sisteme/ procese “similare” modelului si

nu exact coincidente, disponibilitatea lor poate impunechiar schimbarea modelului

n Datele pot fi incomplete sau prea “incarcate” (zgomotsau cantitati mari de date)

Iesirile sunt sensibile la incertitudinea intrarilor(“garbage in, garbage out”)Gradul de acuratete (detaliere) al modelului estedependent (si) de calitatea datelorn Variabilitatea datelor e o conditie a validitatii modelului

Generarea datelorIn exemplul anterior, am putea folosi la fel de bine un sir de 100 de numere aleatoare uniform distribuite intre 10 si 20, cu media “apropiata” de 15 (cu atat mai apropiata cu cat numarul lor este mai mare)mai mare)Apare ca metoda generala aceea de a desprinde observatii sintetice din proces pentru a genera date de intrare pentru modelProblema este de a “potrivi” datele generate cu cele observate n datele de intrare generate trebuie si validate!

DiscutieEste clar ca in multe cazuri simularea implicaelemente aleatoare/ stochasticeIn exemplul anterior, nu stim apriori cat va luaservirea unui client, dar stim ca timpul de servireurmeaza o distributie de probabilitateurmeaza o distributie de probabilitateFiindca modelul de simulare este oricum o aproximare, scopul generarii n.a. si v.a. este saaproximam “corect” datele de intrare“Corect” inseamna ca generarea de numere sivariabile aleatoare trebuie sa produca dintr-o formula distributionala un set de esantioane(numerice), avand doua proprietati importante…

Proprietatile esantioanelorIdentitatea distributiei (potrivire, uniformitate): Esantioanele produse trebuie sa aiba aceeasidistributie ca si datele reale din procesà in termeni statistici, c.p. media si varianta esantionuluisunt aceleasi cu media si varianta populatiei de intrare

Independenta: Cand un set de esantioane esteplasat in secventa in care este produs, nu trebuiesa existe vreun sablon (chiar si neintentionat!) de repetare a acelei secvente

Cum garantam similaritatea distributiei cu datele?

Presupunem ca datele ce pot fi culese din sistem sunt IID (independente si identic distribuite)Mai intai se incearca gasirea unei distributii de probabilitate, ce va fi apoi utilizata in generarea intrarilor modelului de simulareintrarilor modelului de simulareCea mai buna distributie “teoretica” este cea care se potriveste cel mai bine cu cea a datelor empirice (culese)“Adecvarea” distributiei teoretice (tip, parametri) cu datele empirice este uneori dificila

Metoda histogramelorModalitate simpla de a vedea daca un esantion de date este adecvat unei distributii; etape:n Se deseneaza histograma frecventelor aparitiei datelor n Se estimeaza parametrii unei distributii posibilen Se deseneaza functia densitatii de probabilitaten Se deseneaza functia densitatii de probabilitaten Se determina cat de similare sunt cele doua forme

frecv

ente

valori ale datelor

Testul Hi-patrat (Pearson)Formalizeaza notiunea ant. de

similaritate a distributiilorn Oi reprezinta numarul valorilor

de date observate in cel de-al i-lea interval (sunt k intervale)

n pi este prob. ca o valoare saintre in cel de-al i-lea interval

frecv

ente

valori ale datelor

iO

ii npE =intre in cel de-al i-lea interval sub distributia ipotetica

n Ar fi de asteptat sa observamin intervalul I, Ei = npi, dintr-un total de n observatii

n Daca pp. distributionala estecorecta, atunci χ0

2 urmeaza o distr.χ2 cu k-s-1 gr.de libertate(s e nr.parametrilor distributieiipotetice)

pdf

valori ale datelor

ii npE =

∑=

−=

k

i i

ii

EEO

1

220χ

Independenţa datelorDouă seturi de date (esantioane) sunt independente dacă orice subset de valori dintr-unul nu oferă nici o informaţie despre vreun subset de valori “corespondente” in celălalt2 sau mai multe v.a. sunt independente dacă pentru orice submulţime proprie de v.a. orice eveniment determinat de v.a. din submulţime este independent de orice eveniment v.a. din submulţime este independent de orice eveniment determinat de variabilele din mulţimea complementară2 sau mai multe v.a. X1, X2, . . . , sunt independente şi identic distribuite dacă variabilele au aceeaşi distribuţie de probabilitate şi sunt independente (i.i.d.)2 observaţii sunt independente dacă obţinerea primei observaţii nu influenţează obţinerea celeilalte observaţii Echivalent, includerea în eşantion a unui element nu influenţează includerea altui element

Generarea numerelor aleatoare

Notiuni de baza

Generarea numerelor aleatoare

AplicabilitateApare ca instrument de lucru in cazul sistemelor si proceselor stochastice (nedeterministe) – ce necesita modele cu elemente stochasticeImplica utilizarea distributiilor de probabilitate ca elemente de baza de modelareelemente de baza de modelareLarg utilizata si in alte domenii: n Simularea statica (Monte-Carlo) – de ex. calculul lui πn Analiza probabilistica a algoritmilor – cu conditia sa putem

caracteriza in mod rezonabil distributia datelor de intraren Criptografia – la baza constructiei cheilor de criptare si a

altor parametri ai algoritmilor si protocoalelor criptografice...

Ce este un numar “aleator”?Nu putem spune ca un anumit numar este aleator “Aleatorizarea” (randomness) este un proces nedeterminist ce produce astfel de numere (fara insa a putea fi siguri niciodata asupra urmatoarei insa a putea fi siguri niciodata asupra urmatoarei valori produse)Surse bune de numere puraleatoare: ruleta, dar si altedispozitive fizice (electronice,radioactive) mult mai rapide§Totusi, acestea sunt foarte greu de utilizat in simulare

Numere pseudo-aleatoareCel mai important in simulari, care de obicei se fac pentru a compara diverse evolutii ale unui sistem, este pastrarea conditiilor de operareAceste conditii sunt influentate de esantioanele datelor de intrare, la randul lor determinate de datelor de intrare, la randul lor determinate de numerele aleatoare folosite

⇒trebuie pastrata sursa de numere aleatoare in toate simularile

⇒chiar daca sunt pseudo-aleatoare (generate de algoritmi - deterministi) acestea trebuie sa satisfaca anumite proprietati statistice

Proprietati ale unui “bun” generator si numerelor aleatoare generate

Numerele generate trebuie sa fie independente statistic (fara autocorelare)Generatorul trebuie sa fie rapidMemoria necesara algoritmului de generare nu trebuie sa fie excesivasa fie excesivaPerioada de repetitie a numerelor generate trebuie sa fie suficient de marePericolul degenerarii sirului de numere trebuie eliminat (nu trebuie ca de la un anumit rang, numerele sa nu mai respecte conditiile impuse)Sirul de numere aleatoare trebuie sa fie reproductibil

Metode analitice de generare a n.a.(1)

Mijlocul patratului (Von Neumann)Ø Un numar initial (seed) este ridicat la patrat, si cifrele

din mijloc formeaza primul n.a. (prin repozitionareapunctului zecimal se poate obtine un numar intre 0 si1); acesta se ridica din nou la patrat si se obtine prin1); acesta se ridica din nou la patrat si se obtine prinaceeasi tehnica al doilea n.a., iar procedeul continua

Ø Sursă slaba de n.a. – prin faptul ca anumite secventede numere aleatoare se repeta

Ø Pornind de la ideea de baza, s-au construit algoritmimai buni, bazati pe metode recurente de generare

X0 = 9524 (seed)X0

2 = 95242 = 90706576à X1=7065R1= 0.7065

X 2 = 70652 = 49914225à X =9142

Exemplul 1

X12 = 70652 = 49914225à X2=9142

R2 = 0.9142

X22= 91422=83576164 à X3 = 5761

R3 = 0.5761…

X0 = 1258 (seed)1258, la patrat = 15825645825 339306259306 866016366016 36192256

Exemplul 2

6016 361922561922 36940846940 481636001636 26764966764.....

…

Probleme ale algoritmului “mid-square”.Repetarea secventelor

ExempluX0 = 5197X0

2 = 51972 = 27008809à X1=0088R1= 0.0088R1= 0.0088X1

2 = 882 = 00007744à X2=0077R2= 0.0077X2

2= 772=00005929 à X3 = 0059R3 = 0.0059

Zero-urile dupa punct apar in fiecare n.a. R i din sir

ExempluXi = 6500Xi

2 = 65002 = 42250000 à Xi+1=2500Ri= 0.2500

Probleme ale algoritmului “mid-square”.Degenerarea sirului

Ri= 0.2500Xi+1

2 = 25002 = 06250000 à Xi+2=2500Ri+1=0.2500

...Toate valorile ulterioare ale lui Xi, Ri vor fi 2500Concluzie: algoritmul mid-square nu este bun!

Metode analitice de generare a n.a.(2): Metode congruentiale liniare (Lehmer,1951)

LCG produc secvente de intregi X1, X2,… intre 0..m -1 conform cu urmatoarea relatie recursiva:

Xi+1 = (aXi + c) mod m, i = 0, 1, 2,…n Numim valoarea initiala X0 sămânţa generatorului (seed), a

este multiplicatorul constant, c e incrementul, iar m modululeste multiplicatorul constant, c e incrementul, iar m modululn Toti parametri sunt intregi n Dupa cum c ≠ 0 sau c = 0, avem doua forme:w Metoda congruentiala mixtaw Metoda congruentiala multiplicativa

n Selectia valorilor pentru a, c, m si x0 afecteaza foarte mult proprietatile statistice si lungimea ciclului

n N.a. distribuite uniform intre 0 si 1, U(0,1) se genereaza cu relatia: Ui = Xi /m, i = 1, 2, …

Metoda congruentiala mixta

Se caracterizeaza prin c ≠ 0 Exemplu:O secventa de n.a. cu x0 = 27, a = 17, c = 43, m = 100m = 100X1 = (17 x 27 + 43) mod 100 = 502 mod 100 = 2R1 = 2/100 = 0.02X2 = (17 x 2 + 43) mod 100 = 77 mod 100 = 77R2 = 77/100 = 0.77X3 = (17 x 77 + 43) mod 100 = 1352 mod 100 = 52R3 = 52/100 = 0.52...

Metoda congruentiala multiplicativa

Se caracterizeaza prin c = 0 Exemplu:Putem genera n.a. intre 0 si 1 prin aplicarea relatiei:relatiei:

si limitarea numarului de cifre zecimale retinut dupa efectuarea impartirii

mxx i

i =+1

Probleme ale LCG

i 22Xi+4 Xi+1 Ui--------------------------0 191 422 44 .69842 972 27 .4286

i 22Xi+4 Xi+1 Ui---------------------------11 378 0 .000012 4 4 .063513 92 29 .4603

X0=19, Xi+1=(22Xi + 4)mod 63

2 972 27 .42863 598 31 .49214 686 56 .88895 1236 39 .61906 862 43 .68257 950 5 .07948 114 51 .80959 1126 55 .873010 1214 17 .2698

13 92 29 .4603…62 708 15 .238163 334 19 .301664 422 44 .6984…

Observam: repetarea sirului dupagenerarea a 64 valori (modulul), darsi faptul ca repetitia valorilor nu s-a produs inainte.

Proprietati generale ale LCG

Orice LCG va cicla (cel mult dupa generarea a m n.a.); lungimea ciclului s.n. perioada LCGPerioada maxima pentru un LCG este mConditia necesara de a obtine un bun generator este “m foarte mare”foarte mare”Perioada este de obicei mai mica decat mExemplu:

X0 = 20, Xi+1 = (50Xi + 20)mod 100X1 = (50*20 + 20)mod 100 = (1020)mod 100 = 20

Conditia “m foarte mare” nu este si suficienta pentru a obtine un bun generatorExista conditii generale ce garanteaza un bun generator?

Teorema 1Un LCG are perioada maxima d.d.:

1. (m,c)=1 – m si c sunt prime intre ele2. daca exista q, prim, ce divide m, atunci acesta divide a-13. daca 4 divide m, atunci 4 divide a-1.Demonstratia este f. dificila (teorema de numere prime)Demonstratia este f. dificila (teorema de numere prime)Exemplu:n m=10d, pentru un intreg pozitiv d.n a se alege din seria 1, 21, 41, 61, 81,.....n c se alege din seria 1, 3, 7, 9, 11, 13, 17, 19,...

(intregi impari ce nu se divid cu 5)Aplicatie: demonstrati ca LCG din exemplu verifica conditiile teoremei

Modalitati de accelerare a LCGDepasirea (Overflow Division)n Ideea: intr-un calculator zecimal cu lungimea cuvantului 4,

6000+4001=0001; sau 34561332 mod 10000 = 1332, deci stocarea pe 4 biti implica efectuarea operatiei modulo

n Putem alege m=2b unde b=lungimea cuvantului calculatorn Putem alege m=2b unde b=lungimea cuvantului calculator

n Exemplu: pentru un PC cu procesor pe 32 de biti, m=232 sau chiar m=231, tinand cont de lungimea reala (fara semn)

Eliminarea lui c si obtinerea unui LCG multiplicativn Totusi, fara c rezultatul din teorema 1 nu are sens

n Exista o teorema ce stabileste conditii asemanatoare pentru generatoare multiplicative cu modul prim (PMMG)

Teorema 2Perioada generatorului este m-1 daca:

1. m este cel mai mare numar prim mai mic decat 2b

2. cel mai mic numar k pentru care ak-1 este divizibil prin m este k=m-1

Exemplu: Exemplu: n m=231-1, prim; a=75=16807n Nu putem aplica “overflow division” pt. acceleraren O metoda apropiata, numita “simulated division”,

asigura practic aceeasi viteza (principiu asemanator)

Modalitate de verificare a n.a. generate

Utilizarea unei simulari pentru a calcula valoarea numarului π(pi)• Fie (x, y) coordonatele unui punct P din patrat• Pentru punctele de pe P(x,y)• Pentru punctele de pe circumferinta cercului:

x2 +y2 = r2

• Folosind generatorul de n.a. pe care il avem, acoperim patratul prin 10 000 puncte aleatoare; fie a numarul de puncte din sfertul de cerc

x

yr

P(x,y)

Fie a numarul de puncte din sfertul de cercAria sfertului de cerc = Numar de puncte in sfertul de cerc

Aria patrat Numar de puncte in patrat

Acuratetea determinarii lui pi depinde de calitatea generatorului de n.a.

2

arπ

2500

100001*14

110000*

4

2

2

a

a

arr

r

=⇒

=

=

π

π

π

x

yr

P(x,y)

Functii de generare a n.a. in C/C++. Functiile rand() si srand()

Returneaza valori intregi generate (pseudo) aleator

rand() – returneaza acelasi sir de numeren Aplica metoda congruentiala multiplicativa (factor 232) si

returneaza secvente de n.a. intre 0..RAND_MAX (constanta simbolica e definita in stdlib.h, valoarea uzuala este 32767)simbolica e definita in stdlib.h, valoarea uzuala este 32767)

n Sirul de numere returnat poate fi schimbat daca se modifica valoarea implicita a variabilei seed (reinitializare generator)

srand() – face (re)initializarea generatorului de n.a.n Utilizare: srand(int iSeed)

n iSeed poate fi data explicit, ca o constanta (1=val.implicita), sau setata diferit la fiecare rulare, in functie de timp

Functia time() si operatorul %Trebuie inclus header-ul <time.h> ce contine definitia: “time_t time(time_t *tloc);”, echivalenta cu:“int time(int *tloc);” n tloc este locatia de memorie a unei variabile intregi unde poate fi

stocata valoarea generata (optional)

Descriere: time() returneaza valoarea intreaga (in sec.) de Descriere: time() returneaza valoarea intreaga (in sec.) de la 1/1/1970, pentru a obtine o valoare diferita a sămânţei la fiecare rulare a unui program n Daca tloc ≠ 0, valoarea returnata este si stocata in locatia spre

care pointeaza tloc

Operatorul % (modulo) permite scalarea valorilor:n rand( ) % 10 ⇒ un n.a. intre 0 si 9 inclusivn rand( ) % b + a ⇒ un n.a. intre a si b-1 inclusiv

Exemplu: generarea a 10 numere intre 0..20

// printing 10 random numbers// between 0 and 20:// Same numbers each run#include <iostream.h>using namespace std; main()

// printing 10 random numbers// between 0 and 20// Different numbers each run#include <iostream.h>#include <time.h>using namespace std;main()

int i, iNum;i = 1while ( i<=10 )

iNum = rand() % 21;cout << iNum << " ";i++;

int i = 1;

// print the timecout << time(NULL) << endl;

// seed the random number// generator with the time

srand( time(NULL) );while( i<=10 )

cout << rand() % 21 << " ";i++;

Tema: Proiect + ReferatConstruiti pachetul propriu de rutine de generarede numere aleatoare; implementati cel putin treimetode (functii) de generare de n.a. Implementati functii-criteriu de verificare privindcalitatea numerelor generatecalitatea numerelor generateImplementati pe baza generatorului de n.a. 2-3 generatoare de distributii simple (de ex.uniforma, binomiala, Bernoulli)Studiati proprietatile esantioanelor generate, princomparatie si cu date generate folosind Excel


Generarea datelor de intrare


Generarea datelor de intrare2. Generarea distribuţiilor.

Fiind data o v.a. X si o variabila x, se defineste funcţia de repartitie (cdf):Cazuri:n FX(x): functie continua in x, daca X este v.a. continua

F (x): discreta in x, daca X este v.a. discreta

Distribuţii (repartiţii)

n FX(x): discreta in x, daca X este v.a. discretan FX(x): continua pe portiuni, daca X este v.a. mixta

Proprietăţi :n 0 ≤ FX(x) ≤ 1, -∞ < x <∞n FX(x) este functie monoton crescatoare in xn Avem 1)(lim,0)(lim ==

∞→−∞→xFxF X

xX

x

Functia densitatii de probabilitate (pdf)Daca X este v.a. continua, atunci

Proprietati ale pdf :1.

2.

Functia de repartitie (pmf)

Daca X este v.a. discreta, cu valorile posibile:x1, x2, ..., xn (altfel scris xi unde i=1, 2,...,n)

cu probabilităţile de aparitie p(xi) = P(X=xi), vom numi:p(xi) – functia masei de probabilitate pentru v.a. X(xi, p(xi)) – distributia de probabilitate (repartitia) lui X(xi, p(xi)) – distributia de probabilitate (repartitia) lui X

Proprietati ale pmf (probabilităţii elementare):1.

2.

ioricepentruxp i ,0)( ≥

1)(1

=∑=

n

iixp

Distribuţia eșantionată (de sondaj)Este data de o functie de tipul pdf sau pmf (sauechivalent de cdf) ce caracterizeaza valorile cetrebuie obtinute (si pe care statistica si le poateasuma) din esantioane aleatoare repetateO modalitate simpla de aproximare a distributieiO modalitate simpla de aproximare a distributieieșantionate: selecţia repetată a unui mare numarde esantioane aleatoare din multimea de intrareCalculul valorilor statistice pentru fiecare esantionsi construirea unei histograme dă o imagine aproximata a distributiei esantionate

Histograma

Se consideră un număr mare de secvenţe de aruncare a unei monede netrucate, și proporţia medie de apariţie a a banului (cap)Histograma apariţiilor, la 10000 aruncări:la 10000 aruncări:(cf. Wikipedia)Alte ex. de statistici:n Suma v.a.n Media v.a.n Dispersia v.a.

Media aritmetică de sondaj(sample average, sample mean-value)

Raportul dintre suma tuturor valorilor xobservate în eşantionul considerat şi numărul total n al acestora:

Observaţii∑

=

=n

1i

*ix

n1x

ObservaţiiÎn cazul valorilor observate, aranjate în ordine crescătoare sau descrescătoare:

unde:n - numărul total al valorilor observate;ni - frecvenţa absolută corespunzătoare valorii xi;fi - frecvenţa relativă corespunzătoare valorii xi.

∑∑==

==n

1iii

n

1iii xfxn

n1x

Dispersia de sondaj (σ2)(sample variance)

S.n. și moment centrat de ordinul doi:

Valoarea numerică a sa caracterizează în modul cel mai

∑=

−=n

iii xxn

n 1

22 )(1σ

Valoarea numerică a sa caracterizează în modul cel mai adecvat împrăştierea repartiţiei statisticeDispersia de sondaj poate fi folosită ca estimareaproximativă a dispersiei din populaţia originară, considerându-se formula corectă:

∑=

−−

=n

ii xx

n 1

22 )(1

1σ

Generarea unor esantioane aleatoare de date dupa identificarea unei distributii de probabilitatetrebuie sa respecte doua proprietati importante:nUniformitate: Distributia esantionului aleator si cea

Metode de esantionare (sampling)

Uniformitate: Distributia esantionului aleator si ceaidentificata pentru datele colectate sunt identice à in termeni statistici, media si varianta esantionului suntidentice cu media si varianta populatiei de intrare

n Independenţă: Atunci cand setul de esantioane e plasatin secventa in care a fost produs, nu exista un sablonneintentionat in aceasta secventa

Teoreme importante: Inegalitatea lui Cebîşev

Putem avea o imagine asupra repartiţiei prin cunoaşterea mediei şi dispersiei

Inegalitatea lui Cebîşev arata cat de mari sunt probabilităţile abaterilor de la medie:probabilităţile abaterilor de la medie:

Se poate aplica atât v.a. discrete cat şi continue

2

2

)|(|εσ

εµ ≤≥−xP

Teoreme importante: Legea numerelor mari

Bernoulli: Probabilitatea ca modulul diferenţei intre frecventa relativa de aparitie a unui eveniment E şi probabilitatea p a lui E sa fie mai mic decât un ε pozitiv, arbitrar de mic, este ≈1 pentru un nr. de experimente n suficient de mare

pnP 1 11)|(| ε −≥<−

Cebîşev: Probabilitatea ca modulul diferenţei intre media aritmetica A a valorilor medii a n v.a. independente şi media aritmetica a v.a. sa fie mai mica decât un ε pozitiv, arbitrar de mic, este ≈1 pentru n suficient de mare

np

nnP 2

1

411)|(|ε

ε −≥<−

nbAX

nP

n

ii 2

2

1

1)|1(|ε

ε −≥<−∑=

Proprietati generale ale distributiilor esantionate1. Distributia esantionata a unei statistici tinde sa

se centreze pe valoarea estimata a parametrului statistic corespunzator

2. “Imprastierea” valorilor distributiei esantionate 2. “Imprastierea” valorilor distributiei esantionate a multor statistici tinde sa fie tot mai mica pe masura ce marimea esantionului creste

3. Tot pe masura ce marimea esantionului creste, distributia esantionata a multor statistici devine tot mai similara unei distributii normale (forma de “clopot”)

Proprietati generale ale distributiilor esantionate (cont.)

Cand distributia esantionata a unei statistici estecoincidenta cu parametrul corespunzator al populatiei din care este extrasa, statistica s.n. nebalansata (unbiased) și constituie un estimator nebalansat al parametrului populatieinebalansat al parametrului populatiein Ex. este un estimator nebalansat al mediei

Deviatiile standard ale distributiilor generate suntin general mai mici decat deviatia standard a populatiei de intrare (σ). Variatia in distributia generata scade pe masurace marimea esantionului creste

x

Distribuţia normală (Gauss-Laplace)

Este definită den funcţia de repartiţie:

unde:

( )( )

dxexFx x

∫∞−

−−

= 2

2

22

21;; σ

µ

πσσµ

unde:

n funcţia de densitate a repartiţiei v.a. X:

R x0,σ R,μ ∈>∈

( )( )

2

2

2

21 σ

µ

πσ

−−

=x

exf

Distributia esantionata a medieiDistributia esantionata a mediei, , este acea distributie de probabilitate descriind esantioane aleatoare repetate dintr-o populatie (proces)

x

Daca se considera valoridintr-o populatie de intraredintr-o populatie de intrarecu media µ si deviatiastandard σ, formand maimulte esantioane (n), valorile medii formeazadistributia esantionata a mediilor (simple)

Media si deviatia standard a distributieiesantionate a mediilor ( )

Daca este media esantioanelor aleatoare x1, x2, …,xn, dintr-o populatie sau proces cu media µ sideviatia standard σ, atunci media distributieiesantionate a mediilor coincide cu µ , indiferentde numarul de esantioane (n)

xx

de numarul de esantioane (n)Abaterea distributiei esantionate descrise de , este egala cu abaterea standard a populatiei, raportata la radicalul marimii esantionului

xxσ

nxσ

σµµ == x si

Teorema de limita centrala (TLC)TLC (eng. Central Limit Theorem) afirmă că: pentru nvariabile aleatoare continue, identic repartizate cu aceeaşi medie (m) şi aceeaşi dispersie (σ2), atunci v.a.medie a eșantioanelor este aprox. normal repartizată, cu aceeaşi medie (m) și dispersia mai mică (σ2/n)aceeaşi medie (m) și dispersia mai mică (σ2/n)

Acest fapt are loc chiar pentru valori mici ale lui n

De fapt, TLC este un rezultat important și pentru căstabilește o “cheie de verificare”: , distribuţiaesantionata a mediilor, este aproximativ normala, independent de tipul distributiei populatiei de intrare

x

Teorema de limita centrala (cont.)

Pe masurace marimeaesantionuluicreste destulde mult

Distributia de esantionare devine aproape

de mult(≥ 30) ...

devine aproape normala.

X

(cf. Kendall – Introduction to Statistics)

Metode de generare a v.a. de repartitie data (non-uniforma)

Metoda transformarii inverseMetoda transformarii directe – se aplica pentru distributia normalaMetoda convolutieiMetoda acceptarii-rejectarii

Metoda transformarii inverse (1)Este aplicabila daca functia de distributieeste inversabilaMetoda se aplica unor distributii continue:n Exponentialan Exponentialan Uniforma (≠ U[0,1])n Geometrica

cat si tuturor distributiilor discreteDesi cea mai directa, nu este si cea maieficienta dpdv computational

Metoda transformării inverse (2)Fie o distributie oarecare descrisa prin cdf FX(x), pentru care exista inversa F-1

X(y) pe 0 ≤ y ≤ 1:F-1(y) = min x | F(x) ≥ y Daca U[0,1] e distributia uniforma, atunci v.a. X Daca U[0,1] e distributia uniforma, atunci v.a. X = F-1(U) are cdf F(x)Justificare. Se poate da ca o consecinta directa a relatiei:

[U<F(x)] ⊂ [X≤x] ⊂ [U≤F(x)] pentru orice xsau:

Justificare: v.a. X = F-1(U) are cdf F(x)

Daca v.a. X are cdf FX(x) si exista inversa F-1X(y)

pe 0 ≤ y ≤ 1, putem defini o noua v.a. Z=FX(X) pentru care FZ(z) = P(Z ≤ z) = P(FX(X) ≤ z) daca0 ≤ z ≤ 1.Deoarece exista F-1 (y) si din cauza proprietatiiDeoarece exista F-1

X(y) si din cauza proprietatiide monotonie: P(FX(X) ≤ z) = P(X ≤ F-1

X(y)) = FX(F-1X(z)) = z

care defineste v.a. Z ca U[0,1] (distrib.uniforma) atunci v.a. X = F-1(U) are cdf F(x)

Transformarea inversa

Transformarea inversa aplicata unei distributii continue oarecare•Fie o v.a. avand pdf f(x) = x/2, pentru 0<x<2

•Prin integrare directa rezulta F(x) = x2/4, pentru0<x<2

•Inversa este U2(U)F-1 =•Inversa este

•Prin urmare, pe baza generatorului de n.a. cudistributie uniforma U[0,1], se obtine v.a. X cucdf F(x) = x2/4, data de:

U2(U)F-1 =

U2X =

Transformarea inversa aplicataunei distributii discrete oarecare•Fie o v.a. avand pmf f(x) data de:

•Transformarea inversa conduce la obtinerea v.a.X pe baza generatorului de n.a. cu distributie

.4,3,2,1pentru ,10/][ === xxxXP

X pe baza generatorului de n.a. cu distributieuniforma U[0,1]:

≤<≤<≤

<

== −

UUU

U

UFX

6.046.03.033.01.02

1.01

)(1

Transformarea inversa aplicata la generarea distributiei exponentialeInterpretand parametrul λ ca medie a nr.de aparitiipe unitatea de timp, stiind ca daca U este distributieuniforma pe [0,1] si 1-U este U[0,1], avem:

Transformarea inversa aplicata la generarea distributiei geometrice

Functiile distributionale sunt:

,...2,1pentru ,)1()(: 1 =−= − xppxfpmf x

[ ] [ ] intreaga partea denota unde ,)1(1)(: xpxFcdf −−=

Atunci:

unde prin log(1-U)=-E s-a notat exponentiala

[ ] intreaga partea denota unde ,)1(1)(: pxFcdf −−=

Distributii uzuale si aplicatiile lor

Distributie Aplicatii

Bernoulli • Modelarea unui calculator, daca e functional sau nu• Un pachet intr-o retea isi atinge sau nu destinatia• Un bit dintr-un pachet soseste la destinatie cu

eroare (afectat de zgomot)eroare (afectat de zgomot)

Binomiala • Modelarea numarului de procesoare functionaleintr-un sistem multiprocesor

• Numarul de pachete dintr-o retea care isi atingdestinatia, fara pierderi

• Numarul de biti dintr-un pachet ce sosesc la destinatie cu eroare

• Numarul de articole dintr-un lot ce au anumitecaracteristici

Distributii uzuale si aplicatiile lor (2)


Binomiala negativa

• Numarul de interogari locale intr-o baza de date distribuita, inaintea accesului n la distanta

• Numarul de retransmiteri necesar pentru un mesaj continand n pachetecontinand n pachete

• Numarul de biti succesivi fara eroare intr-un pachet, inaintea primirii celui de-al n-lea bit eronat

Geometrica • Numarul de interogari locale intr-o baza de date distribuita, inaintea acceselor succesive la distanta

• Numarul de pachete transmise cu succes, intre cele ce necesita retransmiterea

• Numarul de biti succesivi fara eroare intr-un pachet



Poisson • Numarul de cereri la un server intr-un interval de timp dat

• Numarul de defectari ale componentelor, in timpunitarunitar

• Numarul de interogari intr-o baza de date in t sec.• Numarul de erori de tiparire intr-un formular

Exponentiala • Timpul intre cereri succesive de servire• Timpul intre caderi succesive ale unui dispozitiv

Erlang • Modelarea timpilor de servire intr-o retea de cozi (m servere cu timpi de servire distribuiti exponential)



Normala • Modelarea erorilor de masurare• Distributia mediilor simple ale esantioanelor unui

mare numar de observatii independente (cf. teoremei de limita centrala)teoremei de limita centrala)

Log-normala • Modelarea unei distributii normale transformate

Uniforma • Modelarea dispozitivelor de i/e selectate pentru urmatoarea operatie de i/e

• Numerele de inregistrari returnate de cautarile intr-un fisier

• Numerele de pista returnate de cautarile pe disc

Tema: Proiect + ReferatConstruiti un pachet propriu de generare de distributii; folositi metoda transformarii inverse acolo unde ea se aplicaReprezentati grafic distributiile obtinuteCalculati momentele (statisticile) semnificativepentru esantioanele generate; comparati-le cu cele teoreticeStudiati proprietatile esantioanelor generate, princomparatie si cu date generate folosind Excel


Modele pentru sistemele (dinamice)


Modele pentru sistemele (dinamice) cu evenimente discrete

Terminologie şi concepte de bazăTipuri de modele. Modele bazate pe stareAutomate cu stări finiteReţele Petri “clasice”. Descrieri

Sumar

Reţele Petri “clasice”. Descrieri Modelarea conceptelor dinamiceModele şi limbaje. Exemple de modelareModele bazate pe urme. Nivele de studiuAlte tipuri de modele şi clasificări

Terminologie şi concepte de bazăSistem - o colecţie de entităţi in interacţiune

Model - o reprezentare abstractă a sistemului

Entitate - componentă a sistemului cu reprezentare explicităin model (obiect de interes in sistem)

Atribut - o proprietate a unei entităţi Atribut - o proprietate a unei entităţi

Set - colecţie de entităţi asociate, permanent sau temporar

Eveniment - o apariţie instantanee ce schimbă starea sistemului

Activitate - o perioada de timp de lungime cunoscuta la începutul ei

Întârziere - o perioada de timp nespecificată ca lungime →necunoscută până la terminarea ei

Concept cheie: “Eveniment”Este un rezultat brusc al îndeplinirii simultane a mai multor condiţiiPoate fi:§ Endogen: apărut in interiorul sistemului

§ Exogen: apărut in mediul extern, dar care afectează sistemul

Intr-o alta perspectiva: n evenimentul este rezultatul unui “proces-eveniment”,

doar acesta determinând timpul apariţiei salen tranziţiile de stare rezulta prin combinarea proceselor

eveniment, asincrone si concurente

Dinamica de sistem si modelEvoluţia in timp a SDED depinde de interacţiunea complexa a momentelor de apariţie a diferitelor tipuri de evenimente Dinamica SDED este determinata de interacţiunile complexe ale sincronizării evenimentelor discrete complexe ale sincronizării evenimentelor discrete asociate cu activităţile/resursele n Dinamica modelului trebuie sa o reflecte pe cea a

sistemului de baza n DAR: dinamica modelului poate fi ameliorata prin unele

metode

ComplexitateaImprimă dificultatea descrierii unui SDED

Complexitatea crescută a sistemului rezultă din: n Capacitatea crescută (numărul mare de componente)w Sisteme simple: aparate electrocasnice, linii de fabricaţie → w Sisteme simple: aparate electrocasnice, linii de fabricaţie →

un model programat poate avea sute sau mii de linii de cod

w Aplicaţii complexe: calculatoare, reţele de calcul sau de comunicaţie → modelele au sute de mii de linii de cod

n DAR şi din interacţiunea complexa a momentelor de apariţie a diferitelor tipuri de evenimente

Metode de descriereEste posibil ca “funcţionarea” dorită a modelului să nu poată fi obţinută fiindcă nu este descrisă corect şi complet funcţionarea sistemuluin Apar erori de implementare datorită descrierilor

incomplete sau eronateincomplete sau eronateMetodă uzuală: utilizarea unui limbaj naturaln Descrierea precisă a sistemului este foarte dificilă

Metodă recomandată: utilizarea de formalismeşi modele computaţionalen Sunt precise, neambiguen Pun la dispoziţie un set de obiecte şi reguli pentru

compunerea obiectelor

Tipuri de modele

n Modele bazate pe staren Modele bazate pe urmen Modele orientate pe activitaten Modele orientate pe activitaten Modele orientate pe structurăn Modele orientate pe daten Modele eterogene

Modelele bazate pe stareReprezintă sistemul ca un set de stări şi un set de tranziţii între stări – o tranziţie e determinatăde evenimente externeCategorii:n Automate cu stări finiten Automate cu stări finite şi căi de daten Automat cu stări finite ierarhice concurenten Reţele Petri

Se utilizează pentru sisteme de control:n monitorizarea unor intrări de control; n setarea unor ieşiri de control

Automate cu stări finite (ASF)Un set de stări ale sistemuluiUn set de tranziţii posibile între stăriUn set de acţiuni asociate cu stările sau tranziţiile<S, I, O, f, h, s ><S, I, O, f, h, s0>S = s0, s1, …, sl setul de stăriI = i0, i1, …, im setul de intrăriO = o0, o1, …, on setul de ieşirif – funcţia stării următoare, f : S x I → Sh – funcţia de ieşire s0 – starea iniţială

Tipuri de ASF (1)Maşina Mealy (bazată pe tranziţii)h : S x I → O

Ex. Controler de ascensor într-o clădire cu 3 etajeI = r1, r2, r3

→ etajul cerut → etajul cerut O = d1, d2, n, u1, u2

→ direcţia şi nr. de etajecu care trebuie să se deplaseze ascensorul

Tipuri de ASF (2)Maşina Moore (bazată pe stări)h : S → O

Ex.

Critica modelelor ASFMaşina Moore necesită un nr. mai mare de stări decât maşina Mealyn Justificare: fiecare valoare de ieşire necesită propria

stare (pot exista arce multiple ce indica aceeasi stare)

Ambele sunt modele teoretice si idealizateAmbele sunt modele teoretice si idealizateSpaţiul si timpul sunt modelate si referite absolutProcesele lucrează sincronSe pot utiliza pentru sisteme la care predominăpartea de controlNu permit descrierea sistemelor complexe (aparefenomenul de “explozie a stărilor”)

Automate cu stări finite şi căi de date

Extind modelul ASF cu tipuri de date complexe/ variabilen Modelul ASF utilizează numai tipuri de date şi operaţii booleene

Permit astfel reducerea numărului de stări

Descriere: ASFD = <S, I, O, V, f, h, s0>n V = v0, v1, …, vn setul variabilelor

n f – funcţia stării următoare, f : S x I x V → Sn h – funcţia de acţiune, h : S → O + V (Moore)

n I, O şi V pot conţine tipuri de date complexe, ca şi limbajele de programare

n f şi h pot conţine operaţii aritmetice

n h descrie şi actualizarea variabilelor

ASFD – Exemplu (controler ascensor)

ASFD se pot utiliza şi pentru sisteme (predominant) de control, şi pentru cele la care predomină partea de calculTotuşi, niciunul dintre modelele ASF si ASFD nu este adecvat pentru sistemele complexe, deoarece ele nu permit reprezentarea explicită a concurenţei şi a ierarhiei

Automate cu stări finite ierarhice concurente (ASFIC)

ASFIC reprezintă o extensie a ASF, ce permite:n Construcţia ierarhica a modelelor n Concurenţan Descrierea lor intr-un limbaj grafic (statecharts)

Se pot grupa într-o nouă stare ierarhică mai Se pot grupa într-o nouă stare ierarhică mai multe stări Fiecare stare poate fi descompusa intr-un set de (sub)stăriDouă metode de descompuneren SAU: o stare este descompusă în (sub)stări secvenţialen ŞI: stările se pot executa concurent

Ierarhizarea stărilor

Fără ierarhie

A

Cu ierarhie

Tranziţiile pot fi structurate sau nestructuratenTranziţiile structurate sunt permise între stări cu acelaşi nivel ierarhicnTranziţiile nestructurate pot apărea între 2 stări oarecare

Stările A1 şi A2 au fost grupate în starea ierarhică ATranziţia în starea B la evenimentul z se realizează din starea A, nu A1 sau A2

A1 z

B

A2 z

x y w

A1 z

B

A2

x y

A

w

Concurenţa

B

Concurenţă

Fiecare stare se execută prin mai multe sub-stări concurenteComunicaţia se realizează prin variabile globaleDouă sau mai multe stări concurente pot fi grupate într-o nouă stare ierarhică

Starea B a fost descompusă în stările concurente C şi DStările C şi D sunt descompuse fiecare în două stări ierarhice

C1

C2

x y

C

D1

D2

u v

D

StatechartsLimbaj grafic ce permite ierarhia, concurenţa şi comunicaţia între stările concurente; utilizează tranziţii nestructurate

Starea Y este descompusă în două stări concurente, A şi D; prima constă din două substări B şi C, iar a doua cuprinde substările E, F şi G.Dacă apare evenimentul b în timpul stării C, are loc transferul în starea B. Dacă apare evenimentul a în timpul stării B, are loc transferul în starea C, dar numai dacă este îndeplinită condiţia P în momentul apariţiei evenim. În timpul transferului din starea B în starea C, se va executa acţiunea c, care este asociată cu această tranziţie.

Reţele Petri “clasice” (C/E)Model orientat pe stare, ce extinde modelele de tipul AF pentru a permite modelarea dinamicii asincrone a unui sistem (inclusiv concurenta, comunicaţie etc.)Elemente: locaţii, conţin simboluri ce s.n. jetoane (0/ 1), si tranziţii, plus arce ce leagă elemente de tip diferit si tranziţii, plus arce ce leagă elemente de tip diferit n in RP C/E poate exista cel mult un arc intre 2 noduri

Terminologien Sistem C/E: reţea C/E + marcajn Configuraţii: marcajele posibile ale unei reţele C/E n Cazuri: configuraţiile accesibile din marcajul iniţial (→case graph)

In anii ’60 -’70, accentul principal s-a pus pe dezvoltări teoretice; din anii ’80 se insista pe instrumente şi aplicaţii

DescrieriGrafice (grafuri bipartite) şi matematice, cu semanticăformală şi posibilităţi de analizăCaracteristici importante: stări distribuite şi tranziţii localeExemplu: RP = <P, T, Pre, Post, M>Exemplu: RP = <P, T, Pre, Post, M>

P = l0, l1, …, lm setul poziţiilor (locaţiilor)T = t0, t1, …, tn setul tranziţiilorPre : T → L+, funcţia de intrare, ce defineşte locaţiile care

furnizează intrări unei tranziţiiPost : T → L+, funcţia de ieşire, defineşte locaţiile de ieşire

pentru fiecare tranziţieM : L → 0,1, funcţia de marcaj, defineşte numărul de simboluri

din fiecare locaţie

Condiţii şi resurseReţelele de tip C/E modelează fluxurile de informaţii, la nivel fundamental (true/false)

Aplicaţii: cele in care fluxul de resurse si/sau numarul de resurse disponibile este important (document workflow, data flow, linii de fabricaţie, reţele de comunicaţie, www)data flow, linii de fabricaţie, reţele de comunicaţie, www)

2

3

Reţelele de tip P/T reprezintă o generalizare (extensie) imediata:n Elementele de stare sunt echivalente locaţiilor

unde sunt stocate resurse (jetoanele)n Elementele de acţiune sunt reprezentate de

tranziţiile locale sau transportul resurselorn Poate fi aplicata o descriere matematica

similara cu cea a RP C/E

Exemplu RP: O reţea PT (1)p1

p2p3

t2p4t3

p5

t6t1

p8

p5 p6 p7t4 t5

Exemplu RP (2)p1

p2 p3

t6t1

p8

t2p4t3

7654321

001010100000010000001000100000000100000010000001

Pre

pppppppp

=

p5

p5 p6 p7t4 t5

654321

87

001010tttttt

p

654321

87654321

010100010000001000000001000100000010000001100000

Post

tttttt

pppppppp

=Matricea de incidenţă

−−−

−−

−−

−−

==

011110110000011000001001100100000110000011100001

Pre-PostI

Exemplu RP (3)p1p2 p3

p5

t6t1 p8

t2p4

p5

p

p7

t3

t t

=

=000014

)()5()4()3()2()1(

pMpMpMpMpMpM

M

=′

000104

Mp6t4 t5

110

)8()7()6(

pMpMpM

p5 p7

p1p2 p3

p5

t6t1 p8

t2p4

p6

t3

t4 t5

010

t2 este validata si se declanseaza

),(),(Post),(Pre'

tCMttMM

⋅+=⋅+⋅−=

O reţea PT poate fi mai întâi definită structural, de ex. prin 5-tuplul: (P, T, A, C, w), unden P este o mulţime finită de poziţii (locaţii)n T este un set finit de tranziţiin A este o mulţime de arce, o submulţime a mulţimii

(P×T)∪(T×P)

O alta definiţie formală (pt. reţele PT)

(P×T)∪(T×P) n C: P → (N ∪ ∞) \0 este o funcţie de capacitate a

poziţiilor (capacitatea unei poziţii e implicit nelimitată)n w e funcţia de ponderare aplicată arcelor, w:A→1,2,3 ...

(ponderea unui arc se consideră implicit unitară)Prin M0: P → N ∪ ∞ notăm funcţia numită marcaj iniţialDefiniţia dinamică a reţelei PT constă în evidenţierea modalităţilor (legilor) de evoluţie a marcajului iniţial

Modelarea conceptelor dinamice in RP (1)(C/E si PT)

A B

concurenţă

A B A B

concurenţă sincronizare comunicare

A B

conflict/alegere

A B

resurse/multiplicitate

A B

date/individualitate

Modelarea conceptelor dinamice in RP (2)

(a) secvenţiere; (b) ramificaţie; (c) sincronizare;(d) conflict la resurse; (e) concurenţă

Concluzii (modelare cu reţele Petri elem.)

Se poate utiliza pentru a testa şi valida anumite proprietăţi utile ale sistemelorn Siguranţa: este garantată prin faptul că numărul de

simboluri nu creşte nedefinitFuncţionalitatea: este garantată prin lipsa blocajelor n Funcţionalitatea: este garantată prin lipsa blocajelor → va exista întotdeauna cel puţin o tranziţie care poate fi declanşată

Avantaj: modelarea sistemelor concurenteDezavantaj: nu este utilă pentru sisteme complexe

Modele şi limbajeUn model computaţional: descrie funcţionalitatea dorită a sistemului → noţiune conceptualăLimbajul: descrie modelul sub o formă concretăUn model poate fi descris într-o varietate de Un model poate fi descris într-o varietate de limbajen Exemplu: model al programului secvenţial → C,

C++, Java

Un limbaj poate descrie o varietate de modelen Exemplu: C++ → model obiectual, model al

programului secvenţial, automat de stare

Exemplu

Controler pentru un ascensorn Specificaţie modificată:

“Deplasează ascensorul în sus sau în jos până la etajul cerut. La etajul cerut, deschide uşa pentru cel etajul cerut. La etajul cerut, deschide uşa pentru cel puţin 10 secunde şi păstrează uşa deschisă până când etajul cerut se modifică. Păstrează uşa închisă în timpul deplasării. Schimbă direcţia doar dacă nu sunt cereri la etaje superioare în timpul deplasării în sus sau dacă nu sunt cereri la etaje inferioare în timpul deplasării în jos…”

Interfaţa sistem

Două blocuri:n RezCereri

rezolvă diferitele cereri de etaje într-un

UnitControl

b1

down

open

floor

req

up

cereri de etaje într-un singur etaj cerut

n UnitControldeplasează ascensorul la etajul cerut

butoane îninteriorul

ascensorului

b1...

RezCereri

...

butoaneup/down la fiecare etaj

b2bNup1

up2dn2

dnN

up3

dn3

dn1

Descrierea unităţii de controlInputs: int floor; bit b1..bN; up1..upN-1; dn2..dnN;Outputs: bit up, down, open;Global variables: int req;void UnitControl()

up = down = 0; open = 1;while (1)

while (req == floor);while (req == floor);open = 0;if (req > floor) up = 1;else down = 1;while (req != floor);up = down = 0;open = 1;delay(10);

Modelul ASF pentru UnitControl

GoingUp

req > floor

!(req > floor)

req > floor

u,d,o, t = 1,0,0,0timer < 10

Idle

req < floor

!(timer < 10)

req < floor

DoorOpen

GoingDn

u,d,o,t = 0,0,1,0

u,d,o,t = 0,1,0,0

u,d,o,t = 0,0,1,1

u: up; d: down; o: open; t: timer_start

req == floor

!(req < floor)

Modelul ASFIC (1)Modificarea controlerului pentru ascensor n Intrarea fire → trecerea în modul de incendiun Deplasarea ascensorului la primul nivel şi deschiderea uşii

Fără ierarhie

req>floor UnitControl

Idle

GoingUp

req>floor

req<floor

!(req>floor)

timeout(10)

req<floor

DoorOpen

GoingDn

req>floor

u,d,o = 1,0,0

u,d,o = 0,0,1

u,d,o = 0,1,0

req==floor!(req<floor)

fire

firefire

fire

FireGoingDn

floor>1

u,d,o = 0,1,0

u,d,o = 0,0,1

!fire

FireDrOpen

floor==1

fire

u,d,o = 0,0,1

UnitControl

Modelul ASFIC (2)Cu ierarhie

GoingUp

req>floor

!(req>floor)req>floor

u,d,o = 1,0,0

ModNormal

UnitControl

fire

!fireFireGoingDn

floor>1

u,d,o = 0,1,0

FireDrOpen

floor==1

fire

ModIncendiu

u,d,o = 0,0,1

Idle

req<floor

timeout(10)

req<floor

DoorOpen

GoingDn

u,d,o = 0,0,1

u,d,o = 0,1,0

req==floor!(req>floor)

u,d,o = 0,0,1

Modelul ASFIC (3)Controlerul pentru ascensor reprezentat prin modelul ASFIC cu două stări concurente

ControlerAscensor

Cu starea concurentă RezCereri

ModNormal

ModIncendiu

fire!fire

UnitControl

ControlerAscensor

RezCereri

...

Exemplu ASF/ RPAutomat de distribuţie (vânzare): n Distribuie 2 tipuri de batoane, de 20 bani si 15 banin Se pot folosi doar 2 tipuri de monede, de 10 b si 5bn Nu returnează rest

Modelarea:n Se realizează diagrama de tranziţie a stărilorn Se obţin apoi modelele cu ASF si RP

Modelul ASF

155

10

vânzare baton 15b

5

201010

55

10

5

vânzare baton 20b

0

Modelul cu RP ordinară (maşină de stare)

510

vânzare baton 15b

10

5

5

10

5

vânzare baton 20b

Modele bazate pe urmeComportarea SDED este in mod naturaldescrisa de înregistrarea sau urma “lăsată” deapariţia unor schimbări discrete, calitative, insistemMicro-schimbările continue, cantitative pot fi pursi simplu ignorateIn afara modelelor bazate pe stare, modelelebazate pe urme, studiate la diferite nivele,sunt foarte utile

Nivele de studiu/ modelare (1)Nivelul logic – “urma” este secvenţa de

evenimente, in ordinea aparitiei lors = e1 e2 e3 ...;

Exemple: Exemple: n reţelele Petri (“cazuri” = urme)n maşinile cu stări finite (Wonham) n procesele recursive finite (Inan-Varaiya) n procesele secvenţiale comunicante (Hoare)

Nivele de studiu/ modelare (2)

Nivelul temporal - urma este secventa de perechi

s = (e1,t1) (e2,t2) (e3,t3) ...

Exemple: Exemple: n reţele Petri temporale n modele algebrice min-maxn grafuri data-flow

Nivele de studiu/ modelare (3)Nivelul statistic - comportarea sistemului e

descrisa de secvenţa perechilor de v.a.s = (e1,t1) (e2,t2) (e3,t3) ...

(unde ei si ti sunt v.a. si pentru orice realizare ω, s(ω)= (e (ω),t (ω)) (e (ω),t (ω)) (e (ω),t (ω)) ... este o= (e1(ω),t1(ω)) (e2(ω),t2(ω)) (e3(ω),t3(ω)) ... este ourma descrisa la nivel temporal)

Exemple:Lanţurile MarkovSistemele cu cozi de aşteptare si reţelele de coziModelele de simulare - având la baza procesele semi-Markov generalizate (GSMP)

Alte tipuri de modele (1)Modele orientate pe activitaten Descriu sistemul ca un set de activităţi

n Activităţile sunt asociate prin dependenţe de date sau de execuţiedate sau de execuţie

n Exemplu: graf al fluxului de date

n Se utilizeaza pentru sisteme dominate de datew Transformă şiruri de date de intrare în şiruri de

date de ieşire → sisteme DSP

Alte tipuri de modele (2)Modele orientate pe daten Reprezintă sistemul ca o colecţie de date

asociate prin atribute, apartenenţă la clase etc.etc.

n Utilizate mai ales pentru sisteme de programen Exemplu: diagramele E/R (entitate – relaţie)

<fig>

Alte tipuri de modele (3)Modele orientate pe structurăn Descriu modulele fizice ale sistemului şi

interconexiunile dintre acestean Nu reprezintă funcţionarea sistemuluin Exemplu: schemă-blocModele eterogenen Integrează caracteristici ale mai multor

modele n Exemplu: graf al fluxului de control/date

Alte clasificăriModele analitice (teoretice)n sistemice, in general deterministe , descrierea se

face la nivel logic sau temporaln operaţionale, in general probabilistice (statistice)

Modele de simularen derivate din modelele operaţionalen adecvate pentru analiza asistata de calculator

Pentru modelarea SDED la nivel statistic (cea mai completa) se pot folosi in tandem: n modele operaţionale + modele de simulare

Utilizarea modelelor statisticeModelele operaţionale - se pot folosi in cazurile când putem obţine prin calcul formule/ rezultate exacte (având modalităţi de a simplifica problemele computaţionale)n Exemple: sisteme cu cozi de aşteptare, reţele de cozin Limitare: cozi simple

reţele de cozi factorizabilereţele de cozi factorizabile

Modelele de simulare - oferă un instrument complet ce aproximează dinamica sistemului prin oferirea de ipostaze non-continue incrementalen Pro:

Dinamica originala a SDED este de acest tip!n Contra:

Dificultăţi computaţionale (există soluţii!)


Modelarea logică şi controlul


Modelarea logică şi controlul supervizor al sistemelor dinamice cu

evenimente discrete

Modelare şi control cu automate finiteLimbaje formale şi expresii regulateObţinerea modelelor ASF. Echivalenţa stărilor

Sumar

stărilorControlul supervizor: descrierea problemei şi implementărilorStudiu de caz: Controlul supervizor al unei reţele de calculatoare conectate liniar

Alegerea unui model pp. un compromis între:n Puterea de modelare (generalitatea)w reţelele Petri includ strict clasa automatelor finite şi sunt la

rândul lor strict incluse în clasa algebrelor procesuale

n Complexitatea modelului

Modelare şi control

n Complexitatea modelului w aceasta implică şi complexitatea controlului

De exemplu, o problemă de control poate fi: n indecidabilă (nu se poate găsi un algoritm finit pentru

rezolvare) pentru un model sistem cu reţele Petri sau algebre procesuale

n rezolvabilă în cazul modelării SDED cu automate de stare finite (ASF), ce facilitează sinteza unui controler

Modelul ASF este un model formal bazat pe stare, ce consideră explicit stările unui sistemn Poate apare explozia stărilor (multiplicarea stărilor,

exponenţial, cu depăşirea unui prag de complexitate)! De aceea, majoritatea modelelor SDED nu consideră

Modele ASF pentru control

n De aceea, majoritatea modelelor SDED nu consideră explicit stările - abordare incompletă ce poate oferi doar observarea unui sistem, nu şi controlul !

ASF au o aplicabilitate foarte largă, caracterizată de generalitate, putere analitică şi controlabilitate n Cea mai cunoscută aplicaţie: în teoria compilării, la

recunoaşterea limbajelor regulate

Ideea utilizării ASF în modelarea logică a SDED: orice SDED este “un generator de limbaj”El are un “alfabet” de evenimente asociat şi generează o urmă sau traiectorie

Modelarea SDED cu ASF

Suntem interesaţi de secvenţele de evenimente ce pot fi generate (analogie cu generarea şirurilor de atomi lexicali în limbajele regulate, cf. unui set de reguli)

Asimilarea generatorului cu o structură de tip ASF este utilă pentru aplicarea tehnicilor de control convenţionale

Termenul “generator” este folosit alternativ cu ASF

Definiţie. Un limbaj formal L, definit peste un alfabet (mulţime) de simboluri E, e o mulţime de şiruri (de obicei finite) formate cu simboluri din En Lungimea unui şir este dată de numărul de simboluri alăturate

(concatenate) pentru formarea saŞirul vid, notat ε, ce nu conţine nici un simbol, este considerat

Limbaje formale

n Şirul vid, notat ε, ce nu conţine nici un simbol, este considerat prin convenţie de lungime 0

Dacă evenimentele se consideră ca simboluri din E n “Limbajul” poate fi gândit ca o modalitate formală de a descrie

comportarea unui SDED, ce specifică toate secvenţele admisibile de evenimente pe care SDED e capabil să le “execute”

n O dificultate: simple reprezentări finite ale limbajului nu sunt întotdeauna şi lucrative → sunt necesare modalităţi (expresii) compacte în definiţia sa, manipulabile prin operaţii bine definite

Definiţie. O expresie regulată R este un şir de simboluri construit pe baza alfabetului limbajului (inclusiv şirul vid), folosind doar operaţiile uzuale cu mulţimi (∪, ∩, ¬, etc.), plus operaţiile de concatenare şi închidere (Kleene), definite astfel:

Expresii regulate

concatenare şi închidere (Kleene), definite astfel:n (concatenare) dacă A, B sunt expresii regulate peste E,

atunci AB=cc=ab, a∈A, b∈B e o expresie regulată peste alfabetul E

n (închidere) dacă A este expresie regulată peste E, atunci şi A* = A0 ∪A1∪ ... ∪An-1∪An∪... este o expresie regulată, unde A0=ε şi An=AAn-1, ∀n>0

Definiţie. Un limbaj ce admite doar expresii regulate se numeşte limbaj regulatn Dacă I⊆E* este un limbaj (regulat), se defineşte închiderea lui I,

notată Ī, ca mulţimea tuturor şirurilor ce reprezintă prefixe de şiruri din I, adică: Ī = s s∈E* şi ∃t∈E* a.î. st∈ I

n Dacă limbajul e identic cu închiderea sa, el s.n.închis (prin prefix)

Limbaje regulate

n Dacă limbajul e identic cu închiderea sa, el s.n.închis (prin prefix) Avantajul utilizării expresiilor regulate în descrierea limbajelor este acela că asigură o reprezentare compactă finită, chiar pentru limbaje potenţial infinite (cu număr infinit de şiruri de simboluri)Modelul Ramadge-Wonham: un SDED este asimilat unui limbaj formal (regulat) – sau, mai concret, unui automat generator al acestui limbaj → dar ce fel de automat?Se ştie că ASF generează expresii (deci limbaje) regulate

Teorema lui Kleene. Dacă un limbaj este regulat, există un ASF ce-l genereazăOrice limbaj generat de un ASF este regulat

Definiţia 2.2.3. Un automat (generator) este un 5-tupluG = (X, E, f, x0, Xm)

ASF, limbaje şi expresii regulate

G = (X, E, f, x0, Xm)caracterizat de:n X - mulţimea stărilorn E - alfabetul (mulţimea) de simboluri (evenimente)n f :E×X→X - funcţia de tranziţie - funcţie parţială, în sensul că

pentru o stare x fixată, f(e)=f(e,x) este definită doar pentru o anumită submulţime Γ(x)⊆E, ce depinde de x

n x0 – starea iniţială; n Xm - mulţimea stărilor marcate (se preferă această denumire în

locul celei consacrate ce face referire la aceste stări ca stări finale)

Exemplu

Recunoașterea unei ER folosind generarea sa de către un ASF. Orice expresie regulată E poate fi recunoscută de un

automat finit care recunoaşte orice cuvânt din limbajul descris de E, şi doar acele cuvinte. Starea 1 este starea

iniţială, iar stările 1 şi 2 sunt stări finale

Execuţia ASF când la intrare este prezentat cuvântul ''abbab''. Pentru că după terminarea procesării şirului automatul nu este într-o stare

finală, rezultă că acest cuvânt nu e descris de expresia regulată

Modelul generator pleacă din starea iniţială x0 şi execută tranziţii de stare determinate de secvenţa de evenimenteEvenimentele apărute sunt considerate spontane (nu apar mecanisme de constrângere care să forţeze apariţia lor în sistem), asincrone (fără referire la vreun ceas de timp) şi instantanee (fără durată temporală)Modelul este unul logic ce poate îngloba nedeterminismul:

ASF generator

Modelul este unul logic ce poate îngloba nedeterminismul: mai mult de un eveniment poate fi executabil (validat pentru selecţie) într-o anumită staren Putem adăuga la model o mulţime de evenimente valide în starea

x, Γ(x), dacă ea depinde de stare şi este (în general) diferită de En Nu vom face distincţie între ASF deterministe şi nedeterministe;

definiţia ultimei categorii comportă o singură modificare, a funcţiei de tranziţie a stărilor: f :E×X→2X, unde 2X e mulţimea părţilor lui X

n Deşi, aparent, ASF nedeterministe pot genera un set extins de limbaje, de fapt orice limbaj generat de acesta poate fi generat de un ASF determinist

Notăm E* mulţimea tuturor şirurilor finite de evenimente din E, ce include şirul vid, notat εPutem construi funcţia de tranziţie extinsă, f :E*×X→X definită prin f(ε,x)=x şi f(es,x)=f(e,f(s,x)), ∀x∈X unde f este definită

Funcţia de tranziţie extinsă este tot o funcţie parţială, adică pentru

Funcţia de tranziţie extinsă

n Funcţia de tranziţie extinsă este tot o funcţie parţială, adică pentru o anumită stare x fixată f(s)= =f(s,x) este definită doar pentru o anumită submulţime de secvenţe E*(x)⊆E* ce depinde de x

Trebuie să facem distincţie între: n mulţimea tuturor secvenţelor finite de evenimente ce pot apărean mulţimea tuturor secvenţelor finite de evenimente observabile (de

ex. pentru că ele corespund execuţiei unor procese complete) Este convenabilă de asemenea eliminarea din model a stărilor ce nu pot fi atinse

În evoluţia sa, SDED defineşte: n un limbaj (închis prin prefix) L(G)=s∈E*f(s,x0) definită n un limbaj marcat Lm(G)=s∈L(G)f(s,x0) ∈ Xm

(interpretarea este cea de mai sus, ca mulţime a secvenţelor finite de evenimente ce pot apărea, respectiv ca mulţime a tuturor secvenţelor finite de evenimente ce pot fi observate)

Limbaje generate de ASF

tuturor secvenţelor finite de evenimente ce pot fi observate) Definirea componentelor accesibile se face astfel:n Xac = x∃s∈E* a.î. f(s,x0)=xn Xacm = Xac ∩ Xmn Fac = f E×Xacn Gac = (Xac, E, Fac, x0, Xacm)SDED s.n. accesibil dacă G = Gac şi co-accesibil dacă orice şir (parţial) de evenimente din L(G) se poate completa la un şir din Lm(G): ∀s∈L(G), ∃t∈Lm(G) a.î. st∈Lm(G).

Bazate pe o descriere la nivel logic a unui SDED, se pot găsi mai multe modele ASF n Aparent, ele sunt distincte deoarece au o dimensionalitate diferită

a spaţiului stărilorn De dorit este obţinerea celui cu număr minim de stări, având în

vedere şi explozia spaţiului stărilor, semnalată anterior Reducerea (agregarea) spaţiului stărilor se bazează pe

Echivalenţa stărilor

Reducerea (agregarea) spaţiului stărilor se bazează pe echivalenţa stărilor, a cărei definiţie (cea considerată aici) are în vedere o raportare la stările marcate Definiţia 2.2.4. Fiind dat ASF: (X, E, f, x0, Xm, Γ), dacă X este spaţiul stărilor, R⊆X e un spaţiu de stări echivalentcu X, relativ la Xm, dacă ∀x,y∈R stări distincte şi orice şir u, f(x,u)∈Xm d.d. f(y,u)∈Xmn Altfel spus: orice şir comun aplicat stărilor x şi y conduce la

acelaşi set de stări marcate n Distincţia între x şi y e imposibil de făcut prin observaţia pasivă a

sistemului, iar x şi y pot fi tratate ca o unică stare “agregată”

Evoluţia SDED modelat prin ASF, aşa cum a fost descrisă până acum, este o evoluţie spontană, necontrolatăPentru un sistem dinamic în general şi pentru un SDED în particular:n dacă starea completă a sistemului este observabilă, se poate

Controlul supervizor: Problema

n dacă starea completă a sistemului este observabilă, se poate construi un controler în buclă de reacţie (feedback controler)

n dacă doar evenimentele sunt observabile, implementarea unui controler se face aplicând în prealabil un artificiu ce constă în crearea unei copii a sistemului ce se execută în paralel şi sincron cu sistemul, acţiunea de control necesară fiind decisă prin măsurarea stării copiei sistemului

Controlerul sau copia sistem plus controlerul formează un supervizor

Schema controlului supervizor

SDEDSistem de

observare a evenimentelor

Stare

Evenim.observate

Intrări de control

Copie SDEDFeedback Controler(compensator dina-mic de stare) Stare

(estimată sau exactă)

SUPERVIZOR

Se partiţionează E prin identificarea a 2 submulţimi:n mulţimea evenimentelor controlabile Ec – acelea ce pot fi validate

sau invalidate din exteriorul sistemului datn mulţimea evenimentelor necontrolabile Enc (Ec∩Enc=Φ) – sunt cele

a căror apariţie nu poate fi prevenită şi deci pot fi considerate permanent validate

Controlul supervizor: Implementarea

permanent validate

Un supervizor poate controla SDED prin: n observarea secvenţelor de evenimente generate n dezactivarea, activarea sau forţarea evenimentelor controlabile,

pentru a îndeplini un obiectiv de control, în funcţie de secvenţele observate

Prin aceasta, supervizorul asigură generarea de către sistem a unui sublimbaj a lui L(G)

Formal, supervizorul poate fi introdus ca tuplu S=(S,Ψ): n S=(Y, E, g, y0, Ym) e automat generator, numit şi recunoscător –

recunoaşte un limbaj asupra aceleiaşi mulţimi de evenimente E n Ψ: E×Y→0,1 (sau, echivalent, Ψ: Y→2E) – este o funcţie de

control feed-back cu valori în şablonul de control sau mulţimea de validare a evenimentelor (1-validare, 0-invalidare)

Supervizorul urmăreşte/controlează comportarea SDED-G:

Supervizorul

Supervizorul urmăreşte/controlează comportarea SDED-G:n Îşi schimbă starea conform cu evenimentele generate de G n Aplică Ψ, pentru validarea/invalidarea evenimentelor controlabile

din subsetul ce generează tranziţii în starea corespunzătoare din GPrin această legare, funcţiile de tranziţie atât pentru G, cât şi pentru S, sunt modificateComportarea în buclă deschisă a SDED-generator G (dar închisă prin prefix), aşa cum a fost descrisă ea anterior, este dată de limbajul închis (prin prefix):

L(G)=s s∈E* & f(s,x0) definită

Pentru automatul generator notat S/G, se generează un limbaj L(S/G), caracterizat de faptul că generarea unui şir s din acest limbaj este permisă d.d. s∈L(G) şi s∈L(S), iar fiecare eveniment e∈S este validat de funcţia ΨComportarea marcată a automatului generator e dată prin Lm(S/G)– limbaj ce conţine acele şiruri din L(S/G) marcate atât în G cât şi în SSupervizorul este văzut în acest caz ca o funcţie S : L → Γ⊆2E ce

Comportarea în buclă închisă

Supervizorul este văzut în acest caz ca o funcţie S : L → Γ⊆2E ce specifică pentru fiecare şir de evenimente s∈L intrarea de control ce poate fi aplicată (Γ e notaţia pentru mulţimea intrărilor de control)Limbajul (închis prin prefix) generat de sistemul în buclă închisă, notat L(S/G), este definit de următoarele condiţii:a) ε∈L(S/G);b) şirul st ∈ L(S/G) d.d. s ∈ L(S/G), t ∈ S (s) şi st ∈ L(G).

Se spune că SDED generator G şi supervizorul S se execută în paralelastfel: un eveniment e∈E poate apare atunci când G×S este în starea (x,y) d.d. el este posibil atât în G în starea x, cât şi în S în starea y

Specificaţia globală a unei probleme de control pentru sisteme de calcul, reţele de calculatoare sau sisteme distribuite poate fi foarte generală Exemplu: “controlul tranziţiilor de stare ce pot asigura o funcţionare eficientă, non-blocantă şi rapidă a unei reţele”

Probleme de control globale în sistemele de calcul

funcţionare eficientă, non-blocantă şi rapidă a unei reţele” Rezolvarea problemei pentru această categorie de sisteme se poate face şi global, dar în general, din motive de reducere a complexităţii, ea se face local În sistemele distribuite, se implementează supervizorul ca sistem descentralizat şi localn el este compus dintr-o mulţime de subsisteme supervizor n fiecare dintre acestea observă şi controlează o parte a sistemului

global, prin accesul doar la o parte a evenimentelor controlabile

Se impun: n rafinarea specificaţiei în sub-specificaţii locale, după

descompunerea în subsisteme a sistemului distribuit dat (etapă care în general nu ridică probleme şi admite mai multe soluţii)identificarea subspecificaţiei unei probleme de control

Acţiuni specifice locale

n identificarea subspecificaţiei unei probleme de control este echivalentă de multe ori cu impunerea unor noi reguli locale de operare

n trasarea unei scheme de prioritate în cazul suprapunerii acţiunilor de control, datorată suprapunerii parţiale a subsistemelor controlate w acest lucru este necesar deoarece o soluţia descentralizată

indică doar acţiunile de control ce trebuie luate de fiecare supervizor local

Studiu de caz

Controlul supervizor al unei reţele Controlul supervizor al unei reţele de calculatoare conectate liniar

Descrierea problemeiFormularea unui protocol de control al unei reţele de cozi compusă din N servere aranjate liniar, fiecare având o coadă de intrare de capacitate limitată

S2S1 B1

...

Bn Sn+1

Sistem global(reţea de servere interconectate liniar)

Rafinarea specificaţieiUn mesaj ce intră în sistem este procesat de primul server, transmis apoi pentru a fi procesat în coada următorului server ş.a.m.d., până ce este procesat de toate serverele şi părăseşte sistemul Serverele se pot defecta (căderi de curent), nu înainte însă de a salva starea curentă, pentru a relua procesarea după reparare din exact acelaşi punct după reparare din exact acelaşi punct La intrarea şi ieşirea din reţea, înainte de S1 şi după Sn+1, se află buffere de capacitate pp. nelimitată (nu au influenţă asupra sistemului, de aceea nu au fost figurate)Fiecare server Si se poate afla în una dintre următoarele 3 stări: liber (Idle); ocupat (Working); defect (Defective)Bufferul Bi plasat înaintea serverului Si are tot trei stări posibile: buffer gol (0); buffer ocupat (1); buffer plin (2)

Diagramele de stare pentru Si şi Bi

Stările iniţiale sunt marcate în figura următoare printr-o săgeată incidentă; fiind considerate totodată stări marcate, săgeata e cu dublu sens

Serverul S Bufferul BI

WD

0

1 2

si ei

di

ri

Serverul Si

si+1

ei

ei

si+1

Bufferul Bi

Descrierea formală a sistemuluiConsiderând separat fiecare server şi fiecare buffer ca SDED generatoare de evenimente, comportarea (închisă) în buclă deschisă a fiecărui automat de acest fel poate fi descrisă folosind formalismul expresiilor regulate astfel:

L(Si) = (si(diri)*ei)*(ε+si(di+(diri)*))L(Si) = (si(diri)*ei)*(ε+si(di+(diri)*))L(Bi) = (ei(eisi+1)*si+1)*(ε+ei(ei+(eisi+1)*))

Limbajele marcate, Lm(Si)= (si(diri)*ei)* şi Lm(Bi)= (ei(eisi+1)*si+1)*, subliniate în expresiile anterioare, respectă totodată condiţiile:

Lm(Si) ⊆ L(Si) şi Lm(Bi) ⊆ L(Bi)

Problema localăDescompunem reţeaua în subreţele suprapuse parţial, formate din serverele Si şi Si+1 şi bufferul Bi dintre eleUrmărim determinarea subsistemelor supervizor CSi ce le controlează local Vom impune apoi pentru controlul global constrângeri:Vom impune apoi pentru controlul global constrângeri:n Ex: prioritatea supervizorului de index minim (CSi-1) în cazul

implementării de acţiuni locale conflictuale asupra aceluiaşi server Si

Fără a pierde generalitatea, rezolvăm problema pentru supervizorul CS1 – subsistemul format din serverele S1 şi S2 şi bufferul B1

Subsistemul local controlatAcţiunea supervizorului se poate exercita doar asupra evenimentelor controlabile, “început prelucrare la serverul Si (si)” sau “repararea serverului Si (ri)”, prin variabilele de control validare start (vsi), respectiv validare reparaţie (vri)

I

D

si/vsi

ei

di

ri/vri

Serverul Si

S2S1 B1

validare reparaţie (vri)

Reguli locale de operare1. Serverul S1 nu poate începe servirea dacă B1 plin – pt. a

evita ca evenimentul sfârşit prelucrare la serverul S1 să încerce scrierea într-un buffer plin (e1 necontrolabil)

2. Serverul S2 nu poate începe servirea dacă bufferul B1 gol3. Serverul S1 nu poate începe servirea dacă serverul S2

este defect (pericol de blocaj prin umplerea bufferului)3. Serverul S1 nu poate începe servirea dacă serverul S2

este defect (pericol de blocaj prin umplerea bufferului)4. Dacă S1 şi S2 defecte simultan, S1 trebuie reparat primul

(pentru a preveni blocajul)5. Serverele S1 şi S2 nu pot începe servirea dacă deja

lucrează6. Un server defect nu poate valida începutul servirii (se pp.

că serverele se pot defecta doar în timp ce lucrează), ci doar terminarea reparaţiei

Codificarea stărilor Pentru sistemul local controlat (S1-B1-S2) există 3x3x3(27) stări posibile

Regulile 1-6 permit înlăturarea a 6 stări, cele în care S1

este ocupat sau defect şi B1 plin

Proiectarea controlerului Trebuie făcută astfel încât doar tranziţiile de stare permise să aibă loc

Acţiunea se poate exercita doar asupra evenimentelor controlabile “început prelucrare la serverul Si (si)” şi “repararea serverului S (r )”, prin variabilele de control “repararea serverului Si (ri)”, prin variabilele de control validare start (vsi), respectiv validare reparaţie (vri)

Următoarea tabelă, a stărilor reduse ale controlerului , indică valorile variabilelor de control necesare în fiecare stare a sistemului controlat: 0 – invalidare, 1 – validare, X – valoare indiferentă

Reducerea stărilor controleruluiPutem considera pentru controler acelaşi număr de stări ca pentru sistemul controlat (0, 1, X), sau putem reduce numărul de stări- deci complexitatea controlerului, luând doar combinaţiile distincte pentru variabilele de control

1

2410

3

56

16

1218

e1

s1 e2

s2

e2

e

e2

e2

e1

d2

d1

d1

d1

r1

d2

d2

r2

r2

r2

r1

Diagrama stărilor sistemului local controlat (S1-B1-S2)

56

7

8

9

11 17

1913

14

15

21

20

e1

s1

e1

s2

e2

s1

e1

e1

e2

d1

r1

d1

r1

d1

r1

d2

r2

d1

d2d2 r2

r2

r1d2

r2

s2 s2

1 3e1

s2

2

d2

r2 r2

d2

d2

r2

e2

e2

s1,

s1,

e1

8Diagrama stărilor controlerului

5 7s2

d1d1 r1

r1

6

d1

r1

d2d2

r2

e2e2

4


Modelare dinamică cu reţele Petri.


Modelare dinamică cu reţele Petri. Analiza RP

Caracteristici dinamice ale SED/ modelelor cu RPn Elemente constitutive (structurale) ale RPn Dinamica sistemelor cu RPTipuri simple de RP. Exemplen RP ordinare

Sumar

n RP ordinaren RP generalizate

Metode de analiză a RP ordinaren Analiza accesibilităţii

n Determinarea invarianţilor

Alte proprietăţi şi clasificări derivate

Caracteristici dinamice in sistemele cu evenimente discrete

SED sunt inerent dinamice si paralele, pot fi caracterizate prin 3 trăsături esenţiale de comportament,superpozabile:

n Concurenţa: posibilitatea ca mai multe evenimente să aibă loc de o manieră independentă unul faţă de altul

Sincronizarea: se referă la necesitatea ca execuţia n Sincronizarea: se referă la necesitatea ca execuţia anumitor evenimente să aştepte producerea altor evenimente

n Conflictele (interblocajele): o manieră de a ţine cont de competiţia între acţiuni multiple simultane sau de anumite fenomene, precum excluderea mutuală

Reţele Petri (RP)Reţele Petri (RP)Surprinderea unor astfel de trăsături necesită adoptarea unor modele care să înglobeze în cel mai înalt grad dinamica sistemelor modelate:

FSM, DTS (diagrame de tranziţie a stărilor)FSM, DTS (diagrame de tranziţie a stărilor)RPRP, , introduse in 1962 de introduse in 1962 de CC.. AA.. PetriPetrinn Profesor onorific al Universităţii din HamburgProfesor onorific al Universităţii din Hamburg

nn Membru al Academia EuropæMembru al Academia Europæ

nn In 2007 a fost onorat pentru întreaga In 2007 a fost onorat pentru întreaga activitate de către ATLAS ("Academy of activitate de către ATLAS ("Academy of Transdisciplinary Learning and Advanced Transdisciplinary Learning and Advanced Studies“) cu "Academy Gold Medal of Honor“Studies“) cu "Academy Gold Medal of Honor“

ReţeleReţelelele Petri Petri (cont.)(cont.)

Utilizează stări distribuite şi tranziţii localeAu permis iniţial modelarea unor sisteme cu componente concurente în interacţiune, fiind extinse ca instrumente matematice generale ulteriorModelarea dinamică necesita astfel de descrieri de tip Modelarea dinamică necesita astfel de descrieri de tip calitativ (logic) care să poată servi ca bază pentru analiza şi sinteza SDED Accentul este pus pe modelarea dependenţelor cauzale, fără sincronizare globală (doar transmitere de mesaje)Pe lângă anumite proprietăţi analitice, caracterul vizual al RP poate fi un element important în modelare

Elemente constitutive structurale(Logic)n Condiţii

Pot fi îndeplinite sau nu.n Evenimente

Pot avea loc daca anumite condiţii sunt îndeplinite.Relaţii (flux de control) n Relaţii (flux de control) Arata relaţiile intre condiţii si evenimente.

→Condiţiile, evenimentele si relaţiile formează un graf bipartit (graf cu doua tipuri de noduri)

(Grafic)n Locaţii (cercuri)n Tranziţii (dreptunghiuri)n Arce, ce conectează locaţiile cu tranziţii sau tranziţiile

cu locaţii

Concept dinamic cheie: Tranziţia stărilor

Logic, reprezintă apariţia unui eveniment/ o acţiuneGrafic, este mişcarea unor jetoane (token-uri), notate ca puncte negre, din locaţie în locaţie, prin “aprinderea” tranziţiilor Aceasta din urma depinde de condiţiile de intrare simbolizate de disponibilitatea jetoanelorsimbolizate de disponibilitatea jetoanelorSpunem ca o tranziţie este validata daca exista un număr suficient de jetoane in locaţiile sale de intrareO tranziţie validata se poate aprinde oricândDupă aprindere, token-urile vor fi transferate de la locaţiile de intrare (stare veche) către cele de ieşire, fiind astfel un element de identificare si in acelaşi timp o notaţie pentru noua stare

Arce si capacităţiArcele au implicit capacitatea 1; daca este diferita de 1, capacitatea este marcata pe arc Locaţiile au implicit capacitate infinitaO tranziţie este validata daca numărul de jetoane in fiecare din

Locaţie cu token

numărul de jetoane in fiecare din locaţiile sale de intrare este cel puţin egal cu capacitatea arcului ce o uneşte cu o locaţie de intrare

P1

P2

T1

Arc de capacitate 1

TranziţieLocaţie

Exemplul 1Automat de distribuţie (vânzare): n Distribuie două tipuri de batoane, de 20 de

bani si de 15 banin Doar două tipuri de monede pot fi folosite, de n Doar două tipuri de monede pot fi folosite, de

10 bani si de 5bn Nu returnează rest

Reprezentare prin diagrama tranzitiilorde stare, ca automat cu stări finite

5 bani 15 baniDepunere 10b

Ia baton de 15b

0 bani

10 bani 20 baniDepunere 10b

Ia baton de 20b

Reprezentare prin RP

5b

Ia baton de 15b

Depunere 5b

Depunere 10b15b

0b

Depunere 10b

Depunere5b

10b

Depunere5b

Depunere 10b20b

Depunere5b

Ia baton de 20b

Scenarii de evolutie

Scenariul 1: n Depunere 5b, depunere 5b, depunere 5b, depunere

5b, ia baton de 20b.Scenariul 2:n Depunere 10b, depunere 5b, ia baton de 15b.n Depunere 10b, depunere 5b, ia baton de 15b.

Scenariul 3:n Depunere 5b, depunere 10b, depunere 5b, ia baton

de 20b.

Dinamica sistemului

5b

Ia baton de 15b

Depunere 5b

Depunere 10b15b

0b

Depunere 10b

Depunere5b

10b

Depunere5b

Depunere 10b20b

Depunere5b

Ia baton de 20b

Tipuri de reţele PetriTipuri de reţele Petri (crit. structural)

RP ordinare, în care fiecare arc nu poate avea decât capacitatea (funcţia de ponderare) egala cu 1n Maşinile de stare (MS) – RP unde orice tranziţie are exact

o locaţie de intrare şi o locaţie de ieşire:n Grafurile marcate, GM) - orice locaţie are 1! tranziţie de

Tttt ∈∀== •• ,1||||n Grafurile marcate, GM) - orice locaţie are 1! tranziţie de

intrare şi 1! tranziţie de ieşire: n Reţelele cu alegere liberă (AL) – dacă 2 tranziţii au o

locaţie de intrare comuna, atunci au toate locaţiile de intrare comune: (sauechiv. dacă 2 locaţii au o tranziţie comuna de ieşire, vor avea toate tranziţiile de ieşire comune)

n Reţelele cu alegere liberă extinse (ALE) –acele RP ce pot fi transformate in RP AL

Pppp ∈∀== •• ,1||||

'',', ttttTtt •••• =⇒≠∩∈∀ φ

Tipuri Tipuri simple simple de reţele Petride reţele Petri (cont.)n Reţelele cu alegere asimetrică (AA) – RP în care, dacă două

locaţii au o tranziţie comuna de ieşire, atunci una din ele are toate tranziţiile de ieşire ale celeilalte (posibil altele in plus)

RP

PN

RP

AA ALE AL MS GM

RP generalizate, unde pot fi aplicate ponderi generale arcelor

Grafuri marcate

Nu poate exista conflict pe resurse, dar putem avea concurenţă(ramificare, sincronizare)

RP cu AL (“free-choice”)Foarte utilizate in modelarea conceptelor de flux (control)Realizeaza un compromis rezonabil intre puterea descriptiva siposibilitatea de analiza: “rezultatul alegerii intre 2 tranzitii nu poate fi influentat de restul sistemului (alegerile sunt libere)” In exemplul de mai jos, avem alegere libera pentru prima retea; In exemplul de mai jos, avem alegere libera pentru prima retea; pentru cea de-a doua, datorita sincronizarii la t2, tranzitia t3 poate influenta alegerea lui t1 sau t2

Reţele Petri “clasice”

Reţele condiţii/evenimente (C/E)Sunt cele folosite în introducerea RP:o subclasă de reţele Petri in care locaţiile pot avea 1/0 simboluri, ce pot modela atâtcondiţii cât și evenimente:

locaţiile reprezintă condiţii, ce pot avea inscrise valori true/ falsen locaţiile reprezintă condiţii, ce pot avea inscrise valori true/ falsen tranziţiile reprezintă evenimente locale

Un eveniment este validat d.d. n toate pre-condiţiile sale (conectate prin arce incidente) sunt true n toate post-condiţiile sale sunt false

Apariţia unui eveniment neagă pre- și post-condiţiile sale

Reţele C/E (cont.)Evenimentele cu aceleaşi pre- sau post-condiţii sunt in conflict Doar evenimentele non-conflictuale validate pot apărea concurentTerminologie:

Marcajul reţelei = distribuţia token-urilorn Marcajul reţelei = distribuţia token-urilorn Sistem C/E= reţea C/E + marcajn Configuraţii: marcaje posibile ale unei reţele C/En Cazuri ale unui sistem C/E: configuraţii accesibile din

marcajul iniţial (→ case graph)

Automatele sunt o subclasă secvenţiala a sistemelor C/Eexact o condiţie este adevărata,fiecare eveniment are o singura pre- si post-condiţie

Descrieri formaleGrafice (grafuri bipartite)/ matematice: au semanticăformală şi posibilităţi de analizăn Caracteristici importante: stări distribuite şi tranziţii locale

Sistemice: RP = <P, T, Pre, Post, M>P = l0, l1, …, lm setul poziţiilor (locaţiilor)P = l0, l1, …, lm setul poziţiilor (locaţiilor)T = t0, t1, …, tn setul tranziţiilorPre : T → L+, funcţia de intrare, ce defineşte locaţiile care

furnizează intrări unei tranziţiiPost : T → L+, funcţia de ieşire, defineşte locaţiile de ieşire

pentru fiecare tranziţieM : L → 0,1, funcţia de marcaj, defineşte numărul de

simboluri din fiecare locaţie

Condiţii şi resurseReţelele de tip C/E modelează fluxurile de informaţii, la nivel fundamental (true/false)

Aplicaţii: cele in care fluxul de resurse si/sau numarul de resurse disponibile este important (document workflow, data flow, linii de fabricaţie, reţele de comunicaţie, www)data flow, linii de fabricaţie, reţele de comunicaţie, www)

2

3

Reţelele de tip P/T reprezintă o generalizare (extensie) imediata:n Elementele de stare sunt echivalente locaţiilor

unde sunt stocate resurse (jetoanele)n Elementele de acţiune sunt reprezentate de

tranziţiile locale sau transportul resurselorn Poate fi aplicata o descriere matematică

similară cu cea a RP C/E

O reţea PT e o reprezentare de forma (P, T, A, C, w, M0), formată dintr-o parte structurală şi o parte dinamică.Partea structurală este un graf orientat bipartit unde:n P este o mulţime finită de poziţii (locaţii)n T este un set finit de tranziţii

A este o mulţime de arce, o submulţime a mulţimii (P×T)∪(T×P)

Reţele poziţii/tranziţii (P/T)

n A este o mulţime de arce, o submulţime a mulţimii (P×T)∪(T×P) n C: P → (N ∪ ∞) \0 este o funcţie de capacitate a poziţiilor

(capacitatea unei poziţii se consideră implicit nelimitată)n w este o funcţie de ponderare aplicată arcelor, w:A→1,2,3 ...

(ponderea unui arc se consideră implicit unitară)

Prin M0: P → N ∪ ∞ notăm funcţia numită marcaj iniţialPartea dinamică a reţelei PT constă în evidenţierea modalităţilor (legilor) de evoluţie a marcajului iniţial

Starea Starea şşi evoluţia reţelelor PTi evoluţia reţelelor PTStarea unei reţele PT date (definită structural) e complet descrisă de marcajul său M=[M(p1), M(p2),…,M(pn)]Spaţiul stărilor unei RPT marcate este complet definit de marcaje, adică de toţi vectorii n-dimensionali ale căror elemente sunt pozitive, M=0, 1, 2, …n

O tranziţie tj∈T într-o RPT marcată este validată dacă:O tranziţie tj∈T într-o RPT marcată este validată dacă:n M(pi) ≥ w(pi, tj), pentru orice pi∈I(tj);n M(pk) ≤ C(pi)-w(tj, pk), pentru orice pk∈O(tj)- I(tj);n M(p) ≤ C(p)-w(tj, p) + w(p, tj), pentru orice p∈O(tj) ∪ I(tj),

unde I(ti) este mulţimea locaţiilor de intrare în tranziţia tiiar O(ti) mulţimea locaţiilor de ieşire din tranziţia ti

Aprinderea unei tranziţii este echivalentă cu:n M’(pi) = M(pi) - w(pi, tj), pentru orice pi∈I(tj) - O(tj)n M’(pk) = M(pk) + w(tj, pk), pentru orice pk∈O(tj) - I(tj)n M(p) = M(p) - w(p, tj) + w(tj, p), pentru orice p∈O(tj)∩I(tj)

Exemplul 2

p1 t1 p2

2

2 2

În figura de sus, tranziţia nu este validată şi deci nu se poate produce În a doua variantă de marcaj tranziţia este validată În dreapta apare noul marcaj după producerea tranziţiei

p1 t1 p2

2

p1 t1 p2

2

Exemplul 3: Cazuri - configuraţia iniţială

p1

p2

p4 t2

M0 = [2, 0, 0, 1]

În configuraţia iniţială singura tranziţie validă este t1. Când tranziţia t1 se aprinde este eliminat un jeton din locaţia p1 şi se plasează câte un jeton în locaţiile p2 şi p3 (se poate aplica de asemenea formula pentru a se obţine noua stare)

p3 t1

t3

Exemplul 3: pasul 1

p1

p2

p4t2

M1 = [1, 1, 1, 1]

În această stare toate cele trei tranziţii sunt valideDacă se aprinde tranziţia t2, e eliminat un jeton din locaţiile de intrare p2 şi p3 şi plasat în locaţiile de ieşire p2 şi p4

p3t1

t3

Exemplul 3: pasul 2

p1

p2

p4 t2

M2= [1, 1, 0, 2]

S-a eliminat un jeton din locaţiile de intrare p2 şi p3 şi s-a plasat un jeton în locaţiile de ieşire p2 şi p4Dacă însă în starea precedentă s-ar aprinde tranziţia t3, atunci s-ar obţine starea descrisa pe următorul slide

p3 t1

t3

Exemplul 3: pasul 3

p1

p2

p4 t2

M2 = [0, 1, 0, 0]

În această stare nu mai este activată nici o tranziţie şi nu sunt posibile schimbări de stare

p3 t1

t3

Metode de analiză a RP ordinareAnaliza dinamică (analiza accesibilităţii) are ca scop determinarea mulţimii stărilor (accesibile)n Utilizează reguli algebrice ce descriu validarea şi aprinderea

tranziţiilor n Acestea conduc la reprezentarea evoluţiei dinamice a RP

prin formarea unor ecuaţii prin formarea unor ecuaţii Analiza structurală are ca idee de bază eliminarea derivării spaţiului stărilor şi prin aceasta evitarea problemei “exploziei stărilor”. n Această abordare nu poate furniza o informaţie la fel de

bogată ca priman De multe ori o asemenea detaliere nici nu este necesară, ci

sunt dorite doar anumite caracteristici calitative ale RP şi sistemului modelat (de ex. determinarea invarianţilor)

Ecuaţiile de accesibilitateDefinim al k-lea vector de evoluţie uk, un vector m-dim.de forma: uk = [0, 0, .., 0, 1, 0, …, 0], unde 1 apare în poziţia j si arata că tranziţia j este a k-a tranziţie aprinsăTrebuie definită şi matricea de incidenţă I ca matrice mxn, unde m este numărul de tranziţii, n numărul de locaţii, iar intrarea (i, j) este de forma: locaţii, iar intrarea (i, j) este de forma: n Iij = w(tj, pi) - w(pi, tj) → I = Post - Pre

Folosind matricea de incidenţă putem scrie o ecuaţie de stare vectorială Mk = Mk-1+ukI, valabilă pentru orice k∈N, si deduce o condiţie necesară de accesibilitate a unui marcaj:

, ce se poate scrie si ca:

unde:

IuMMd

k

kd )(

10 ∑

=

+= MxI ∆=

∑=

=d

k

kux1

Exemplul 3 (reluare)

p1

p2

p4 t2

Se vor folosi ecuaţiile anterioare pentru exemplul 3Marcajul iniţial este M = [2, 0, 0, 1]

p3 t1

t3

Exemplul 3 (cont.)Matricea de incidenţă pentru această reţea Petri este:

: Iij = w(tj, pi) - w(pi, tj)ePostttt

I

pppp

Pr1101

11000111

2

1

4321

−=

−−−−

−=

Dacă se aprinde tranziţia t1 după marcajul iniţial M0:

M1 = [2 0 0 1] + [1 0 0] = [2 0 0 1]+[-1 1 1 0]= [1 1 1 1]

t1101 3 −−−

−−−−

−

110111000111

Exemplul 3 (cont.)În cazul în care în continuare se aprinde tranziţia t2 vom obţine:

M2 = [1 1 1 1] + [0 1 0] = [1 1 1 1] +

−−−−

−

110111000111

+[0 0 -1 1] = [1 1 0 2]

Având marcajul iniţial M0 se pot genera toate secvenţele de marcaje accesibile → stări accesibileAcordând marcajelor semnificaţia de stare, se observă similaritatea cu o ecuaţie de stare din teoria sistemelor

−−− 1101

Exemplul 4: Calculul algebric (1)p1

p2p3

t2p4t3

p5

t6t1

p8

p5 p6 p7t4 t5

Exemplul 4 (2)p1

p2 p3

t6t1

p8

t2p4t3

7654321

001010100000010000001000100000000100000010000001

Pre

pppppppp

=

p5

p5 p6 p7t4 t5

654321

87

001010tttttt

p

654321

87654321

010100010000001000000001000100000010000001100000

Post

tttttt

pppppppp

=Matricea de incidenţă

−−−

−−

−−

−−

==

011110110000011000001001100100000110000011100001

Pre-PostI

Exemplul 4 (3)p1p2 p3

p5

t6t1 p8

t2p4

p5

p

p7

t3

t t

=

=000014

)()5()4()3()2()1(

pMpMpMpMpMpM

M

=′

000104

Mp6t4 t5

110

)8()7()6(

pMpMpM

p5 p7

p1p2 p3

p5

t6t1 p8

t2p4

p6

t3

t4 t5

010

t2 este validata si se declanseaza

),(),(Post),(Pre'

tIMttMM

⋅+=⋅+⋅−=

Determinarea (P-)invarianţilor

Un invariant este un vector pozitiv definit la dreapta* care anulează matricea de incidenţă

X ≥ 0: XI = 0

* Cu cel putin o componenta pozitiva si celelalte pozitive sau nule

XMi= XM0 + XI →

X ≥ 0: XI = 0

XMi = XM0

Alte proprietăţi şi clasificări derivate Autonomie. O reţea Petri se numeşte autonomă dacă nici timpul şi nici altă constrângere de sincronizare externă nu sunt implicate în modeln O RP autonomă se păstrează ca o descriere pur calitativă a

sistemului observatn Reţeaua din exemplul 3, anterior, este autonomăn Reţeaua din exemplul 3, anterior, este autonomă

Simplitate. O RP se numeşte simplă dacă elementele ei distincte (locaţii sau tranziţii) nu pot avea mulţimi de intrare sau ieşire similaren Reţeaua din exemplul anterior este simplă

Puritate. O RP se numeşte pură dacă nu conţine cicluri n Reţeaua din exemplul 3 nu e pură, deoarece există ciclul (p2,t2)

Accesibilitate. Se referă la posibilitatea de atingere a unei stări, codificate de un marcaj al reţelei, dintr-o altă stare

Alte proprietăţi şi clasificări (2)Mărginire (limitare). O RP se numeşte (n) mărginită dacă numărul de jetoane din fiecare locaţie poate atinge cel mult valoarea n n Reţeaua din exemplul anterior este mărginită

Siguranţă. O RP se numeşte sigură dacă marcajul fiecărei locaţii poate fi doar 0 sau 1 (marcaj boolean), iar arcele au pondere unitarălocaţii poate fi doar 0 sau 1 (marcaj boolean), iar arcele au pondere unitarăViabilitate. O RP se numeşte viabilă dacă, indiferent de marcajul iniţial şi de evoluţia sa, nici o tranziţie nu poate deveni inactivă de o manieră permanentă. n Reţeaua din exemplul anterior eşuează într-o stare terminală şi

deci nu este viabilăInvarianţi. O RP poate prezenta o serie de caracteristici invariante în timpul evoluţiei sale dinamice, în principal referitoare la marcajele sau stările sale

Alte proprietăţi şi clasificări (3)Conservativitate. O RP se numeşte conservativă dacă numărul total de jetoane este constant (un invariant al reţelei)n Reţeaua din exemplul anterior nu este conservativă

Sub-conservativitate. O RP se numeşte sub-conservativădacă numărul total de jetoane este constant sau în dacă numărul total de jetoane este constant sau în descreştere pe parcursul evoluţiei (dinamicii) salen Reţeaua din exemplul anterior nu este sub-conservativă

Reversibilitate. O RP se numeşte reversibilă dacă din fiecare marcaj accesibil se poate ajunge din nou la marcajul iniţialn Reţeaua din exemplul anterior nu este reversibilă

Ex. Este RP de mai jos simplă?Într-o RP simplă 2 tranzitii nu pot avea aceleași seturide locaţii de intrare si iesire

Obs: Reţelele simple fara elemente izolate ce indeplinesc sialte restrictii suplimentare legate de marcaje si capacitateaarcelor sunt reţelele condiţii/evenimente (C/E)


Sinteza modelelor cu reţele Petri


Sinteza modelelor cu reţele Petriordinare şi generalizate

Exemple de sinteza a modelelor cu RPn Modelarea conceptelor dinamice în RP

ordinare

Extensii ale modelelor de baza cu RP:

Sumar

Extensii ale modelelor de baza cu RP: n RP temporizaten RP stochasticen RP de nivel inalt

Metode de analiză si sinteza (modelare) folosind RP ordinare si generalizate

Exemplul 5: Un sistem de asteptare(1 server, 1 coada)

No Activitate(Locatie)

Entitate implicata Server Activ

A1 Client.creare Client o

A2 Client.coada Client o

A3 Servire Client, Server þ

A4 Client.terminare Client o

A5 Client.iesire Client o

A6 Server.gol Server o

No Eveniment (Tranzitie) Preconditie PostconditieT1 Sosire A1 A2T2 Inceput servire A2, A6 A3T3 Sfarsit servire A3 A4, A6T4 Plecare A4 A5

Constructia retelei Petri (1)Incepe cu plasarea locatiilor (activitatilor) in succesiune logica

A6Server.gol

A1Client.creare

A2Client.coada

A3servire

A4Client.terminare

A5Client.iesire

Constructia retelei Petri (2)Se figureaza tranzitiile (evenimentele)

sosireT1

inceputT2

sfarsitT3

plecareT4

A1Client.creare

A2Client.coada

A3servire

A4Client.terminare

A5Client.iesire

A6Server.gol

Constructia retelei Petri (3)Arcele indica relatiile logice in RP

sosireT1

inceputT2

sfarsitT3

plecareT4

A1Client.creare

A2Client.coada

A3servire

A4Client.terminare

A5Client.iesire

A6Server.gol

Constructia retelei Petri (4)Token-urile marcheaza starea initiala a RP

sosireT1

inceputT2

sfarsitT3

plecareT4

A1Client.creare

A2Client.coada

A3servire

A4Client.terminare

A5Client.iesire

A6Server.gol

Dinamica sistemului (1)Creare clientClient Sosire Inceput Plecare

1 19,25Server : golCoada : 0

A1 A2 A3 A4 A5

A6

T1 T2 T3 T40

0 0

0

Dinamica sistemului (2)Sosire clientClient Sosire Inceput Plecare

1 19,252 26,50

Server : golCoada : 1

A1 A2 A3 A4 A5

A6

T1 T2 T3 T41

1 0

0

Dinamica sistemului (3)Servire

Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50

Server : ocupatCoada: 0

A1 A2 A3 A4 A5

A6

T1 T2 T3 T41

0 1

0

Dinamica sistemului (4)Terminare client (in sistem)


Server : golCoada: 0

A1 A2 A3 A4 A5

A6

T1 T2 T3 T41

0 0

0

Dinamica sistemului (5)Iesire client (din sistem)



A1 A2 A3 A4 A5

A6

T1 T2 T3 T41

0 0

1

Dinamica sistemului (6)Sosire client

Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,503 31,40


3 31,40

A1 A2 A3 A4 A5

A6

T1 T2 T3 T42

1 0

1

Dinamica sistemului (7)Servir client

Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40


3 31,40

A1 A2 A3 A4 A5

A6

T1 T2 T3 T42

0 1

1




3 31,404 31,75

A1 A2 A3 A4 A5

A6

T1 T2 T3 T43

1 1

1




3 31,404 31,755 42,40

A1 A2 A3 A4 A5

A6

T1 T2 T3 T44

2 1

1

Dinamica sistemului (10)Terminare client

Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40 31,80


3 31,40 31,804 31,755 42,40

A1 A2 A3 A4 A5

A6

T1 T2 T3 T44

2 0

1

Dinamica sistemului (11)Servire – Iesire client

Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40 31,80 44,75


3 31,40 31,80 44,754 31,755 42,40

A1 A2 A3 A4 A5

A6

T1 T2 T3 T44

1 1

2

Exersaţi singuri…

Modelarea conceptelor dinamice cu RPModelarea conceptelor dinamice cu RP

Modelarea conceptelor dinamice in RP (1)(C/E si PT)

A B

concurenţă

A B A B

concurenţă sincronizare comunicare

A B

conflict/alegere

A B

resurse/multiplicitate

A B

date/individualitate

Modelarea conceptelor dinamice in RP (2)

(a) secvenţiere; (b) ramificaţie; (c) sincronizare;(d) conflict la resurse; (e) concurenţă

Producător/consumator

Proces de transmitere/recepţie

Semaforrg

green

gy

yr

red

yellow

Doua semafoare

OR

rg

green

rg

green

rg

green

ORgy

yr

red

yellow

gy

yr

red

yellow

gy

yr

red

yellow

Implementarea nedeterminismuluiMai multe tranziţii sunt validate, dar numai una se poate declanşa

Soluţie

rg1

g1

rg2

g2

gy1

yr1

r1

y1

gy2

yr2

r2

y2

x

Trenuri (varianta 1)Consideram un sistem feroviar circular cu 4 linii (unidirecţionale), numerotate (1,2,3,4) si doua trenuri (A,B)n Nu putem avea doua trenuri pe aceeaşi linie in acelaşi

timp; identitatea trenurilor nu este importantatimp; identitatea trenurilor nu este importanta


timp; dorim sa distingem insa identitatea trenurilortimp; dorim sa distingem insa identitatea trenurilor


timp, dar nici pe linii vecine (condiţie de siguranţa); timp, dar nici pe linii vecine (condiţie de siguranţa); identitatea trenurilor nu este importanta

Trenuri (varianta 4)Consideram un sistem feroviar circular cu 4 linii (unidirecţionale), numerotate (1,2,3,4) si doua trenuri (A,B)n Liniile sunt marcate ca libere, ocupate sau cerute

Un tren va cere linia următoare înainte de a o ocupan Un tren va cere linia următoare înainte de a o ocupa

RP generalizateRP cu arce multiple (sau capacitate a arcelor > 2)n Numărul de arce intre o locaţie de intrare si o tranziţie

determina numărul de jetoane necesare in prima, pentru a o valida pe cea de-a doua

n Numărul de arce determina si numărul de jetoane ce se n Numărul de arce determina si numărul de jetoane ce se consuma/ se produc

wait enter before make_picture after leave gone

free

Exerciţii: Procese de fabricaţie (1)

Modelaţi ca RP procesul de fabricaţie a unui scaun din componente: n 4 picioare

3 bare de susţinere spătarn 3 bare de susţinere spătarn 1 cadru spătarn 1 suport şedere

Atenţie in selectarea ordinii de asamblare

Exerciţii: Procese de fabricaţie (2)Modelaţi procesul de producţie a unui automobil, indicat in diagrama următoare

car

subassembly2engine

subassembly1

subassembly2

wheelchassis

chair2

4

Echivalenţa definiţiilorOrice set de reţele Petri (diagrame) ilustrând un sistem dinamic poate fi transformat in model formal, si invers

Exerciţii:Transformaţi reţelele Petri obţinute anterior in modele formaleÎncercaţi analiza accesibilităţii și analiza dinamicăpe aceste modele

Extensii ale modelului de baza:RP temporizate

Timpul nu este prins in modelul RP de bazaModalităţile de extensie temporizata a lor au in vedere introducerea întârzierilor deterministe atât pentru locaţii, cat si pentru tranziţiiPot fi derivate concepte noi, de ex. timpul de ciclare (τ): pp. reţeaua consistenta, τ este timpul completării unei pp. reţeaua consistenta, τ este timpul completării unei secvenţe de declanşări ce reface marcajul initial:n Întârzieri pentru locatiiw τmin=maxyk

TD (A+) Tx/ykTM0

n Întârzieri pentru tranzitiiw τmin=maxyk

T(A-) TDx/ykTM0

n Rezulta pentru o RP temporizata simpla (GM)w τmin = maxtotal delay in Ck/M0 (Ck)

RP stochasticeAsemănătoare RP temporizate, diferenţa e in intarzierile introduse, care sunt nedeterministe n De ex., putem avea întârzieri de tranzitare modelate ca v.a.

distribuite exponenţialApar proprietăţi noi: n graful de accesibilitate al unei RP stochastice mărginite este n graful de accesibilitate al unei RP stochastice mărginite este

izomorf cu un lanţ Markov finitn O RP stochastica reversibila generează un lanţ Markov ergodic, in

care distribuţiile de probabilitate in starea stabila dau estimatorii de performanta:w Probabilitatea unei condiţii particularew Valoarea aşteptata a numărului de simboluri (jetoane)w Numărul mediu de declanşări in unitatea de timp

RP stochastice generalizate adaugă tranziţii imediate pentru a reduce spaţiul stărilor

RP de nivel inaltIncludem in aceasta categorie:n RP cu predicate/tranziţiin RP coloraten RP cu simboluri individualizate

Orice RPNI poate fi translatată intr-o reţea ordinara:Orice RPNI poate fi translatată intr-o reţea ordinara:n Fiecare locaţie se translatează intr-un set de locaţii,

de ex. cate una pentru fiecare culoare a jetoanelor conţinute

n Fiecare tranziţie se translatează intr-un set de tranziţii, cate una pentru fiecare modalitate de declanşare

RPNI: exemple

a,ad,d

<a,b>

<x,z>2xa

d

<a,c>

<d,b>

2

2

<a,b><b,c><d,a>

e<x,y>+<y,z> <a,b>

<b,c>

<d,a>

e

Aplicabilitatea RPNIProgramare logican Modelarea seturilor de clauze (Horn)

B ← A1, A2, ..., Anunde Ai si B sunt formule “atomice”

Predicat(argumente)Predicat(argumente)n Instructiunea scop (goal statement) se modeleaza ca

tranzitie fara iesiri (sink transition) n Asertiunile de fapte – ca tranzitii sursan Reprezentarea ca RPNIw Fiecare simbol predicat distinct este o locatiew Fiecare clauza este o tranzitie w Ponderile sunt argumente

n La final, trebuie sa existe conditii suficiente pentru a declansa tranzitia scop

Invarianti numerici

In toate cazurile

A“#A < n”

n

A“|A| - #A < n”n

A B “(|A| - #A < n) n m

• pot fi aplicat metode logice pentru retele P/T, folosindinegalitati asupra numarului de resurse ca propozitii elementare

• tehnicile numerice specifice pot fi insa mai eficiente

Evenimente moarte (nevalidabile) Invarianti sistem (fapte)

“(|A| - #A < n) and (|B| - #B < n)”

A

B “(#A < n)or (|B| - #B < n)”

n

m

Invarianţi, tehnici numerice

+−

=altfel,0

la la de arce exista daca, la la de arce exista daca,

:, ptnntpnn

C tp

pnnm p locatiain jetoane exista daca ,:=

• Matricea de incidenta C a unei retele P/T pure (fara cicluri):

•Vectorul marcajelor m al unei retele P/T: t

pn

Contributialui t la ppnnm p locatiain jetoane exista daca ,:=

ori de adeclanseaz se tranzitiadaca ,: ntnf t =•Vectorul de aprindere f al unui multi-set de tranzitii (fara reprezentarea ordinii!):

•Vectorul pondere i al unor locatii: set de locatii cu suma jetoanelor constanta

''**)'(:', mimimimimmmm tp

ppp

pp

t ⋅===⋅⇒∀ ∑∑a

• Conditia necesara, nu si suficienta de accesibilitate:

00)'(' =⋅⇒=−⋅⇔⋅=⋅ Cimmimimi tttt

lui t la p

'mfCm t =⋅+

Propoziţii si predicate

17 x+y=z

P

a Scheme cu conditiibPa Pb

1 7

Retele predicate/tranzitii:• jetoanele individuale sunt extensii de predicate si inlocuiesc conditii propozitionale• cuantificatori si specificatori intr-o logica a predicatelor permit grupari de evenimente la nivel propozitional in scheme cu evenimente la nivel de predicate

P

Q

R

7

2

x

y

z

x+y=z

Scheme cu evenimente

P

QR

7

2

1

2

27

3

9

Concluzii

Modelarea cu reţele Petri ord./ NI se poate utiliza pentru a testa şi valida anumite proprietăţi utile ale sistemelorn Siguranţa: este garantată prin faptul că numărul de

simboluri nu creşte nedefinitsimboluri nu creşte nedefinitn Funcţionalitatea: este garantată prin lipsa blocajelor → va exista întotdeauna cel puţin o tranziţie care poate fi declanşată

Avantaj: modelarea sistemelor concurenteDezavantaj: nu este utilă pentru sisteme complexe


Lanţuri şi procese Markov


Lanţuri şi procese Markov şi semi-Markov generalizate

Terminologie şi concepte de bază. Nivele de modelare (rev.)Categorii de modele statisticeSecvenţe şi procese aleatoareLanţuri Markov. Problema ergodicităţii

Sumar

Lanţuri Markov. Problema ergodicităţiiProcese MarkovLanţuri Markov înglobateProcese semi-Markov generalizate (GSMP)Definirea GSMPGenerarea GSMP

Terminologie şi concepte de bazăSistem - o colecţie de entităţi in interacţiune

Model - o reprezentare abstractă a sistemului

Entitate - componentă a sistemului cu reprezentare explicităin model (obiect de interes in sistem)

Atribut - o proprietate a unei entităţi Atribut - o proprietate a unei entităţi

Set - colecţie de entităţi asociate, permanent sau temporar

Eveniment - o apariţie instantanee ce schimbă starea sistemului

Activitate - o perioada de timp de lungime cunoscuta la începutul ei

Întârziere - o perioada de timp nespecificată ca lungime →necunoscută până la terminarea ei

Nivele de studiu/ modelare (1)Comportarea SDED este in mod natural descrisa deînregistrarea (urma) generată de apariţia unorschimbări discrete, calitative, in sistemModelele bazate pe urme sunt studiate la diferitenivele:nivele:

Nivelul logic – “urma” este secvenţa de evenimente, inordinea apariţiei lor

s = e1 e2 e3 ... Exemple: reţelele Petri (“cazuri” = urme); maşinile cu stări finite (Wonham); procesele recursive finite (Inan-Varaiya); procesele secvenţiale comunicante (Hoare)

Nivele de studiu/ modelare (2)Nivelul temporal - urma este secvenţa de perechi

s = (e1,t1) (e2,t2) (e3,t3) ... Exemple: reţelele Petri temporizate, modelele algebrice min-max, grafurile data-flow

Nivelul statistic - comportarea sistemului este descrisă deNivelul statistic - comportarea sistemului este descrisă desecvenţa perechilor de v.a.

s = (e1,t1) (e2,t2) (e3,t3) ...(unde ei si ti sunt v.a. si pentru orice realizare ω, s(ω) =(e1(ω),t1(ω)) (e2(ω),t2(ω)) (e3(ω),t3(ω)) ... este o urmadescrisa la nivel temporal)

Exemple: lanţurile Markov, sistemele cu cozi de aşteptaresi reţelele de cozi, modelele de simulare - având la bazaformalismul GSMP

Categorii de modele statistice (1)I. Modele analitice (teoretice)

n sistemice (improprii), provenite in general din modele deterministe – unde descrierea se face la nivel logic sau temporaloperaţionale, in general probabilistice (statistice); n operaţionale, in general probabilistice (statistice); se pot folosi in cazurile când putem obţine prin calcul formule/ rezultate exacte (având modalităţi de a simplifica problemele computaţionale)w Ex.: sisteme cu cozi de aşteptare, reţele de coziw Limitare: la cozi simple &

reţele de cozi factorizabile

Categorii de modele statistice (2)II. Modele de simulare

n derivate din modelele operaţionalen adecvate pentru analiza asistata de calculatorn oferă un instrument complet ce aproximează

dinamica sistemului prin oferirea de ipostaze non-dinamica sistemului prin oferirea de ipostaze non-continue incrementale

n Pro: Dinamica originala a SDED este de acest tip!n Contra: Dificultăţi computaţionale (exista soluţii!)

Pentru modelarea SDED la nivel statistic (cea mai completa) se pot folosi in tandem: n modele operaţionale + modele de simulare

Lanțuri MarkovSunt procese aleatoare discrete (asociate cu sisteme ce se pot afla în stări diferite, ce se schimbă aleator în pași discreți), cu a.n. “proprietate Markov”Poate fi util să gândim aceste sisteme ca evoluând în pași discreți în timp, deși timpul nu este determinantpași discreți în timp, deși timpul nu este determinantProprietatea Markov: distribuția de probabilitate de trecere a sistemului în starea următoare (și de fapt în toate stările următoare) depinde doar de starea curentă, nu și de stările anterioareConsecință: deși stările următoare sunt aleatoare, nu pot fi prezise, pot fi descrise proprietățile statistice ale sistemului cu mulți pași înainte

Un exempluUn iepure mănâncă doar varză, morcovi sau lăptuci Dacă a mâncat morcovi ieri, nu va mai mânca azi, ci va servi doar varză sau lăptuci cu probabilitate egalăDacă a mâncat varză ieri, va putea mânca azi, cu prob. 10%, dar și morcovi sau lăptuci cu prob. 40%, prob. 10%, dar și morcovi sau lăptuci cu prob. 40%, respectiv 50%Dacă a mâncat lăptuci ieri, nu va mai mânca azi, ci va servi doar varză sau morcovi cu prob. 40%/ 60%Modelul obiceiurilor alimentare ale iepurelui este un lanț Markov, și se pot calcula proprietăți statistice ca de ex. numărul (%) de zile în care iepurele a mâncat morcovi, pe o perioadă lungă de timp → 100 zile

Câmp de evenimente elementare. Variabilă aleatoare(Ω, E, P): câmp (finit sau infinit) de evenimente elementare

n Ω: mulţimea de realizări posibile ale unui experiment aleator (mulţime de evenimente elementare)

n E: mulţimea submulţimilor din Ω (spaţiul evenimentelor)n P: măsura de probabilitate

X:Ω→R este variabilă aleatoare dacă valoarea sa depinde de o realizareX:Ω→R este variabilă aleatoare dacă valoarea sa depinde de o realizaredin Ω si este caracterizata de:Ø desfacerea lui Ω in evenimente elementare, incompatibile:

E1,E2,...,En Ø mulţimea valorilor reale x1,x2, ...,xnØ mulţimea probabilităţilor asociate evenimentelor elementare

p1,p2,...,pn

n O v.a. modelează translatarea mulţimii rezultatelor unui experiment aleator pe o mulţime reală

Secvenţe şi procese aleatoareSecvenţă aleatoare (stochastică):

Un şir de v.a. X1, X2,..., Xn,... indexate printr-o variabilăindependentă (de obicei cu semnificaţie de timp)

Definirea se face prin specificarea funcţiei de distribuţie (deobicei aceeaşi) a componentelor, v.a. X1, X2,..., Xn,...

Proces aleator (stochastic)Definite ca limita unei secvenţe aleatoare când variabila deindexare devine continua; notaţie X(t)

Ne interesează procesele aleatoare a căror comportare este integral caracterizată printr-o unică distribuţien V.a. ale lor sunt i.i.d. (independente şi identic distribuite)

n Ele sunt intuitiv descrise de secvenţe de extrageri aleatoare dintr-o mulţime de bază ce respectă o distribuţie fixă

Probabilităţi condiţionate în secvenţele aleatoare

Fie (Ω, E, P) un câmp finit de evenimente elementare, iar X1, X2,..., Xn,... un şir de v.a. Notăm E1

n, E2n,..., Em

n,... desfacerea corespunzătoarev.a. Xn în evenimente elementare, incompatibileProbabilitatea condiţionată P(Ejnn)|Ej11∩…∩Ejn-1

n-1 este în general dependentă de succesiunea de evenimente, Probabilitatea condiţionată P(Ejn )|Ej1 ∩…∩Ejn-1 este în general dependentă de succesiunea de evenimente, Ej11,…,Ejn-1

n-1,Ejnn

Dacă P(Ejnn)|Ej11∩…∩Ejn-1n-1 = P(Ejnn) pentru ∀n ∈Ν şi

∀şir Ej11,…,Ejnn, atunci acest şir este o simplă succesiune de v.a. independenteDacă P(Ejnn)|Ej11∩…∩Ejn-1

n-1 = P(Ejnn)|Ejn-1n-1 pentru ∀n

∈Ν şi ∀şir Ej11,…,Ejnn, atunci acest şir constituie un lanţ Markov simplu

Lanţuri şi procese MarkovO clasă de modele destul de generale (se aplică cu succes şi în modelarea altor tipuri de sisteme)Procesele Markov se caracterizează prin aceea că:n starea la un moment dat t este suficientă pentru starea la un moment dat t este suficientă pentru

calculul stării la momentele următoare n nu este necesară cunoaşterea stărilor unui sistem

(continuu) la momentele anterioare

Lanţurile Markov păstrează această proprietate, sistemul modelat fiind însă studiat doar la momente discrete de timp

Lanţuri MarkovDefiniţie. Dacă procesul stochastic X descris de secvenţa X=Xnn=0,1,2,... are proprietatea P(Xn+1=j| X0,X1, X2,..., Xn) = P(Xn+1=j| Xn), atunci el se numeşte lanţ MarkovInterpretare: Probabilitatea apariţiei unui eveniment la momentul n+1 depinde doar de starea curentă (n), nu şi momentul n+1 depinde doar de starea curentă (n), nu şi de stările sistemului la momentele anterioareLanţurile Markov multiple de ordinul p se definesc prin dependenţa probabilităţii apariţiei unui eveniment la momentul n+1 de cele p stări ale sistemului la momentele anterioare, generate prin apariţiile altor evenimente la cele p momente anterioare

Modelul Markov simpluNotaţii:n (Ω, E, P) – câmp de evenimente elementaren X=Xnn=0,1,2,... – secvenţă stochastică (şir de v.a. independente)n Ψ – spaţiul stărilor posibile ale procesului, de cardinal numărabil

(simplificat, Ψ e asimilat cu Ν, adică Xn=j arată că procesul descris de variabila aleatoare X este în starea j la momentul n)descris de variabila aleatoare Xn este în starea j la momentul n)

n P(i,j)=P(Xn+1=j|Xn=i) - probabilitatea de tranziţie din starea i în j n P=[P(i,j)]i,j∈Ψ - matricea de tranziţie;n π(i) - probabilitatea stării i∈Ψ

Modelul este caracterizat de 2 tipuri de ecuaţii:

enormalizar de ecuatia - 1=(i)

balans de ecuatiile - ij),P(i,(j)=(i)

i

j

π

ππ

∑

∑

Ψ∈

Ψ∈

Ψ∈⋅

Tipologie şi proprietăţi (1)Dacă la momentul n probabilitatea stării i nu depinde decât de starea considerată, nu şi de variabila aleatoare Xn prin care se concretizează, adică P(Xn=i)=π(i) pentru orice n, lanţul Markov se numeşte staţionar

O mulţime de stări din Ψ se numeşte închisă dacă nici o O mulţime de stări din Ψ se numeşte închisă dacă nici o stare din afara acestei mulţimi nu poate fi atinsă dintr-o stare aflată în mulţime

O mulţime închisă de stări se numeşte nedecompozabilădacă nici o submulţime proprie a sa (strict inclusă în ea) nu este închisă

Tipologie şi proprietăţi (2)Un lanţ Markov este nedecompozabil dacă singura mulţime nedecompozabilă este însuşi spaţiul stărilor, Ψ

n În cazul unui lanţ Markov nedecompozabil, un proces aflat într-o stare i poate trece cu o probabilitate nenulă în orice stare jîn orice stare j

O stare i∈Ψ se numeşte periodică dacă este parcursă periodic de procesul stochastic X; cu alte cuvinte, dacă Xk=i, atunci Xl=i doar dacă l=k+m⋅d, unde d∈Ν este un divizor comun al lui k şi l (numit perioadă), iar m∈Ζ

Dacă nici o stare nu este periodică, lanţul Markov se numeşte aperiodic

Ergodicitatea lanţurilor MarkovÎntr-o accepţiune generală, X=Xnn=0,1,2,... este un lanţ Markov ergodic dacă pentru orice funcţie f:Ψ→R avem:

(i)f(i)=E[f(X)]unde E[f(X)],=a.s.)Xf(

n1

ik

1-n

0=knπ⋅∑∑

Ψ∈∞→lim

f(X). luia stare pe media este i0=kn Ψ∈∞→

Putem considera mai general, ca probabilităţi de trecere de la starea i la momentul l la starea j la momentul m: P(l,m)(i,j), iar prin fixarea momentelor l,m dar menţinerea ca variabile a stărilor i,j formăm matricele de trecere:

P(l,m)=[P(l,m)(i,j)]i,j∈Ψ

Relaţia lui ChapmanMatricele de trecere definite anterior respectă o relaţiederivată direct din definiţia lanţului Markov simplu:

P(l,n)=P(l,m) x P(m,n), unde l<m<n (m stare intermediară)n Pentru determinarea matricelor de trecere este deci necesar şi

suficient să cunoaştem matricele de tranziţie definite anterior: suficient să cunoaştem matricele de tranziţie definite anterior:

P=[P(i,j)]i,j∈Ψ=P(n,n+1)

Un lanţ Markov omogen este caracterizat de faptul că probabilităţile de trecere depind numai de diferenţa n=m-l, între momentele l şi mÎn acest caz relaţia lui Chapman se poate scrie simplu:

P(m+n)=P(m) × P(n)

iar lanţul este determinat doar de matricea de tranziţie P=P(1); evident că P(n)=Pn

Este problema comportării probabilităţilor P(n)(i,j) pentru n→∞, convergenţa către o limită:

Rezultate importante: 1. Dacă limita probabilităţilor de trecere (sau a matricelor

Problema ergodică pentru sisteme nedecompozabile

P=P(n)sauj)P(i,=j)(i,P(n) ji, nnlimlim ,|

∞→∞→Ψ∈

1. Dacă limita probabilităţilor de trecere (sau a matricelor de trecere) există, acest lucru este independent de starea iniţială din care se pleacă n Intuitiv, se poate porni aşa la definirea ergodicităţii

2.Dacă X=Xnn=0,1,2,... este un lanţ Markov ergodic, noullanţ Markov Y=Ynn=0,1,2,... definit prin Yk=Φ(Xk, Xk+1,...), unde Φ:R∞→R e o funcţie măsurabilă, este ergodic3.Dacă un lanţ Markov nedecompozabil este aperiodic şi are un număr finit de stări distincte, el este ergodic

ObservaţiiNoţiunea de proces aleator, sub forma particulară sub care a fost introdusă anterior, constituie o generalizare directă a noţiunii de variabilă aleatoare Un proces aleator este în esenţă o funcţie parametrizată definită pe produsul dintre spaţiul unui parametru t (de obicei o submulţime reală) şi câmpul de probabilitate, cu valori reale; prin fixarea parametrului t, funcţia se reduce valori reale; prin fixarea parametrului t, funcţia se reduce la o variabilă aleatoare în sensul definit anteriorRepartiţiile variabilelor aleatoare obţinute pentru diferite valori ale parametrului t pot fi în general identice sau diferite, în ansamblu ele constituie repartiţiile de probabilitate finit dimensionale ale procesului aleatorÎn cazul lanţurilor Markov am considerat ca spaţiu al parametrului t mulţimea numerelor întregi nenegativeDefiniţia proceselor Markov are în vedere întreaga semidreaptă reală pozitivă

Procese MarkovDefiniţie. Un proces aleator Y=Yt, t∈[0,∞) se numeşte proces Markov, cu un spaţiu numărabil de stări Ψ, dacă

∀s>0 şi j∈Ψ: P(Yt+s=j Yu, u ≤s)=P(Yt+s=j Ys)Prin analogie cu un lanţ Markov, un proces Markov se numeşte omogen dacă P(Yt+s=j|Ys) nu depinde de s

Funcţia de tranziţie pentru un proces Markov se defineşte analog: P(t)(i,j) = P(Yt+s=j|Ys=i); proprietăţi:

n P(t)(i,j) ≥ 0, ∑k∈Ψ P(t)(i,k) = 1, i∈Ψ

n Ec. Chapman-Kolmogorov: ∑k∈Ψ P(t)(i,k) ⋅P(s)(k,j) = P(t+s)(i,j), sau în formă matriceală: P(t+s) = P(t)xP(s)

Lanţ Markov înglobat unui procesDacă:

1) W(t) e intervalul de rămânere a unui proces Markov într-o stare Y(t), măsurat în spaţiul parametrului t: W(t) = infs>0: Y(t+s)≠Y(t), atunci: (W(t>u)| Y(t)=i = e-λ(i)u, unde u>0, iar λ(i) e rata de tranziţie a stării i2) T(n), n=0,1,2,..., este timpul celei de-a n-a tranziţii a procesului, X(n)=Y(T(n)) starea imediat următoare tranziţiei la T(n), notând X(n)=i: X(n)=Y(T(n)) starea imediat următoare tranziţiei la T(n), notând X(n)=i: P(X(n+1)=j,T(n+1)-T(n)>u |X(0),...,X(n); T(0),...T(n) =Q(i,j)⋅e-λ(i)u

3) Q(i,j) – probabilitatea de tranziţie din starea i în starea j, satisface condiţiile: Q(i,j)≥0, Q(i,i)=0 - prin convenţie, şi ∑k∈Ψ Q(i,k) = 1,

atunci:

Procesul stochastic X=X(n), n=0,1,2,... este un lanţ Markov definit de probabilităţile de tranziţie Q(i,j), numit lanţul Markov înglobat procesului Markov Y

ObservaţiiProprietatea evidenţiată anterior pt. lanţurile şi procesele Markov de a fi “lipsite de memorie” (nu impun memorarea evoluţiei trecute), implică două constrângeri importante:(M1) toată informaţia de stare trecută este irelevantă;(M2) timpul petrecut în starea curentă este irelevant

Prima constrângere este definitorie pentru studiul tuturor Prima constrângere este definitorie pentru studiul tuturor aspectelor markoviene şi păstrează destul de largă clasa acestor sisteme A doua restricţionează de fapt natura v.a. ce specifică intervalul de timp între două tranziţii de stare consecutive şi are drept consecinţă importantă faptul că, într-un lanţ Markov, timpii între evenimentele ce determină tranziţiile de stare sunt distribuiţi după o lege exponenţialăn Prin aceasta se determină o anumită restrângere a tipurilor de

sisteme reale ce pot fi încadrate aici

Formalismul GSMPUn lanţ Markov poate fi înglobat şi unui proces stochastic ce nu este proces Markov n De ex., un lanţ Markov înglobat unui proces pentru

care probabilităţile de tranziţie între stări au legea de distribuţie de tip Markov sau exponenţial, în timp ce distribuţie de tip Markov sau exponenţial, în timp ce duratele de timp între tranziţii sunt arbitrar distribuite, se numeşte proces semi-Markov

Analog, se defineşte şi un proces semi-Markov generalizat (GSMP), în cazul unei dependenţe mai generale de comportarea trecutăFormalismul GSMP stă la baza modelelor de simulare, din categoria modelelor statistice

ObservaţiiUn proces semi-Markov este o extensie a unui proces Markov, determinată de relaxarea constrângerii (M2)Timpii între tranziţiile de stare nemaifiind cu necesitate distribuiţi exponenţial, rezultă că un eveniment ce determină o tranziţie de stare poate apărea în orice determină o tranziţie de stare poate apărea în orice moment, impus de orice lege distribuţională Se păstrează însă constrângerea (M1), cea definitorie: când un asemenea eveniment apare, probabilitatea de atingere a noii stări nu depinde de stările trecute, ci doar de starea curentăProcesele semi-Markov pot fi definite direct ca procese aleatoare în câmp borelian de evenimente, sau generate prin evoluţia unui automat de stare temporal stochastic

Care procese aleatoare pot fi GSMP? Considerăm în câmpul de probabilitate (Ω, E, P) procese stochastice continue în timp:

x(ω,t) : (Ω, E, P) × T+ → X, unde X este o mulţime numărabilă (spaţiul stărilor) Pentru fiecare stare x∈X există o mulţime unică Γ(x)⊂N, numită lista de evenimente (active) asociate stării numită lista de evenimente (active) asociate stării Fiecare eveniment are un timp de apariţie asociat; fie Γ=∪x∈XΓ(x) mulţimea tuturor evenimentelor Un astfel de proces constituie un GSMP; traiectoria sa constă din segmente constante pe porţiuni (secvenţe de stare) şi salturi între 2 stări la momente asociate evenim.Lungimea unei secvenţe de stare se mai numeşte şi timp de menţinere a stăriiSecvenţa evenimentelor declanşate se numeşte urmă

GSMP: bază a modelelor de execuţie

Toate evenimentele asociate unei stări sunt competitive (şi pot fi planificate) pentru tranzitarea către starea următoareFiecare eveniment are asociată şi propria sa distribuţie de salt pentru determinarea stării următoare de salt pentru determinarea stării următoare La fiecare tranziţie a sistemului, noi evenimente sunt planificate (activate), şi le sunt asociate durate de viaţă generate conform unor distribuţii de probabilitate Vechile evenimente nedeclanşate pot fi păstrate în noua stare cu timpii asociaţi (GSMP neintreruptibil) sau pot fi abandonate în noua stare (GSMP intreruptibil)

GSMP: procese aleatoare şi structuri temporale stochastice

Formal, fiind date în câmpul de probabilitate (Ω, E, P) mulţimile distribuţiilor Φe, e∈Γ şi probabilităţilor de tranziţie P(x, x’,e), ansamblul (X(ω,t), C(ω,t)) format din procesul aleator X şi structura temporală stochastică C se defineşte astfel: C se defineşte astfel:

n pe de o parte, prin specificarea modului de generare a componentelor structurii temporale, pe baza distribuţiilor Φ

n pe de altă parte prin specificarea legilor de evoluţie dinamică (aleatoare, având în vedere probabilităţile de tranziţie a stărilor P) ale procesului X

GSMP: automate de stare stochasticeşi structuri temporale stochastice

Pentru generarea GSMP se poate utiliza un automat de stare stochastic (ale cărui stări tranzitează probabilistic), cu o structură temporală stochastică asociată

Definiţie. Numim automat de stare stochastic structura (X, E, Γ, p, p0, C), caracterizată de:(X, E, Γ, p, p0, C), caracterizată de:n X – mulţimea stărilor (cel mult numărabilă)n E – mulţimea evenimentelor (numărabilă)n Γ(x) – mulţimea evenimentelor active în starea x (Γ(x)⊆E)n P : X×X×E → [0,1] - funcţia de probabilitate a tranziţiilor

de staren p0(x) – setul de probabilităţi asociate stării iniţiale x0,

p0(x)= p(x0=x);n C=Ce, e∈E - structură temporală stochastică, fiecare

componentă a sa fiind o v.a. distribuită după o anumită lege Φe

ObservaţiiUn automat de stare stochastic se obţine prin extensia multiplă a unui automat de stare temporaln structura temporală nu se mai consideră dată ci se

generează pornind de la distribuţiile Φe date n funcţiile de tranziţie a stărilor, ca şi starea iniţială, nu

mai sunt date univoc, ci probabilisticmai sunt date univoc, ci probabilisticUn automat de stare stochastic generează o secvenţă de stare stochastică x1,x2,...,xk,xk+1,... printr-un mecanism de tranziţie bazat pe probabilităţile tranziţiilor de stare P condus de secvenţa de evenimente e1,e2,...,ek,ek+1,... n dacă xk=x, atunci xk+1=x’ cu probabilitatea p(x,x’,e’),

e’ fiind evenimentul ce declanşează tranziţia, adică intrarea în starea x’

Generarea GSMPMecanismul de alegere al evenimentului declanşator e’ este identic cu cel pentru automatul de stare temporal

re fiind timpii reziduali rezultaţi din structura temporală stochastică C=Ce, e∈E. Calculul noilor timpi reziduali se poate face dacă: rr min*=

;minarg')(

exe

reΓ∈

=

Calculul noilor timpi reziduali se poate face dacă: şi are în vedere doar cazul neintreruptibilităţii evenimentelor nedeclanşate:

Prin next(ce’) s-a notat generarea unei noi durate de activare pentru evenimentul declanşat, pe baza distribuţiei indicate Φe’Secvenţa stărilor generate de un automat de stare stochastic este un proces aleator, care îndeplineşte constrângerea M1 şidefineşte un GSMP

exerr

)(min*

Γ∈=

'.*,);( '' eerrrcnextr eeee ≠−==


Sisteme cu cozi de aşteptare şi


Sisteme cu cozi de aşteptare şi reţele de cozi

Modelarea analitică a sistemelor şi reţelelor de aşteptare. Notaţia Kendall generalizatăNotaţia Kendall simplificatăLegea lui Little

Sumar

Legea lui LittleComportare tranzitorie şi permanentă (staţionară,de echilibru statistic)Probabilităţi de tranziţie şi de stareMăsuri de performanţă la echilibru statistic

Sisteme cu cozi de aşteptareCaracterizează un sistem prin:

fluxul de intrare - descrie modul in care sosesc clienţii (unităţile) in sistem n in general sosirile sunt aleatoare si independente;

coada (cozile) de aşteptare, caracterizata(e) printr-o coada (cozile) de aşteptare, caracterizata(e) printr-o anumita disciplina (o regula), care precizează:n modul de formare a cozii n modul de comportare a unităţilor care aşteaptă n ordinea de servire a unităţilor

staţia (staţiile) de serviren putem avea staţii multiserver

fluxul de ieşire, important in sistemele constituite din reţele de cozi de aşteptare

Notaţia Kendall generalizată

(A/B/C):(D/E/F)A - tipul distribuţiei de intrare

(distribuţia timpilor intre sosiri)B - tipul distribuţiei de servire

(distribuţia timpilor de serviciu)(distribuţia timpilor de serviciu)C - numărul de staţii (servere) in sistemD - disciplina de servire din partea staţiilorE - numărul maxim de clienţi admişi in sistem

(cei care aşteaptă + cei in curs de servire)F - sursa apelanta

(populaţia din care pot proveni clienţii, finita sau nu)

Notaţia Kendall simplificată(pentru sisteme cu coada unica de aşteptare, 1+ servere)

A/B/k/mA - tipul distribuţiei de intrare

(distribuţia timpilor intre sosiri)B - tipul distribuţiei de servire B - tipul distribuţiei de servire

(distribuţia timpilor de serviciu)k - numărul de staţii (servere) in sistemm - dimensiunea maxima a cozii

Codificarea tipului distribuţiei(de intrare sau de servire)

M - distribuţia exponenţiala (notaţia M provine de la faptul că succesiunea stărilor sistemului formează un proces Markov, sau Memoryless)U - distribuţia uniformaU - distribuţia uniformaEk - o distribuţie Erlang cu k niveleHh - o distribuţie hiperexponenţială cu h niveleG sau GI - o distribuţie generalăD - o distribuţie deterministă

…

Disciplina de servireFIFO (FCFS): unităţile sunt servite in ordinea sosirii in sistemLIFO (LCFS): unităţile sunt servite in ordinea inversa sosirii in sistemSIRO: unităţile sunt servite in ordine aleatoareSIRO: unităţile sunt servite in ordine aleatoareSPT: prima unitate servita este cea cu timpul minim de servire PS (partajarea procesorului): pentru intervalul de timp in care k unităţi solicita servirea, serverul va asigura servirea fiecăreia pentru un timp proporţional cu 1/k

Disciplina de servire (cont.)PR (scheme pe baza de priorităţi): clienţilor le sunt date priorităţi la intrarea in coada, clientul prioritar este primul servit n Non-preemptive: o unitate aflata in curs de servire n Non-preemptive: o unitate aflata in curs de servire

nu poate fi întrerupta

n Preemptive: o unitate aflata in servire poate fi scoasa de o alta intrata in sistem cu o prioritate mai mare; reintrarea unităţii întrerupte in servire se poate face din punctul in care a fost întrerupta sau de la început

Sisteme de aşteptare cu server unic

Procesele de sosire a unităţilor în sistem si de servire a clienţilor sunt in general modelate ca procese aleatoare Bufferul poate avea capacitate finita sau infinita (un buffer de capacitate finita poate conduce la blocaje în sistem)

Procese Poissonsunt procese stochastice A(t)t≥0 cu valoripozitive, discrete în timppresupunerile (postulatele) pe care se bazeazăteoria acestor procese stochastice (siteoria acestor procese stochastice (sidezvoltarea formulei distribuţionale Poisson)sunt minimale si conforme cu realitateaexperimentalaExemplu: un proces de numărare a sosirilor într-un sistem de aşteptare - atunci când sosirile au loc pe rând si sunt independente)

Postulatele Poisson1. Într-un interval "mic" de mărime Δt, probabilitatea de

a înregistra exact o sosire e proporţionala cu mărimea intervalului:

P(A(t+Δt)-A(t)=1) = λ•Δt2. În acelaşi interval "mic" de mărime Δt, probabilitatea 2. În acelaşi interval "mic" de mărime Δt, probabilitatea

de a înregistra mai mult de o sosire este neglijabila: P(A(t+Δt)-A(t)>1) = o(Δt)

3. Sosirile sunt independente: probabilitatea unei sosiri într-un interval de timp "mic" e independenta de alte sosiri si de timpul scurs de la ultima sosire în sistem

Distribuţia Poisson: ecuaţii (1)Distribuţie discreta ce modelează numărul de sosiri într-un sistem de aşteptare ca variabila aleatoare X=A(t) Daca Pn(t)=P(A(t)=n): probabilitatea de a înregistra n sosiri în sistem în intervalul (0,t)

Atunci P (t)≥0, P (0)=1, P (0)=0 pt. n>0, Σ P (t)=1Atunci Pn(t)≥0, P0(0)=1, Pn(0)=0 pt. n>0, Σn=0,∞ Pn(t)=1

Rezulta imediat ca Pn(Δt) = λ·Δt + o(Δt) pentru n ≥1

Probabilitatea ca în 2 intervale succesive disjuncte (0, t) si (t, t+Δt) sa nu înregistram nici o sosire:

P0(t+Δt) = P0(t)·P0(Δt) = P0(t)·(1 - λ·Δt - o(Δt))

Distribuţia Poisson: ecuaţii (2)(P0(t+Δt) - P0(t)) / Δt = -λ·P0(t) - o(Δt) / ΔtRezulta prin trecerea la limita cu Δt →0 ecuaţiadiferenţiala (cu condiţie iniţiala)P'0(t) = -λ·P0(t), P0(0)=1, cu soluţia P0(t) = e-λtP'0(t) = -λ·P0(t), P0(0)=1, cu soluţia P0(t) = eProbabilitatea ca în cele doua intervalesuccesive sa înregistram una sau mai multesosiri (n>0):

t)o(+t(t)P 1-n+t))o(-t-(1(t)Pn=

t)(Pk(t)P k-n+t)(P1(t)P 1-n+t)(P0(t)Pnt)=+(tPnn

2=k∆∆∆∆

∆∑∆∆∆

••••

•••

λλ

Distribuţia Poisson: soluţia.(' 0>n pentru0 =(0)P 1,=(0)P (t),P(t)+P-=t)P n01-nnn λλ′

Soluţia acestei ecuaţii diferenţiale este distribuţia Poisson generala de parametru λ:

,n!

e)t(=(t)Pt-n

n

λλ

având atât media cât si dispersia egale cu λt

Triunghiul distribuţiilor fara memorie

Următoarele 3 propoziţii sunt echivalente:A. Timpul între sosiri este distribuit exponenţial, după legea

F(x)=P(t≤x)=P(t ≤ T+xt>T)=1-e-λx,având media 1/λ si dispersia 1/λ2 (un proces Poisson de sosire areo distribuţie exponenţiala pentru timpii între sosiri).

B. Probabilitatea de a avea o singura sosire în sistem într-un intervalB. Probabilitatea de a avea o singura sosire în sistem într-un intervalde timp de mărime Δt (mic) este λ·Δt + o(Δt).

C. Probabilitatea de a avea n sosiri în sistem în intervalul (0,t)respecta distribuţia Poisson:

obţinuta prin rezolvarea ecuaţiei diferenţiale

,n!

e)t(=(t)Pt-n

n

λλ

P+P-=dt

(t)dP1-nn

n λλ

Descompunerea si compunereaproceselor Poisson

Daca un proces Poisson cu mediaλ, X=A(t), t≥0, consta dinevenimente de doua tipuri diferite,cu probabilitati de apariţie p,respectiv 1-p, atunci si v.a.X1=A1(t), X2=A2(t) ce număraapariţiile pt. cele 2 tipuri de

λ λp

λapariţiile pt. cele 2 tipuri deevenimente, sunt procese Poissonindependente, cu media λ⋅p,respectiv λ⋅(1-p).

Daca X1=A1(t) si X2=A2(t) suntprocese Poisson cu media λ1,respectiv λ2, atunci siX=A(t)=A1(t)+A2(t) constituie unproces Poisson cu media λ=λ1+λ2.

λ(1-p)

λ

λ

λ

Indicatori de performantanumărul mediu de unităţi in sistem, fie in coada de aşteptare, fie in curs de servire

timpul mediu de aşteptare

timpul mediu de răspuns sau timpul sistem timpul mediu de răspuns sau timpul sistem (timpul de aşteptare + timpul de servire)

lungimea maxima a cozii de aşteptare

coeficientul de utilizare a serverului (fracţiunea de timp în care serverul este efectiv ocupat)

Legea lui Little (formula de conservare)

Daca:N este numărul mediu de unităţi în sistemλ este rata medie de sosire a unităţilor (clienţilor) în sistem(clienţilor) în sistemT este timpul mediu de rămânere a unui client în sistem

Atunci:

N = λ•T

Demonstraţie (grafica)

ε

s(t) - numărul de sosiri în sistem în intervalul [0,t]

p(t) - numărul de plecări din sistem în intervalul [0,t]

⇒ N(t)=s(t)-p(t), numărul de clienţi în sistem la mom. t

Ti - timpul petrecut de clientul i în sistem

Dreptunghiurile ce compun aria haşurata au baza egala cu Ti, iar înălţimea egala cu 1 (sosirile au loc pe rând)

εττ -)T(=)dN( i

s(t)t

∑∫ εττ -)T(=)dN( i1=i0

∑∫

0.=t

dar ;t

-t

s(t)ts

)dN(=

t

)dN(

ttt

t

0

t

t

0

t

εεττττ

limlimlimlimlim )( ∞→∞→∞→∞→∞→

•∫∫

s(t)

T=;

ts(t);

t

dτN(τ=

i

s(t)

i=

tt

t

tTλ=N

∑∫∞→∞→∞→

10 limlimlim)

Aplicaţia 1:Nod de reţea în regim de testare

Un nod de reţea (server) în testare, primeşte/ transmite pachete de date (mesaje) de lungime fixa, la intervale de timp deterministe si fixe

Timpul sistem al unui mesaj are 4 componente:timpul de prelucrare în nod (împachetare, despachetare)timpul de prelucrare în nod (împachetare, despachetare)timpul de aşteptare, înaintea prelucrării sau transmiteriitimpul de transmitere la nodul următor, de la primul bit la ultimul bit (vom considera transmisia seriala)timpul de propagare, între transmisia primului bit de către nodul curent si recepţionarea sa de către nodul următor (≈0)

Condiţii de calcul

(1) timpul (S secunde) între sosirea mesajelor este fix (deci si rata sosirilor în sistem este fixa: λ=1/S)

(2) nodul poate prelucra si transmite simultan câte un mesaj(3) timpii de prelucrare P si de transmitere kS pentru un

mesaj îndeplinesc cerinţele: k ≤ 1, kS+P < 2Smesaj îndeplinesc cerinţele: k ≤ 1, kS+P < 2SRezulta ca:

Timpii de prelucrare P si transmitere kS sunt singuriirelevanţi, deoarece, datorita capacitaţii de prelucrare sitransmisie asincrona a serverului, mesajele nu aşteaptă!Timpul sistem al fiecarui mesaj este acelaşi, egal si cumedia sa: T = kS+P

Aplicarea legii lui Little Numărul mediu de clienţi în sistem:

N = λT = k+P/S

Interpretare:N nu este o limita catre care converge numărul de clienţin sistem, N(t) - de fapt N(t) nu converge, deoareceîn sistem, N(t) - de fapt N(t) nu converge, deoarecesistemul nu atinge o stare de echilibru statistic!Totuşi, aplicarea legii lui Little este riguroasa prininterpretarea lui N ca valoare fixa a mediei temporale anumărului de unitati în sistem, determinat la momentediscrete de timp, în timp (foarte lung):

t)dtNk1=N

k

0k(lim ∫∞→

Aplicaţia 2:Sistem de calcul în time-sharing

Task-urile necesita un timp mediu de pregătire G si de prelucrare P (dar pot fi ţinute în coada de către procesor, în aşteptarea servirii)

Condiţii de calcul Există întotdeauna un utilizator gata sa ia locul altuia care se ridica de la terminal (deoarece suntem interesaţi în estimarea valorii maxime pentru rata de ieşire a unităţilor din sistem) Echivalent, numărul de utilizatori din sistem este constant (N)Echivalent, putem considera reintrarea imediata în sistem a Echivalent, putem considera reintrarea imediata în sistem a oricărui utilizator ce încheie un taskT este timpul sistem mediu pentru un utilizator, cu structura:

T = G+D+P, unde D este timpul de aşteptare al task-ului utilizator, ce ia valori discrete între 0 (intrare directa în execuţie) si (N-1)•P (aşteptare maximala după toţi ceilalţi utilizatori)

Aplicarea legii lui LittleIntre punctele A si C: λ = N/T0 ≤ D ≤ (N-1)•P ⇒ G+P ≤ T ≤ G+N•P ⇒

Intre punctele B si C (intrarea si iesirea serverului):

P+GN

PN+GN

≤≤⋅

λ

N,1 N min≤≤ λ

(rata de procesare a joburilor nu poate depăşi 1/P)

Limitele de variaţie ale timpului mediu de aşteptare per utilizator atunci când sistemul este integral utilizat:

P+G

N,P1

PN+GN min≤≤

⋅λ

PN+G T P+GP,N ⋅≤≤⋅max

Variaţia ratei de prelucrare λ

Variaţia timpului sistem mediu pentru un utilizator

DiscuţieCând N creste:n rata de ieşire tinde spre valoarea maxima 1/Pn timpul mediu de aşteptare pentru un utilizator

creste proporţionalRata de ieşire maximala depinde de parametrii-Rata de ieşire maximala depinde de parametrii-sistem ca:n proporţia între timpii de pregătire si de execuţien disciplina de servire

Limitele obţinute nu depind de parametrii-sistem

InterpretăriCât timp N<1+G/P, N reprezintă un factor deblocaj în sistem, deoarece procesorul rămânenefolosit o fracţiune importanta din timp(corespunzătoare momentelor de angajare simultana atuturor utilizatorilor în pregătirea task-urilor lor)tuturor utilizatorilor în pregătirea task-urilor lor)

Când N>1+G/P, puterea de procesare aserverului este cea care determina blocajul

Reţele de cozi de aşteptareO reţea de cozi este un sistem ce constă din mai multe servere, fiecare având asociat un buffer

Unităţile (clienţii) pot aparţine mai multor clase

Clienţi aparţinând unor clase diferite pot necesita Clienţi aparţinând unor clase diferite pot necesita servicii diferite, chiar de la acelaşi server

După un serviciu, un client poate fi dirijat într-un anumit mod n De ex., pentru a cere efectuarea unui alt serviciu la

un server diferit de primul sau a părăsi sistemul

Clasificarea reţelelor de cozi după modalitatea de dirijare

Reţele deschise - au loc: n sosiri în sistem ale unităţilor din exterior (de obicei

modelate ca procese Poisson) n parasiri ale sistemului de către clienţi după efectuarea

unor serviciiReţele închiseReţele închisen fiecare client circula între servere, pentru serviri, fara a

părăsi sistemul; n din exterior nu pot intra noi clienţi în sistem, deci

numărul total de clienţi este o constanta sistemReţele mixten deschise pentru anumite clase de clienţi si închise

pentru altele

Reţele de cozi factorizabile Distribuţia staţionara a reţelei poate fi descompusa într-un produs de distribuţii ale fiecăruia dintre subsistemele de aşteptare (cozile) componente, analizabile separat n Pentru reţelele deschise ⇒ independenta distribuţiilor staţionare

ale cozilor individuale (distribuţia staţionara e produsulale cozilor individuale (distribuţia staţionara e produsuldistribuţiilor individuale ce se obţin prin analiza separata a fiecăreicozi considerând o rata de sosire adecvata, modificata, ce reflectamodalitatea de dirijare în reţea)

n Pentru reţelele închise ⇒ dependenta dintre cozi poate ficapturata prin normalizarea soluţiei independente peste un spaţiude stare normalizat; în acest caz, pot apare dificultaticomputaţionale în calculul constantei de normalizare

Reţele Jackson deschiseCaracteristici:

M staţii de servire (cu server unic), fiecare având un buffer de capacitate infinitaSosirile din exterior ale clienţilor la fiecare staţie i dintre cele M sunt procese Poisson cu media λ0,icele M sunt procese Poisson cu media λ0,i

După efectuarea unui serviciu de către serverul i, un client poate cere servirea din partea unui alt server j -cu probabilitatea qi,j, sau poate parasi sistemul - cu probabilitatea qi,0 :

q-1=q ji,

M

j=1i,0 ∑

Ecuaţii de fluxDaca:

n timpul de [de]servire al serverului i este exponenţial distribuit cu media si=1/μi

n λi este rata de sosire medie a clienţilor la serverul i (includem atât clienţii ce sosesc din exteriorul (includem atât clienţii ce sosesc din exteriorul sistemului la serverul i, cât si pe cei care sosesc din sistem, după servirea lor de către alt server)

Atunci:

M1,2,...,=iq+= ,ji,j

M

j=1i0,i •∑λλλ

Reţele Gordon-Newell închiseCaracteristici:

Se bazează pe aceleaşi premise ca si o reţea Jackson, exceptând faptul ca λ0,i=0 si qi,0=0, pentru orice i (aceasta exprima faptul ca reţeaua este închisa -numărul total N de clienţi în sistem este fix) numărul total N de clienţi în sistem este fix) Daca notam starea sistem cu n=(n1,n2,...nM), unde ni e numărul de clienţi în bufferul serverului i:

N=n i

M

=1i∑


Simularea sistemelor dinamice cu


Simularea sistemelor dinamice cu evenimente discrete (SDED)

Simularea (Shannon): Procesul construirii unui model pentru un sistem/proces real si efectuare de experimente folosind modelul pentru:

intelegerea comportarii sistemului realintelegerea comportarii sistemului realurmarirea evolutiei dinamice a sistemuluievaluarea unor strategii de operare

Modelare și simulareModel: o reprezentare a unui sistemn Modelele matematice folosesc notații simbolice și

ecuații matematice/ modelele de simulare pot fi considerate tipuri particulare de modele matematice:- Deterministe: un set cunoscut de intrări corespunde - Deterministe: un set cunoscut de intrări corespunde

cu un set unic de ieșiri- Stochastice: una sau mai multe intrări sunt v.a.,

fapt ce determină ieșiri aleatoaren Modelele fizice, constructive

Modelare: procesul de construire a unui modelSimulare: imitarea modului de operare al unui sistem sau proces real, de obicei în timp

Modalități de simulare discretă (stochastică)

Statică, de ex. simularea Monte-Carlo1. Se definește un domeniu al intrărilor posibile2. Se generează aleator intrări din domeniu pe baza

unei distribuții de prob. (cel mai adesea uniformă)3. Se fac calcule deterministe folosind aceste intrări3. Se fac calcule deterministe folosind aceste intrări4. Se agregă rezultatele individuale în cel final

n Ex: valoarea lui π/4 este aproximată de raportul între aruncările într-un cerc și cele în pătratul “circumscris”

Dinamică, de ex. simularea sistemelor dinamice cu evenimente discrete

Simularea SDEDmodalitate sistematică de generare a traiectoriilor dinamice ale sistemului producerea unor secvenţe de ipostaze (imagini) ale SDED reprezintă dinamica (evoluţia) in timpale SDED reprezintă dinamica (evoluţia) in timpconcept important: starea, caracterizată prin variabilele de stare ce iau valori discreten variabilele continue (ex. timpul), nu sunt considerate

independent, ci doar în relaţie cu apariţia unor evenimente; ele sunt discretizate si considerate ca variabile-anexa sau deduse

Starea in simularea SDEDstarea fizică – cea uzuala in TS, aici tipic discreta Ex: nr.unităţilor din coada unui server intr-o reţea de cozistarea matematică (ipostaza la mom. t), include:n o informaţie completa asupra stării fizice a sistemului

la momentul tla momentul tn toate elementele necesare pentru determinarea in

mod unic a evoluţiei viitoare a sistemului, n o lista a evenimentelor viitoare (LEV) ce vor determina

tranziţiile de stare n valori curente ale statisticilor cumulative/contorilor ce

vor fi folosite in calculul statisticilor rezumative finale

Dinamica simulării SDEDEste determinata de evenimente, ce pot fi:n externe (ex. sosirea unei unităţi in sistem)

n interne (ex. terminarea servirii unui client la un server)

Apariţia unui eveniment împreuna cu îndeplinireaApariţia unui eveniment împreuna cu îndeplinireaunor condiţii logice (reguli de operare) determina otranziţie de stare

In noua stare noi evenimente pot fi planificateEvenimentele existente continua sau vor fi

terminate conform cu LEV

Evenimenteleapariţii instantanee care schimbă starea sistemdelimitează activităţi in sistempot fi:n endogene: apariţii in interiorul sistemuluin endogene: apariţii in interiorul sistemuluin exogene: apar in mediu (in afara sistemului) dar

afectează sistemul

in simulare, parametrul timp este doar asociatapariţiei evenimentelor, iar progresia temporala asimulării este implicita avansului in procesarea LEV

Simulatoareun simulator este un program de calculator prin care se modeleaza:n comportamentul intern al unui sistem realn procesele de intrare ce dirijeaza sau controleaza

sistemul simulatiesirea unui simulator consta intr-un set de iesirea unui simulator consta intr-un set de masuratori legate de reactiile observabile si performanta sistemului realmasuratorile obtinute sunt doar estimatori ai masurilor reale, deoarece simularea nu are ca suport sistemul real, ci un model al acestuia (mai mult sau mai putin fidel)

Metodologii de simulareConstrucţia unui simulator se face pe baza unei

metodologii de simularesimularea condusa de timp implica existenta unui ceas de timp central avansat cu increment fix n generează algoritmi ineficienţi si este mult mai puţin n generează algoritmi ineficienţi si este mult mai puţin

utilizata n prezintă un anumit interes doar in cazul simulării

paralele (distribuite) metodologia generala de simulare pentru SDED este simularea condusa de evenimenten planificarea corecta a execuţiei evenimentelor impune

cu necesitate includerea lor intr-o lista ordonata după timpii de apariţie ai evenimentelor (LEV)

Abordări in simularea SDEDPlanificarea de evenimenten impune ca atunci când o activitate începe, durata ei

sa fie calculata (sau generata aleator) si evenimentul ei de sfârşit sa fie plasat in LEV

n se definesc schimbări de stare pt. fiecare evenimentmecanismul de avans temporal si garantarea apariţiei n mecanismul de avans temporal si garantarea apariţiei cronologice a evenimentelor e complet bazat pe LEV

Interacţiunea proceselorn se descriu procesele asociate cu entităţile – acestea

pot fi permanente sau temporare n simularea se constituie ca un ansamblu de procesen mai multe procese pot fi simultan active in model si

interacţiunea dintre ele poate fi complexa

Cum decurge simularea dirijată de evenimente...

LEV, menţinuta ordonata, se compune din:n “evenimentul iminent" - cel aflat in fruntea

listei, ce poate fi deja in curs de trataren celelalte evenimente (“potenţiale”), numite n celelalte evenimente (“potenţiale”), numite

astfel deoarece ele pot decalate, modificate sau chiar anulate prin simularea evenimentului iminent

“Activitate" in cadrul simulării - apariţia unui eveniment, urmata de tratarea lui, prin care se modifica starea sistem si (potenţial) LEV

Compus dintr-o coada de dimensiune maxima n=500 si un server

... pentru un sistem simplu de aşteptare

COADA SERVER

Va fi considerat complet stochastic:n Procesul de sosire este aleatorn Timpul de servire este aleator

Sosirea clienţilorClienţi inaşteptare

Client in servire

Plecarea clienţilor

Definire sistem si obiectiveEntităţi: Clienţi, Coada, Servern nu este necesara reprezentarea explicita a clienţilor

(individualizarea lor)

Evenimente: sosire client, plecare clientDate colectateDate colectateêUtilizare serverê Lungimea maxima a coziiêTimp de aşteptare client(i)êTimp de răspuns al sistemuluiêProcentajul clienţilor ce aşteaptă peste o valoare prag

Definirea statica a modeluluiStarea sistem este descrisa de variabilele:n lqt=numărul de clienţi aflaţi in coada de aşteptare la un

moment datn lst=numărul de clienţi aflaţi in servire la un moment dat, 1 sau

0 (sau starea serverului, ocupat sau liber)

Evenimente:Evenimente:n sosirea unui client in sistem;n plecarea unui client din sistem prin terminarea servirii sale;

Activităţi:n timpul între sosiri, definit de o tabela ce se generează aleatorn timpul de servire, definit in acelaşi mod

Întârzieri: aşteptări in coada, pana serverul devine liber

Descrierea dinamica a modeluluiCum afectează fiecare eveniment starea sistem,

atributele entităţilor, conţinutul seturilor?Cum sunt activităţile definite (determinist, probabilistic,

printr-o ecuaţie matematica)?Care sunt evenimentele de început/sfârşit al activităţii?Poate o activitate începe indiferent de starea sistem,Poate o activitate începe indiferent de starea sistem,

sau este condiţionata de starea sistem?Care sunt evenimentele de început/sfârşit al fiecărui tip

de întârziere?Care sunt condiţionările pentru ca o întârziere sa

“înceapă" sau sa se "termine"?Care este starea sistemului la momentul iniţial?Ce evenimente "primare" trebuie generate la momentul

iniţial pentru ca simularea sa poată începe?

Dinamica simulării in interacţiunea proceselor

Se identifica entităţile caracteristice in sistemPot coexista, interacţiona si intra in competiţie multiple copii ale entităţilorCodul de simulare este non-procedural: in mod separat, se descriu entităţile “tipice”separat, se descriu entităţile “tipice”Pot exista multe tipuri de entităţi, inclusiv cele de “excepţie” (de ex. pentru tratarea defectelor)Este de obicei necesar un soft specializatn Altfel, se recurge la serializare si planificare de

evenimenten Oricum, eficienţa este mai scăzuta in cazul execuţiei

secvenţiale

Creare Nod Nod in Coada Terminare Nod

Activitate Servire

Diagrama proceselor asociate entităţilor

18

Activitate Servire

Aceasta tehnica este adecvata când rezolvarea unei probleme este echivalenta cu descrierea unor activităţi relativ independente desfăşurate in paralel, dar care comunica si interacţionează pe parcursul execuţiei lor

Fazele unui studiu de simulare

Faza de planificarea) Specificarea problemei

• intrebari esentiale: “Ce se cere? La ce va folosi?”

• uneori se poate formula doar obiectivul atasat unei descrieri vagi a procesului studiat

b) Estimarea resurselor• implica alegerea modalitatii de abordare, studii de

fezabilitate, evaluarea costurilor de timp si personal, ca si stabilirea graficului de derulare a activitatilor

c) Analiza sistemului si a datelor • se identifica diversele nivele de detaliere necesare

Faza de modelareConsta in:a) Construcţia modelului: pot exista mai multe modele candidate, trebuie ales unul

b) Colectarea datelor: datele reale permit b) Colectarea datelor: datele reale permit identificarea modelului adecvat

c) Translaţia modelului: codificarea intr-un program ("model programat")

Faza de verificare/validare (1)Verificarea consta in depanare si testare programValidarea este mai ampla – la întrebarea “reflecta

programul in mod fidel sistemul?” răspunsul e DA numai daca se respecta câteva principii de lucru

In dezvoltarea unui model valid asociat datelor de In dezvoltarea unui model valid asociat datelor de intrare distingem următorii paşi:

a. colectarea datelor brute din sistemul studiatb. identificarea distribuţiei statistice a datelor, prin:- construirea distribuţiei frecvenţiale a datelor de intrare

(histograma);- asumarea unei presupuneri distribuţionale (in practica apar mai

frecvent doar câteva distribuţii standard)

Faza de verificare/validare (2)Paşi in validare (cont.):

c. estimarea parametrilor distribuţiei asumated. testarea concordantei intre distribuţia asumata (cuparametri estimaţi) si datele de intrare, folosind:§ testul χ2§ testul χ§ testul Kolmogorov-Smirnov

ØDaca testul de concordanta eşuează, ipoteza că dateleurmează legea distribuţionala propusa trebuie respinsasi se încearcă o noua ipoteza distribuţionala (se reia cupasul b)ØDaca mai multe iteraţii ale acestei proceduri eşueazăin găsirea unei concordante intre distribuţia asumata sidatele colectate, trebuie folosita distribuţia empirica

Faza de execuţieConsta in:a) Proiectarea experimentelor: se aleg execuţii genericeb) Experimentare: se executa programul cu date b) Experimentare: se executa programul cu date reale!c) Analiza: se interpretează rezultateled) Implementarea/Documentarea: • cum se implementează deciziile rezultate din simulare?• cum se documentează modelul in vederea reutilizării?

Măsurători de performanţăFundamentale sunt răspunsurile la câteva întrebări:

Ce alternative se simulează (se executa)? Cat de lunga este o execuţie?Ce se măsoară?Maximul, minimul, totalul, media, varianta, momente de Maximul, minimul, totalul, media, varianta, momente de ordin superior, distribuţii specifice de frecventa, timpii intre sosiri, timpii de servire, lungimi ale cozilor, rate de pierdere sau eroare etc.Care sunt proprietăţile (statistice) ale "masurilor" de care suntem interesaţi?Sunt necesare si alte execuţii? Trebuie schimbat modelul? Trebuie schimbaţi parametrii?

Planificarea de evenimenteRămâne cea mai adecvată programării standard, si cea mai eficienta in cazul execuţiei secvenţialeSe utilizează de obicei funcţii de biblioteca pentrun Prelucrarea listelorn Generarea numerelor aleatoaren Generarea numerelor aleatoaren Generarea variabilelor aleatoaren Colectarea statisticilorn Managementul (ordonarea) LEV si ceasului de timp

“Nod de sincronizare" - ansamblul procedurilor ce implica întreţinerea LEV (adăugarea, suprimarea sau modificarea de evenimente)

Ipostaza sistem tipica

Exemplu numeric

UnitTimpi între sosiri

Timp sosire

1 - 0

2 2 2

Unit Timp servire

1 2

2 1

Unit Timp sosire

Încep servire

Timp servire

Termin servire

1 0 0 2 2

2 2 2 1 32 2 2

3 4 6

4 1 7

5 2 9

6 6 15

2 1

3 3

4 2

5 1

6 4

2 2 2 1 3

3 6 6 3 9

4 7 9 2 11

5 9 11 1 12

6 15 15 4 19

Algoritmul de planificare evenimente/ avans al timpului simulării

1) Scoaterea evenimentului iminent din LEV

2) Avansul ceasului sistem (CLOCK) la momentul apariţiei evenimentului

3) Execuţia evenimentului iminent 3) Execuţia evenimentului iminent ⇒actualizarea stării sistemului, a atributelor entităţilor

sistemului, a seturilor

4) Generarea evenimentelor viitoare si plasarea lor in LEV in poziţia corecta

5) Actualizarea rezultatelor cumulative si statistice

Tratare eveniment “sosire client”

Plasează clientul sosit in coada

Planifica următoarea sosire

Server ocupat?DaNu

Plasează clientul sosit in coadaOcupa server

Planifica eveniment de plecare client

Return

Da

Selecteaza client din coadapentru servire

NuCoada vida?

Elibereaza serverul

Tratare eveniment “plecare client”

Actualizeaza statisticile pentru coadasi noul client in servire

Return

Actualizeaza statisticile pentru server

Planifica evenimentul de plecare

Colecteaza datele pentru clientul care pleaca

Programarea modeluluiPoate fi făcuta intr-un limbaj procedural (C)Proiectul C (anexat) e compus din fişierele sursa: n "sp.c“: simulatorul principal, ce conţine rutinele de

iniţializare, avans timp, tratare a evenimentelor si generare a rapoartelor generare a rapoartelor

n "rndevg.c“: conţine rutine pentru generarea distribuţiilor statistice

n "rndevg.h“: fişierul header ce conţine definiţiile de prototipuri si constante

Un număr de 10 execuţii fără modificarea parametrilor modelului permite o analiza simpla

Execuţia modelului programat Valoarea de start (seed)

Utilizarea serverului

(%)

Lungimea maxima a

cozii

Timpul total al simularii

(min.)

% clientilor ramasi > 4 min.în sistem

Timpul de raspuns

mediu (min.)

Numarul plecarilor din

sistem

61011 72.55 13 44095.2 71.47 3.2 10 000

61136 70.65 16 45352.9 70.59 3.2 10 000

61190 71.47 11 44751.2 71.08 3.2 10 000

61209 71.39 20 44774.6 71.07 3.2 10 000

61225 72.11 11 44569.0 71.45 3.2 10 000

61237 70.95 13 45121.3 70.01 3.2 10 000

61249 72.03 11 44461.9 70.73 3.2 10 000

61265 72.25 10 44412.3 71.32 3.2 10 000

61280 71.40 16 44675.1 71.23 3.2 10 000

61299 71.57 14 44909.6 71.07 3.2 10 000

Media 71.64 13.5 44712.3 71.002 3.2 10 000

Abaterea 0.564 2.94 343.1 0.426 0 0


Studiu de simulare secvenţială


Studiu de simulare secvenţialădiscretă

Formularea problemei si planului

Colectare date si definire model

Model programat valid?

Proiectarea experimentelor

Da

Nu

Fazele studiului de simulare

Model conceptual valid?

Constructia programului si verificarea

Executii pilot

Executia experimentelor

Analiza rezultatelor simularilor

Interpretare si documentare program

NuDa

Scopul studiuluiDe a relua si aprofunda metodologia de baza a simulării (planificarea de evenimente) si de a identifica unele probleme des întâlnite, evidenţiate de un exemplu simpluExemplu de lucru: acelaşi sistem de procesare Exemplu de lucru: acelaşi sistem de procesare M/M/1/n (poate fi un calculator, o maşina-unealta)Spre deosebire de cursul anterior, vom încerca un studiu pas cu pas (software-independent)Vor fi reexaminaten Terminologia de bazan Câteva probleme statistice importante

Sistemul simplu de aşteptare

Sosirea unitatilor Plecarea unitatilor

Server

Coada (FIFO) Unitate in servire

4567

Se urmăreşte estimarea:§ Capacitaţii de procesare§ Timpului de aşteptare in coada§ Lungimii utile a cozii§ Proporţiei de timp in care serverul este ocupat§ etc.

Specificare si iniţializare modelLa momentul iniţial (t=0) sistemul este golDate de intrare (observate sau generate, nu interesează deocamdată cum), de ex. in minute:

Client (unit) Timp de sosire Timp intre sosiri Timp de servire1 0.00 1.73 2.902 1.73 1.35 1.762 1.73 1.35 1.763 3.08 0.71 3.394 3.79 0.62 4.525 4.41 14.28 4.466 18.69 0.70 4.367 19.39 15.52 2.078 34.91 3.15 3.369 38.06 1.76 2.37

10 39.82 1.00 5.3811 40.82 . .

. . . .

. . . .Condiţie de oprire: t>20

Obiective & Masuri de performantaCapacitatea de procesare totala pe durata simulării (P)Timpul de aşteptare mediu al unităţilor in coada

N = nr. unităţilor ce aşteaptă in coadaWQ

N∑

Timpul de aşteptare maxim al unităţilor in coada

N = nr. unităţilor ce aşteaptă in coadaWQi = timpul de aşteptare in coada al unităţii iŞtim ca: WQ1 = 0 (?)

N > 1 (de ce?)N

WQN

ii∑

=1

iNi

WQmax,...,1=

Măsuri de performanţă (2)Media (in timp) a numărului de unităţi in coada

Numarul maxim de unităţi in coada 20

)(200∫ dttQ Q(t) = numărul de unităţi in coada

la momentul tNumarul maxim de unităţi in coada

Timpul mediu si maxim total in sistem al clienţilor (sau timpul de ciclare)

)(max200

tQt≤≤

iPi

P

ii

TSP

TSmax

,...,11 ,

=

=∑ TSi = timp in sistem al clientului i

Măsuri de performanţă (3)

Gradul de utilizare a serverului (proporţia de timp in care serverul este ocupat)

=∫ ttB

dttB mom. laocupat este serverul daca1)(,

)(20

0

=

ttB

mom. laliber este serverul daca0)(,

20

Validarea consistentei datelor de intrare

Timpul mediu intre sosiri = 4.08 min.Timpul mediu de servire = 3.46 min.Deci unităţile sunt procesate mai repede decât sosesc (in medie), ceea ce înseamnă ca:

Sistemul va opera in regim stabil după un timpn Sistemul va opera in regim stabil după un timpn Daca toţi timpii intre sosiri si cei de servire ar fi exact

pe medie, unităţile nu ar intra in coadan Dar in general datele aleatoare au o anumita

variabilitate - coada se va forman Daca timpul mediu intre sosiri < timpul mediu de

servire, coada va creste “exploziv”

Modelarea analiticaEste aici posibila si utila, ca prima aproximaţie, folosind un model M/M/1Necesita insa presupuneri suplimentare: n Timpii intre sosiri ~ distribuiţi exponenţial

Timpii de servire ~ exponenţial, independent n Timpii de servire ~ exponenţial, independent n Trebuie ca E(servire) < E(inter-sosiri)n Analiza se face doar in starea stabilan Se pot obţine rezultate exacte; de ex., timpul mediu

de aşteptare in coada:

time) E(service time) ivalE(interarr 2

==

− S

A

SA

Sµµ

µµµ ,

Statistici cumulative si contoriNumărul curent de unităţi serviteTotalul timpilor de aşteptare in coadaNumărul curent de unităţi ce au stat in coadaTimpul maxim de aşteptare in coada (curent)Totalul timpilor in sistemTotalul timpilor in sistemTimpul maxim in sistem (curent)Aria de sub curba Q(t) (ce da media lungimii cozii)Maximul curent pentru Q(t)Aria de sub curba B(t) (ce da gradul de ocupare a serverului)

Dinamica simulării in abordarea prin planificarea de evenimente

Se identifica evenimentele caracteristiceSe iniţializează si se menţine un ceas de timp globalSe creează si se menţine LEV Se decide logica fiecărui tip de eveniment pentrun Tranziţiile de staren Actualizarea statisticilorn Actualizarea LEV

Se procesează logic evenimentele pe rând, in ordinea stricta a LEV (numita si calendar de evenimente)Trebuie specificata si o regula de oprire (timp maxim de simulare, număr maxim de unităţi procesate)

Tratarea evenimentelor (1)La sosirea unei noi unităţi in sistem

Actualizează variabilele statistice (acumulatori persistenţi)n Valoarea ariei de subQ(t)n Max Q(t)n Valoarea ariei de sub B(t)

Se aplica unităţii sosite “stampila de timp” curenta (se va Se aplica unităţii sosite “stampila de timp” curenta (se va utiliza ulterior)Daca serverul este liber:n Start procesare (planifica plecarea), pune serverul pe ocupat,

pune timpul de aşteptare in coada pe 0Altfel, daca serverul este ocupat:n Pune unitatea “la coada”, incrementează lungimea cozii

Planifica următorul eveniment de sosire

Tratarea evenimentelor (2)

La plecarea unei unităţi din sistem, după servireIncrementează acumulatorul corespunzătorCalculează timpul in sistem al unităţii (momentul curent –momentul sosirii)Actualizează variabilele statistice (ca la sosire)Actualizează variabilele statistice (ca la sosire)Daca coada este nevidă:n Scoate prima unitate din coada, calculează timpul sau de

aşteptare in coada, începe servirea (planifica evenimentul de plecare)

Altfel (daca coada este vida):n Trece serverul in starea liber (nu se mai planifica vreun

eveniment de plecare in LEV)

Tratarea evenimentelor (3)

La sfârşitul simulării:Se actualizează statisticileSe calculează masurile de performanta folosind valorile curente, care sunt si finale, ale acumulatorilor

Observaţii:La începutul simulării, trebuie făcute iniţializări (de ex. in LEV se pune primul eveniment de sosire si evenimentul de sfârşit)După tratarea fiecărui eveniment, se continua cu primul eveniment din LEV (eveniment iminent)

System

Clock

B(t)

Q(t)

Arrival times of custs. in queue

Event calendar

Number of completed waiting times in queue

Total of waiting times in queue

Area under Q(t)

Area under B(t)

Simularea pas cu pas: set-up

Q(t) graph B(t) graph

Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...

01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 0.00

B(t) 0

Q(t) 0


<empty>

Event calendar [1, 0.00, Arr] [–, 20.00, End]

Number of completed waiting times in queue 0

Total of waiting times in queue 0.00

Area under Q(t) 0.00

Area under B(t) 0.00

Iniţializări la t = 0.00



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 0.00

B(t) 1

Q(t) 0


<empty>

Event calendar [2, 1.73, Arr] [1, 2.90, Dep] [–, 20.00, End]





t = 0.00, sosirea unităţii 1

1



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 1.73

B(t) 1

Q(t) 1


(1.73)

Event calendar [1, 2.90, Dep] [3, 3.08, Arr] [–, 20.00, End]






12



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 2.90

B(t) 1

Q(t) 0


<empty>






t = 2.90, plecarea unităţii 1

2



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 3.08

B(t) 1

Q(t) 1


(3.08)







23



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 3.79

B(t) 1

Q(t) 2


(3.79, 3.08)







234



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 4.41

B(t) 1

Q(t) 3


(4.41, 3.79, 3.08)







2345



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 4.66

B(t) 1

Q(t) 2


(4.41, 3.79)







345



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 8.05

B(t) 1

Q(t) 1


(4.41)







45



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 12.57

B(t) 1

Q(t) 0


()







5



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 17.03

B(t) 0

Q(t) 0

Arrival times of custs. in queue ()

Event calendar [6, 18.69, Arr] [–, 20.00, End]








01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 18.69

B(t) 1

Q(t) 0

Arrival times of custs. in queue ()

Event calendar [7, 19.39, Arr] [–, 20.00, End] [6, 23.05, Dep]






6



01

23

4

0 5 10 15 20

012

0 5 10 15 20

System

Clock 19.39

B(t) 1

Q(t) 1


(19.39)

Event calendar [–, 20.00, End] [6, 23.05, Dep] [8, 34.91, Arr]






67



01

23

4

0 5 10 15 20

012

0 5 10 15 20

t = 20.00, sfârşitul simulării

67

System

Clock 20.00

B(t) 1

Q(t) 1


(19.39)

Event calendar [6, 23.05, Dep] [8, 34.91, Arr]





01

23

4

0 5 10 15 20

012

0 5 10 15 20



Timpul mediu de aşteptare in coada:

Media in timp a numărului de unităţi in coada:

Operaţii la sfârşitul simulării

min./unit. 53.2617.15

unitati Nr.decoadain totalTimpul

==

Media in timp a numărului de unităţi in coada:

Utilizarea serverului:

unitati 79.020

78.15ceas de finala Valoarea

)( curba sub de Aria==

tQ

92.020

34.18ceas de finala Valoarea

)( curba sub de Aria==

tB

Replicarea simulăriiValoarea unei singure simulări (“replicări”) nu este foarte

semnificativa dpdv statisticTabelul următor permite compararea a 5 replicări:

Se poate observa variabilitatea mare intre replicări

Modificarea parametrilorIn mod uzual, simularea se aplica in mod repetat nu doar prin simpla replicare, ci pentru diferite configuraţii ale modelului, cu parametri modificaţiIn acest fel se face acordarea si optimizarea modelului (după anumite criterii)modelului (după anumite criterii)Exemplu: ce se întâmpla daca se dublează rata sosirilor?n Datele de intrare se obţin prin înjumătăţirea timpilor

intre sosirin Se va relua execuţia modelului pentru configuraţia

modificatan Se vor executa 5 replici ale simulării


Verificarea si validarea simularilor.


Verificarea si validarea simularilor. Analiza iesirilor

SumarCorectitudinea estimatorilor. Rolul etapelor de validare si verificareTipuri de estimatorin Estimatori (ne)balansatin Estimatori consistentin Estimatori consistentin Estimator interval si grad de incredere

Analiza iesirilor. Determinarea intervalelor de incredereClasificarea simularilorSimulari complete si de stare stabila

O practica uzualaSe construieste modelul, se executa simulareaSe obtin estimari ale masurilor de performanta relevante ale sistemului , de ex.n Timpul mediu in coada

Timpul mediu in sistemn Timpul mediu in sistemn Rata de iesire a clientilorn % clientilor ce asteapta in coada (eventual raportand

timpul de asteptare la o valoare prag), etc.Se utilizeaza aceste estimari pentru a se lua unele decizii, sau a se trage anumite concluzii privind sistemul

... Dar deficitara!Exista 2 probleme majore in aceasta abordare; pentru ca estimarile sunt si ele v.a., nu stim:n Cata incredere putem avea in ele si care este

eroarea maxima de obtinere a lor (pentru a o compara eventual cu eroarea admisibila)?compara eventual cu eroarea admisibila)?Principiu (foarte important in statistica!):“O estimare nu are valoare decat insotita de o indicatie asupra acuratetei estimarii“

n Cat de mare este influenta asupra estimarilor a comportarii initiale (tranzitorii) a sistemului, sicat de corecta este includerea acesteia?

Validare si verificareO simulare este valida daca modelul de simulare reprezinta cu acuratete sistemul realn Validarea raspunde la intrebarea “A fost construit

modelul adecvat?”O simulare este verificata daca programul de O simulare este verificata daca programul de simulare reprezinta translatia corecta a modelului (modelul programat)n Verificarea raspunde la intrebarea “A fost construit in

mod adecvat (corect) modelul?”Doar un model valid si verificat poate permite analiza diverselor scenarii de functionare (“what-if analysis”)

Iesiri deterministe si stochasticeSimularea este un instrument puternic, orientat dinamic, ce permite obtinerea unui set larg de rezultate (date de iesire)Pentru un model determinist, exista un set unic de date de iesire pentru fiecare set dat de date de date de iesire pentru fiecare set dat de date de intrare Pentru un model stochastic (si) datele de iesire sunt aleatoare, ele fiind deci doar estimari ale parametrilor reali ai sistemuluin De aceea o singura executie a unui model

stochastic nu este niciodata suficienta

Acuratetea estimariiPoate fi data sub forma:n unui prag (interval, probabilitate) de increderen erorii standard a estimarii (la randul ei o estimare

a deviatiei standard a estimarii)Estimarea erorii nu se poate face pe baza unei singure simulari (nu avem posibilitatea de a compara mai multe valori)Este necesara repetarea simularii si “replicarea” estimatorului

Estimatori si inferenta statisticaInferenta statistica este o metoda de analiza a unui sistem caracterizata prin utilizarea datelor experimentale ca baza a diferitelor concluziiUn estimator punctual al unui parametru sistem θ este un numar calculat pe baza datelor experimentale, notat Uneori termenul de estimator desemneaza statistica

θUneori termenul de estimator desemneaza statistica folosita pentru a calcula un rezultatDe exemplu:

arata atat ca estimatorul punctual al mediei unei populatii are valoarea 31.75, cat si ca acest estimator a fost calculat folosind media esantionului ca estimator

75.31ˆ == xµ

Estimatori si statisticiDualitatea terminologica se justifica prin aceea ca un estimator punctual este de obicei obtinut prin selectarea unei statistici adecvate si calculul unei valori pentru un set de date experimentaleDe exemplu,De exemplu,Ø statistica naturala pentru estimarea mediei

unei populatii, µ, este media esantionului de date,

Ø statistica naturala pentru estimarea variantei σ2 este varianta esantionului de date, s2

x

ExempluO metoda des folosita de biologi pentru estimarea unei populatii este un experiment de captura/recaptura; daca se doreste de ex. estimarea numarului de pesti dintr-un lac – parametrul de estimat este marimea populatiei, N:n Se captureaza mai intai un numar mic de pesti, de exemplu 100,

care se marcheaza si se elibereaza in laccare se marcheaza si se elibereaza in lacn Dupa un timp suficient pentru a permite pestilor marcati sa se

amestece cu ceilalti, se re-captureaza un numar mai mare de pesti, de exemplu 500

n Daca intre acestia se gasesc de ex. 20 marcati (adica 4%) este rezonabila estimarea ca 4% din totalul pestilor sunt marcati!?

n Aceasta sugereaza ca putem folosi 100:(4/100) = 2500 ca estimator punctual pentru marimea populatiei de pesti, N

Prin repetarea re-capturarii precizia metodei creste !Repetarea permite si estimarea erorii estimatorului

Tipuri de estimatori

Estimatori (ne)balansatiUn estimator al unui parametru θ s.n. nebalansatdaca:Altfel, s.n. balansat, iar cantitatea s.n. balansul lui θ (bias) Cele mai importante statistici (media, abaterea

θθµ

θ=ˆ

θ θµθ

−ˆ

Cele mai importante statistici (media, abatereapatratica medie s2) sunt estimatori nebalansatiO exceptie importanta este deviatia standard a esantionului, s - estimator “usor” balansat al deviatiei standardn Balansul este neglijabil pentru esantioane largin Pentru esantioane mici, poate fi aplicat un factor de

corectie

Estimatori consistentiDaca, prin cresterea marimii esantionului (n), n un estimator poate fi facut oricat de apropiat de un

parametru θn sau, echivalent, probabilitatea ca el sa fie oricat de

apropiat de parametru poate fi oricat de apropiata de 1

θ

apropiat de parametru poate fi oricat de apropiata de 1 s.n. estimator consistent al parametrului θ

Metoda cea mai simpla prin care se poate arataca un estimator este consistent este aceea de a arata ca eroarea standard descreste pe masurace marimea esantionului creste

θ

Eroarea standard (a mediei)E un estimator al deviatiei standard a distributieide esantionare asociate cu metoda de estimare(de obicei, distributia normala)

, unde: σ este deviatia standard a esantionuluin este marimea esantionuluinx

σσ =

n este marimea esantionuluiFormula se deduce usor:n Fie v.a. X1, X2, ..., Xn - n observatii independente dintr-o

populatie cu media μ si deviatia standard σ

n Atunci varianţa sumei T = (X1 + X2 + ... + Xn) este nσ2

n Varianţa mediei esantionului, T/n, este (1/n2). nσ2, de unde se deduce deviatia standard a lui T/n (radicalul)

n

Estimator interval si grad de incredere

Un estimator punctual, doar el, nu furnizeaza informatii despre precizia si gradul de incredere intr-o estimareAlternativa la raportarea unei singure valori (cea mai plauzibila) este de a calcula si furniza un interval in care se poate gasi parametrul estimat, cu un grad de incredere foarte mare, acesta se numesteincredere foarte mare, acesta se numesten Estimator interval, sau n Interval de incredere

Doar daca gradul de incredere (notat de obicei prin psau α) este mare (apropiat de 1, sau 100%) si intervalul rezultat este (destul de) ingust, in jurul mediei, precizia estimarii valorii parametrului este rezonabila

Determinarea intervalului de incredere (1)

Metoda, ilustrata pentru o populatie sau un proces cu media µ, se bazeaza pe o proprietate importanta a distributiei esantionateCand n este mare, distributia lui este aprox. normala (Teorema de limita centrala) si se poate

xx

normala (Teorema de limita centrala) si se poate standardiza prin

sau

tinand cont de faptul ca deviatia standard a populatiei sau procesului (σ) nu este cunoscuta si trebuie inlocuita prin cea a esantionului (s)

nxz

/σµ−

=ns

xz µ−=

Determinarea intervalului de incredere (2)

V.a. z are aproximativ o distributie normala standard

Cele mai folosite valori pentru pragul de incredere p (sau α) sunt 90%, 95%, si 99%, si ele conduc la obtinerea valorilor critice pentru z de1.645, 1.96, si respectiv 2.575

1.96From Wikipedia, the free encyclopedia

1.96 este valoarea aprox. a valorii percentile de 97.5% pentru distributia normale avand interpretarea: 95% din aria de sub curba normala se afla sub cca 1.96 deviatiistandard ale medieiPe baza teoremei de limitaPe baza teoremei de limitacentrala, acest numar poate fifolosit in constructia pragurilor(intervalelor) de incredere de 95% Ubicuitatea acestui parametru se datoreaza uneiconventii arbitrare dar comune de utilizare a intervalelorde 95% in dauna celor de 90% sau 99%

Comportare tranzitorie vs. permanenta

In simularea unui sistem putem fi interesati:n In estimarea parametrilor de performanta doar in

regim permanentw In acest caz nu este corecta includerea comportarii

tranzitorii a sistemului; includerea ei produce balansarea estimatorilor si trebuie aplicate corectii

n In estimarea parametrilor de performanta incluzand si regimul tranzitoriu al sistemuluiw In acest caz se considera influenta comportarii

tranzitorii a sistemului asupra estimatorilor

Simulare completa si de stare stabila

Distinctia intre cele 2 cazuri este caracterizata ca simulare completa, respectiv pentru stare stabila(“Terminating vs. Steady State Simulations”)Exista multe sisteme ce ar putea fi simulate atat complet, sau doar pentru starea stabilacomplet, sau doar pentru starea stabilaDecizia de a face simularea complet, sau doar pentru starea stabila, se ia pe baza:n tipului de sistem modelatn tipului de parametri ce sunt urmariti si ale

caror valori se vor obtine prin simulare

Clasificarea simularilor (dupa analiza iesirilor)

Simulari ce includ regimul tranzitoriu (complete)

Nu se doreste eliminarea regimurilor tranzitorii, deoarece sistemul nu ar fi opera corect fara eleExemplu:n Simularea activitatii unei banci, pentru a

determina numarul de personaldetermina numarul de personalw Banca deschide la 9, initial nu sunt clientiwOpereaza “normal” pana la ora 16w La ora 16 se inchid usile, nu se mai admit clienti in

banca; cei aflati inauntru isi termina operatiunile si parasesc banca

Simulare completaO simulare ce include regimul tranzitoriu, pentru care masurile dorite de performanta se definesc relativ la intervalul complet [0, TF], unde TF este momentul la care apare evenimentul final EF

T este de obicei variabila aleatoaren TF este de obicei variabila aleatoaren TF este predeterminat la inceputul simulariin Sau se specifica evenimentul final EF

Trebuie de asemenea definite conditiile initiale la momentul 0

Simulare de stare stabilaO simulare ce nu include regimul tranzitoriu si pentru care masurile dorite de performanta (de obicei formule derivate din variabilele de stare) se definesc ca limite pe masura ce lungimea simularii creste la infinitsimularii creste la infinitn Starea sistem este independenta de conditiile initialen Exista o perioada de “Warm-Up” initiala (posibil si o

perioada finala similara) - un interval de timp in care simularea progreseaza fara a se colecta date statistice

ATENTIE: Exista sisteme care nu ajung in starea stabila!

Analiza simularilor completeSe foloseste metoda replicarilor independente n Simularea se executa de un anumit numar de

ori, de fiecare data bazata pe:w un sir diferit de numere aleatoare (scos de acelasi

generator, samanta diferita)generator, samanta diferita)w conditii initiale diferite, independent alese

n Fiecare executie s.n. replicareIn mod tipic, caracteristicile si comportamentul de iesire al modelului difera mai mult in faza initiala decat in finalul simularilor replicate

Colectarea statisticilor intermediareDaca avem n replici ale simularilor, m observatii intermediare pentru fiecare simulare, fie:

xij = cea de j-a observatie din replica iyi = un parametru de performanta calculat in replica i

Atunci, pentru i=1,2,...n si j=1,2,...,m:Atunci, pentru i=1,2,...n si j=1,2,...,m:

Determinarea intervalelor de incredere

Aceste valori constituie estimatori nebalansati: n (si in plus independenti) ai mediei (valorii asteptate) si

dispersiei (abaterii patratice) la m momente diferiten ai mediei si dispersiei ca masuri globale de performanta

Desi nu putem concluziona ca seturile x si valorile Desi nu putem concluziona ca seturile xij si valorile yi sunt independente, putem determina intervale de incredere aproximative pentru E(xij) si E(yi) folosind:

ExempluSe considera un sistem M/M/1Se doreste ca prin simulare sa fie estimati urmatorii parametri:n Rata de utilizare a serverului, ρn Timpul mediu petrecut de un client in sistem, ωn Timpul mediu petrecut de un client in sistem, ω

Se executa patru simulari distincte (cu 4 fluxuri diferite de numere aleatoare) pentru a genera:n Timpii intre sosirin Timpii de servire

Rezultatele simularilor pentru aceeasi durata de timp sunt date de tabelul urmator:

Rezultate si prelucrariNr.executie (n) Utilizarea server

(ρn)Timp mediu in

sistem (ωn)1 0,808 3,74

2 0,875 4,532 0,875 4,53

3 0,708 3,84

4 0,842 3,98

•Sa se estimeze utilizarea serverului cu un interval de incredere dat (de ex., 95%)

•Sa se testeze daca utilizarea serverului verifica un prag standard dat (de exemplu, daca ρ≥0.9)

Concluzii (1)Simularile nu pot lua decizii: ele doar furnizeaza informatii si date ce pot ajuta pe cei ce iau deciziiDoar dupa validarea siverificarea ei, o simulare poate constitui baza luarii unor decizii corecten Validarea ne asigura ca modelul de simulare reprezinta cu n Validarea ne asigura ca modelul de simulare reprezinta cu

acuratete sistemul realn Verificarea ne asigura ca programul de simulare (modelul

programat) reprezinta translatia corecta a modelului de simulare

Simularea nu poate fi “mai buna” decat datele pe baza carora a fost construitaSimularile nu produc date sau valori reale ale parametrilor sistem, ci doar estimatori ai lor Estimatorii sunt variabile aleatoare

Concluzii (2)Pentru a putea lua decizii valide trebuie sa stim si:n care este acuratetea estimatorilorn care sunt tipurile de estimatori ce pot fi folositi

Cele mai importante statistici (media, abaterea patratica medie s2) sunt estimatori nebalansatimedie s ) sunt estimatori nebalansatiAsigurarea preciziei reprezentarii datelor se face prin metode statistice: erori standard, intervale de incredere, replicari independente ale simularii n Determinarea intervalelor de incredere se bazeaza pe apropierea

distributiei esantionate a mediilor de distributia normala (n mare)n Estimarea acuratetei unei simulari necesita date obtinute din

cateva repetari (replici) ale simularii

Concluzii (3)In simularea unui sistem putem fi interesati:n In estimarea parametrilor de performanta doar in regim

permanent; in acest caz nu este corecta includerea comportarii tranzitorii a sistemului, ce ar produce balansarea estimatorilor

n In estimarea parametrilor de performanta incluzand si regimul tranzitoriu al sistemului, caz in care se considera influenta comportarii tranzitorii a sistemului asupra estimatorilor

Decizia de a face simularea doar pentru starea stabila sau completa se ia pe baza:n tipului de sistem modelat

n tipului de parametri ce sunt urmariti si ale caror valori se vor obtine prin simulare


Accelerarea execu iei simulărilor.


Accelerarea execu iei simulărilor. Simularea paralelă (distribuită)

SumarCaracteristici și dificultățiNivele de paralelism/ distribuţie în simulareSimularea paralelă prin interacţiunea proceselor. Partajarea domeniului spaţiu-timp între PLProblema timpului simulăriiAbordări conservative și optimisteConcluzii

ProblemaPentru a fi semnificativă statistic, o simulare de SDED trebuie să fie lungă sau repetatăSimulările secvenţiale, uneori repetate, durează aproape întotdeauna prea multProblema reducerii timpului de execuţie, se poate soluţiona pe două căi:n prin paralelizare sau distribuţia sarcinilor de

prelucrare, vizând execuţia simultană a unora dintre ele şi pe ansamblu scăderea timpului de simulare;

n prin utilizarea metodelor statistice pentru reducerea duratei sau numărului de simulări necesare.

Argumente pt. paralelizarea (distribuția) prelucrărilor

Multe sisteme constau din subsisteme "operând" în paralel → paralelismul inerent unui sistem poate fi exploatat prin simularea sa paralelăExecuţii independente ale simulării sunt necesare dpdv statistic şi acest lucru poate fi făcut în mod dpdv statistic şi acest lucru poate fi făcut în mod eficient în paralelUnele sarcini ale simulării, precum colectarea statisticilor cumulative, sunt independente şi pot avea loc în paralel în raport cu celelalte sarcini,

etc.

DificultăţiSimularea paralelă este o aplicaţie cu paralelism neregulat, cu grad mare de dependenţă între date, grad redus de similitudine a operaţiilor şi asincronism

n spre deosebire de alte aplicaţii uşor paralelizabile ce se caracterizează prin regularitate (problemele numerice caracterizează prin regularitate (problemele numerice ce implică structuri de date mari de tip matricial)

În simularea paralelă (distribuită), deşi se pot pune în evidenţă relativ uşor componente distincte ale modelului de simulare, există interacţiuni şi deci interdependenţe.

n spre deosebire de prelucrarea în ordine strictă a evenimentelor în relaţie cauzală din simularea secvenţială - o aplicaţie cu o bază formală solidă!

Exemplu Există (şi) în simularea secvenţială a SDED situaţii în care LEV conţine în primele sale poziţii mai multe evenimente având asociate momente de timp identice

Trebuie făcută însă distincţia între:a) evenimente ce au (potenţial) acelaşi timp de apariţie a) evenimente ce au (potenţial) acelaşi timp de apariţie dar se exclud reciproc din punct de vedere logic (apariţia unuia dintre ele anulează apariţia celorlalte) şi deci nu pot fi practic simultane – evenimente mutual exclusiveb) evenimente ce au acelaşi timp de apariţie, dar apariţia unuia dintre ele poate modifica (decala, întârzia) apariţia celorlalte - evenimente intercondiţionatec) evenimente ce au acelaşi timp de apariţie dar execuţii independente una de alta - evenimente concurente

Nivele de paralelism/ distribuţie în cadrul unei simulări (1)La nivelul aplicaţiei:

Copii (replici) independente ale aceluiaşi model, cu parametri de intrare diferiţi, se execută pe diferite procesoare; nu este necesară nici un fel de coordonare sau sincronizare între procesoare în timpul simulării, ceee ce permite un înalt nivel de eficienţăTotodată codul secvenţial al programului de simulare poate fi reutilizat, evitându-se astfel o paralelizare costisitoare a programului

Nu există limitări importante în scalabilitatea rezolvării unei asemenea probleme compuse din mai multe experimente de simulare (mărirea numărului de procesoare)

Totuși, este posibil ca uneori o singură execuţie a unei simulări lungi, echivalentă cu mai multe execuţii scurte, să fie preferabilă din motive legate de incapacitatea sistemului simulat de a-şi atinge rapid starea de echilibru

Nivele de paralelism/ distribuţie în cadrul unei simulări (2)La nivelul componentelor (srutinelor) programului:

Pot fi programate pentru execuţia paralelă o serie de sarcini independente în cadrul unei simulări, precum generarea numerelor aleatoare, tratarea evenimentelor, colectarea statisticilor cumulative, manipularea i/e şi a colectarea statisticilor cumulative, manipularea i/e şi a fişierelor, generarea de rapoarte grafice etc. Datorită numărului relativ mic de sarcini independente în cadrul unei simulări, scalabilitatea şi deci accelerarea sunt limitate în acest caz S-au raportat rezultate bune în privinţa eficienţei simulărilor (45-60%) atunci când numărul de procesoare rămâne mic (3-5), aceasta scăzând însă rapid cu creşterea numărului de procesoare.

Nivele de paralelism/ distribuţie în cadrul unei simulări (3)La nivelul componentelor sistemului fizic modelat:

În modelul de simulare pot fi evidenţiate sub-modele Pentru sistemele fizice cu topologie fixă, ca de exemplu reţelele de cozi, modalitatea naturală de decompoziţie constă în asignarea unui proces pentru fiecare server constă în asignarea unui proces pentru fiecare server (împreună cu coada aferentă), modelând deplasarea clienţilor în reţea prin mesaje între proceseÎn simularea unui sistem cu topologie dinamică, ca de ex. un joc de biliard sau un scenariu militar, procesele pot reprezenta componentele ce interacţionează, iar mesajele între procese chiar aceste interacţiuni

Nivele de paralelism/ distribuţie în cadrul unei simulări (3)La nivelul componentelor sistemului fizic (cont.):

Pot fi programate pentru execuţia paralelă o serie de sarcini independente în cadrul unei simulări, precum generarea numerelor aleatoare, tratarea evenimentelor, colectarea statisticilor cumulative, manipularea i/e şi a colectarea statisticilor cumulative, manipularea i/e şi a fişierelor, generarea de rapoarte grafice etc. Datorită numărului relativ mic de sarcini independente în cadrul unei simulări, scalabilitatea şi deci accelerarea sunt limitate în acest caz S-au raportat rezultate bune în privinţa eficienţei simulărilor (45-60%) atunci când numărul de procesoare rămâne mic (3-5), aceasta scăzând însă rapid cu creşterea numărului de procesoare.

Nivele de paralelism/ distribuţie în cadrul unei simulări (4)La nivelul evenimentelor în cazul menţinerii LEV centralizate:

Gestionarea LEV este asigurată de către un procesor master, accelerarea poate fi atinsă prin distribuirea evenimentelor simultane către o mulţime de procesoare slave în vederea execuţiei concurenteslave în vederea execuţiei concurenteSarcina păstrării consistenţei în structura evenimentelor revine procesorului master ce trebuie să prevină execuţia distribuită a evenimentelor simultane (mutual exclusive sau intercondiţionate) cu potenţial efect de violare a cauzalităţii în LEVAceastă posibilitate este adecvată pentru execuţia pe o maşină multiprocesor cu memorie partajată unde LEV poate fi implementată printr-o structură de date comună

Nivele de paralelism/ distribuţie în cadrul unei simulări (5)La nivelul evenimentelor în cazul menţinerii descentralizate

a LEV:

se menţin mai multe sub-liste cf. unei împărţiri pe grupe de evenimente (pt. asignări regulate a evenimentelor la procesoare, fiind posibilă şi o asignare nestructurată)procesoare, fiind posibilă şi o asignare nestructurată)este de aşteptat obţinerea unor viteze de simulare mult mai mari datorită faptului că se permite execuţia concurentă a evenimentelor cu timpii asociaţi diferiţischemele de implementare a paralelismului /distribuţiei la acest nivel necesită protocoale pentru sincronizare locală, ce pot creşte costurile de comunicaţie, în funcţie de dispersia evenimentelor în spaţiu (între procesoare) şi timp în cadrul modelului de simulare

Simularea paralelă/distribuită prin interacţiunea proceselor

Poate fi privită ca o partajare a domeniului spaţiu - timp între procesele logice

Modalităţi de simulare paralelă: a) spaţială; b) temporală

var. var. var.

stare

timp

var. stare

timp

Principii generale (1)Este necesară mai întâi identificarea şi implementarea unui set de procese logice (PL), capabile să trateze în paralel apariţia diferitelor evenimenteTrebuie creat și un sistem de comunicaţie (SC), care să asigure PL posibilitatea de a schimba date locale, dar şi asigure PL posibilitatea de a schimba date locale, dar şi de a-şi sincroniza activităţile localeFiecărui PLi i se alocă o regiune Ri a domeniului spaţiu -timp, ca sub-model sau parte a modelului de simulare; în cadrul regiunii Ri, o implementare a PLi operează secvenţial:

n planifică şi execută evenimente localen generează evenimente locale sau pentru alte PLn avansează un ceas de simulare local etc.

Principii generale (2)Fiecare PLi poate avea acces doar la un subset partiţionat static de variabile de stare Si ⊂ S, în general disjunct faţă de variabilele de stare asignate altor PL;În fiecare PLi pot fi procesate două tipuri de evenimente:n interne, ce pot afecta cauzal doar Si ;n interne, ce pot afecta cauzal doar Si ;n externe, ce pot afecta cauzal şi alte subseturi Sj ⊂ S (i≠j);

O interfaţă de comunicare (IC) ataşată unui PL, compusă din canale de intrare/ieşire ale unui PL, are rol de urmărire a efectelor evenimentelor, atât externe generate asupra altora, cât şi externe generate de alte PL asupra luiMecanismul de bază al IC este trimiterea, primirea şi prelucrarea de mesaje eveniment având înglobat un marcaj desemnând timpul local de emitere (timestamp).

Partajarea domeniului spaţiu-timp între PLi

Spaţial: modelul este împărţit între procesoare, iar fiecare dintre acestea avansează simultan în timp cu celelalte în simularea unei componente a modelului stocată localn Problema sincronizării: constrângerea de cauzalitate locală

impune ca procesarea evenimentelor de către un PL să se facă în ordinea crescătoare a timpilor asociaţi fiecărui eveniment în PL

Temporal: intervalul de timp al simulării e împărţit în subintervale, fiecare dintre procesoare realizând simularea într-un subinterval a întregului model

Timpul (virtual al) simulării

Simularea sincronă implementează timpul virtual printr-un ceas de timp global: n fie reprezentat explicit, central, printr-o structură de date n fie implicit într-o procedură ce se execută în paşi

Caracteristic este faptul că toate PL, la fiecare moment Caracteristic este faptul că toate PL, la fiecare moment de timp real, se conduc după valori de timp identice Simularea asincronă relaxează total restricţia de sincronizare: n fiecare PL se conduce după valori proprii ale ceasului de

timp virtual (local) n deci la un moment dat al timpului real, timpul local virtual

în diferitele PL este diferit

Abordări asincrone (1)Conservativă : execuţia unui eveniment în fiecare PL are loc d.d. se respectă strict regula de cauzalitate locală De ex., un criteriu suficient, nu şi necesar, de procesare a evenimentului iminent într-un PL, este ca valoarea ceasului de simulare asociat PL să fie mai mică decât toţi ceasului de simulare asociat PL să fie mai mică decât toţi timpii asociaţi celorlalte PL Metodele conservative au caracteristic faptul că evită ab initio orice eroare datorată nerespectării cauzalităţii Un eveniment E dintr-un PL este tratat numai dacă există certitudinea că orice eveniment viitor Ev, generat de PL respectiv sau primit printr-un canal de intrare de la alt PL, nu va anula corectitudinea rezultatelor obţinute prin tratarea evenimentului E

Abordări asincrone (2)Optimistă: un PL poate procesa evenimentul iminent din LEV locală, fără a se asigura de respectarea strictă a constrângerii de cauzalitate locală În acelaşi timp, un istoric al simulării este păstratDacă se constată ulterior încălcarea constrângerii de Dacă se constată ulterior încălcarea constrângerii de cauzalitate locală (de exemplu, PL respectiv primeşte ca urmare a activităţii altor procese un eveniment cu timpul virtual asociat mai mic decât ceasul local al simulării), PL trebuie să poată reveni şi reface în mod corect simularea din punctul în care a apărut problema

Comparaţie între protocoaleleconservative şi optimiste (1)

Cel mai mare dezavantaj al simulărilor conservative este că nu exploatează complet paralelismul sistemului: n dacă există cea mai mică posibilitate ca un eveniment E1 să

afecteze un alt eveniment E2, simularea conservativă este practic o execuţie cvasisecvenţialăo abordare conservativă se dovedeşte a fi excesiv de defetistă, n o abordare conservativă se dovedeşte a fi excesiv de defetistă, prin plasarea întotdeauna în cea mai nefavorabilă situaţie.

O problemă este și întoarcerea, către metodele de simulare condusă de timp, prin avansul ceasurilor de timp locale în incremenţi mici (pt.evitarea interblocajelor) Pentru a determina dacă un mesaj poate fi tratat de o manieră sigură, metodele conservative se bazează profund pe structura sistemului de simulat (dacă există mai mult de o singură intrare viteza simulării scade rapid)

Comparaţie între protocoaleleconservative şi optimiste (2)

În cazul aplicării mecanismului optimist (time warp), ptr. cazul anumitor sisteme, timpul unei simulări poate fi consumat mai mult în efectuarea de calcule incorecte şi reveniri (roll-backs) neproductive Necesitatea salvării periodice a stării sistemului pentru a Necesitatea salvării periodice a stării sistemului pentru a putea face recuperarea unei erori, cere şi timp şi mai ales spaţiu de memorie, iar această informaţie de stare nu este întotdeauna utilizată Implementarea sa este mai complicată, algoritmii fiind şi foarte dificil de validat Chiar o implementare corectă poate avea performanţe foarte slabe dacă programarea nu s-a făcut suficient de atent ţinând cont de anumite caracteristici ale sistemului

Criteriu Metode conservative Metode optimiste

Principiuoperaţional.

Regulile de cauzalitate locală sunt strict respectate;sunt tratate doar evenimentele sigure.

Este posibilă violarea temporară a regulilor de cauzalitate locală, dar la detectarea unei erori de acest fel se revine.

Spaţiul stărilor.

Utilizarea tuturor modelelor conservative este compatibilă cu modele de simulare având spaţii

Sunt eficiente atunci când, în model, spaţiul stărilor şi necesa- rul de spaţiu de modele de simulare având spaţii

de stări arbitrar de mari.necesa- rul de spaţiu de memorie per stare sunt mici.

Consumul dememorie.

Conservativ, consecinţă a metodei aplicate, dar nu optimal [Jef85].

Excesiv, datorită overhead-ului necesar pentru salvarea stărilor. Sunt necesare scheme complexe de administrare a memoriei pt.a preveni epuizarea memoriei.

Reprezentarea timpului

Se execută implicit în TGV; nu sunt necesare calcule explicite legate de TGV.

Se bazează pe calculul explicit şi dificil (fără suport hardware) al TGV.

Exploatareparalelism

Paralelismul sistemului nu este bine exploatat; dacă apar rar constrângeri cauzale, protocolul este prea pesimist.

Paralelismul sistemului este bine exploatat; dacă constrângerile cauzale apar rar, protocolul aduce câştiguri de timp

Sincronizarea.

Mecanismul de sincronizare este interblocant; consecinţe:

Mecanismul sincronizării este recuperatoriu; deci. interblocant; consecinţe:

-prevenirea interblocajelor bazată pe mesaje nule adaugă overhead de comunicare;-detectarea/elim.interblocajelor pp. de obicei un proces central;-programatorul trebuie să fie familiarizat cu mecanismele de sincronizare pentru a obţine performanţe de vârf.

este recuperatoriu; deci-anulările introduc de asemenea un overhead de comunicare;-programatorul nu trebuie să fie familiarizat cu mecanismele de sincronizare; -recuperarea în lanţ degradează puternic performanţele.

Comunicaţia.

În general intensă. E necesară sosirea şi procesarea în ordine cronologică a mesajelor, stricta separare a canalelor de intrare.

Nu foarte intensă. Mesajele pot veni în orice ordine, dar trebuie executate în ordine cronologică; se poate menţine o singură coadă de intrare; nu e nevoie ca mesajele să fie primite în ordinea în care au fost trimise.care au fost trimise.

Configurare Majoritatea tehnicilor necesită interconectarea statică a proceselor.

Admit configurarea dinamică a proceselor.

Lookahead-prospectare

Necesar pentru a face operabil protocolul, esenţial pentru performanţă.

Nu este esenţial, dar poate fi utilizat pentru optimizarea performanţelor.

Balansareaîncărcărilor.

Bună, cât timp toate canalele statice sunt utilizate egal; dis-persia mare a evenimentelor în timp şi spaţiu nu deranjează.

Bună, cât timp progresia TLV este apropiată între PL;dispersia mare a evenimentelor în timp şi spaţiu degradează performanţa.

Agresivitate. Redusă. Ridicată.

Risc. Nu există. Potenţial ridicat, dar poate fi redus prin aplicarea fi redus prin aplicarea unor tehnici specifice [Lub89].

Overhead (sarcină suplimentară)

Introdus mai ales de mecanismele de detectare şi recuperare a deadlock-ului.

Introdus mai ales de mecanismele de salvare a stării şi rollback.

Granularitate Poate fi mare (fină). Mărirea ei poate conduce la mărirea raportului overhead/calcul

Suport hardware.

Nu este obligatoriu. De dorit, nu atât pentru calcule, cât pentru salvarea stării/ detecţia erorilor (“rollback chip”).

Implementare.

Uşor de implementat; structuri de control şi de date simple.

Dificil de implementat şi depanat; structuri de date simple,dar manipulări şi structuri de control complexe. E esenţială complexe. E esenţială organizarea memoriei. Se pot face optimizări ce influenţează performanţa.

Preprocesarea.

Este necesară pentru a evita creşterea overheadului de comunicaţie.

Nu este necesară, procesele rulează relativ independent, comunică şi se sincronizează rar.

Detecţia erorilor şi recuperarea lor.

Erori puţine şi detectabile. Erori frecvente, dificil de detectat (pot fi şterse prin rollback) fără ajutorul suportului hardware pentru întreruperi şi protecţia memoriei.

Depanarea. Relativ uşor de realizat. Consumatoare de timp şi dificilă, pentru că implică analiza detaliată a unor scenarii complexe de scenarii complexe de rollback.

Robusteţe. Schimbări minore ale aplicaţiei pot avea efecte catastrofice asupra performanţei.

Comportarea este stabilă; automat, sistemele TW tind să încetinească propagarea erorilor, prin acordarea de priorităţi mai mari calculelor ce implică evenimente cu timp mai mic.

ConcluziiProblema “paralelizării” simulărilor nu este deloc o problemă trivială Indiferent ce componentă a simulatorului considerăm, descompunerea şi exec. în paralel trebuie analizată atentn pe de o parte sub aspectul eliminării unor probleme n pe de o parte sub aspectul eliminării unor probleme

de inconsistenţă/ greşeli de simulare n pe de altă parte în vederea obţinerii unei accelerări

semnificative faţă de tratarea secvenţială

Date post:	31-Jan-2016
Category:	Documents
Upload:	smarandache-gabi
View:	289 times
Download:	4 times

All Coursesas

Documents