Detail předmětu

Petriho sítě

FIT-PESAk. rok: 2012/2013

Základní koncepty a prostředky popisu diskrétních systémů Petriho sítěmi, klasifikace Petriho sítí, teorie C/E Petriho sítí, metody analýzy C/E Petriho sítí, teorie P/T Petriho sítí, metody analýzy P/T Petriho sítí, jazyky Petriho sítí a problém automatizované syntézy modelů, podtřídy a rozšíření Petriho sítí, barvené Petriho sítě, hierarchické a objektově orientované Petriho sítě, nástroje pro práci s Petriho sítěmi, aplikace.

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

prof. RNDr. Milan Češka, CSc.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Výsledky učení předmětu

Získané vědomosti a dovednosti umožní aktivně využívat Petriho sítě a podpůrné počítačové nástroje při modelování, návrhu, verifikaci a implementaci široké třídy systémů. Na základě získaných teoretických znalostí je student schopen přenášet postupy této teorie i do jiných tříd formálních modelů.

Kompetence a schopnosti aplikovat a rozvíjet pokročilé informační technologie založené na vhodných formálních modelech systémů, vytvářet a využívat takové modely a teorie k automatizaci návrhu a verifikaci  implementace počítačových systémů.

Prerekvizity

Základní znalosti z binárních relací, teorie grafů a formálních jazyků včetně konečných a zásobníkových automatů, Turingových strojů, pojmů algoritmické složitosti a a principů počítačového modelování.

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Osnovy výuky

  1. Úvod, filozofie, historie a aplikace Petriho sítí, pojem sítě a odvozených základních pojmů.
  2. C/E Petriho sítě, případy a kroky, stavový prostor C/E systémů, cyklické a živé C/E systémy, ekvivalence C/E systémů.
  3. Bezkontaktní C/E systémy, komplementace, případové grafy a jejich aplikace pro analýzu C/E systémů.
  4. Procesy C/E systémů, relace podobnosti a její oblasti, výskytové sítě, vlastnosti procesů a jejich kompozice.
  5. Vlastnosti C/E systémů, pojem synchronizační vzdálenosti, speciální synchronizační vzdálenosti, C/E systémy a výroková logika, fakta.
  6. P/T Petriho sítě, definice, evoluční pravidla, stavový prostor, základní problémy analýzy (bezpečnost, omezenost, konzervativnost, živost).
  7. Reprezentace nekonečného stavového prostoru, strom dosažitelných značení, výpočet a využití stromu dosažitelných značení pro analýzu P/T sítí.
  8. Pojem invariantu, P a T invarianty, definice, výpočet a využití invariantu pro analýzu P/T sítí.
  9. Podtřídy a rozšíření P/T sítí, stavové stroje, značené grafy, P/T sítě s volným výběrem, sítě s inhibitory, časované a stochastické Petriho sítě.
  10. Pojem jazyka Petriho sítě, typy jazyků, uzávěrové vlastnosti jazyků Petriho sítí, vztah těchto jazyků k Chomského hierarchii (modelovací schopnost).
  11. Barvené Petriho sítě, základní vyjadřovací prostředky, inskripční jazyk, počítačový nástroj pro práci s těmito sítěmi (CPN Design).
  12. Metody formální analýzy barvených Petriho sítí, výskytový graf, invarianty, využití v analýze systémů.
  13. Hierarchické a objektově orientované Petriho sítě, prostředky hierarchického návrhu, substituce a invokace, začlenění prostředků objektově orientovaného návrhu, PNtalk jako jazyk pro práci s OO Petriho sítěmi.

Učební cíle

Pochopení základních konceptů a metod modelování systémů prostřednictvím Petriho sítí. Zvládnutí teorie Petriho sítí a její aplikace pro modelování, navrhování a verifikaci počítačových systémů. Praktické zvládnutí využívání počítačových nástrojů pro typické aplikace Petriho sítí.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů.

Prerekvizity a korekvizity

Základní literatura

Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8 Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3-540-60943-1 Girault, C., Valk, R.: Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications, Springer Verlag, 2002. ISBN 3-540-41217-4 Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4 Desel, J., Reisig, W., Rozenberg, G.: Lectures on Concurrency and Petri Nets, Advances in Petri Nets, Lecture Notes in Computer Science, č. 3098, Springer Verlag, 2004. ISBN 3-540-22261-8

Doporučená literatura

Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8 Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3-540-60943-1 Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-2 magisterský navazující

    obor MIN , 2 ročník, letní semestr, povinný
    obor MGM , 2 ročník, letní semestr, volitelný
    obor MIS , 2 ročník, letní semestr, povinně volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Milan Češka, CSc.

Osnova

  1. Úvod, filozofie, historie a aplikace Petriho sítí, pojem sítě a odvozených základních pojmů.
  2. C/E Petriho sítě, případy a kroky, stavový prostor C/E systémů, cyklické a živé C/E systémy, ekvivalence C/E systémů.
  3. Bezkontaktní C/E systémy, komplementace, případové grafy a jejich aplikace pro analýzu C/E systémů.
  4. Procesy C/E systémů, relace podobnosti a její oblasti, výskytové sítě, vlastnosti procesů a jejich kompozice.
  5. Vlastnosti C/E systémů, pojem synchronizační vzdálenosti, speciální synchronizační vzdálenosti, C/E systémy a výroková logika, fakta.
  6. P/T Petriho sítě, definice, evoluční pravidla, stavový prostor, základní problémy analýzy (bezpečnost, omezenost, konzervativnost, živost).
  7. Reprezentace nekonečného stavového prostoru, strom dosažitelných značení, výpočet a využití stromu dosažitelných značení pro analýzu P/T sítí.
  8. Pojem invariantu, P a T invarianty, definice, výpočet a využití invariantu pro analýzu P/T sítí.
  9. Podtřídy a rozšíření P/T sítí, stavové stroje, značené grafy, P/T sítě s volným výběrem, sítě s inhibitory, časované a stochastické Petriho sítě.
  10. Pojem jazyka Petriho sítě, typy jazyků, uzávěrové vlastnosti jazyků Petriho sítí, vztah těchto jazyků k Chomského hierarchii (modelovací schopnost).
  11. Barvené Petriho sítě, základní vyjadřovací prostředky, inskripční jazyk, počítačový nástroj pro práci s těmito sítěmi (CPN Design).
  12. Metody formální analýzy barvených Petriho sítí, výskytový graf, invarianty, využití v analýze systémů.
  13. Hierarchické a objektově orientované Petriho sítě, prostředky hierarchického návrhu, substituce a invokace, začlenění prostředků objektově orientovaného návrhu, PNtalk jako jazyk pro práci s OO Petriho sítěmi.

Cvičení na počítači

6 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Milan Češka, CSc.

Projekt

7 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Milan Češka, CSc.