Curs Mssed

8/9/2019 Curs Mssed

http://slidepdf.com/reader/full/curs-mssed 1/83

8/9/2019 Curs Mssed


CUPRINS

Capitolul I. Conceptul de sistem cu evenimente discrete

Breviar...................................................................................................5

Problemă rezolvată................................................................................7

Probleme propuse................................................................................11

Capitolul II. Lim!"e #orm!le $i !utom!te

Breviar.................................................................................................13Probleme rezolvate..............................................................................2


Capitolul III. Re%ele &etri

Breviar.................................................................................................!0

Probleme rezolvate..............................................................................50


Biblio"ra#ie...................................................................................................$

http://opt/scribd/conversion/tmp/scratch6127/

http://opt/scribd/conversion/tmp/scratch6127/

8/9/2019 Curs Mssed


Conceptul de Sistem cu Evenimente Discrete 5

C%PI&'(U( IConceptul de Sistem cu Evenimente 'iscrete

(RE)IAR

U) sistem din!mic cu evenimente discrete *S+,+- este u) sistemi)ami/ /ara/terizat pri)tru) spaiu is/ret al stărilor i pri) traie/torii estare /o)ti)ue pe poriu)i. oi#i/ările e stare se )umes/ tra)ziii i survi)/a urmare a apariiei eve)ime)telor4 ) mo asi)/ro).

Evenimentele au urată )ulă. 6) a#ară e /azul ) /are apar altespe/i#i/aii4 se /o)sieră /ă la u) mome)t at are lo/ u) si)"ur eve)ime)t.U) eve)ime)t poate #i ie)ti#i/at /a

• a/iu)e spe/i#i/ă *e8 la)sare operaie-9

• moi#i/are )e/o)trolabilă ) /arul u)ui pro/es *e8 e#e/tarea u)eiresurse i)tru) motiv oare/are-9

• rezultatul satis#a/erii simulta)e a mai multor /o)iii.

,ve)ime)tele su)t e re"ulă eti/:etate. ulimea eve)ime)telorle"ate e #u)/io)area u)ui pro/es oare/are etermi)ă ast#el eleme)tele u)ui

8/9/2019 Curs Mssed


Modelarea şi analiza SDED – 103 probleme

!l#!et *mulime #i)ită e simboluri- Σ ast#el )/;t ele i păstreazăsem)i#i/aia e #e)ome) /alitativ epe)e)t e spe/i#i/ul apli/aiei.

%st#el4 i) pu)/t e veere #ormal4 u) sistem /u eve)ime)te is/retese e#i)ete ast#el

'e#ini%ie U) S,+ este u) sistem /are evoluează "e)er;) spo)ta)eve)ime)te i poate #i e#i)it /a u) <uaruplu

-444* 0qQG δ Σ=

u)e

Q = mulimea stărilor sistemului9

Σ = al#abetul eve)ime)telor pe /are le poate "e)era sistemul9

q0 = starea i)iială9

δ = #u)/ia e tra)ziie e stare4 e#i)ită ast#el9

δ > × Σ→ Σ .

Oserv!%ii

1. 6) #u)/ie e ime)siu)ea lui Q4 S,+ se mpart ) sisteme /u)umăr #i)it e stări i respe/tiv sisteme /u )umăr i)#i)it e stări9i)i#ere)t )să e ime)siu)e4 Q este )umărabilă9

2. ?u)/ia e tra)ziie δ )u este e#i)ită )toteau)a pe)tru toate pere/:ile i) *Q × Σ -4 /eea /e )seam)ă /ă )u este obli"atoriu /ai) #ie/are stare a sistemului să poată #i "e)erate toateeve)ime)tele i) Σ 9

3. %l#abetul Σ are )toteau)a u) )umăr #i)it e eve)ime)te.

6) /o)/luzie4 moelarea u)ui pro/es real /a S,+ i)/lue4 i)i#ere)t e

#ormalismul utilizat4 următoarele etape1. +e#i)irea variabilelor e stare4 respe/tiv a #ormatului eleme)telor

q ∈ Q9 a/ă mulimea > este #i)ită4 atu)/i se poate e#i)i ))tre"ime pri) e)umerare9

2. Stabilirea stării i)iiale q0 ∈ >9

3. +e#i)irea tuturor eve)ime)telor i) Σ /a a/iu)i /are moi#i/ăvaloarea a /el pui) o variabilă e stare9

8/9/2019 Curs Mssed



!. +e#i)irea #u)/iei e tra)ziie δ 4 /eea /e revi)e e #apt laes/rierea e8pli/ită a moelului.

6) #u)/ie e /omple8itatea pro/esului moelat4 etapele 3 i ! pot #i/ompletate simulta).

6) #u)/ie e moul ) /are tratează timpul4 moelele S,+ pot #impărite ) următoarele /ate"orii

- moele auto)ome @ utilizate pe)tru a)aliza /alitativă a #u)/io)ării

sistemelor9 ) /azul a/estor moele )u este luată ) /o)sieraree/;t ori)ea ) /are apar eve)ime)tele i )u i)tervalul e timpi)tre apariia a ouă eve)ime)te su//esive9

- moele temporizate @ utilizate at;t pe)tru a)aliza /alitativă /;t i4mai ales pe)tru a)aliza per#orma)elor sistemelor @ i)tervalul etimp i)tre apariiile a ouă eve)ime)te su//esive este spe/i#i/at )mo etermi)ist9

- moele sto/asti/e sau probabilisti/e @ ) /are su//esiu)eaeve)ime)telor este ată pri) i)termeiul u)or istribuii e

probabilitate.

&rolem* re+olv!t*

,- Să se moeleze /a S,+ pro/esul /o)st;) i)tru) server i o /oaăe ateptare. Capa/itatea serverului este e u) /lie)t la u) mome)tat4 iar /apa/itatea /ozii este presupusă a #i )elimitată. %tu)/i /;) u)/lie)t i)tră ) sistem4 el i)tră ) /oaa e ateptare. +e )ată /eserverul este liber4 el preia /;te u) /lie)t i) /oaa e ateptare4 )ori)ea sosirii a/estora. I)trarea /lie)ilor ) sistem /a i urataservi/iului su)t aleatoare. Se presupu)e /ă urata e s/:imbare a/lie)tului servit ) /azul ) /are /oaa este )eviă este)esem)i#i/ativă. I)iial4 serverul este liber.

8/9/2019 Curs Mssed


$ Modelarea şi analiza SDED – 103 probleme

ezolvare!

Pro/esul propus va #i moelat /a S,+ auto)om4 )tru/;t )u e8ista )i/i oi)i/aie temporală.

,- 'e#inire! . ) mo evie)t4 sistemul va avea u) )umăr i)#i)it estări4 eoare/e /apa/itatea /ozii e ateptare )u este limitată. 6)a/est /az4 se va e#i)i stru/tura stărilor sistemului pri) spe/i#i/areavariabilelor e stare4 i a)ume s @ starea serverului i l @ lu)"imea/ozii e ateptare.

6)tru/;t serverul )u poate #i e/;t liber sau o/upat4 se poate /o)siera/a s ∈ A04 14 ast#el s = 0 sem)i#i/a server liber4 iar s = 1 @ server o/upat.

> = A* s" l - s ∈ A04 14 l ∈

/-'e#inire! st*rii ini%i!le q0 = *04 0- @ server liber i /oaa eateptare viă.

0-'e#inire! !l#!etului de evenimente

%l#abetul e eve)ime)te va /o)i)e ouă eleme)te4 i a)ume

e1 @ i)trarea u)ui /lie)t ) sistem9

e2 @ ieirea u)ui /lie)t i) sistem.

1- 'e#inire! #unc%iei de tr!n+i%ie2

=+

=+=

0-41*

1-14*--44** 1

sdacal s

sdacal sel sδ

respe/tiv i)trarea u)ui /lie)t ) sistem i)/reme)tează lu)"imea /ozii4 a/ăla mome)tul i)trării serverul era o/upat sau tre/e serverul ) starea eo/upatD4 a/ă era liber

=−

≥−=

0-41*

1-14*

--44** 2 l dacal s

l dacal s

el sδ

respe/tiv ieirea u)ui /lie)t i) sistem e/reme)tează lu)"imea /ozii4 a/ăa/easta era )eviă sau eliberează serverul4 ) /az /o)trar.

oelul auto)om poate #i moi#i/at ) veerea a)alizei per#orma)elorsistemului ) /azul ) /are i)#ormaia espre pro/es este /ompletată /ui)#ormaii temporale.

8/9/2019 Curs Mssed


Conceptul de Sistem cu Evenimente Discrete E

%/este i)#ormaii vor )soi /ele ouă tipuri e eve)ime)te stabilitea)terior4 ) ma)iera următoare se presupu) /u)os/ute uratele e timpi)tre ouă sosiri su//esive i e aseme)ea timpul e servire a#ere)t #ie/ărui/lie)t.

#1 = 0.!9 #2 = 1.29 #3 = 0.59 #! = 0.79 #5 = 0.29 # = 0.9 #7 = 0.29 #$ = 1.!9F

S 1 = 2.09 S 2 = 0.79 S 3 = 0.29 S ! = 1.19 S 5 = 3.79 S =0.9F

6) /o)#ormitate /u atele e mai sus4 evoluia )umărului e /lie)i i) /oaae ateptare este /ea preze)tată ) #i"ura următoare

0 1 2 3 ! 5 7 $ E

e1 = 0.!

e$ = 1.

e3 = 2.1

e% = 2.!

e& = 3.3

e' = 3.1

e( = !.0

e) = 3.$

e13 = $. = *+&,

e1$ = 7.2

e11 = 5.$

e10 = 5.

e- = !.E

1

2

3

Q+t,

t

Sosiri

Ple/ări

8/9/2019 Curs Mssed


10 Modelarea şi analiza SDED – 103 probleme

'/uparea serverului este /ea preze)tată ) #i"ura e mai Gos. +upă /um se poate observa4 serverul pro/esează /lie)i o urată e timp e 747 u)ităi etimp i) totalul e $4 u)ităi e timp. %/easta reprezi)tă o o/upare e$E453H.

0 1 2 3 ! 5 7 $ E

e1 = 0.!

e$ = 1.

e3 = 2.1

e% = 2.!

e& = 3.3

e' = 3.1

e( = !.0

e) = 3.$

e13 = $. = *+&,

e1$ = 7.2

e11 = 5.$

e10 = 5.

e- = !.E

1

.+t ,

t

Sosiri

Ple/ări

8/9/2019 Curs Mssed



&roleme propuse

/- ?ie u) sistem e /al/ul /u ouă pro/esoare P1 i P24 /are lu/rează ) paralel. oul ) /are tasurile soses/ spre pro/esare poate #i es/ris) raport /u mome)tul e timp is/ret al apariiei lor pri) i)termeiulu)ei #u)/ii bi)are a*t - 4 t ∈ 4 ast#el a+t,=1 a/ă la mome)tul tsosete u) tas i a+t, = 0 ) /az /o)trar. Se presupu)e /ă )u pot sosisimulta) ouă sau mai multe tasuri.

Presupu)em /ă pe)tru u) i)terval e timp t = 0414..410 #u)/ia a+t, arevalorile A141414041404141404041.

(a sosirea u)ui tas sistemul e /al/ul apli/ă următoarea re"ulă ealo/are a a/estuia /ele ouă pro/esoare lu/rează alter)ativ4 primul#ii) P1. Se presupu)e /ă a/ă u) tas este trimis la Pi4 i=142 i a/el

pro/esor este o/upat4 atu)/i tasul va atepta )tro /oaă e/apa/itate i)#i)ită. +urata e pro/esare a u)ui tas la pro/esorul P1

alter)ează )tre ! u)ităi e timp i o u)itate e timp *)/ep;) /u !-4iar urata e pro/esare pe P2 este e 2 u)ităi e timp. ?ie /*t - )umărultotal e /lie)i /are părăses/ sistemul la mome)tul t 4 iar 1*t - 4 2*t -

lu)"imile /ozilor e ateptare la pro/esoarele P1 respe/tiv P2. Se /erea- ese)ai o ia"rama e timp t 0414...4 10 i)i/;) sosirile i

ple/ările. I)iial 1*0- = 2*0- = /*0- =09

b- /o)struii u) tabel /u valorile 1*t -4 2*t,4 i /*t - pe)tru toit = 04 14 F4109

/- presupu)em /ă se lu/rează ) timp /o)ti)uu. Sosirile au lo/ lamome)tele 0419 0479 2429 5429 E4E. +uratele e pro/esare pe P1

alter)ează )tre !42 i 141 iar pe P2 este #i8at la 2 u)ităi e timp. ?ieu) moel /o)us e eve)ime)te /u setul e eve)ime)te E = Aa4 d 14d 24 u)e aD sem)i#i/a sosirea iar d iD ple/area e pe pro/esorulPi. Co)struii u) tabel /u valorile 1* -4 2* - 4 /* -4 t * - u)e 1* -4

2* - su)t lu)"imile /ozilor e ateptare 9 /* - este )umărul/umulativ e ple/ări upă eve)ime)tul . * = 1424F-4 iar t * -mome)tul e timp la /are apare eve)ime)tul . +a/ă ouăeve)ime)te apar simulta) presupu)em /ă o ple/are apare)toteau)a )ai)tea u)ei sosiri. Comparai )umărul e a/tualizări) a/est moel /u u) moel ) timp /u ea)tioa)e la 041 u)ităi etimp.

8/9/2019 Curs Mssed



0- %/eeai problemă /u următoarele re"uli e alo/are a tasurilor *a/ăouă eve)ime)te apar simulta) se /o)sieră /ă ple/area este prioritară#aă e sosire-

a- trimite tasul pro/esorului P1 /;t timp lu)"imea /ozii este /el mult24 alt#el trimite /ătre pro/esorul P2.

b- trimite tasul /ătre pro/esorul /u /oaa /ea mai s/urtă. 6) /az ee"alitate trimite /ătre pro/esorul P2.

1- U) pro/es e #abri/aie simplu este /ompus i) ouă mai)i 1 i 2

i u) robot /are es/ar/ă piesele prelu/rate e pe 1 i le tra)sportă pe2. Nu e8istă sto/uri la /ele ouă mai)i 4 e/i a/ă o piesă este#ur)izată lui 1 ) timp /e a/easta #u)/io)ează atu)/i piesa estereGe/tată. +a/ă robotul tra)sportă piesa lui 2 ) timp /e a/easta esteo/upată atu)/i el ateaptă a/olo p;)ă /;) 2 se eliberează. Se/o)sieră /ă timpul e reve)ire a robotului e la mai)a 2 *upă /e aepus piesa- ) poziia i)iiala este i#erit e zero 4 e/i 1 poate #i#orată o/azio)al să păstreze piesa prelu/rată *i să )u a//epte altele-

p;)ă /;) robotul evi)e ispo)ibil. ?ie 1 i 2 stările lui 1

respe/tiv 24 iar 3 starea robotului. Presupu)em /ă timpii e pro/esare pe 1 i 2 su)t 045 pe 1 i 145 pe 24 iar timpii etra)sport e la 1 la 2 e 042 se/ iar e la 2 ) poziia i)iiala *1-e 041 se/. Presupu)em /ă piesele soses/ la 1 upă următoareas/:emă

041 047 141 14 245 se/

a- ie)ti#i/ai toate valorile posibile pe)tru 1 4 2 i 39

b- e#i)ii u) set mi)imal e eve)ime)te E pe)tru a/est sistem9

/- pe)tru i)tervalul J0404 043K /o)struii u) tabel /u valorile lui 1* -4 2* -4 3* - i t * - u)e 14 24 3 su)t stările mai)ilor i robotuluiupă al lea eve)ime)t iar t * - este mome)tul apariiei aleve)ime)tului . +a/ă ouă eve)ime)te apar simulta) /o)sierăm/ă termi)area pro/esării apare )toteau)a )ai)tea sosirii u)ei )oi

piese9

- ie)ti#i/ai toate stările pe)tru /are 1 este #orată să atepte p;)ă/;) braul robotului preia piesa #i)ită *prelu/rată- *e pe 1-.

8/9/2019 Curs Mssed


2imbae 4ormale şi #utomate 13

C%PI&'(U( IILim!"e 3orm!le $i Autom!te

(RE)IAR

'e#ini%ii

U) al5abet este o mulime #i)ită e simboluri.

U) cuv6nt este o se/ve)ă #i)ită e simboluri ale a/eluiai al#abet.

U) limba este o mulime e /uvi)te /u simboluri ale a/eluiaial#abet.

Not!%ii2

(u)"imea u)ui /uv;)t4 7 reprezi)tă )umărul e simboluri /are/ompu) /uv;)tul.

Cuv;)tul vi ε */orespu)e eve)ime)tului )ul sau4 mai pre/is4u)ui eve)ime)t )eobservabil-.

