Remerciez-le!

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

Master 1 IF, ENS de Lyon Évaluation de performance 14 décembre 2011 TD 11 : Rés

Master 1 IF, ENS de Lyon Évaluation de performance 14 décembre 2011 TD 11 : 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) ⩾1 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 1 Donner l’évolution des réseaux de Pétri suivants. Quelles propriétés les distinguent ? Exercice 2 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. 1. choix non déterministe 2. addition du nombre de jetons situés dans deux places 3. soustraction d’une constante 4. multiplication par une constante 5. division par une constante 6. un compteur binaire 7. le schéma d’attente d’une ﬁle G/D/1 et d’une ﬁle G/D/C 8. un réseau de Jackson fermé cyclique (lorsqu’on quitte on ﬁle, on entre dans la suivante) 1/5 Master 1 IF, ENS de Lyon Évaluation de performance 14 décembre 2011 Exercice 3 (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. 1. Comment caractériser les réseaux M-bornés en terme de marquages accessibles ? 2. En déduire un algorithme pour déterminer si un réseau de Pétri est M-borné. Quel est sa complexité ? 3. 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 4 (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 = A0 ⊗Xn ⊕A1 ⊗Xn−1 ⊕· · · ⊕AK ⊗Xn−K où les Xi sont des vecteurs et les Aj sont des matrices sur le semi-anneau (max,plus). 1. Par analogie avec le cas des récurrences n-linéaires usuelles, exprimer cette récurrence sous forme d’une chaîne de Bellman, i.e. d’une récurrence à un pas. On peut voir les chaînes de Bellman comme l’analogue des chaînes de Markov pour les semi- anneaux. Quelle hypothèse faut-il faire sur A0 ? 2. Rappeler l’équation (max,plus) qui permet de calculer le dateur dτ(n) qui donne la date du ne tirage de la transition τ. De même, donner l’équation (min, plus) qui exprime le compteur nτ(t) donnant le nombre de tirages de la transition τ dans l’intervalle [0, t]. 3. Réciproquement, comment associer un graphe d’événements temporisé à une récurrence (max,plus)-linéaire ? On rappelle qu’un graphe d’événements temporisé est un graphe d’événements muni d’une fonction de retard σ : P →R+. L’apparition d’un jeton dans la place p lorsqu’on tire la transition •p est alors retardée de σ(p). 4. Les équations précédentes déﬁnissent une récurrence (max,plus) linéaire matricielle pour le dateur et (min, plus) pour le compteur. Le comportement asymptotique d’une chaîne de Bellman est donné par le résultat suivant : Il existe λ ∈R+, d ∈N et N ∈N tels que pour tout n ⩾N, A⊗(n+d) = λd ⊗A⊗n. Comment ce résultat se traduit-il concrètement pour le graphe d’événements temporisé dont le dateur est décrit par la ma- trice A ? 5. En examinant les « transitions limitantes » du graphe d’événements, donner la signiﬁcation des paramètres λ, d et N dans le résultat de la question précédente. Exercice 5 (Accessibilité) 1. Dans le cas général, le problème de l’accessibilité est EXPSPACE-diﬃcile. Donner un semi-algorithme pour le résoudre. 2. Montrer que si l’on retire la contrainte de positivité du marquage, alors on peut résoudre le problème de l’accessibilité en temps polynomial avec des outils d’algèbre linéaire. En déduire une méthode de preuve d’inaccessibilité. 2/5 Master 1 IF, ENS de Lyon Évaluation de performance 14 décembre 2011 Solutions ▶Exercice 1 Leurs diﬀérences sont : – la présence ou l’absence d’interbloquages (l’existence d’une exécution inﬁnie) – l’existence ou non de concurrence (plusieurs transitions qui s’excluent mutuellement) – l’explosion du nombre de jetons ▶Exercice 2 1. 3/5 Master 1 IF, ENS de Lyon Évaluation de performance 14 décembre 2011 2. n m 3. n n-1 Il suﬃt de savoir faire la décrémentation (ci-dessus) puis d’itérer. 4. n K n .... .... K fois 5. n K fois .... .... .... Si on renverse simplement les arcs de la multiplication, on ob- tient un réseau qui peut eﬀectuer la division mais pas sur toutes ses exécutions. On utilise donc un jeton circulant pour n’au- toriser qu’une unique transition à chaque étape. 6. .... n n/2 On utilise une succession de division par deux. Le jeton circu- lant devient alors un cas particulier de la méthode de l’exercice 3 pour borner une place. 7. On ne représente ici que deux contraintes : – une unique personne par serveur – les arrivées sont exogènes d’où l’utilisation d’une transition sans prédécesseur (transition de contrôle) qui peut donc être tirée à tout instant 8. La sortie d’une ﬁle est l’entrée de la suivante donc il n’y a pas besoin de transition de contrôle. ▶Exercice 3 1. Les réseaux de Pétri bornés n’ont qu’un nombre ﬁni de marquages accessibles, borné par (M + 1)|P|. 2. Il suﬃt de calculer l’ensemble des conﬁgurations accessibles. Si cet ensemble est de cardinal trop grand ou qu’une coordonnée d’un marquage accessible dépasse la borne, alors il n’est pas M-borné. En fait, la seconde condition se produira toujours avant la première (ou au pire au même moment), de sorte qu’elle est suﬃsante pour déﬁnir l’algorithme. 3. Pour chaque place p, on ajoute une contre-place p telle que t ∈•p ⇐⇒ t ∈p• et t ∈p• ⇐⇒ t ∈•p, i.e. on inverse le sens d’interaction des transitions voisines de p. Le marquage initial de p vaut µ0(p) = M −µ0(p). On a alors l’invariant µ(p) + µ(p) = M et la condition de positivité d’un marquage assure la M-bornitude. ▶Exercice 4 1. La méthode usuelle de résolution des systèmes n-linéaires consiste à isoler x : (1 −a0)xn = a1xn−1 · · · + aKxn−K ⇐⇒ xn = a1xn−1 · · · + aKxn−K 4/5 Master 1 IF, ENS de Lyon Évaluation de performance 14 décembre 2011 avec ai = (1 −a0)−1ai. Dans ce cas, on représente les xi par un vecteur X = (xn, . . . , xn−K+1). L’équation se représente ma- triciellement par Xn+1 = AXn avec A la matrice compagnon des ai :                  a1 . . . . . . aK 1 0 ... ... 1 0                  Évidemment, cela s’étend sans diﬃculté au cas où les ai sont des matrices et les xi des vecteurs. Dans le cas des semi-anneaux, il faut veiller à ne pas faire de soustraction. Ainsi, (I −A0)−1 s’écrit plutôt A∗ 0 = P k⩾0 Ak 0, sous réserve que cela aie un sens. Il faut par exemple que A0 soit triangulaire stricte, donc nilpotente, ce qui assure la convergence de la série. Au ﬁnal, on obtient une matrice compagnon (pour la multiplication à gauche) dont les coeﬃcients intéressants sont les Ai = AiA∗ 0 :                      A1 0 −∞ . . . ... . . . −∞ 0 AK                      2. Dans les deux cas, c’est la recherche du « jeton limitant » qui permet de trouver les équations. dp(τ) = max p′∈••p{dp′(n −µ(p)) + σ(p)} nτ(t) = µ(p) + min p′∈••p{np′(t −σ(p))} 3. L’originalité de cette traduction réside dans le fait que les états de la récurrence sont représentés par les transitions du graphe d’événements et les transitions de la récurrence (i.e. les coeﬃcients diﬀérents de −∞) par les places. – coordonnée k { transitions tk – coeﬃcient (Am)ij , ε { uploads/Ingenierie_Lourd/ corrige-td11.pdf