Sieć Petriego
Z Wikipedii
Sieć Petriego – matematyczna reprezentacja dyskretnych systemów rozproszonych. Sieci Petriego zostały zdefiniowane w latach 60. XX w. przez Carla Adama Petriego. Przez swoją zdolność do wyrażania współbieżnych zdarzeń uogólniają one teorię automatów.
Sieć Petriego w najprostszej wersji składa się z "miejsc", "tranzycji" oraz krawędzi skierowanych. Taką siecią można jedynie opisać układ jako statyczne połączenie możliwych do osiągnięcia stanów. Aby opisać konkretny stan układu, potrzebne są "żetony", które można przemieszczać pomiędzy miejscami poprzez przejścia, po krawędziach grafu. Tradycyjnie miejsce oznacza się okręgiem, w którym można umieścić żeton prezentowany przez koło. W jednym miejscu może znajdować się dowolna, nieujemna liczba żetonów. Tranzycje oznacza się prostokątami lub kreskami a krawędzie to strzałki. Krawędzie mogą mieć wagi większe lub równe 1. Wagi równej 1 nie oznacza się, tak jak pokazano na rysunku. Waga określa ile dokładnie żetonów przechodzi po krawędzi.
W najprostszej postaci, żetony w sieci Petriego są nierozróżnialne między sobą. Bardziej złożone postacie sieci Petriego korzystają z pojęć kolorowania żetonów, czasu aktywacji przejść oraz hierarchii. Poza nimi istnieje wiele innych różnych rozszerzeń Sieci Petriego, takich jak sieci obiektowe (z żetonami, które mogą być Sieciami Petriego), z ograniczonymi pojemnościami miejsc, łukami wzbraniającymi i inne.
Spis treści |
[edytuj] Aktywacja i odpalenie przejścia
Przejście może być aktywne lub nie. Przejście aktywne to takie, którego wszystkie krawędzie wejściowe połączone są z miejscami mającymi żetony w takiej ilości, że jest ona większa lub równa wadze odpowiednich krawędzi. Tylko przejście aktywne może być odpalone.
Odpalenie przejścia to zabranie z wszystkich miejsc wejściowych tylu żetonów, ile wynika z wag krawędzi łączących miejsca z przejściem. Następnie na miejscach wyjściowych połączonych z przejściem pojawiają się żetony. Ilość żetonów "wchodzących" i "wychodzących" z przejścia nie musi być taka sama. W jednym ruchu można odpalić tylko jedno przejście.
[edytuj] Praktyka stosowania i alternatywy
W praktyce można przyjąć, że miejsca z leżącymi w nich żetonami to chwilowe stany układu. Przejścia to przetwarzanie danych lub fizycznych materiałów a żetony to dane lub materiały.
Większość problemów przeznaczonych dla sieci Petriego można rozwiązać również konstruując drzewo Karpa-Millera (jak np. problem zakrywania).
[edytuj] Dziedziny zastosowań
- bioinformatyka
- analiza danych
- inżynieria oprogramowania
- organizacja pracy
- programowanie równoległe
[edytuj] Narzędzia programowania
- APE
- ARP
- CoopnTools
- CPN ML
- CPN Tools
- CPN-AMI
- DPNSchematic
- HiQPN-Tool
- HPSim
- Integrated Net Analyzer
- JARP
- JFern
- JPetriNet
- Maria
- Marigold
- Model-Checking Kit
- NEPTUN
- PED
- PEP
- Petri Net Browser
- Petri Net Kernel
- Petri Net Simulator
- PetriEdiSim
- Petrigen
- PetriSim
- Platform Independent Petri Net Editor
- PNES
- PNSF2VERILOG
- PNSim
- PNtalk
- Poseidon
- Poses++
- PROD
- Renew
- SEA
- SimPRES
- SimulaWorks
- SIPN-Editor
- StpnPlay
- Tina
- Visual Object Net++
- WebSPN
- WINSIM
- Woflan
- XPetri
- XRL
[edytuj] Bibliografia (po angielsku)
- Harald Störrle: Models of Software Architecture - Design and Analysis with UML and Petri-Nets, Books on Demand GmbH, ISBN 3-8311-1330-0.
- Robert-Christoph Riemann: Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus, Herbert Utz Verlag, ISBN 3-89675-629-X.
- Kurt Jensen: Coloured Petri Nets, Springer Verlag, ISBN 3-540-62867-3
- Janette Cardoso, Heloisa Camargo: Fuzziness in Petri Nets, Physica-Verlag, ISBN 3-7908-1158-0.
- James Lyle Peterson: Petri Net Theory and the Modeling of Systems, Prentice Hall, ISBN 0-13-661983-5.
- Mengchu Zhou, Frank Dicesare: Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic Publishers, ISBN 0-7923-9289-2.
- Mengchu Zhou: Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach, World Scientific Publishing Company, ISBN 981-02-3029-X.
- Iwan G. Tabakow: Fault Diagnosis of Discrete Event Systems Using Place Invariants, Springer Berlin / Heidelberg, ISBN 978-3-540-28895-4.