(imbaG vi φ *reprezi)tă limbaGul #ără )i/i u) /uv;)t-.

8/9/2019 Curs Mssed


1! Modelarea şi analiza SDED – 103 probleme

,voluia ori/ărui S,+ poate #i repreze)tată /omplet pri)tro pere/:e elimbaGe *(4 (m- /u următoarele proprietăi

( i (m su)t e#i)ite pe al#abetul e i)trare9

( @ reprezi)tă toate evoluiile posibile ale S,+ i se )umetelim!" 4ener!t5

(m @ reprezi)tă toate evoluiile orite ale S,+ i se )umete lim!"m!rc!t5

(m ⊆ (.Oper!%ii pe lim!"e

?ie (4 (14 (24 limbaGe e#i)ite peste al#abetul Σ . Cele mai utilizateoperaii pe limbaGe su)t

• euniunea

( = (1 ∪ (2 =A vL v ∈ (1 sau *i- v ∈ (2

• Concatenarea

( = (1⋅ (2 = Av L v = s⋅ t u)e s∈ (1 i t ∈ (2

• 8nc9iderea iterativ: *sau operatorul ;leene-

( = (M

(M =∞

=0i

(i 4 (1 = ( ⋅ (4 (0 = AO

Oserv!%ie2 'peraia e )/:iere iterativă se poate e8ti)e i la u)al#abet */o)sierat /a u) limbaG /u /uvi)te e lu)"ime 1- Σ Σ M

reprezi)tă mulimea tuturor /uvi)telor /are pot #i #ormate /usimbolurile lui Σ .

• 8nc9iderea pre5iat:

pr *(- = 2 = A s ∈ Σ M L ∃ t ∈( a.. s⋅ 7 = t

• <ntersec=ia

( = (1 ∩ (2 = Av L v ∈ (1 i v ∈ (2

• >roiec=ia lui ( peste o submulime e eve)ime)te Σ ⊆ Σ

8/9/2019 Curs Mssed



(↑Σ = A s↑Σ L s ∈ ( /u

Σ∈

=Σ↑Σ∈∀alt5el

daca

4

44-*

ε

σ σ

σ σ

Σ↑

Σ∈Σ↑=Σ↑⋅Σ∈Σ∈∀

alt5el s

daca s s s

4

4-*44-*

σ σ

σ σ

&ropriet!te import!nt*2 (imbaGul "e)erat e /ătre u) S,+ este)toteau)a e"al /u )/:ierea sa pre#i8ata *( = pr*(--.

'e#ini%ie

?ie Σ u) al#abet9 atu)/i o e6presie re4ul!t* *,R- se e#i)ete ast#el

• ε este o ,R /are moelează limbaGul /e /o)i)e oar eve)ime)tul)ul9

• φ este o ,R /are moelează limbaGul vi9

• *∀- a ∈ Σ 4 a este o ,R /are moelează limbaGul repreze)tat eAa

• a/ă a4 b su)t ,R4 atu)/i *a⋅ b-4 *a b-4 aM4 bM su)t ,R &ropriet!te2 +a/ă α este ,R4 atu)/i α M = ε α ⋅ α M.

'e#ini%ie2 U) automat 5init determinist %?+ se e#i)ete /a u) <ui)tuplu

G = *Q4 Σ 4 q0 4 δ 4 Qm-

u)e

Q = mulimea *#i)ită- a stărilor9

Σ = al#abetul e eve)ime)te4


δ = #u)/ia e tra)ziie 9 δ Q × Σ Q"

*∀- q ∈ Q4 a∈Σ i 7 ∈Σ M su)t satis#ă/ute următoarele relaii

a- δ *q4 ε - = q

b- δ *q4 7a- = δ *δ *q4 7-4 a- = qQ ∈Q

8/9/2019 Curs Mssed



Qm = mulimea stărilor mar/ate.

Not!%ii2

stare5

starea i)iială *u)i/a -9

stare mar/ată9

atra)ziia sub eve)ime)tul a.

Oserv!%ii 2

1- +a/ă Qm ≠ φ 4 atu)/i automatul se )umete acceptor .

2- +ouă automate 1 si 2 su)t ec7iv!lente a/ă limbaGele lor"e)erate i respe/tiv /ele mar/ate4 su)t e"ale1 e/:ivale)t /u 2 ⇔ 2*1- = 2*2- $i 2m*1- = 2m*2-

'e#ini%ie 2 U) automat 5init nedeterminist %?N se e#i)ete /a u) <ui)tuplu

G = *Q4 Σ 4 δ 4 q04 Qm-

u)e si)"ura i#ere)ă #aă e %?+ este ată e moul e e#i)ire al #u)/ieie tra)ziie4 respe/tiv

δ Q × Σ 2> /u 2> mulimea tuturor submulimilor lui Q?

i

δ *q4 ε - = qδ *q4 a- = A pL p∈Q4 /eea /e )seam)ă /ă4 i) starea q4 pri)

eve)ime)tul a4 se poate aGu)"e )tro mulime e stări *evoluia )ueste u)i/ă-.

U) /uv;)t e i)trare 7 ∈∑M este a//eptat e u) %?N a/ă mă/ar u)a i)treevoluiile δ *q04 7- ∈ Qm.

8/9/2019 Curs Mssed



Pe)tru ori/e %?N se poate /o)strui u) %?+ e/:ivale)t Q4 )umitobservatorul lui .

Q = *>Q " Σ " δ @" <0 " > 4 @,4

'e#ini%ie 2 U) #4A cu tranzi=ii ε *%?Nε - se e#i)ete /a u) <ui)tupluG!

G = *Q4 Σ ∪A ε 4 q0 4 δ 4 Qm-.

+i#ere)a #aă e /lasele e automate preze)tate a)terior este ată e moul

e e#i)ire al lui δ ?Pe)tru a e#i)i #u)/ia e tra)ziie a %?Nε se i)trou/e )oiu)ea enc9idere ε a unei st:ri < a automatului *ε M *q-- 4 ast#el

ε M *q- = δ *q4 ε M- =AqQ LqQ ∈> mulimea tuturor stărilor ) /arese aGu)"e por)i) i) q sub o se/ve)ă e ε .

%tu)/i #u)/ia e tra)ziie a u)ui %?Nε se e#i)ete ast#el

δ Q × *Σ ∪A ε - 2> 9

δ *q4 ε - =M

Gε *q-

Pe)tru u) /uv;)t e i)trare s ∈ *Σ ∪A ε -M si σ∈ Σ 4

( )( )( )

sqq qq

GG q sq sq4T 4TTT

MMU-K-44**J-4*

δ σ δ

ε σ δ δ ε σ δ

∈ ∈

==

Ca i ) /azul %?N4 pe)tru ori/e %?Nε se poate /o)strui u) observatoretermi)ist.

Al4oritmul de construc%ie ! unui oserv!tor determinist G os pentru un

!utom!t nedeterminist 4ener!l G nd

Co)sier;) /ă automatul etermi)ist este e#i)it /a

obs = *>obs4 Σ 4 δ obs4 <04obs4 >m4obs-

iar automatul )eetermi)ist /a

) = *>)4 Σ )4 δ )4 <04)4 >m4)-4

8/9/2019 Curs Mssed


1$ Modelarea şi analiza SDED – 103 probleme

) /are

∪Σ

Σ=Σ

O%?Nu)avema/a 4OA

%?Nu)avema/a 4nd

Vi #olosi) *pe)tru a putea rezolva /u al"oritmul /o)stru/ia observatoruluiat;t pe)tru %?N /;t i pe)tru %?Nε - următoarea #u)/ie

UR 2>) × Σ )→ 2>)

Cu e#i)iia

=O%?Nestea/a8-4*O

%?Nestea/a 84UR*8-

)

M

)

al"oritmul e /o)stru/ie a observatorului pe)tru u) automat )eetermi)isteste următorul

Pas 1 <04obs = UR*<04)- i se i)trou/e <04obs ) lista stărilor )ee8plorate*(SN-.

Pas 2 %t;ta timp /;t e8istă stări ) (SN

Pas 2.1 ,8tra"ere a u)ei stări q i) (SN.

Pas 2.2 I)/luere a stării q ) mulimea >obs. +a/ă ∃qnd ∈qobs a.qnd ∈>m4) atu)/i se aau"ă qobs ) >m4obs.

Pas 2.3 Pe)tru #ie/are eve)ime)t e∈Σ )

Pas 2.3.1 ,valuare a stării q@ obs ) /are evoluează qobs la apariiaeve)ime)tului e

δ obs*qobs4 e- = q@ obs=UR*δ nd *qobs4 e--=

B UR*obsnd qq ∈

δ )*<)4 e--

Pas 2.3.2 +a/ă <Qobs∉>obs I)trou/ere a lui <Qobs ) (SN.

Pas 2.! 6)toar/ere la Pas 2.

'ri/e e8presie re"ulată *,R- poate #i repreze)tată pri)tru) %?Nε 4 pe baza e#i)iiei ,R i utiliz;) următoarele operaii

8/9/2019 Curs Mssed


2imbae 4ormale şi #utomate 1E

?ie r 1 i r 2 ,R /are pot #i e8primate pri) %?N ε 4 respe/tiv

1 = *Q14 Σ 14 q14 δ 14 A 5 1-

2 = *Q24 Σ 2 4 q24 δ 24 A 5 2-

%tu)/i

1. %?N ε /orespu)zător reuniunii r = r 1 r 2 este

1

q0

2

q1

q2

5 0

5 1

5 2

%utomatul /orespu)zător lui r este

= *Q1 ∪Q2 ∪Aq0 4 5 0 4 Σ 1 ∪Σ 2 4 δ 4 q0 4 A 5 0 -

δ *q0 4 ε - = Aq1 4 q2

δ *q4 a- = δ 1 *q4 a- a/ă q ∈Q1 WA 5 1 i a ∈Σ 1 ∪A ε

δ *q4 a- = δ 2 *q4 a- a/ă q ∈Q2 WA 5 2 i a ∈Σ 2 ∪A ε

δ * 5 14 ε - = δ * 5 24 ε - = A 5 0

2. %?N ε /orespu)zător conc!ten*rii r = r 1 r 2 este

1 2 q1 q2 5 1 5 2

= *Q1 ∪Q2 4 Σ 1 ∪Σ 2 4 δ 4 q1 4 A 5 2-

δ *q4 a- = δ 1 *q 4 a- a/ă q ∈Q1 W A 5 1 si a ∈ Σ 1 ∪ A ε

8/9/2019 Curs Mssed



δ *q4 a- = δ 2 *q 4 a- a/ă q∈Q2 i a ∈ Σ 2 ∪A ε

δ *A 5 14 ε - = Aq2

3. %?N ε /orespu)zător oper!torului 8leene r = r 1M este

=*Q1 ∪Aq0 4 5 0 4 Σ 1 ∪ Aε 4 δ 4 q0 4 A 5 0-

δ *q0 4 ε - = Aq1 4 5 0

δ *q 4 a- = δ 1 *q4 a- pe)tru q ∈ Q1 W A 5 1 i a ∈ Σ 1

δ * 5 1 4 ε - = Aq1 4 5 0

1q0 q1 5 0 5 1

Teorem* +a/ă ( este u) limbaG a//eptat e u) automat #i)it etermi)ist4atu)/i ( poate #i s/ris /a e8presie re"ulată.

,8presia Re"ulată a limbaGului a//eptat e /ătre automat este o reu)iu)e

m ><toate

) 1R

∈a tuturor traie/toriilor /are /o)u/ e la starea i)iială /ătre o stare

mar/ată.

Oserv!%ie2ni reprezi)tă toate traie/toriile e la qi la q G #ără să trea/ă

pri)tro stare /u u) )umăr mai mare e/;t n.

'e#ini%ii2

1

iG1

GM1

1

i iG R R -R *R R −−−−=

8/9/2019 Curs Mssed



=∪=+

≠==

GiB . a /AO<a -4X * <LOA a

Gi. a / a B<a -4X * <LA aR

Gi

Gi0

i G

'e#ini%ie2 ?ie ouă %utomate ?i)ite *+etermi)iste-

G1 =* Q1 4 Σ 1 4 Y1 4 δ 1 4 q01 4Qm1-

G2 =* Q2 4 Σ 2 4 Y2 4 δ 2 4 q02 4Qm2-

Se )umete compunere sincron: a automatelor G1 i G2 )otată G1 LL G2 u)automat G /are are stările G =*Q 4 Σ 4 δ 4 q04 Qm- ast#el

Q = Q1 × Q2

Σ = Σ 1 ∪ Σ 2

q0 = *q01 4 q02-

Qm = Qm1 × Qm2

+e#i)irea #u)/iei e tra)s#er *∀- q = *q1 4 q2- ∈ Q i σ ∈ Σ

*δ1*q14σ- 4δ2*q24σ- - a/ă σ∈Σ1 ∩Σ2 i ∃δ1 *q14σ- i∃δ2*q24σ-

*δ1*q14σ- 4 q2 - a/ăσ∈Σ1 WΣ2 i ∃δ1 *q14σ-

* q14δ2*q24σ- - a/ăσ∈Σ2 WΣ1 i ∃δ2 *q24σ-

Nu se e#i)ete pe)tru ori/e /az /are )u /orespu)e /elor e#i)ite mai sus

δ*q4 - =

6) a/est /az4 limbaGul "e)erat e automatul rezultat i limbaGul mar/at alautomatului rezultat au următoarele e#i)iii

