Fakulta informačních technologií VUT v Brně

Detail předmětu

Teoretická informatika 2

TI2 Ak. rok 2005/2006 letní semestr 6 kreditů

Základy teorie Petriho sítí, problémy analýzy Pertiho sítí, bezpečnost, omezenost, konzervativnost, živost, metody analýzy, jazyky Petriho sítí, 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.

Garant předmětu

Jazyk výuky

česky

Zakončení

zkouška (písemná)

Rozsah

39 hod. přednášky, 12 hod. pc laboratoře, 14 hod. projekty

Bodové hodnocení

60 zkouška, 20 půlsemestrální test, 20 projekty

Zajišťuje ústav

Přednášející

Cvičící

Marek Vladimír, Ing. (UITS FIT VUT)
Novosad Petr, Ing. (UITS FIT VUT)

Získané dovednosti, znalosti a kompetence z předmětu

Získané a 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í lze přenášet postupy této teorie i do jiných tříd formálních modelů.

Dovednosti, znalosti a kompetence obecné

Na základě získaných teoretických znalostí lze přenášet postupy této teorie i do jiných tříd formálních modelů.

Cíle předmětu

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í.

Prerekvizity

Požadované prerekvizitní znalosti a dovednosti

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í.

Literatura studijní

  • Reisich W.: Petri nets, Springer Verlag 1985
  • Jensen K.: Coloured Petri nets, Springer Verlag 1993
  • Češka M.: Petriho sítě, Akad.nakl. CERM, Brno 1994

Literatura referenční

  • Reisich W.: Petri nets, Springer Verlag 1985
  • Jensen K.: Coloured Petri nets, Springer Verlag 1993
  • Češka M.: Petriho sítě, Akad.nakl. CERM,Brno 1994

Osnova přednášek

  • Úvod, filozofie, historie a aplikace Petriho sítí, pojem sítě a odvozených základních pojmů.
  • 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ů.
  • Bezkontaktní C/E systémy, komplementace, případové grafy a jejich aplikace pro analýzu C/E systémů.
  • Procesy C/E systémů, relace podobnosti a její oblasti, výskytové sítě, vlastnosti procesů a jejich kompozice.
  • Vlastnosti C/E systémů, pojem synchronizační vzdálenosti, speciální synchronizační vzdálenosti, reprezentace vlastností výrokovou logikou, fakta.
  • P/T Petriho sítě, definice, evoluční pravidla, stavový prostor, základní problémy analýzy (bezpečnost, omezenost, konzervativnost, živost).
  • 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í.
  • Pojem invariantu, P a T invarianty, definice, výpočet a využití invariantu pro analýzu P/T sítí.
  • 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ě.
  • 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).
  • 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).
  • Metody formální analýzy barvených Petriho sítí, výskytový graf, invarianty, využití v analýze systémů.
  • 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.

Osnova ostatní - projekty, práce

Sedm projeků, resp. domácích úloh z oblasti návrhu a analýzy nízkoúrovňových a vysokoúrovňových Petriho sítí.

Průběžná kontrola studia

Bodové hodnocení výsledků půl semestrální zkoušky a vypracovaného projektu.

Kontrolovaná výuka

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