Název:

Teoretická informatika 2

Zkratka:TI2
Ak.rok:ukončen 2005/2006
Semestr:letní
Studijní plán:
ProgramOborRočníkPovinnost
EI-BC-3VTB2.st/2.rčvolitelný
EI-MGR-3VTN2.povinně volitelný - skupina M
EI-MGR-5VTI2.st/3.rčpovinně volitelný - skupina M
Vyučovací jazyk:čeština
Informace veřejné:http://www.fit.vutbr.cz/study/courses/TI2/public/
Kredity:6 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:39001214
 zkouškatestycvičenílaboratořeostatní
Body:60200020
Garant:Češka Milan, prof. RNDr., CSc., UITS
Přednášející:Češka Milan, prof. RNDr., CSc., UITS
Cvičící:Marek Vladimír, Ing., UITS
Novosad Petr, Ing., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Prerekvizity: 
Modelování a simulace (MSI), UITS
Teoretická informatika 1 (TI1), UITS
 
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í.
Anotace:
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.
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í.
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ů.
Osnova přednášek:
  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, reprezentace vlastností výrokovou logikou, 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.
Osnova počítačových cvičení:
  1. Práce s počítačovými nástroji pro analýzu a verifikaci na základě nízkoúrovňových Petriho sítí (INA, LoLA, PEP, Pesim) - 2 cvičení.
  2. Počítačové nástroje pro formální analýzu a verifikaci nad modely popsanými pomocí modelovacích jazyků jiných než Petriho sítě (Spin, Uppaal).
  3. Počítačové nástroje pro simulaci, analýzu a verifikaci na základě barvených/vysokoúrovňových Petriho sítí (Design/CPN, PROD, Renew) - 2 cvičení.
  4. Počítačové nástroje pro simulaci, analýzu a verifikaci na základě objektově orientovaných Petriho sítí (PNtalk). ˙
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í.
Literatura referenční:
  1. Reisich W.: Petri nets, Springer Verlag 1985
  2. Jensen K.: Coloured Petri nets, Springer Verlag 1993
  3. Češka M.: Petriho sítě, Akad.nakl. CERM,Brno 1994
Literatura studijní:
  1. Reisich W.: Petri nets, Springer Verlag 1985
  2. Jensen K.: Coloured Petri nets, Springer Verlag 1993
  3. Češka M.: Petriho sítě, Akad.nakl. CERM, Brno 1994
Kontrolovaná výuka:
Písemná půl semestrální zkouška, průběžná kontrola a hodnocení projektů.
Průběžná kontrola studia:
Bodové hodnocení výsledků půl semestrální zkoušky a vypracovaného projektu.