1- (m *G1 LL G2- = A s∈Σ M Z s↑ Σ 1 ∈ (m *G1- i s↑ Σ 2 ∈ (m

*G2-

2- ( *1 LL 2- = A s∈Σ M Z s↑ Σ 1 ∈ ( *G1- i s↑ Σ 2 ∈ ( *G2-

Oserv!%ie2 +a/ă Σ 1 = Σ 2 atu)/i (m*G1 LL G2- = (m *G1- ∩ (m*G2- i(*G1 LL G2- = (*G1-∩( *2-.

8/9/2019 Curs Mssed



%utomatele stuiate p;)ă a/um pot #i /o)sierate /a mai)i e stare /u ieiri bi)are #aă e u) /uv;)t e i)trare at 7 se poate spe/i#i/a )umai a/ăa/esta este sau )u a//eptat *respe/tiv a/a δ *q04 7-∈>m-. 6) a)umitesituaii este e orit să se i#ere)ieze stările mar/ate4 respe/tiv )emar/ate4)tre ele. Pe)tru a/easta se #oloses/ aa)umitele mai)i e stare /u ieiri oore i eal[.

'e#ini%ie2 ' mai)ă oore se poate e#i)i /a u) se8tuplu

M = *Q 4 Σ 4 ∆ 4 δ 4 λ 4 q0-

u)e

Q = mulimea *#i)ită- a stărilor

Σ = al#abetul e eve)ime)te *#i)it i el-

q0 = starea i)iială

δ = #u)/ia e tra)ziie δ Q × Σ Q

∆ = al#abetul ieirilor

λ = #u)/ia e alo/are a ieirilor λ Q → ∆

Co)#orm e#i)iiei4 ori/e mai)ă oore ă u) răspu)s λ *q0- aso/iat u)eii)trări )ule *ε -.

E6emplu2

Să se proie/teze mai)a oore /are /al/ulează restul moulo 3 pe)tru u) ir bi)ar e i)trare */are are sem)i#i/aia u)ui )umăr )tre" ) #ormat bi)ar-

,vie)t4 e8ista oar trei ieiri posibile ∆ = A04 14 24 /eea /e )seam)ă /ă)umărul ma8im e stări este tot trei.

Pe)tru i)trarea )ulă *e/:ivale)tă /u )umărul 0-4 ieirea "e)erată trebuie să#ie 0. Rezultă4 pri) e#i)iie4 /ă λ *q0- = 0.

6) /o)ti)uare4 se #olosete următorul raio)ame)t a/ă u) ir e i)trare bi)ar 7 /orespu)e )umărului )atural n4 atu)/i 70 i /orespu)e lui $n i71 lui *$n1-.

Rezultă următoarea stru/tura pe)tru mai)a oore orită

8/9/2019 Curs Mssed



<1 <2

9

<0

,

1 0

1

01

0

/

'e#ini%ie2 ' mai)ă eal[ poate #i e#i)ită /a u) se8tuplu

e = *Q4 Σ 4 ∆ 4 δ 4 λ 4 q0-

u)e

Q = mulimea *#i)ită- a stărilor9

Σ = al#abetul e eve)ime)te *#i)it i el-9

∆ = al#abetul ieirilor9


δ = #u)/ia e tra)ziie /u e#i)iia δ Q × Σ → Q9

λ = #u)/ia e alo/are a ieirilor λ Q × Σ → ∆ .

Co)#orm e#i)iiei4 pe)tru o i)trare )ulă *ε - o mai)ă eal[ "e)erează oieire )ulă *ε -.

+i) pu)/tul e veere al puterii e moelare4 mai)ile oore i eal[ su)te/:ivale)te9 i) pu)/tul e veere al lu)"imii /uv;)tului e ieire4 mai)aeal[ va a u) răspu)s e lu)"ime /u 1 mai mi/ă e/;t mai)a oore

pe)tru a/eeai lu)"ime a /uv;)tului e i)trare.

Minimi+!re! !utom!telor 2?ie 4 / ∈(. %tu)/i R ( este o rela=ie de ec9ivalen=: aso/iata limbaGului (*sau R ( /- a/ă i )umai a/ă pe)tru *∀- z ∈ Σ M4

1. #ie z∈ ( i /z ∈ (

2. #ie z ∉( i /z ∉(.

8/9/2019 Curs Mssed



Relaia R ( mparte limbaGul ( ) /lase e e/:ivale)ă. Numărul e /lase ee/:ivale)ă se )umete inde.

Se poate emo)stra /ă i)e8ul u)ui limbaG re"ulat este #i)it.

?ie = *Q4 Σ 4 δ 4 q04 Qm- u) %?+. Se e#i)ete relaia e e/:ivale)ă R aso/iata automatului ast#el

pe)tru 4 / ∈ Σ M4 R / a/ă i )umai a/ă δ *q04 - = δ *q04 /-.

6) plus4 a/ă R /4 pe)tru *∀- z ∈Σ M avem z R /z. *Ceea /e revi)e la

δ *q0 4 z- = δ *δ *q0 4 -4 z- = δ *δ *q0 4 /-4 z- = δ *q0 4 /z--

' relaie e e/:ivale)ă e a/est tip se )umete invariant: la dreapta *#aăe operaia e /o)/ate)are-.

Teorem* */riteriul [:illNeroe- Următoarele a#irmaii su)t e/:ivale)te

1. (imbaGul ( ⊆ Σ M este a//eptat e u) automat #i)it9

2. ( este reu)iu)ea u)or /lase e e/:ivale)ă etermi)ate e o relaiee e/:ivale)ă i)varia)tă la reapta /u i)e8 #i)it9

3. ?ie relaia e e/:ivale)ă e#i)ită pe limbaGul ( ast#el

*∀- 4 / ∈ ( 4 R ( / a/ă i )umai a/ă *∀- z ∈ Σ M 4 z ∈ ( )umai )/azul ) /are i /z ∈ ( .

Ca o /o)se/i)ă a teoremei e mai sus4 o stare p este ec9ivalent: /u o stareq a automatului a/ă i )umai a/ă pe)tru ori/e ir e i)trare 4 δ * p4 -este stare mar/ată )umai atu)/i /;) δ *q4 - este o stare mar/ată.

#loritmul de minimizare a unui automat

Start

&!s , pe)tru #ie/are p∈ Qm i q ∈Q W Qm bi#ează ) tabel lo/aia

/orespu)zătoare *stările mar/ate )u su)t e/:ivale)te i) pu)/t eveere al obie/tivului /u /ele )emar/ate-9

&!s / pe)tru #ie/are pere/:e e stări isti)/te * p4 q- ∈ Qm × Qm sau* p4 q, ∈*QZQm-× *QQm-

&!s /-, dac: *∀- a ∈ Σ 4 *δ * p4 a-4 δ *q4 a-- este bi#ată ) tabel

atunci

1- bi#ează * p" q-9

8/9/2019 Curs Mssed



2- bi#ează su//esiv toate pere/:ile i) lista e e/:ivale)e a pere/:ii * p"q-.

alt5el

pe)tru toi a∈Σi)trou/ere a pere/:ii * p" q- ) lista e e/:ivale)e a

pere/:ii *δ * p4a-4 δ *q4a-- ) a#ara /azului ) /areδ * p"a- = δ *q" a-.

Stop

%l"oritmul e mi)imizare a automatelor a #ost elaborat pe baza /riteriului[:ill @ Neroe. %/est al"oritm urmărete "ăsirea pere/:ilor e stări /aresu)t e/:ivale)te *au a/eeai evoluie-. %/est lu/ru se realizează pri)elimi)area stărilor /are )u su)t e/:ivale)te. %l"oritmul veri#i/ă toate

pere/:ile isti)/te e stări.

?ie automatul G = *Q4 Σ 4 δ 4 q04 Qm-. Se /o)struiete u) tabel /are să/o)i)ă toate pere/:ile e stări isti)/te. +i) matri/ea /are are pe li)ii i pe/oloa)e toate stările se păstrează oar eleme)tele e sub ia"o)ala

pri)/ipală a matri/ei.

6) a/est #el4 toate pere/:ile * p4 q- rămase )emar/ate reprezi)tă ouă /;teouă stări e/:ivale)te.

8/9/2019 Curs Mssed



&roleme re+olv!te

:- Să se proie/teze u) %?+ peste al#abetul Σ = Aa" b/are a//eptă/uvi)tele /are )u /o)i) 3a /o)se/utiv.

ezolvare.

%utomatul obi)ut este /el i) #i"ura 2.1.

b

q0

b

aq1

a a

b

a"bq2q3

?i"ura 2.1

;- Să se proie/teze %?+ peste al#abetul Σ = Aa" b/are a//eptă irurileaD4 bbD i abaD.

ezolvare.

%?+ /erut este ilustrat ) #i"ura 2.2.

a

b

ab

q02

a b a

b

a"b

a"bq10

q5

q20 q30

q!0

?i"ura 2.2

8/9/2019 Curs Mssed



&roleme propuse

<- Să se proie/teze u) %?+ peste al#abetul Σ = Aa" b/are a//eptă/uvi)tele /e /o)i) mi)im 3a i )u se termi)a /u b.

=- Să se proie/teze automatul etermi)ist peste al#abetul Σ = Aa" b /area//eptă /uvi)tele ) /are pere/:ea aaD este urmată e subirul babD.

>- Care este %?+ /are peste al#abetul Σ = Aa" b a//eptă irurile /u)umăr par e aD i )u /o)i) subirul bbD\

,9- Să se proie/teze %?+ /are a//eptă peste al#abetul Σ = Aa4 b4 c/uvi)te /u )umăr par e aD4 par e bD i impar e cD.

,,- Să se proie/teze %?+ /are a//eptă peste al#abetul Σ = Aa" b" c/uvi)te /are /o)i) mi)im 2 cD *)u )eapărat /o)se/utivi- i )u /o)i)se/ve)a acaD.

,/- Să se /o)struias/ă peste Σ = Aa4 b u) %?+ /are a//eptă irurile /e/o)i) /el pui) 2 DaD i )u /o)i) subirul bbD.

,0- Să se proie/teze u) %?+ /are a//eptă toate irurile peste al#abetulΣ =Aa" b /are /o)i) /el pui) 3 DaD i /el mult 2 DbD.

,1- Să se proie/teze %?+ /are peste al#abetul Σ = Aa" ba//eptă/uvi)tele /e /o)i) subirul abaD i )u /o)i) subirul bbD4.

,:- Să se /o)struias/ă %?+ peste al#abetul Σ = A14 24 3 /are a//eptă/uvi)tele ) /are suma ultimelor ouă simboluri este !.

,;- Să se /o)struias/ă u) %?+ peste al#abetul Σ = Aa" b /are a//eptă/uvi)te /e /o)i) )umăr par e aD i )u /o)i) subirul abbD .

,<- Să se proie/teze %?+ peste al#abetul Σ = A14 24 34 /are a//eptă toate/uvi)tele /are se termi)ă /u subirul 123D.

,=- Care este automatul /are peste al#abetul Σ = Aa" b" c re/u)oate/uvi)tele /e /o)i) )umăr par e aD i )umăr impar e cD\

8/9/2019 Curs Mssed



,>- Care este automatul /are peste al#abetul Σ = Aa" b re/u)oate/uvi)tele /e /o)i) )umăr impar e bD i /are )u /o)i) subirulbbaD\

/9- ?ie u) la/ăt ele/tro)i/ prevăzut /u ouă butoa)e eti/:etate /u aD irespe/tiv bD. (a/ătul se es/:ie a/ă se apasă pe butoa)e )/ombi)aia abaD. +i) poziia es/:isD el poate #i )/:is )umai pri)apăsarea buto)ului bD. Să se moeleze #u)/io)area la/ătului pri)tru) automat #i)it etermi)ist.

/,- Să se /o)struias/ă %?+ /are a//eptă setul tuturor irurilor i)al#abetul Σ = A04 1 /u )umăr e"al e 0 i 1 ast#el )/;t #ie/are pre#i8are /el mult )/ă u) 0 ) plus #ata e )umărul e 1 i )/ă /el mult u)1 ) plus #aă e )umărul e zerouri.

//- Să se /o)struias/ă %?+ a#ere)t u)ui sistem e parolare peste al#abetulΣ = Aa" b" c" d /are #u)/io)ează upă următoarele re"uli

• parola are trei /ara/tere i)tre /are ouă trebuie sa #ie ie)ti/e ar)e/o)se/utive9

• /ara/terul d )u trebuie să #a/ă parte i) parolă @ a/ă a4 atu)/i seaGu)"e )tro stare e blo/aG9

• parola /ore/ta /o)u/e )tro stare mar/ata ) automat.

/0- Ce iruri a//epta automatele

a-a"bb

a a

b

b-

b

a

ba

bb a

a

\

8/9/2019 Curs Mssed



/1- Co)struii automatul e/:ivale)t /u

<2

q3q0

b

a q1 a"b

a

b

a"b

/:- Să se "ăseas/ă %?+ /orespu)zător %?Nului

q!

q3

q2q1

a"b

a"b

b

a"b

a a

/;- Se ă automatul e#i)it ast#el = AA p" q" r" s44 A0414 δ 4 p4Aq"s4 u)e δ este e#i)it pri) tabelul e mai Gos. Se /ere %?+e/:ivale)t.

0 1

> q"s q

Q r q" r

s p

S F p

8/9/2019 Curs Mssed



/<- Să se /al/uleze observatorul pe)tru automatul e mai Gos

b

q0

b

a

q1

q3

a

b

ε

ε

q2

/=- Să se /o)struias/ă %?+ e/:ivale)t pe)tru următorul %?Nε .

b

a

a

a

ε

εq0

q1

q3

q2

q!ε4 b

a

b

/>- Să se proie/teze %?+ e/:ivale)t /u următorul automat %?Nε

8/9/2019 Curs Mssed



b

ε

a"bq0

a

q1

q3

a

b ε

q2

a

q!

q5

b

09- Să se /o)struias/ă %?N ε pe)tru e8presia re"ulata

*ab-M *a bab-M

0,- Să se /o)struias/ă automatul %?+ /are mar/:ează limbaGul e#i)it ee8presia re"ulata

*a -*ba-M a*ba-MaM4 Σ =Aa" b"

0/- Să se /o)struias/ă automatul %?+ /are re/u)oate /uvi)tele /ees/riu limbaGul

a*ba-MaM

00- Se /ere %?+ /orespu)zător e8presiei re"ulate peste al#abetulΣ = A041

01 *011-0M1

01- Să se "ăseas/ă e8presia re"ulata pe)tru automatul

q1q0

a

b

a

b

0:- Să se etermi)e e8presia re"ulată pe)tru %?+ i) #i"ura

8/9/2019 Curs Mssed



ba

ba

b aq0

q1 q2

0;- Să se /al/uleze e8presia re"ulată a//eptată e automatul

b

b

a a a

q0q1 q$

0<- Care este e8presia re"ulată pe)tru automatul e mai Gos \

a"ba

a b

b

q0

q1 q2

0=- ?ie automatul e mai Gos. Care este e8presia re"ulată /are es/rielimbaGul a//eptat e a/est automat\

q2q0

a"b

b

b

a a

q3

0>- Să se etermi)e e8presia re"ulată pe)tru automatul

8/9/2019 Curs Mssed



0

0

01

1

1

.

19- Să se "ăseas/ă ,R pe)tru automatul e mai Gos0

q0

0

1

1

1

0

q1

q3

1,- Să se "ăseas/ă ,R pe)tru automatul e mai Gos

1

0

q0

0

1

0

0

1

q1

q2

q3

1/- Co)struii moelele lui 14 2 i robotului i) problema 1.3.%le"ei stările /u sem)i#i/aie #izi/ă pe)tru /ompo)e)telesistemului i u) set e eve)ime)te /are să /aptureze

8/9/2019 Curs Mssed



/omportame)tul /ompo)e)telor i)iviuale /;t i al )tre"uluisistem.

10- U) pro/esor este pre/eat e o /oaa e /apa/itate 1 ast#el /a)tre"ul sistem #ormat i) pro/esor i /oaa are /apa/itatea totalăe 2 Goburi. ,8ista ouă tipuri i#erite e Goburi ]1 i ]2 /are #a//erere /ătre pro/esor4 ]1 #ii) mai prioritar e/;t ]2. +e a/eea4a/ă la sosirea Gobului ]1 el "ăsete pro/esorul o/upat /u Gobul ]2

