Rețea Petri

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

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ă[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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.

Legături externe[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]

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