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 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 s

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