[DUS | Cvičenie] 3 - Graf dosiahnutelnosti, Strom pokrytia

Zhrnutie prednášky

Cvičenie sa venuje konštrukcii grafu dosiahnuteľnosti (a nadväzne stromu pokrytia) v Petriho sieťach ako systematickému spôsobu prehľadania všetkých dosiahnuteľných značkovaní z počiatočného stavu. Vysvetľuje sa, že vrcholy grafu predstavujú konkrétne značkovania a hrany reprezentujú prechody, ktorými sa z jedného značkovania dostaneme do druhého, pričom sa vychádza z algoritmu prezentovaného na prednáške. Ukazujú sa dva spôsoby zápisu značkovaní – sčítanie miest s ich počtom značiek (A+B) alebo vektorový zápis – s výhodami a nevýhodami oboch pri porovnávaní stavov. Postup sa demonštruje krok po kroku na konkrétnej sieti so siedmimi miestami, kde sa postupne generujú nové vrcholy a hrany podľa spustiteľných prechodov z každého neoznačeného značkovania. Na záver cvičenia zaznievajú aj organizačné informácie o blížiacej sa prvej zápočtovej písomke vrátane jej obsahu a technických požiadaviek.

• - Graf dosiahnuteľnosti systematicky zachytáva všetky stavy (značkovania) dosiahnuteľné z počiatočného značkovania.
• - Vrcholy grafu reprezentujú značkovania, hrany reprezentujú prechody medzi nimi.
• - Existujú dva spôsoby zápisu značkovaní: sčítanie miest (A+B) alebo vektorový zápis počtu značiek v jednotlivých miestach.
• - Vektorový zápis uľahčuje vizuálne porovnávanie značkovaní, zápis s pluskami je rýchlejší pri málo značkách.
• - Algoritmus postupne spracúva neoznačené vrcholy, generuje nové značkovania podľa spustiteľných prechodov a pridáva ich do grafu.
• - Na písomke sa vyžaduje ručné kreslenie grafu dosiahnuteľnosti.
• - Prvá zápočtová písomka bude o dva týždne, obsahovať bude aj teoretické otázky (cca 10% hodnotenia) a vyžaduje prihlásenie cez školský Google účet.

Zhrnutie pripravené s pomocou AI z prepisu videa.