Reţea Petri
De la Wikipedia, enciclopedia liberă
|
[[wiki]]
|
Acest articol sau această secţiune trebuie pus(ă) în formatul standard. Ştergeţi eticheta la încheierea standardizării. Acest articol a fost etichetat în martie 2006 |
Retelele Petri sunt o reprezentare matematică a sistemelor discrete distribuite. Definite de către Carl Adam Petri în anii 1960 în teza sa de doctorat, reţelele Petri au abilitatea de a generaliza teoria automatelor, prin expresivitatea lor ridicată în domeniul evenimentelor concurente.
Cuprins |
[modifică] Noţiuni de bază
O reţea petri este un graf orientat bipartit, ale cărui noduri sunt locuri sau tranziţii. Fiecare arc al acestui graf leagă un loc şi o tranziţie. Nu există arce între două locuri şi nici între două tranziţii. Dacă de la un loc L există un arc orientat spre o tranziţie T, atunci L este loc de intrare pentru T; invers, dacă arcul este orientat de la tranziţia T la locul L, atunci L este loc de ieşire pentru T. Locurile pot conţine un număr variabil de jetoane, iar întreaga distribuţie a jetoanelor în locurile reţelei se numeşte marcaj. Tranziţiile se produc consumând jetoane din locurile de intrare şi producându-le în cele de ieşire.
Execuţia unei reţele Petri este un proces nedeterminist. La execuţie, se analizează la fiecare pas tranziţiile active. O tranziţie se numeşte activă în momentul în care fiecare din locurile sale de intrare conţine cel puţin un jeton. Execuţia unei tranziţii presupune modificarea marcajului reţelei, prin eliminarea câte unui jeton din fiecare loc de intrare şi adăugarea câte unui jeton în fiecare loc de ieşire. O singură tranziţie se poate executa la un anumit pas
Reţelele Petri de o complexitate mai mare au capabilitatea de a introduce ierarhii în reţele.
[modifică] Reţele Petri colorate
Jetoanele într-o reţea Petri standard nu se disting între ele ca şi aparenţă vizuală. Pentru acest lucru se folosesc reţelele Petri colorate (în engleză Colored Petri Nets, deseori regăsite sub acronimul CPN). Activarea unei tranziţii este determinată în totalitate de prezenţa jetoanelor în locurile de intrare.
Reţelele Petri stocastice adaugă capacitatea de reprezentare a evenimentelor nedeterministe ca moment al producerii.
[modifică] Probleme reprezentabile prin reţele Petri
Marea majoritate a problemelor reprezentabile cu reţele Petri sunt deterministe (prezenţa unei soluţii poate fi anticipată prin aplicarea unui algoritm), cum are fi cazul problemelor de acoperire, rezolvate prin implementarea Arborelui Karp-Miller.
Problemele de prezenţă (în engleză reachability problem; determinarea dacă într-o reţea un anumit punct este accesibil) sunt cunoscute a fi deterministe dar implementările oferă timpi exponeţiali în rezolvări.
Mai multe despre aceste clase de probleme şi reprezentarea lor cu reţele Petri pot fi găsite aici cât şi în lucrarea lui Kurt Jensen, Coloured Petri Nets şi în cea a lui M. Ahmone Marsan et al. - Modelling with Generalized Stochastic Petri Nets.
[modifică] Legături externe
[modifică] Bibliografie
- Tannenbaum, Andrew (2004). “Capitolul 3.5.2”, Reţele de calculatoare, ediţia a patra, Editura Byblos.
