460-4146/01 – Petriho sítě (PES)
Garantující katedra | Katedra informatiky | Kredity | 4 |
Garant předmětu | doc. Mgr. Pavla Dráždilová, Ph.D. | Garant verze předmětu | doc. Mgr. Pavla Dráždilová, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný typu A |
Ročník | 1 | Semestr | zimní |
| | Jazyk výuky | čeština |
Rok zavedení | 2022/2023 | Rok zrušení | |
Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Porozumět základním pojmům a metodám systémového modelování pomocí Petriho sítí. Naučit se používat Petriho sítě při řešení problémů spojených s návrhem, analýzou a verifikací složitých systémů. Získat základní praktickou zkušenost s programovými nástroji pro práci s Petriho sítěmi.
Dovednost reprezentovat a navrhovat diskrétní systémy s bohatou strukturou, s distribuovanými stavy a s paralelními procesy pomocí modelů ve tvaru Petriho sítí.
Schopnost analyzovat tyto systémy prostředky teorie Petriho sítí (metody stavového prostoru, algebraické metody, kompoziční metody).
Při práci s Petriho sítěmi umět používat programové nástroje podporujícími návrh, editaci, simulaci a formální analýzu Petriho sítí.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Projekt
Anotace
Petriho sítě jsou jedním z nejpoužívanějších nástrojů pro modelování a návrh složitých systémů s paralelními procesy, distribuovanými stavy a hierarchickou strukturou. Mají mnoho aplikací v oblasti byznys modelování, paralelního programování, operačních systémů, distribuovaných databází a řízení složitých procesů jakéhokoliv druhu. Přednáška seznamuje se základním pojmovým aparátem a metodami teorie Petriho sítí a s metodikou použití této teorie při praktickém návrhu a modelování informačních systémů. Výuka klade důraz na rozvoj schopnosti přecházet od výchozího neformálního slovního popisu systému k jeho formálně přesné a přitom názorné (grafické, síťové) reprezentaci.
Povinná literatura:
1. MARKL, J.: Petriho sítě I. Učební texty v elektronické podobě, VŠB-TU Ostrava, http://drazdilova.cs.vsb.cz/Data/Sites/5/petrinet/petrinetsylabus.pdf
2. REISIG, W.: Understanding Petri Nets, Springer-Verlag, 2013.
Doporučená literatura:
1. K. Jensen, G. Rozenberg: High-level Petri nets: theory and application. Springer Science & Business Media, 2012.
2. R.David, H.Alla: Petri Nets and Grafcet /Tools for modelling discrete event systems/. Prentice Hall Ltd., 1992.
3. W.Resig-G.Rozenberg (Eds.): Lectures on Petri Nets I: Basic Models, LNCS 149, Springer, 1998.
4. W.Resig-G.Rozenberg (Eds.): Lectures on Petri Nets II: Applications, LNCS 1492, Springer, 1998.
5. M.A.Marsan, G.Balbo, G.Conte, S.Donatelli, G.Franceschinis: Modelling with Generalised Stochastic Petri Nets. John Wiley & Sons, 1995.
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Průběžná kontrola studia:
Problémy zadávané ve cvičení k samostatnému (domácímu) řešení.
Práce s programovými nástroji volně dostupnými na webu pro práci s Petriho sítěmi.
Semestrálním práce - návrh Petriho sítě modelující reálný problém a její analýza - rozsah sítě je upřesněn po dohodě s přednášejícím. Prezentace semestrální práce.
Zápočtová písemka na konci semestru.
Podmínky udělení zápočtu:
Získání alespoň 12 bodů (z 25 možných) ze zápočtové písemky na konci semestru.
Získání alespoň 7 bodů (z 15 možných) za aktivitu během semestru (řešení zadaných úkolů, znalost práce s programovými nástroji, semestrální práce).
Bodové ohodnocení celého předmětu se skládá ze tří položek:
- Zápočtová písemka na konci semestru max 25 bodů (min 12 bodů),
- Semestrální práce max 15 bodů (min 7 bodů),
- Závěrečná písemná zkouška max 60 bodů (min 30 bodů).
E-learning
Studijní opory jsou dostupné v LMS studentům předmětu.
Další požadavky na studenta
Další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Problém analýzy, modelování a návrhu distribuovaných systémů se synchronizací, paralelismem a hierarchickou strukturou. Petriho sítě jako vhodný nástroj pro řešení tohoto problému.
2. Úvod do modelování pomocí Petriho sítí. P/T Petriho sítě. Petriho sítě s inhibičními hranami, s prioritami či resetovacími hranami.
3. Struktura a systém Petriho sítě. Statika a dynamika Petriho sítí. Stav (značení) a množina dosažitelných stavů PN-systému. Graf dosažitelnosti.
4. Stupeň proveditelnosti přechodu a relace definované na množině všech přechodů: konflikt, souběžnost, kauzalita, exkluzivita, konfúze.
5. Vlastnosti Petriho sítí: omezenost, bezpečnost, živost, neexistence uzamčení, reverzibilita, konzervativnost. Stavová analýza Petriho sítí pomocí grafu dosažitelnosti či pokrytí.
6. Strukturní analýza Petriho sítí. Metody grafové a metody algebraické. Zámky a pasti. Fundamentální rovnice.
7. P-invarianty a konzervativní komponenty sítě. T-invarianty a repetiční komponenty sítě. Duální Petriho sítě.
8. Speciální typy Petriho sítí: automatové sítě, synchronizační sítě a sítě s volným výběrem.
9. Syntéza bezpečných, živých a reverzibilních Petriho sítí. Jednoduchá hierarchizace metodou substituce míst a přechodů.
10. Jazyky Petriho sítí a jejich vztah k Chomského hierarchii jazyků.
11. Úvod do modelování pomocí Petriho sítí vyšší úrovně. Časované Petriho sítě.
12. Barevné Petriho sítě.
13. Stavová analýza barevných Petriho sítí.
Cvičení:
1. Příklady modelování a návrhu systémů s paralelismem a hierarchickou strukturou pomocí Petriho sítí.
2. Příklady na P/T Petriho sítě a Petriho sítě s inhibičními hranami, Petriho sítě s prioritami.
3. Příklady na strukturu a systém Petriho sítě. Statika a dynamika Petriho sítí. Stav (značení) a množina dosažitelných stavů PN-systému. Konstrukce grafu dosažitelnosti či pokrytí.
4. Příklady na stupeň proveditelnosti přechodu a relace definované na množině všech přechodů: konflikt, souběžnost, kauzalita, exkluzivita, konfúze.
5. Příklady na určení vlastností Petriho sítí: omezenost, bezpečnost, živost, neexistence uzamčení, reverzibilita, konzervativnost. Problém dosažitelnosti a problém pokrytí. Stavová analýza Petriho sítí.
6. Příklady na strukturní analýzu Petriho sítí. Metody grafové a metody algebraické. Zámky a pasti. Fundamentální rovnice.
7. Určení P-invariantů a konzervativních komponent sítě. Určení T-invariantů a repetičních komponent sítě. Duální Petriho sítě. Analýza Petriho sítí na základě P(T)-invariantů.
8. Příklady speciálních typu Petriho sítí: automatové sítě, synchronizační sítě a sítě s volným výběrem.
9. Příklady na syntézu bezpečných, živých a reverzibilních Petriho sítí. Jednoduchá hierarchizace metodou substituce míst a přechodů.
10. Generování a rozpoznávání jazyků Petriho sítí.
11. Příklady na speciální rozšíření pojmu Petriho sítě: časované Petriho sítě. CPN tool jako nástroj pro editaci, simulaci a analýzu barevných Petriho sítí.
12. Příklady barevných Petriho sítí.
13. Příklady na stavovou analýzu barevných Petriho sítí.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky