Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrige td11 1 Master IF ENS de Lyon Évaluation de performance décembre TD Réseaux de Pétri lionel rieg ens-lyon fr Dé ?nition Réseau de Pétri Un réseau de Pétri est la donnée d ? un graphe orienté biparti P T E et d ? une fonction P ? N Les éléments de P

Master IF ENS de Lyon Évaluation de performance décembre TD Réseaux de Pétri lionel rieg ens-lyon fr Dé ?nition Réseau de Pétri Un réseau de Pétri est la donnée d ? un graphe orienté biparti P T E et d ? une fonction P ? N Les éléments de P sont appelés les places et ceux de T les transitions On note ? t et t ? respectivement les voisinages négatifs et positifs d ? une transition On dé ?nit de manière analogue ? p et p ? Lorsque chaque place a au plus une transition antécédent et une transition successeur le réseau est un graphe d ? événements et on peut noter ? p et p ? les uniques transitions précédant et suivant la place p si elles existent La quantité p est appelé marquage initial de p Elle dénote le nombre de jetons présents dans la place p On représente graphiquement les places par des cercles contenant des jetons et les transitions par des rectangles Dé ?nition Évolution d ? un réseau de Pétri Un réseau de Pétri évolue par déplacement des jetons entre les places selon les transitions Plus précisément une transition t est franchissable si ??p ?? ? t p et on e ?ectue une telle transition on dit qu ? on tire la transition en retirant un jeton de toutes les places de ? t et ajoutant un jeton dans toutes les places de t ? Exercice Donner l ? évolution des réseaux de Pétri suivants Quelles propriétés les distinguent Exercice Construire des réseaux de Pétri qui e ?ectuent les opérations suivantes Dans la mesure du possible essayer de se restreindre aux graphes d ? événements choix non déterministe addition du nombre de jetons situés dans deux places soustraction d ? une constante multiplication par une constante division par une constante un compteur binaire le schéma d ? attente d ? une ?le G D et d ? une ?le G D C un réseau de Jackson fermé cyclique lorsqu ? on quitte on ?le on entre dans la suivante CMaster IF ENS de Lyon Évaluation de performance décembre Exercice Réseaux de Pétri bornés Un marquage est dit accessible s ? il existe une évolution du réseau de Pétri vers ce marquage Un réseau de Pétri est dit M-borné si le nombre de jetons dans chaque place ne peut dépasser M Comment caractériser les réseaux M-bornés en terme de marquages accessibles En déduire un algorithme pour déterminer si un réseau de Pétri est M- borné Quel est sa complexité Déterminer une transformation entre réseaux de Pétri qui force une place d ? un réseau général à être M-bornée Justi ?er la correction de la transformation Exercice Récurrence max plus -linéaire et graphe d ? événements temporisé On considère une récurrence max plus -linéaire matricielle dont la forme générale est Xn A ? Xn ? A ? Xn ?? ? ? AK ? Xn ??K o? les Xi sont des vecteurs et les A j sont