atu)/i l )lătură. ]obul ]2 se re)toar/e ) /oaa iar Gobul ]1

primete servi/iul. 'ri/e Gob )ou sosit /are "ăsete sistemul pli)este reGe/tat i pierut. Co)struii u) automat /are să es/rie#u)/io)area a/estui sistem.

11- ?ie ouă pro/esoare P1 i P2 /are operează ) paralel. Capa/itateatotală a lui P1 */oaa plus pro/esor- este 1=1 iar /apa/itatea totalaa lui P2 este 2=2. Sistemul primete ouă tipuri e Goburi 1 i 2

/are trebuie pro/esate pe pro/esorul P1 respe/tiv pe pro/esorul P2.+upă pro/esare Goburile părăses/ sistemul. +a/a u) Gob "ăsete/oaa pli)ă la sosire atu)/i el este reGe/tat. Co)struii %?+ulsistemului.

1:- U) sistem e #abri/aie simplu /o)i)e ouă mai)i 1 i 2 i u) bu##er B poziio)at )tre mai)i. I)trarea pieselor pe mai)a 1 este)elimitată. C;) o piesă este pro/esată pe mai)a 1 este plasată )

bu##erul B /are are /apa/itatea e o piesă. Piesa este apoi pro/esată pemai)a 2. ?ie/are mai)ă are posibilitatea e a se e#e/ta. I)iialmai)ile su)t libere. Comportame)tul )tre"ului sistem trebuie săsatis#a/ă următoarele /eri)e

• 1 poate )/epe pro/esarea oar a/ă bu##erul B este "ol9

• 2 poate )/epe pro/esarea oar a/ă bu##erul B este pli)9

• 1 )u poate )/epe pro/esarea a/a 2 este e#e/tă9

• +a/ă ambele mai)i su)t e#e/te atu)/i 2 trebuie reparată prima.

Co)struii automatul /are es/rie /omportame)tul amisibil alsistemului.

1;- Se /o)sieră u) pro/esor /are mparte u) Gob ) ouă tasuri. Primulse e8e/uta tasul 14 upă a/eea tasul 2 mome)t ) /are Gobul

8/9/2019 Curs Mssed



părăsete sistemul *la s#;ritul tasului 1-. Se presupu)e /ă sistemulare /apa/itatea e trei Goburi. Pro/esorul trebuie să termi)e ambeletasuri ale u)ui Gob )ai)te să )/eapă pro/esarea următorului Gob.,8istă u) me/a)ism e timeout pe)tru #ie/are Gob4 /are opereazăast#el /;) u) Gob i)tra ) sistem 4 tasului 1 i se a/oră o u)itate etimp pe)tru e8e/uie9 a/ă Gobul stă ) sistem o u)itate e timp itasul 1 al său )u sa e8e/utat4 atu)/i Gobul este termi)at #orat iurmătorul Gob i) /oaa4 a/ă e8istă va #i pro/esat. Se /o)sierăsistemul i)iial "ol. Presupu)em următoarea s/ară e timp pe)trusosirile Goburilor *09 0429 04E9 149 2- i pe)tru #ie/are se ă timpul ee8e/uie pe)tru #ie/are tas I*04$9 047-9 II*04E9 047-9 III*0439 04-9I^*04E9 045- i ^*0419 142-. Co)struii o ia"ramă e timp i)/luz;)timpii e apariie a eve)ime)telor i tipul eve)ime)telor . Pe bazaa/estei ia"rame etermi)ai /are Gob se termi)ă /ore/t i /are setermi)ă #orat *time out-. Co)struii o ia"ramă e stări tra)ziii.

1<- U) sistem /o)i)e 3 servere /a ) #i"ura următoare. Clie)ii /are i)tră) sistem aGu)" mai )t;i ) /oaa e la serverul 1 i upă /e su)t

pro/esai pe serverul 1 ei su)t rutai pe serverele 2 sau 3. Politi/a erutare este trimiterea /lie)tului )toteau)a /ătre serverul /u /oaa /eamai mi/ă. 6) /azul ) /are /ele ouă /ozi su)t e"ale 4 /lie)tul este rutat/ătre serverul 2. +upă pro/esarea pe serverul 2 sau 3 /lie)ii părăses/sistemul. U) /lie)t /are sosete i) e8terior este a//eptat ) sistemat;t timp /;t )umărul total e /lie)i i) sistem este ma8im 24 alt#el/lie)ii su)t reGe/tai. Să se /o)struias/ă automatul /are es/rie#u)/io)area sistemului.

1

2

3

1=- ' /elula e #abri/aie este al/ătuită i) ouă mai)i 1 i 2 i u)%^. %utomatele /elor trei /ompo)e)te su)t

8/9/2019 Curs Mssed



rea[at1

loaat1

01

1

"iveto2

loaat2

01

2

loaat2

"iveout

02

1 "iveto2

loaat1

%^

a- Să se /o)struias/ă = 1LL 2 LL%^

b- ,ste blo/a)t\

1>- U) sistem e #abri/aie /o)i)e 2 mai)i 1 i 2 i u) robot R /are preia o piesă prelu/rată e pe mai)a 1 i o epu)e pe mai)a 2. Nu e8ista )i/i u) bu##er pe)tru /ele ouă mai)i. +a/ă o piesă este#ur)izată lui 1 ) timp /e a/easta este o/upată atu)/i piesa estereGe/tată. +a/ă robotul tra)sportă piesa /ătre 2 ) timp /e a/easta

este o/upată el ateaptă p;)ă /;) 2 o poate a//epta. +upă /erobotul a epus piesa pe 2 el revi)e ) poziia i)iială4 e u)e poatelua o )oua piesa e pe 1.

Să se /o)struias/ă %?+ /are es/rie #u)/io)area pro/esului.

:9- ?ie u) tro)so) e /ale #erată /are arată /a ) #i"ură. ?ie al#abetulΣ =Ai14 s14 i24 s24 i34 s3 u)e i reprezi)tă i)trarea u)ui tre) petro)so)ul e /ale #erată 4 iar s = ieirea tre)ului e pe tro)so)ul . Se

8/9/2019 Curs Mssed



)otează /u qi variabila e stare aso/iată tre)ului i /are reprezi)tă preze)a tre)ului pe a/el tro)so). %st#el a/ă qi = 1 atu)/i tre)ul sea#lă pe tro)so)4 alt#el qi = 0. Starea )tre"ului sistem este q=*q14 q24 q3-.Să se /o)struias/ă mai)a oore /are moelează a/est sistem i"e)erează ) #ie/are stare valoarea lui q. Care este limbaGul ( /are )u/o)u/e ) starea e blo/aG repreze)tată pe #i"ură\

i3

i1

i2

s1

s2

s3

:,- %/tivitatea e obi)ere a vizelor la /o)sulatul _ este or"a)izată upăurmătoarele re"uli e8istă ouă /ozi 4 u)a pe)tru vize pro#esio)ale

*C 1-4 /ealaltă pe)tru vize turisti/e *C 2-. Coaa C 1 este eservită e u)":ieu4 iar /oaa C 2 e /ătre trei ":iee. 6) /lăirea /o)sulatului sei)tră ast#el "rupuri e /;te ! persoa)e pe)tru /oaa C 1 i "rupuri e/;te 12 persoa)e pe)tru /oaa C 2. U) "rup i)tră ) mome)tul ) /aretoi /ei i) "rupul a)terior au i)trat la ":ieu. +a/ă )umai e8istăsoli/ita)i pe)tru /oaa C 1 atu)/i ":ieul e la /oaa C 1 eservete/oaa C 2. Să se /o)struias/ă automatul sistemului.

:/- ?ie o barieră /u plată /are utilizează mo)ee m. ,8istă oi se)zori a ib4 a pe)tru sesizarea preze)ei u)ui ve:i/ul /u 2 roi4 iar b pe)trusesizarea preze)ei u)ui ve:i/ul /u ! roi. Pe)tru u) ve:i/ul /u 2 roi

este )e/esară o mo)eă pe)tru /a bariera să se rii/e iar pe)truve:i/ulul /u ! roi su)t )e/esare ouă mo)ezi. Să se moeleze /a%?+ #u)/io)area sistemului.

m

ba

8/9/2019 Curs Mssed



:0- ?ie ouă mai)i /u ouă stări posibile lier i ocup!t i setul eeve)ime)te Σ = A s14 5 14 s24 5 24 u)e si @ reprezi)tă a/iu)ea e start#u)/io)areD pe)tru mai)a i4 iar 5 i @ sem)i#i/ă a/iu)ea e s#;rit#u)/io)areD pe)tru mai)a i. Pe)tru #ie/are mai)ă i4 tre/erea i)starea liber ) starea o/upat se #a/e ) /o)/ora)ă /u apariiaeve)ime)tului si4 iar tre/erea i) starea o/upat ) starea liber se #a/e laapariia eve)ime)tului 5 i.

a- Să se /o)struias/ă automatele /e es/riu #u)/io)area mai)ilor i

automatul /e es/rie #u)/io)area )tre"ului sistem. b- Se i)trou/e o spe/i#i/aie e #u)/io)are )tre /ele ouă mai)i

e8istă u) bu##er _ e /apa/itate 1 4 /are poate avea ouă stări 0 @ bu##er "ol i 1 bu##er pli). Se /ere automatul /are es/rie#u)/io)area sto/ului pre/iz;)use eve)ime)tele i)terzise i /elea//eptate e #ie/are stare.

1 2_

:1- +oi #iloso#i stau la o masă pe /are se "ăses/ ouă #ar#urii4 #ie/are )#aa /;te u)ui #iloso# i ouă #ur/ulie situate e o parte i e alta a#iloso#ilor. Comportame)tul #ie/ărui #iloso# este următorul #ie/are#iloso# poate 4?ndi sau poate m?nc!. Pe)tru a tre/e i) starea";)eteD ) starea mă);)/ăD #iloso#ul trebuie să rii/e ambele#ur/ulie e pe masă4 pe r;)4 ) ori/e ori)e. +upă /e #iloso#ultermi)a e m;)/at4 el epu)e ambele #ur/ulie pe masă i revi)e )starea ";)eteD. %le";) u) set e eve)ime)te /;t mairepreze)tativ4 /o)struii at;t automatele a#ere)te e)tităilor sistemului/;t i automatul /are es/rie #u)/io)area )tre"ului sistem.

::- Să se mi)imizeze automatul

8/9/2019 Curs Mssed



a

0 1

2 3

a

a

a

bbb

:;- Să se mi)imizeze automatul

243

2

1

243

q0 1

243

1

13

2

3

1q1

q2

q3 q!

:<- +ouă pro/esoare partaGează o memorie /omu)ă. PartaGarea estee8/lusivă. ?ie/are pro/esor este lier p;)ă /;) trebuie să e8e/ute u)tas4 upă /are tre/e ) starea e cerere !cces memorie. %tu)/i /;)memoria este liberă4 pro/esorul o !loc*4 e8e/ută tasul i apoi oeliberează. 6) a/est mome)t pro/esorul evi)e lier. Să se/o)struias/ă automatele /are es/riu #u)/io)area subsistemelor/ompo)e)te i automatul /orespu)zător #u)/io)ării )tre"ului sistem.

8/9/2019 Curs Mssed


!0 Modelarea şi analiza SDED – 103 probleme

C%PI&'(U( IIIRe%ele &etri

(RE)IAR

'e#ini%ie Reelele Petri *RP- su)t "ra#uri orie)tate /u ouă tipuri e)ouri poziii i tra)ziii. ?ormal4 o RP ori)ară i auto)omă poate #ie#i)ită pri)tru) /vi)tuplu

( ) RP P T I O M = , , , ,0

u)e

P este mulimea poziiilor4 simbolizate pri) /er/uri9 poziiilemoelează variabile e stare sau /o)iii9

& este mulimea tra)ziiilor4 simbolizate pri) bare saureptu)":iuri9 tra)ziiile moelează eve)ime)te sau a/iu)i.

ulimile P i & su)t isGu)/te P T ∩ = ∅

{ } I PxT : ,→ 0 1 reprezi)tă ar/ele /are u/ e la poziii la tra)ziii ise mai )umete i #u)/ie e i)trare sau IN9

8/9/2019 Curs Mssed


e=ele >etri !1

{ }OPxT : ,→ 0 1 reprezi)tă ar/ele /are u/ e la tra)ziii la poziiii se mai )umete i #u)/ie e ieire sau 'U&.

6)tro RP4 )toteau)a u) ar/ u)ete ouă )ouri e tipuri i#erite *o poziie si o tra)ziie-.

M P N : → este ve/torul e mar/aG4 e#i)it pe mulimea poziiilorreelei4 /u valori ) mulimea )umerelor )aturale9 u) eleme)t m*Pi- alve/torului i)i/ă )umărul e Getoa)e e mar/aG i) poziia Pi a reelei la u)mome)t at.

+a/ă se /o)sieră poziiile reelei /a variabile e stare ale sistemuluiast#el moelat4 atu)/i mar/aGul *ve/torul e mar/aG- reprezi)tă stareasistemului.

M 0 este mar/aGul i)iial la la)sarea sistemului *starea i)iială-.

Starea u)ei RP se moi#i/ă pri) e8e/uia tra)ziiilor.

Re4uli pentru e6ecu%i! tr!n+i%iilor2

1.' tra)ziie se e8e/ută )umai a/ă este valiă. ' tra)ziie & G este

