Rețea Petri

Rețelele 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.

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.

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.

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.

Bibliografie

Tannenbaum, Andrew (2004). „Capitolul 3.5.2”. Rețele de calculatoare. Ediția a patra. Editura Byblos.

Legături externe

en Petri Nets World Arhivat în 2 noiembrie 2004, la Wayback Machine.
en Petri Net Markup Language Arhivat în 7 ianuarie 2010, la Wayback Machine.
en exchangeable Routing Language Arhivat în 9 decembrie 2004, la Wayback Machine.