Reţea Petri
De la Wikipedia, enciclopedia liberă
Retelele Petri reprezintă o reprezentare matematică a sistemelor discrete distribuite. Definite de către Carl Adam Petri in anii 1960 in teza sa de doctorat, reţelele Petri au abilitatea de a generaliza teoria automatelor, prin expresivitatea lor ridicată în domeniul evenimentelor concurente.
Cuprins |
[modifică] Elemente componente
O reţea petri este alcătuită din POZITII, TRANZIŢII şi ARCE ORIENTATE. Arcele asociază o tranziţie unui loc şi viceversa. Nu exista arce între două locuri şi nici între două tranziţii. Locurile pot conţine un număr variabil de jetoane. Tranziţiile se produc consumând jetoane din locurile de intrare şi producându-le în cele de ieşire. O tranziţie se numeşte activă în momentul în care conţine jetoane în fiecare din intrările sale.
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 (Colored Petri Nets, engl), 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ţă (en: 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
- en Petri Nets World
- en Petri Net Markup Language
- en exchangeable Routing Language
- en Citate de pe CiteSeer
[modifică] Referinţe
Notă: Articolul este tradus şi adaptat după versiunea în limba engleză