valiă )umai a/ă toate poziiile sale e i)trare *ai/ă toate poziiile Pi pe)tru /are I*Pi4& G-=1- su)t mar/ate *m*Pi-`1-.

2. 6)tro RP ori)ară auto)omă se e8e/ută o si)"ură tra)ziie la u)mome)t at *i)i#ere)t /;te tra)ziii su)t valie-. %/eastă re"ulăare la bază ouă ipoteze

a. +ouă eve)ime)te i)epe)e)te )u pot să aibă lo/ simulta)4

b. ?ie/are tra)ziie reprezi)tă u) eve)ime)t isti)/t.

3.,8e/uia u)ei tra)ziii & G se #a/e ) oi pai

a. +i) #ie/are poziie e i)trare a lui & G se retra"e /;te u) Geto)

e mar/aG4 b. 6) #ie/are poziie e ieire a lui & G se pu)e u) Geto) e mar/aG.

!. ,8e/uia u)ei tra)ziii are urată )ulă.

+i) pu)/tul e veere al )ivelelor e repreze)tare S,+4 e8istăurmătoarele /lase e RP

reele Petri auto)ome @ la )ivel lo"i/4

8/9/2019 Curs Mssed


!2 Modelarea şi analiza SDED – 103 probleme

- reele Petri temporizate4 si)/ro)izate i i)terpretate @ la )iveltemporal *etermi)ist-4

- reele Petri sto/:asti/e @ la )ivel sto/:asti/.

6) a#ară e a/este /lase isti)/te4 a /ăror putere e moelare estei#erită ) #u)/ie e moul e i)te"rare al timpului ) moel4 e8istă o seriee e8te)sii ale moelelor RP4 e8te)sii /are se pot apli/a #ie/ărei /lase4 #ără ale moi#i/a )i/i proprietăile i )i/i puterea e moelare. Rolul e8te)siiloreste e a realiza moele mai /ompa/te.

+i)tre a/estea4 /ele mai /u)os/ute su)t

RP 4ener!li+!te2 se aso/iază po)eri *)umere )aturale- ar/elor. 6)mo impli/it po)erea u)ui ar/ este 1. Se mai )umes/ i RP /u ar/e

po)erate.

I: PxT → N şi O: PxT → N

Pe)tru a/eastă /lasă e reele re"ulile e e8e/uie a tra)ziiilorse moi#i/ă ast#el

a/ă ar/ul Pi →& G are po)erea q 4 & G este valiă a/ă Pi /o)i)e

/el pui) q Getoa)e. pri) e8e/utarea lui & G se retra" q Getoa)e i) Pi 9

a/ă ar/ul & G → P are po)erea m4 pri) e8e/utarea lui & G seaau"ă m Getoa)e ) poziia P .

R& cu c!p!cit*%i2 se aso/iază /apa/ităi *)umere )aturale- poziiilor. 6) mo impli/it4 /apa/itatea u)ei poziii este i)#i)ită.Re"ulile e e8e/uie ale tra)ziiilor se moi#i/ă ast#el o tra)ziieeste e8e/utabilă a/ă i )umai a/ă pri) e8e/uia ei )u se epăete/apa/itatea vreu)eia i)tre poziiile sale e ieire.

Tr!n+i%ii speci!le2• tr!n+i%ie surs* este o tra)ziie /are )u are )i/i o poziie e i)trare. '

ast#el e tra)ziie este ) perma)e)ă valiă9

• tr!n+i%ie c!pc!n* *trapă- este o tra)ziie /are )u are )i/i o poziie eieire.

Not!%ii2

• M = mulimea mar/aGelor a//esibile ple/;) e la mar/aGul 9

8/9/2019 Curs Mssed


e=ele >etri !3

• S = se/ve)ă e e8e/uie = su//esiu)e e tra)ziii /e se pot e8e/uta )a/eastă ori)e9

• 0*S → 2 e8e/utarea se/ve)ei S por)i) e la mar/aGul 0 /o)u/e lamar/aGul 2.

• ar/aG superior 1 ≥ 2 ⇔ m1 *Pi - ≥ m2 *Pi -4 ∀ Pi 9

• ar/aG stri/t superior 1 > 2 ⇔ 1 ≥ 2 i ∃ Pi a.. m1 *Pi - m2 *Pi -.

&ropriet*%ile re%elelor &etri-&ropriet!te! ,2 M*r4inire

1 - ' po+i%ie Pi este m*r4init* pe)tru u) mar/aG i)iial 0 a/ă∀∈M0 4 e8ista u) )umăr )atural m ast#el )/;t4 ori/are ar #ievoluia reelei4 m*Pi-m9

2 - ' R& este m*r4init* pe)tru u) mar/aG i)iial 0 a/ă toate poziiile sale su)t măr"i)ite pe)tru mar/aGul i)iial 09

Se )umete RP in!r* *si"ură- pe)tru u) mar/aG i)iial 0 o reeamăr"i)ită ) /are mar/aGul )i/i u)ei poziii )u epăete valoarea 1.

&ropriet!te! /2 )i!ilit!te!

1- ' tr!n+i%ie & G este vi!il* pe)tru u) mar/aG i)iial 0 a/ă∀∈M04 e8istă o se/ve)ă e tra)ziii S /are por)ete i) i/o)i)e & G9 o tr!n+i%ie & G este cv!sivi!il* pe)tru u) mar/aG i)iial0 a/ă e8istă /el pui) o se/ve)ă e tra)ziii S /are por)ete i)0 i /o)i)e & G 9

2- ' R& este vi!il* pe)tru u) mar/aG i)iial 0 a/ă toate tra)ziiilesale su)t viabile pe)tru mar/aGul i)iial 09 o RP este cv!sivi!il*

pe)tru u) mar/aG i)iial 0 a/ă toate tra)ziiile sale su)t /el pui)

/vasiviabile pe)tru mar/aGul i)iial 09' RP se )umete con#orm* a/ă este bi)ară i viabilă .

&ropriet!te! 02 (loc!"e

1- U) loc!" este u) mar/aG pe)tru /are )i/i o tra)ziie )u mai estevaliă.

2- ' RP se zi/e #*r* loc!"e pe)tru u) mar/aG i)iial 0 a/ă∀∈M04 )u este u) blo/aG.

8/9/2019 Curs Mssed


!! Modelarea şi analiza SDED – 103 probleme

&ropriet!te! 12 Reini%i!li+!ilit!te

1- ' RP are o st!re de primire a pe)tru u) mar/aG i)iial 0 a/ă pe)tru toate mar/aGele a//esibile i∈M04 e8istă o se/ve)a etra)ziii S a.. i*S → a.

2- ' RP este reini%i!li+!il* pe)tru u) mar/aG i)iial 0 a/ă 0 estestare e primire.

Oserv!%ie ăr"i)irea4 viabilitatea4 abse)aZpreze)a blo/aGelor4

rei)iializabilitatea su)t proprietăi /are epi) e mar/aGul i)iial.&ropriet!te! :2 Inv!ri!n%i $i componente conserv!tive

?ie o reea Petri R i P mulimea poziiilor sale. Spu)em /ă avem u)inv!ri!nt lini!r al poziiilor *sau inv!ri!nt de m!rc!"- a/ă e8istă osubmulime PQ = AP14 P2 4...4 Pr 4 PQ⊂P i u) ve/tor e po)eri > = A<1 4<2 4...4 <r 4 <i ∈NM a..

<1 m*P1- <2 m*P2-. . . <r m*Pr - = Co)st. 4 ∀∈M0

ulimea PQ se )umete component* conserv!tiv*. Reeaua R se)umete conserv!tiv* a/ă i )umai a/ă toate poziiile reelei su)t i)/luse)tro /ompo)e)tă /o)servativă.

' se/ve)ă e tra)ziii S se )umete repetitiv* a/ă 0 *S → 0 .

Investi4!re! propriet*%ilor re%elelor &etri

I)vesti"area proprietăilor Reelelor Petri *RP- se poate #a/e #ie #olosi)al"ebra li)iară4 #ie #olosi) arborele e a/operire sau "ra#ul e mar/aGe.

Investi4!re! propriet*%ilor R& cu !"utorul !l4erei lini!re-

Not!%ii2°& G = APi∈P L I*pi4 t G- 0

& G °= APi∈P L '*pi4 t G- 0

°Pi = A& G∈& L '*pi4 t G- 0

Pi °= A& G∈& L I*pi4 t G- 0

c = JdiGK 4 diG

= I*pi4 t G- matri/ea e i)/ie)ă )ai)te

8/9/2019 Curs Mssed


e=ele >etri !5

c = JdiGK 4 diG

= '*pi4 t G- matri/ea e i)/ie)ă )apoi

c = c c = JdiGK matri/ea e i)/ie)ă *este i)epe)e)tă emar/aG-

,/uaia #u)ame)tală

= i c S4

pe)tru o se/ve)ă e e8e/utii S a.. i *S → 4 u)e S este ve/torul/ara/teristi/ al se/ve)ei S *ve/tor e ime)siu)e m ) /are s G /orespu)e

)umă rului e valiări ale tra)ziiei & G ) se/ve)a S.

Investi4!re! propriet*%ilor R& cu !"utorul 4r!#ului de m!rc!"e s!u !l!rorelui de !coperire-

#loritmul de construc=ie a arborelui de acoperire

&!s ,- Ple/;) e la mar/aGul i)iial 0 se i)i/ă toate tra)ziiile valie imar/aGele su//esive /orespu)zătoare. +a/ă u)ul i) a/este mar/aGeeste stri/t superior lui 0 4 se pu)e ω pe)tru #ie/are /ompo)e)tăsuperioară /ompo)e)tei /orespu)zătoare i) 0 .

&!s /- Pe)tru #ie/are )ou mar/aG i al arborelui se #a/e #ie Pas 2.1. #iePas 2.2.

&!s /-,- +a/ă e8istă pe /alea e la 0 la i *e8/lusiv i- u)mar/aG G = i 4 atu)/i i )u are su//esor.

&!s /-/- +a/ă )u e8istă u) mar/aG G = i pe /alea e la 0 la i

atu)/i se prelu)"ete arborele aău";)use toi su//esoriilui i . Pe)tru #ie/are su//esor al lui i

a- o /ompo)e)tă ω a lui i răm;)e o /ompo)e)tă ω alui 9

b- a/ă e8istă u) mar/aG G pe /alea e la 0 la a..

G 4 atu)/i se pu)e ω pe)tru #ie/are /ompo)e)tă alui superioară /ompo)e)tei /orespu)zătoare i) G .

Os- @r!#ul de !coperire *sau e mar/aGe a//esibile- se obi)e i)arborele e a/operire4 pri) /o)/ate)area mar/aGelor /are se repetă . Se obi)) a/est #el bu/le ) "ra#ul e a/operire4 /are ) arbore )u apăreau.

8/9/2019 Curs Mssed


! Modelarea şi analiza SDED – 103 probleme

Re%ele &etri sincroni+!te

1- ' R& sincroni+!t* este u) triplet R4 ,4 Si)/ u)e

R este o RP mar/ată9

, este o mulime e eve)ime)te e8ter)e9

Si)/ & → ,∪Ae4 & #ii) mulimea tra)ziiilor i) R iar eeve)ime)tul si"ur *)toteau)a aevărat-.

2- ' RP este tot!l sincroni+!t* a/ă Si)/ & → ,.,8e/utarea u)ei tra)ziii se #a/e

d!c* tra)ziia este valiă9

!tunci c?nd eve)ime)tul aso/iat se prou/e.

Not!%ie &*84- mulimea tra)ziiilor re/eptive la eve)ime)tul 8 ∈,∪Ae pe)tru mar/aGul .

'e#ini%ie2 S se )umete secven%* de simul!re complet* SSCB )raport /u eve)ime)tul 84 pe)tru mar/aGul 4 a/ă

S este o se/ve)ă e e8e/uii i) mar/aGul 4 /ompusă )umai i)tra)ziii apari);) lui &*84-9

toate tra)ziiile i) &*84- apar /el mult oată ) S 9

toate se/ve)ele S: obi)ute permut;) tra)ziiile lui S su)t easeme)ea se/ve)e e e8e/uie ple/;) e la 9

)u e8istă se/ve)ă e e8e/uii e lu)"ime mai mare /are să /o)i)ătoate tra)ziiile lui S i /are să )epli)eas/ă primele trei /o)iii.

Se nume$te e6ecu%ie iter!tiv* la apariia eve)ime)tului e8ter) ei ose/ve)ă /ompusă i) e8e/utarea u)ei SSC sub apariia lui ei4 urmată

eve)tual e e8e/utarea tuturor SSC posibile sub apariia lui e. +a/ă pe)truu) mar/aG )u este posibilă e8e/uia )i/i u)ei SSC sub e4 atu)/i este)umit mar/aG st!il. 6) /az /o)trar4 se )umete i)stabil.

#loritmul de interpretare a unei > sincronizate

pas1? I)iializări 1- mar/aGul4 2- mulimea mome)telor la /are au lo/eve)ime)tele e8ter)e 3- eve)ime)tul /ure)t 8.

?ie 8 = e. Salt la pas3?

8/9/2019 Curs Mssed


e=ele >etri !7

pas$? Se /o)sieră primul mome)t t la /are are lo/ u) eve)ime)t e8ter) ei .?ie 8 = ei .

pas3? Se etermi)ă mulimea e tra)ziii e8e/utabile sub apariiaeve)ime)tului 8. +a/ă a/eastă mulime este viă4 se suprimă t i)mulimea mome)telor la /are au lo/ eve)ime)te e8ter)e. Salt la pas$?

pas%? Se e#e/tuează o SSC. Se #a/e 8 = e. Salt la pas3?

&ropriet*%i supliment!re !le re%elelor &etri sincroni+!te-

' RP si)/ro)izată este prompt* a/ă pe)tru toate mar/aGelea//esibile stabile i pe)tru toate eve)ime)tele ei4 e8e/uia iterativă subapariia eve)ime)tului e8ter) ei /o)i)e u) )umăr #i)it e SSC.

+a/ă e8istă u) )umăr )atural ast#el )/;t )umărul e SSC ≤ 4atu)/i spu)em /ă reeaua este promptă.

&ropriet!te2 ' RP si)/ro)izată este promptă a/ă )epli)ete următoarele/o)iii

toate tra)ziiile sursă *#ără )i/i o poziie ) amo)te- au aso/iateeve)ime)te e8ter)e9

pe)tru toate /i/lurile P1&1P2&2 ... P<&< a.. avem ar/ele Pi → &i4 &i → Pi1 si&< → P1 e8istă /el pui) o tra)ziie /are să #ie si)/ro)izată pe u)eve)ime)t e8ter).

Oserv!%ie2 Proprietăile RP auto)ome nu se /o)servă atu)/i /;) reeauaeste si)/ro)izată.

Re%ele &etri tempori+!te

R& &tempori+!te se aso/iază #ie/ărei poziii Pi o temporizare i. 6)

mo impli/it4 temporizarea aso/iata u)ei poziii este )ulă.' RP &tempori+!t* este u) ublet R4 &emp u)e


&emp P → >4 u)e > reprezi)tă mulimea e )umere raio)ale pozitive a.. &emp*pi -= i .

8/9/2019 Curs Mssed


!$ Modelarea şi analiza SDED – 103 probleme

Se /o)sieră /a u) Geto) epus )tro poziie Pi ) mome)tul t estei)ispo)ibil pe urata temporizării Jt4 tiK4 upă /are evi)e ispo)ibil. 6)a/est #el4 la u) mome)t e timp oare/are mar/aGul al reelei are ouă/ompo)e)te mar/aGul ispo)ibil i mar/aGul i)ispo)ibil. * = l-.^aliarea u)ei tra)ziii este #ă/ută oar e /ompo)e)ta ispo)ibilă a

poziiilor sale e i)trare.

Ipoteza e lu/ru la mome)tul i)iial mar/aGul 0 este ispo)ibil.

6) veerea a)alizei RP temporizate se /o)sieră /ă o tra)ziie se

e8e/ută e )ată /e evi)e valiă. %/est re"im e #u)/io)are se )umete#unc%ion!re l! vite+* m!6im!l*.

Se emo)strează /a pe)tru o RP temporizată măr"i)ită i /utemporizări /u valori raio)ale4 #u)/io)area la viteza ma8imală /o)u/eupă u) timp la u) re"im repetitiv @ )umit re4im st!%ion!r.

6) /arul re"imului staio)ar se #a/e a)aliza /a)titativă *evaluarea per#orma)elorsistemului. Pe)tru a/easta se e#i)es/ următoarele mărimi

1- 3recven%! de e6ecu%ie # G4 a u)ei tra)ziii & G4 este )umărul meiu ee8e/uii ale lui & G pe u)itatea e timp.

2- Num*rul mediu de m!rc!"e )tro poziie Pi este e"al /u prousul)tre suma #re/ve)elor e e8e/uie ale tra)ziiilor e i)trare )

poziia Pi i urata sa aso/iată i.

U) alt re"im e #u)/io)are este /el la viteza proprie o RPPtemporizată #unc%ione!+* cu vite+* proprie a/ă )i/i u) Geto) )u răm;)e)tro poziie u) i)terval e timp mai mare e/;t urata sa ei)ispo)ibilitate. U) moel /are are #u)/io)are la viteza proprie este/o)sierat a #i u) moel #ără )t;rzieri *)i/i u) Geto) )u ateaptăD să #ieutilizat-.

Re%ele &etri Ttempori+!te se aso/iază #ie/ărei tra)ziii & G o uratăe e8e/uie G. Impli/it4 urata e e8e/uie a u)ei tra)ziii este )ulă.

'e#ini%ie2 ' RP &temporizată este u) ublet R4 &emp u)e


&emp & → >4 /u > o mulime e )umere raio)ale pozitive a..&emp*ti -= i

8/9/2019 Curs Mssed


e=ele >etri !E

Pe)tru a/eastă /lasă e reele u) Geto) poate avea 2 stări rezervat pe)tru e8e/utarea u)ei tra)ziii &i sau )erezervat. ?ie t mome)tul /;) see/ie e8e/utarea tra)ziiei &i i td i mome)tul /;) e8e/uia are lo/e#e/tiv. Pe urata Jt4 tiK Getoa)ele )e/esare e8e/uiei su)t rezervate. Sespu)e /ă t este mome)tul e )/eput i td i mome)tul e s#;rit al e8e/uiei.' tra)ziie este valiată e Getoa)ele )erezervate i) poziiile sale e i)trare.(a mome)tul i)iial toate Getoa)ele su)t )erezervate.

Noiu)ile e #u)/io)are la viteza ma8imală4 #u)/io)are la viteza

proprie i #re/ve)ă e e8e/uie se pot e8ti)e i la reele &temporizate.Repreze)tare "ra#i/ă

bară * - pe)tru o tra)ziie a /ărei temporizare este )ulă9

reptu)":i * - pe)tru o tra)ziie a /ărei temporizare este )e)ulă9

Oserv!%ie2 'ri/e reea Petri &temporizată poate #i tra)s#ormată )troreea Petri Ptemporizată i i)vers.

&temporizare Ptemporizare

Ptemporizare &temporizare

8/9/2019 Curs Mssed



&roleme re+olv!te

:=- Să se stuieze proprietăile e măr"i)ire4 viabilitate4 /i/li/itate i #ără blo/aGe pe)tru reelele Petri ilustrare ) #i"ura următoare

a b

P1P1

2 *3-

&!&!

&3&3 &1&1

P3P3

P2 P2

&2&2

ezolvare?

ra#ul e mar/aGe al reelei i) #i"ura a- este

0 =

2

0

0

1 =

1

1

0

2 =

0

2

0

3 =

0

0

1

! =

1

0

0

5 =

0

1

0

&2

&1

&1

&2

&!

&3

&1

&2

8/9/2019 Curs Mssed


e=ele >etri 51

Se observă /ă )umărul e ve/tori e mar/aG este #i)it4 pri) urmare reeauaeste măr"i)ită. +eoare/e )i/i u) mar/aG )u este ve/tor e blo/aG reeaua )u

prezi)tă blo/aGe. &ra)ziiile &3 i &! se pot e8e/uta o si)"ură ată. +e a/eeaele su)t /vasiviabile4 spre eosebire e /elelalte tra)ziii /are se e8e/ută eu) )umăr i)#i)it e ori. 6) /o)/luzie4 se poate spu)e /ă reeaua este/vasiviabilă. Proprietatea e reversibilitate )u este )epli)ită eoare/e )ue8istă o se/ve)ă e tra)ziii /are să /o)u/ă i) mar/aGul 3 ) mar/aGuli)iial.

Pe)tru reeaua i) #i"ura b- /u po)erea ar/ului &! → P1 e"ală /u 24 "ra#ul

e mar/aGe a//esibile este ilustrat ) #i"ura . +i) "ra# se eu/e /ă reeauaeste măr"i)ită i #ără blo/aGe /a /ea i)ai)te4 ) plus4 pri) bu/lele /are sau#ormat ) "ra#4 reeaua este viabilă4 pe)tru ori/are mar/aG i) "ra# i ori/aretra)ziie put;)use "ăsi o se/ve)ă por)i) e la a/est mar/aG /are să/o)i)ă tra)ziia respe/tivă.

Pe a/est e8emplu se mai poate #a/e o observaie. Pri) bu/lele /are sau#ormat pe "ra# se pot ie)ti#i/a se/ve)ele repetitive *se/ve)e e tra)ziii/are4 por)i) e la u) a)umit mar/aG4 /o)u/ la a/elai mar/aG-. %/esteasu)t S1 = &1&3&!4 S2 = &1&1&2&24 S3 = &1&1&2&3&!. Se poate veea uor /ăi) toate mar/aGele a//esibile e pe a/est "ra# se poate aGu)"e ) mar/aGul

i)iial4 e/i reeaua este reversibilă.Să /o)sieram u) ultim /az ) /are po)erea ar/ului & ! → P1 este 3 *vezi#i"ura b-. 6) a/est /az se obi)e următorul "ra# e a/operire

&!

&3

&2&2

0

2

0

1

1

0

2

0

0

0

0

1

&1 &1

0 =

8/9/2019 Curs Mssed



&!

0

0

2

0=&1

&2

0

1

1

1=

0

2

0

2=&1

&2

&3

1

0

0

3=

0

0

!=&1

0

5=&3

=

&14 &2 &14 &24 &34 &!

Se observă /ă pe a/est "ra# sa substituit4 /o)#orm al"oritmului e/o)stru/ie a arborelui e a/operire4 valoarea 3 /are sar #i obi)ut upă

prima e8e/utare a lui &! /u ω . 6) /o)ti)uare se poate observa /ă reeauaPetri are toate poziiile )emăr"i)ite9 ) a/est #el se eu/e /ă reeaua este)emăr"i)ită. Se păstrează )să proprietăile e viabilitate i e #ără blo/aGe.

59. Să se construiască graful de marcaje şi să se discuteproprietăţile de mărginire, viabilitate şi ciclicitate alereţelei sincronizate din figura de mai jos. Să se compareaceste proprietăţi cu cele ale reţelei nesincronizate.

Rezolvare. P1

e1

&2e1&1

P3P2

e2

&3

P5P!

e3&! e

3&5

8/9/2019 Curs Mssed


e=ele >etri 53

Reţeaua Petri sincronizată este viabilă aşa cum se poatevedea imediat din graful de marcaje accesibile.

A&14 &2Ze1 &3Ze2

A&!4 &5Ze3

0 =

2

0

0

0

0

1 =

0

0

1

1

0

2 =

1

1

0

0

0

Figura

Dacă nsă considerăm aceeaşi reţea dar nesincronizată sepoate vedea, construind din nou graful de acoperire, căaceasta nu mai este viabilă.

Prin e!ecutarea de două ori la r"nd a tranziţiei #$ sau atranziţiei #% pornind de la marcajul iniţial se ajunge la blocaj,deci de la aceste marcaje nici o tranziţie nu va mai putea fie!ecutată. Secvenţele #$ #$ şi #% #% nu sunt posibile pentrureţeaua sincronizată.

0

2

0

0

0

1

0

0

0

1

1

1

0

0

0

0

0

0

11

2

0

0

0

0

0

1

1

0

0

10

1

0

0

1

0

0

1

0

0

0

2

0

0

&5

&1

&!&2&1

&2

&3

&1

&5&2

0 =

&!

8/9/2019 Curs Mssed



&roleme propuse

;9- Pe)tru reeaua Petri i) #i"ura e mai Gos4 să se etermi)e pe baza"ra#ului e mar/aGe proprietăile

- viabilitate9

- măr"i)ire9

- reversibilitate9- blo/aGe9

- /o)#li/te *stru/turale4 e#e/tive-9

- /o)servativitate9

- se/ve)e repetitive9

- i)varia)i e e8e/uie9

- limbaGul "e)erat e reea.

P1

P2 P3

P!

P5

P

&1

&2 &3

&!&5

& &7

8/9/2019 Curs Mssed


e=ele >etri 55

;,- Se ă reeaua Petri i) #i"ura e mai Gos. Se /ere stuierea proprietăilor *măr"i)ire4 viabilitate4 /o)#li/te4 /o)servativitate4i)varia)i- pe baza "ra#ului e mar/aGe4 pe)tru mar/aGul i)iial0= J1 0 0K.

P1

P2P3

P!

&2 &1

&! &3

;/- ?ie reeaua i) #i"ura e mai Gos

P2

P1

P!

P3 P5

P

&1

&2

&3 &!

Se /er

a- proprietăile e măr"i)ire4 viabilitate4 /o)#li/te4 si"ura)ă4 puritate9

b- i)varia)ii e mar/aG9

/- limbaGul "e)erat e RP.

8/9/2019 Curs Mssed



;0- Se /o)sieră RP i) #i"ura e mai Gos. Să se /o)struias/ă arborele ea/operire i să se stuieze proprietăile e măr"i)ire4 viabilitatereversibilitate i /o)servativitate. Care su)t i)varia)ii e mar/aG i ee8e/uie\

&3

&1

P1 P2

P3

P!

&2

;1- Să se /o)struias/ă "ra#ul e mar/aGe al RP i) #i"ură i pe baza lui

a- să se etermi)e proprietăile9 b- să se /ompare proprietăile e la pu)/tul a- /u /ele ale reelei

auto)ome.

P1

P2P!

P3

P5

P

&1

&2 &!

&3 &5

e1

e

e2

e1

e

8/9/2019 Curs Mssed


e=ele >etri 57

;:- Să se stuieze proprietăile reelei Petri i) #i"ura e mai Gos.I)varia)ii e e8e/uie i limbaGul reelei.

P3

P5

P!

P1 P2

&2

&1

&3

&!

;;- Să se realizeze "ra#ul e mar/aGe i să se pre/izeze proprietăile*măr"i)ire4 viabilitate4 blo/aGe4 /o)#li/te4 i)varia)i e mar/aG4i)varia)i e e8e/uie4 /o)servativitate- pe)tru reeaua i) #i"ura emai Gos.

P1P2 P3

P!

&2

&3

&1

&!

P5

8/9/2019 Curs Mssed



;<- +etermi)ai se/ve)a e simulare /ompleta *SSC- ) raport /ueve)ime)tul aD pe)tru mar/aGele i)iiale pe)tru reeaua Petrisi)/ro)izata i) #i"ura e mai Gos

a. 0= J2 1 1 0 0 1K

b. 0 = J2 2 2 0 0 2K

e)io)ai /are i) SSC su)t ma8imale i e8pli/ai răspu)sul.

P1

P2

P!

P3

P5 P

&1&2

&!&3 &5

b

a

a

a

& b

a

;=- Să se etermi)e proprietăile Reelei Petri i) #i"ura e mai Gosutiliz;) "ra#ul e mar/aGe a//esibile.

P3P2

2

P!

3

&3

&1

P1

&2

2

8/9/2019 Curs Mssed


e=ele >etri 5E

;>- ?ie reeaua P temporizată i "e)eralizată i) #i"ura4 u)e i reprezi)tăurata aso/iată poziiei Pi. Pe)tru mar/aGul i)iial repreze)tat ) #i"urae mai Gos se /er

a- "ra#ul e mar/aGe a//esibile9

b- proprietăile reelei.

&1 &2

3

3

3=1

P3

2=1

1=1

P2

P1

<9- Să se construiască graful de acoperire pentru reţeauadin figura e mai Gos at"t n cazul sincronizat c"t şi dacăse consideră reţeaua nesincronizată. Să se discuteproprietăţile reţelei n ambele situaţii.

P1

e2

&1 e1

&2

P2

e3

&5

e2

&3&!e

1

P3

8/9/2019 Curs Mssed



<,- Pentru reţeaua Petri sincronizată din figura e mai Gos săse construiască graful de marcaje accesibile şi să sediscute proprietăţile.

e1&1P2P1

e

1

&!

&2 e

&3 e

2

e2

&5P! P3

</- ?ie reeaua Petri "e)eralizată i) #i"ura e mai Gos.

a- Care su)t tra)ziiile valie i) 0 \

b- +upă e8e/uia a ouă tra)ziii reeaua se blo/:ează. Care su)ttra)ziiile i /are este mar/aGul e blo/aG\

/- ,ste reeaua măr"i)ită\ ]usti#i/ai răspu)sul. Reeaua este viabilă\- +emo)strai /ă se/ve)a &3&1 se poate e8e/uta ma8im e ouă ori.

2

P1

P!

P2

&1 &2

&!&3

P3

8/9/2019 Curs Mssed


e=ele >etri 1

<0- Co)struii arborele e a/operire i "ra#ul e mar/aGe a//esibile pe)trureeaua Petri i) #i"ura e mai Gos. Stuiai proprietăile e măr"i)ire4viabilitate #ără blo/aGe i /o)servativitate.

&2

&1

&3

P1

P2P3

<1- Să se is/ute proprietăile RP i) #i"ura e mai Gos.

P2

P!

P3

P5

&1

&2&!

&3

&5

P

&

&7

P1

8/9/2019 Curs Mssed



<:- Să se /o)struias/ă "ra#ul e mar/aGe i să se pre/izeze proprietăile*măr"i)ire4 viabilitate4 reversibilitate4 /o)servatitivitate4 blo/aGe4/o)#li/te-. Să se etermi)e i)varia)ii e mar/aG i e e8e/uie. +easeme)ea se /ere /o)struirea "ra#ului e mar/aGe a//esibile pe)trureeaua & @temporizată. *uratele aso/iate tra)ziiilor su)t i)i/ate )

para)teze-.

P1

P2

P!

P3

P5

&1

&2 &!

&3&5

*2-

*3-

*2-

*1-

*1-

P

&

<;- Sistemul i) #i"ura e mai Gos prelu/rează ouă tipuri e piese %respe/tiv B4 preluate i) ouă epozite e i)trare /u /apa/itatei)#i)ită. Robotul R 1 )/ar/ă piesele e tip % pe mai)a 1 i

piesele e tip B pe mai)a 2. +upă prelu/rarea pe mai)a 14respe/tiv pe mai)a 24 piesele e tip % su)t tra)s#erate automat) bu##erul B1 e /apa/itate !4 iar piesele e tip B su)t tra)s#erateautomat ) bu##erul B2 e /apa/itate . Robotul R 2 preia piese i)

bu##erele B1 i B2 i )/ar/ă mai)a 3 )t;i /u o piesă e tip % iupă a/eea /u ouă piese e tip B *pe r;)-. %st#el mai)a 3

realizează operaia e asamblare a u)ei piese % i a ouă piese B) ori)ea %BB. +upă asamblare piesele părăses/ sistemul.

8/9/2019 Curs Mssed


e=ele >etri 3

Se presupu)e /ă mai)ile pot prelu/ra o si)"ură piesă la u) mome)tat9 e aseme)ea /apa/itatea e tra)s#er a roboilor este e o piesă. Se/u)os/ timpii e prelu/rare pe /ele trei mai)i urata e prelu/rare au)ei piese e tip % pe mai)a 1 este 1 = 3 u)ităi e timp9

prelu/rarea u)ei piese e tip B pe mai)a 2 se #a/e ) 2 = 2 u)ităie timp9 iar urata operaiei e asamblare pe mai)a 3 este as = 2u)ităi e timp.

Să se moeleze sistemul e prou/ie ast#el )/;t reeaua să #ie

măr"i)ită. Să se ie)ti#i/e i)varia)ii e mar/aG.

11=3

2 2=2

R1% B

B1 *!-

B2 *-

R2

31% 2B

fas = 2

Iesire i) sistem

<<- Co)sierăm e8e/uia e tip Rou)Robi) a mai multor tasuri.%/easta presupu)e tra)s#erul /o)trolului su//esiv #ie/ărui tas pe)true8e/uia u)ei pări a sa. &asurile ) e8e/uie partaGează o a/eeaiu)itate /e)trală4 iar la #ie/are /o)trol #ie/are tas poate e8e/uta u)a

8/9/2019 Curs Mssed


! Modelarea şi analiza SDED – 103 probleme

sau mai multe i)stru/iu)i. Să se /o)struias/ă RP /are moeleazăa/est proto/ol4 ) următoarele /azuri

a- Se /o)sieră ! tasuri4 #ie/are tas e8e/ut;) /;te o si)"urăi)stru/iu)e /;) primete /o)trolul9

b- Se /o)sieră 2 tasuri4 tasul 1 e8e/ut;) 3 i)stru/iu)i4 iar tasul2 e8e/ut;) 5 i)stru/iu)i la primirea /o)trolului.

<ndica=ie?

a, Pe)tru #ie/are tas se vor /o)siera următoarele poziii• poziie ai /are mar/ata sem)i#i/a tasul ) ateptare9

• poziie e8i /are mar/ată sem)i#i/ă #aptul /ă tasul i este )e8e/uie pe)tru o i)stru/iu)e9

• poziie pi /are a/ă este mar/ată sem)i#i/ă #aptul /ă sa at/o)trolul tasului i.

b, Se utilizează o reea Petri "e)eralizată.

<=- Se /o)sieră u) pro/es e prou/ie simplu4 /o)i);) u) /o)sumator

i u) prou/ător /e #oloses/ mpreu)ă u) a/elai sto/4 a/esta av;) o/apa/itate limitată la 3 u)ităi. Prou/ătorul poate prou/e o si)"ură piesă la u) mome)t at4 el put;) epu)e piesa ) sto/ imeiat /e atermi)ato a/ă sto/ul permite epu)erea. Imeiat upă epu)erea

piesei prou/ătorul re)/epe pro/esul e prou/ie. Co)sumatorul lar;)ul său4 imeiat /e a termi)at e /o)sumatD o piesă *u)a si)"urăla u) mome)t at- ia o )oua piesă i) sto/ a/ă a/esta )u este vi. Săse moeleze /u RP #u)/io)area a/estui pro/es.

epu)ere retra"ere

prou/ ător sto/ /o)sumator

<>- ?ie u) sistem e prou/ie /are prelu/rează u) si)"ur tip e piese/o)#orm #lu8ului te:)olo"i/ es/ris ) #i"ura e mai Gos. (a i)trare )sistem4 piesele su)t )/ăr/ate pe paletele preluate i)tru) sto/ e

8/9/2019 Curs Mssed


e=ele >etri 5

/apa/itate 3. Robotul R 1 )/ar/ă piesele alter)ativ pe mai)ile 1 i24 1 #ii) )/ăr/ată prima. Bu##erele B1 *e /apa/itate !- i B2 *e/apa/itate 3- su)t )/ăr/ate automat /u piese e pe mai)ile 1

respe/tiv 2 e )ată /e a/estea termi)a operaia e prelu/rare.Robotul R 2 )/ar/ă mai)a 3 prelu;) piese at;t i) bu##erul B1 /;ti i) bu##erul B2. +upă prelu/rarea pe mai)a 3 piesele părăses/sistemul iar paletele su)t re/i/late la i)trarea sistemului i epuse )sto/ul e palete. Vtii) /ă #ie/are mai)ă poate prelu/ra o si)"ură

piesă la u) mome)t at */apa/itate 1-4 să se /o)struias/ă reeaua Petri/are moelează a/est sistem e prou/ie.

R1

1 *1-

B1 B2

R2

2 *1-

3 *1-

Sto/ palete

8/9/2019 Curs Mssed


Modelarea şi analiza SDED – 103 probleme

=9- Se /o)sieră u) sto/ /e poate /o)i)e u) )umăr i)#i)it e piese.?u)/io)area sa este si)/ro)izată pe ouă eve)ime)te e8ter)eeve)ime)tul e14 sosirea u)ei piese i eve)ime)tul e24 sosirea u)ei/ereri e piesă. ' /erere e piesă este satis#ă/ută imeiat a/ă e8istă

piese ) sto/.

oelai /omportame)tul sto/ului e piese pri)tro reea Petrisi)/ro)izată i /o)struii "ra#ul e mar/aGe a//esibile pe)truurmătoarele ouă situaii

a& se presupune ca o cerere de piesă nesatisfăcută'nefiind piesa n stoc& este (pierdută) 'utilizatorultrebuie să*şi rennoiască cererea&+

b& se presupune că o cerere de piesă nesatisfăcută estememorată, şi satisfăcută atunci c"nd o nouă piesăsoseşte n stoc.

sto/

sosirea u)ei

/ereri e piesa

sosirea u)ei

piese

ple/area pieselor

sosirea

pieselor

e2e

1

=,- Patru #iloso#i4 # 1÷ # !4 stau ) Gurul u)ei mese4 )tre ei #ii) ispuse ba":etele b1÷ b!. U) #iloso# se poate "ăsi )tru)a i) următoareleouă stări poate ";)i sau poate m;)/a. Pe)tru a ma)/a u) #iloso# are)evoie e /ele ouă ba":ete a#late e o parte i e /ealaltă a sa. 6)starea i)iială toi #iloso#ii ";)es/ i ba":etele se a#la pe masă.

a- +es/riei pri)tro reea Petri următorul proto/ol /;) u) #iloso#

orete să mă);)/e el ia mai )t;i ba":eta i) reapta sa4 apoi pe/ea i) st;)"a sa i )/epe să mă);)/e. C;) termi)ă e m;)/at elepu)e pe masă mai )t;i ba":eta i) ma)a reaptă4 apoi pe /eai) ma)a st;)"ă i tre/e ast#el ) starea ) /are ";)ete. I)i/aii)varia)ii mi)imali pe)tru reeaua /o)struită. ,ste a/easta reeaviabilă\ +a/ă e8istă u) blo/aG "ăsii se/ve)a e valiări /are/o)u/e la a/esta i ai o e8pli/aie a a/estui blo/aG.

8/9/2019 Curs Mssed


8/9/2019 Curs Mssed


$ Modelarea şi analiza SDED – 103 probleme

asigură ndeplinirea condiţiei de e!ecuţie a tas-uluirespectiv.

=1- Se /o)sieră o li)ie e asamblare /upri)z;) ouă mai)i #ie/are /u/;te u) sto/ ) i)trare4 aa /um se vee ) #i"ura e mai Gos. Sto/urileau o /apa/itate )elimitată. Sistemul prelu/rează ouă tipuri e piese4

p1 i p24 /are soses/ )tro ori)e aleatoare ) sto/ul 1 ar prelu/rarealor pe mai)ă #ă/;)use pri) alter)a)a. Se presupu)e /ă mai)ile pot

prelu/ra o si)"ură piesa la u) mome)t at.

Fie evenimentul ei (sosirea unei piese de tip pi). 4 piesade tipul $ necesită o prelucrare de 5 unităţi de timp pemaşina $ şi de / unităţi de timp pe maşina % iar o piesade tipul % necesită c"te 1 unităţi de timp pe fiecaremaşină.

a& Să se modeleze acest sistem printr*o reţeasincronizată şi #*temporizată n condiţiile enunţateanterior+

b& 2um se modifică reţeaua n ipoteza că stocul $

conţine permanent cel puţin c"te o piesă de fiecaretip 3

sosire

piese

p14 p2

sto/ 2sto/ 1

masi)a 2masi)a 1

ple/are

piese

p14 p2

=:- Se consideră un flu! de fabricaţie compus din douămaşini, fiecare av"nd un stoc de piese n intrare. 6nsistem e!istă două palete, piesele trec"nd ntre maşinipurtate pe palete. 7ceste palete sunt reciclabile, adicăele se ntorc n stocul $ după ce piesele pe care le*aupurtat sunt terminate pe maşina %. 8aşina $ poate tratao singură piesă la un moment dat, timpul de servirefiind d$ 9 % unităţi de timp, n timp ce maşina % poate

8/9/2019 Curs Mssed


8/9/2019 Curs Mssed



==- ?ie u) sistem e #abri/aie #le8ibil /are prelu/rează ouă tipuri e piese % i B. Piesele su)t )/ăr/ate ) sistem i) ouă epozite ei)trare e /apa/itate i)#i)ită +I%4 +IB i su)t prelu/rate /o)#orm#lu8urilor e #abri/aie i) #i"ura e mai Gos /u următoarelespe/i#i/aii

• Piesele e tip % su)t prelu/rate pe mai)ile 14 2 i !4 iar piesele e tip B pe mai)ile 14 3 i 59 )/ăr/area mai)ii 1 se#a/e automat9

• Robotul R 1 )/ăr/a mai)a 2 /u piese e tip % i mai)a 3 /u piese e tip B9

• &ra)s#erul pieselor e tip % e la mai)a 2 ) sto/ul % *e/apa/itate $- se #a/e automat9 piesele e tip B su)t tra)s#erate easeme)ea automat e la mai)a 3 la mai)a 5.

• Robotul R 2 este impli/at ) următoarele operaii e tra)s#er)/ar/ă /;te 2 piese i) sto/ul % pe mai)a !9 es/ar/ă /;te 2

piese e pe mai)a ! /ătre ieirea % a sistemului9 es/ar/ă /;te o piesă e pe mai)a 5 ) sto/ul B e /apa/itate 5.

• Sto/ul B este "olit automat /;) evi)e pli).• ai)ile 14 3 i 5 prelu/rează o si)"ură piesă la u) mome)t

at9 mai)a 2 poate prelu/ra 3 piese simulta) iar mai)a ! poate prelu/ra 2 piese simulta)9

• +uratele e prelu/rare ale /elor ouă tipuri e piese pe mai)i su)ti)i/ate ) #i"ura4 ast#el mai)a 1 prelu/rează o piesa e tip % )3 u)ităi e timp4 iar o piesa e tip B ) 2 u)ităi e timp9 urata e

prelu/rare a piesei % pe mai)a 2 este e 7 u)ităi e timp iar pemai)a ! e 5 u)ităi e timp9 urată e prelu/rare a piesei B pemai)a 3 este e u)ităi e timp iar pe mai)a 5 e ! u)ităi e

timp.Se /ere moelul RP temporizat pe)tru a/est sistem e #abri/aie.

8/9/2019 Curs Mssed


e=ele >etri 71

%4 B1

*1-

2

*3-

3

*1-

Sto/%

*$-%

Bsto/B

R1 R2

Iesire %

+IB

+I%

%= 3

B=2

B= B = !

5

*1-

%= 7 %= 5

!

*2-

Iesire B

=>- ?ie u) sistem e #abri/aie /are prelu/rează ouă tipuri e piese % iB4 preluate i) ouă sto/uri e /apa/ităi i)#i)ite +I% i +IB4 /a )#i"ura e mai Gos. Robotul R 1 es/ar/ă mai)ile 1 i 2 i )/ar/ămai)a 3 /are asamblează o piesa % i o piesa B4 #ără restri/ii eori)e. Robotul R 2 es/ar/ă 3 )tru) bu##er e /apa/itate 104 /are se"olete automat /;) este pli). ?ie/are mai)ă poate prelu/ra o piesăla u) mome)t at. Prelu/rarea piesei % pe mai)a 1 urează 1 = 5u)ităi e timp4 prelu/rarea piesei B pe mai)a 2 urează 2 =

u)ităi e timp4 iar mai)a 3 e8e/ută operaia e asamblare ) 3 = !u)ităi e timp. Se presupu)e /ă tra)sportul pieselor e /ătre roboi)e/esită /;te o u)itate e timp.

Să se moeleze a/est sistem utiliz;) reele Petri /u tra)ziiitemporizate.

8/9/2019 Curs Mssed



R1

1 *1-

R2

2 *1-

3 *1-

Bu##er

*10-

Iesire sistem

+I% +IB

1 = 5 2 =

fas = !

>9- ?ie u) sistem e prou/ie /are prelu/rează ouă tipuri e piese p1 i

p2 /o)#orm u)ui #lu8 te:)olo"i/ spe/i#i/at ) #i"ura e mai Gos. ai)a1 prelu/rează alter)ativ piese e tip p1 i p24 mai)a 2 prelu/rează)umai piese e tip p1 iar mai)a 3 prelu/rează )umai piese e tip p2.Piesele su)t )/ăr/ate pe palete la i)trarea ) sistem4 i) sto/ul S1 itra)s#erate )tre mai)i. +upă /e piesele părăses/ staia e ieire I

paletele su)t re/i/late la i)trarea sistemului. ,8ista 2 paleteispo)ibile pe)tru piesele e tip p1 i 3 palete ispo)ibile pe)tru

piesele e tip p2. Robotul R 1 e#e/tuează operaia e tra)s#er a pieselore tip p1 e pe mai)a 1 ) sto/ul S2 e la i)trarea mai)ii 2 i a

pieselor e tip p2 e pe mai)a 1 ) sto/ul S3 e la i)trarea mai)ii3. Robotul R 2 es/ar/ă mai)ile 2 i 3 /ătre staia e ieire I.

Capa/itatea e prelu/rare pe)tru toate mai)ile este e o piesă4 iar/apa/itatea e sto/are pe)tru sto/urile S2 i S3 este e ! piese. Se/u)os/ timpii e prelu/rare pe #ie/are mai)a 1 prelu/rează piesa p1

) ! u)ităi e timp i piesa p2 ) 5 u)ităi e timp9 2 prelu/rează piesa p1 ) 5 u)ităi e timp4 iar 3 prelu/rează piesa p2 ) 3 u)ităi etimp. &impii e )/ăr/areZes/ăr/are pe)tru roboi su)t e o u)itate etimp.

Să se moeleze /u reele Petri & @temporizate sistemul e prou/ie.

8/9/2019 Curs Mssed


e=ele >etri 73

p14 p24 B

2

*p1-

3

*p2-

p1

p2

R1 R2

1

*p14p2- I

p14 p24 B

S1

S3

S2

>,- Să se moeleze /u RP &temporizate sistemul e prou/ieilustrat ) #i"ura e mai Gos. Să se /o)struias/ă "ra#ul e mar/aGei să se stuieze /omportame)tul ) timp al sistemului ) re"imstaio)ar

p2

p1

R1

p14 p24 p3

1 I

p3

p14 p22

3

p14 p24 p3

p24 p3

Sistemul prelu/rează trei tipuri e piese p14 p2 i p3 ) următoarele#lu8uri e #abri/aie

p1 1 2 @I *staia e ieire-

p2 123I

p3 13 I

Piesele su)t tra)sportate pe paletele preluate i) sto/ul e la i)trarea

mai)ii 1. ,8istă /;te 3 palete ispo)ibile pe)tru #ie/are tip e piesă.%/estea se re/i/lează la i)trare upă /e piesele părăses/ staia e ieireI. &ra)s#erul pieselor pe traseele 124 134 23 se #a/eautomat. Robotul R 1 es/ar/ă mai)ile 2 i 3 la staia e ieire I4urata tra)sportului #ii) e 2 u)ităi e timp. &impii e prelu/rare

pe)tru #ie/are tip e piesă su)t spe/i#i/ai ) următorul tabel

p1 p2 p3

8/9/2019 Curs Mssed



1 3 u)itati e timp ! u.t. 5 u.t.

2 $ u.t. u.t.

3 5 u.t. 3 u.t.

>/- ?ie u) sistem e prou/ie al/ătuit i) trei mai)i 14 2 i 3

/are prelu/rează piesele p14 p2 i p3 /o)#orm #lu8ului te:)olo"i/i) #i"ura e mai Gos. Se)surile să"eilor i)i/ă ori)ea ) /are

piesele su)t prelu/rate pe #ie/are i) /ele trei mai)i. *Piesele etip p1 i p2 su)t prelu/rate pe toate /ele trei mai)i4 iar piesa e tip p3 este prelu/rată oar pe mai)ile 1 i 2-.

p2 p2

p1 p1

p3

1 32

p3

p3

p1

p2 p2

p1

Se /er

a- reeaua Petri P @temporizată /are moelează sistemul9

b- timpii la /are piesele p14 p2 i p3 părăses/ sistemul tii) /a prioritatea e prelu/rare a piesei p2 prioritatea piesei p1 prioritatea piesei p3. +uratele e prelu/rare pe mai)i pe)tru#ie/are tip e piesă su)t spe/i#i/ate ) tabelul e mai Gos.

p1 p2 p3

1 1 u)itate e timp 1 u.t. 2 u.t.

2 1 u.t. 2 u.t. 1 u.t.3 1 u.t. 1 u.t.

>0- Se /o)sieră /elula e #abri/aie i) #i"ura e mai Gos /are i)/lue

• ouă mai)i /u #u)/io)are similară 1 i 29

8/9/2019 Curs Mssed


e=ele >etri 75

• o ba)ă rula)tă *u) /o)veior- e i)trare C'N^1 /a sursă i)#i)ităe repere9

• u) /o)veior e ieire /a epozit i)#i)it.

M1 M2

CONV1CONV2

p2

p1

Celula poate prou/e ouă tipuri e piese p1 i p24 #ie/are i)tre eletrebui) pro/esată pe ambele mai)i. +uratele e pro/esare respe/tivesu)t

p1 p2

1 3 u)ităi e timp 2 u)ităi e timp

2 1 u)itate e timp ! u)ităi e timp6)/ăr/area pieselor pe ori/are i)tre mai)i are urata e 1 u)itate etimp. +e )ată /e operaia e )/ăr/are a #ost )/:eiată4 pro/esarea

piesei )/epe #ără )t;rziere4 iar es/ăr/area #a/e parte i) pro/esare.Piesa e tip p1 este prelu/rată )t;i pe mai)a 1 i apoi pe mai)a 24iar piesa e tip p2 este prelu/rată )t;i pe mai)a 2 i apoi pe mai)a1. ?ie/are mai)ă poseă u) bu##er e i)trare /u o poziie4 pe)trutra)s#erul pieselor pro/esate pe Gumătate.

Se /er

a- să se /o)struias/ă reeaua Petri temporizată a /elulei e #abri/aie9

b- să se stuieze /omportame)tul ) timp al sistemului *"ra#ul emar/aGe- 9

/- /are este /apa/itatea bu##erelor ataate mai)ilor a/ă )tru) /i/lue prou/ie se prelu/rează o piesa e tip p1 i u)a e tip p2.

>1- Să se moeleze /u RP sistemul e prou/ie repreze)tat ) #i"ura emai Gos4 tii) /ă i)trarea sistemului este es/risă e o sursă i)#i)ităiar ieirea se #a/e #ără restri/ii. Piesele su)t )/ăr/ate automat pe

8/9/2019 Curs Mssed


8/9/2019 Curs Mssed


e=ele >etri 77

prelu/rarea pe mai)ile 3 i 5 piesele su)t epozitate ) bu##ere e/apa/itate i)#i)ită. Se presupu)e /a mai)ile pot prelu/ra o si)"ură

piesă la u) mome)t at4 iar /apa/itatea e tra)sport a /ăru/ioareloreste e o piesă. Se /u)os/ timpii e prelu/rare pe mai)i pe 1 e 2u)ităi e timp *u.t.-4 pe 2 e 3 u .t.4 pe ! e ! u.t.4 pe 3 e ou)itate e timp i pe 5 e 3 u.t. timp. 6)/ăr/area mai)ilor se #a/e)tro u)itate e timp. +e aseme)ea tra)sportul e#e/tuat e #ie/are/ăru/ior urează o u)itate e timp.

>;- Să se /o)struias/ă moelul RP &temporizate pe)tru sistemul e prou/ie es/ris ) #i"ura e mai Gos.

1 *2-

2 *1-

3 *1-

Sto/1 *10-

2 *1-

Sto/2 *2-

Sto/3 *5-

1 = 10

2 = !

3 = 5

R

Sto/ul e i)trare Sto/1 /o)i)e 10 palete ispo)ibile pe /are su)t)/ăr/ate piesele brute /are i)tră ) sistem ) )umăr )elimitat.%)samblul piesă @ paleta este tra)s#erat /ătre mai)a 14 /are poate

prelu/ra ouă piese la u) mome)t at. +upă prelu/rarea pe mai)a14 piesele su)t )/ăr/ate alter)ativ pe /ele ouă mai)i 24 /are pot

prelu/ra o si)"ură piesa la u) mome)t at. +upă prelu/rarea pe

8/9/2019 Curs Mssed



mai)ile 24 piesele su)t epuse ) sto/ul 2 e /apa/itate 3 iar paletelesu)t eliberate i ause la i)trarea sistemului ) sto/ul 1. Robotul R

preia piesele i) sto/ul 2 i le )/ar/ă pe mai)a 3 /are are/apa/itatea 1. &ra)s#erul pieselor e pe mai)a 3 ) sto/ul 3 *e/apa/itate 5- se #a/e automat4 urm;) /a e ai/i piesele sa #ie epusela ieirea sistemului ) loturi e /;te 3. +uratele e prelu/rare pe /eletrei mai)i su)t spe/i#i/ate ) #i"ura.

><- Să se moeleze /a RP următoarea stru/tură e /elulă #le8ibilă *#i"ura

e mai Gos-. Robotul R 1 )/ar/ă mai)ile 1 i 2 i)tru) sto/ e/apa/itate i)#i)ită iar robotul R 2 es/ar/ă mai)ile respe/tive )tru)

bu##er e /apa/itate !. C;) bu##erul se umple el este "olit automat.ai)ile 1 i 2 se pot e#e/ta ) timpul #u)/io)ării4 /eea /eimpli/ă epozitarea piesei /a rebut )tru) /o)tai)er e rebuturi. Se

presupu)e /a mai)ile prelu/rează o si)"ură piesă la u) mome)t at.

Să se evie)ieze totoată )umărul e piese rebut.

R 1

1 *1- 2 *1-

R 2 Rebuturi

I)trare i)#i)ita

>=- (a o pis/i)ă soses/ /lie)i ) )umăr )elimitat. %/etia utilizează pis/i)a ) #elul următor /lie)tul ia u) /o *e8istă 5 /ouriispo)ibile-4 i)tră ) /abi)a *e8istă 3 /abi)e-4 se s/:imbă4 pu)e

8/9/2019 Curs Mssed


e=ele >etri 7E

lu/rurile ) /o4 eliberează /abi)a i apoi i)tră ) pis/i)ă. +upă /e iesei) pis/i)ă4 /lie)tul i)tră mai )t;i ) /abi)ă4 se mbra/ă4 eliberează/abi)a i /oul i plea/ă. Să se moeleze /u RP proto/olul e utilizarea pis/i)ei i să se eu/ă i)varia)ii reelei.

>>- ?ie sistemul e prou/ie i) #i"ura următoare

1

2

3

Sto/2

Sto/1

&oate mai)ile pot avea pa)ă. +upă reparaie mai)ile 1 i 2

/o)ti)uă piesa )/epută4 iar mai)a 3 #a/e e8/epie4 reve)i) )starea i)iială. Piesa e pe 3 se epozitează )tru) sto/ e rebuturi.Să se /o)struias/ă moelul Petri al a/estui sistem ) /are să seevie)ieze )umărul e rebuturi i )umărul e e#e/tări ale mai)ilor.

100. Se consideră un proces de producţie condus prinetic:ete. 7cest sistem este compus din două posturide producţie nseriate. Fiecare post de producţieeste compus la r"ndul său dintr*un sistem deproducţie şi un stoc de produse finite n aval. Pieselebrute se găsesc n stocul ;. Pentru ca o piesa dinstocul i*$ să intre n sistemul de producţie i trebuiesă poarte etic:eta i a acestui post 'i 9 $,%&. 2"nd

prelucrarea ei este terminată ea este depusă nstocul i, etic:eta răm"n"ndu*i deocamdată ataşată.2"nd o piesa este retrasă din stocul i pentru asatisface o cerere din aval 'de la un client e!teriorpentru stocul %, sau de la postul % * prin sosireaunei etic:ete a acestuia * pentru stocul $& se scoatede pe piesa etic:eta i şi se adaugă etic:eta i<$'respectiv etic:eta (sigur) dacă a fost stocul %&. 4

8/9/2019 Curs Mssed


$0 Modelarea şi analiza SDED – 103 probleme

etic:etă i, detaşată de pe o piesă, este ntoarsă laintrarea sistemului de producţie i.

Reprezentaţi acest sistem de producţie printr*o reţeaPetri #*temporizată, cu următoarele ipoteze

$&pentru fiecare post de producţie i avem o poziţiepentru piese n sistemul de producţie i şi o poziţiepentru piese n stocul i, trecerea dintr*una n cealaltăfăc"ndu*se prin validarea unei tranziţii ce corespundeprelucrării unei piese. 4 singură piesă este tratată laun moment dat+

%&sunt trei etic:ete pentru postul $ şi două etic:etepentru postul %+

/&nu s*au făcut ncă cereri de piese din aval de sistemiar n stocul ; sunt / piese brute+

0& tratarea unei piese are o durata de $; unităţi de timp n sistemul de producţie $ şi $% unităţi de timp nsistemul de producţie %. Fiecare buclă de ntoarcere a

unei etic:ete de la ieşirea la intrarea unui sistem deproducţie are o durata de $ unitate de timp. #oatecelelalte operaţii au durată nulă.

sto/ 2sto/ 0 sto/ 1 sistem e prou/tie

2

sistem e prou/tie

1

sosireau)ei

piesesatis#a/erea

u)ei /ereri

,9,- ?ie sistemul es/ris e #lu8ul te:)olo"i/ i) #i"ura e mai Gos.Sistemul prelu/rează ouă tipuri e piese % i B preluate i)sto/uri e /apa/itate i)#i)ită. Piesele e tip % su)t )/ăr/ate pe

palete e /;te 2 poziii */apa/itate 2 piese- iar piesele e tip B

8/9/2019 Curs Mssed


e=ele >etri $1

su)t )/ăr/ate pe palete e /;te ! poziii. Robotul R 1 )/ar/ă paletele /u piese e ambele tipuri ) bu##ere /orespu)zătoare4ast#el paletele /u piese e tip % su)t )/ăr/ate ) bu##erul B% e/apa/itate 3 *palete- iar paletele /u piese e tip B su)t )/ăr/ate )

bu##erul BB e /apa/itate 2 palete. Pri) urmare bu##erul B% poate a//epta ma8im piese % iar bu##erul BB poate a//eptama8im $ piese B. Robotul R 2 es/ar/ă /ele ouă bu##ere i)/ar/ă mai)ile 1 i 2 /u /;te o piesa % respe/tiv /;te o piesaB. ai)ile 1 i 2 pot prelu/ra o si)"ură piesă la u) mome)tat. 6) mome)tul ) /are o paletă evi)e liberă *au #ost preluatetoate piesele e pe ea- ea este re/i/lată la i)trarea sistemului )sto/ul /orespu)zător. +upă prelu/rarea pe mai)ile 1 irespe/tiv 2 piesele e tip % su)t epuse automat ) bu##erul B1

*e /apa/itate 3 piese- iar piesele e tip B su)t epozitateautomat ) bu##erul B2 e /apa/itate !. ai)a 3 realizeazăoperaia e asamblare a u)ei piese % i a ouă piese B ) ori)eaB%B. 6)/ăr/area mai)ii 3 se #a/e automat i) bu##erele B1 iB2. Piesele asamblate su)t epuse )tru) sto/ e /apa/itate 3 /arese "olete automat /;) se umple.

Să se /o)struias/ă reeaua Petri a a/estui sistem ast#el )/;t ea să #iemăr"i)ită.

8/9/2019 Curs Mssed


$2 Modelarea şi analiza SDED – 103 probleme

1 *1-

B%

2 *1-

3

R 1

BB

B1 B2

B % B

?% ?B

R 2

,9/- ?ie ouă mai)i ie)ti/e 1 i 2 e /apa/itate 1 /are prelu/rează piese e u) si)"ur tip. Piesele su)t preluate i)tru) sto/ i)#i)it /e/o)i)e palete e /;te 2 obie/te */u 2 poziii- i )/ăr/ate pemai)i e /ătre robotul R 1. 6)/ăr/area mai)ilor 1 i 2 se #a/e

pri) alter)a)ă4 prima mai)ă )/ăr/ată #ii) 1. Robotul R 2 preia piesele prelu/rate e pe mai)ile 1 i 2 i le )/ar/ă pe mai)a3. Capa/itatea mai)ii 3 este e 2 piese.

Să se moeleze /u RP a/est sistem tii) /ă ieirea este #ără restri/ii.Să se "ăseas/ă i)varia)ii e mar/aG.

8/9/2019 Curs Mssed


e=ele >etri $3

R 1

1*1- 2*1-

R 2

3*2-

,90- Celula e #abri/aie i) #i"ură prelu/rează ouă tipuri e piese p1

i p2 /are se "ăses/ ) )umăr )elimitat la i)trarea ) sistem.Piesele su)t mai )t;i prelu/rate alter)ativ pe mai)a 1 *e

/apa/itate 1-4 prima ată e8e/ut;)use prelu/rarea u)ei piese etip p1. +upă termi)area operaiei4 mai)a 1 este es/ăr/ată e/ătre robotul R 1 /are epu)e piese e tip p1 )tru) epozit +p1 i

piese e tip p2 )tru) epozit +p2. Cele ouă epozite +p1 i +p2

au /apa/itate limitată i a)ume 5 i respe/tiv poziii *lo/uri-.Robotul R 2 )/ar/ă mai)a 2 /u piese e tip p1 i) epozitul +p1

i )/ar/ă mai)a 3 /u piese e tip p2 i) epozitul +p2.Capa/itatea mai)ii 2 este e 2 piese4 iar a mai)ii 3 e osi)"ură piesă. Piesele prelu/rate pe mai)a 2 su)t es/ăr/ate e/ătre robotul R 2 la ieirea sistemului. 6) urma operaiei e

prelu/rare pe mai)a 3 piesele e tip p2 su)t es/ăr/ate automat pe /ăru/iorul %^ /are poate tra)sporta /;te 2 piese la ieireasistemului.

Să se /o)struias/ă moelul Petri temporizat al /elulei4 /o)sier;) /ă#ie/are operaie e prelu/rare urează 1 u)ităi e timp *pe #ie/aremai)ă- i #ie/are operaie e tra)s#er *)/ăr/are4 es/ăr/are4tra)sport- urează 2 u)ităi e timp at;t pe)tru roboi /;t i pe)tru/ăru/ior.

8/9/2019 Curs Mssed


$! Modelarea şi analiza SDED – 103 probleme

P1 P2

R 1

1

23Cap2 Cap1

Cap5 Cap

+p1 +p2

R 2

%^

8/9/2019 Curs Mssed


e=ele >etri $5

(I(LIO@RA3IE

1. Cassa)ras C.4 (a#ortu)e S.4 <ntroduction to Discrete Event S/stems4gluder %/aemi/ Publis:ers4 (o)ra4 septembrie 1EEE.

2. +avi R.4 %lla h. Du Gra5cet au eseau de >etri4 ,. hermes4 Paris41EE7.

3. Stă)es/u %.. /ole/tiv Sisteme Dinamice cu Evenimente Discrete4UPB4 1EE

4. Szar#a/z[ . – ComputerF#ssisted Manaement and Control o5 Manu5acturin S/stems" Spri)"er ^erla" (o)o) (imite 1EE7.

Curs Mssed

Documents

Transcript of Curs Mssed