Réseaux de Petri

Les réseaux de Petri sont des modèles mathématiques dont la structure sous-jacente est un graphe orienté avec deux types de sommets : les places (dessinées avec des ronds) et les transitions (dessinées avec des rectangles). Les places contiennent des jetons et une dynamique est associée au transitions : activer une transition mange des jetons dans les places en entrée et envoie des jetons dans les places en sortie. Ces modèles ont été introduits par C. Petri (rien à voir avec les boites du même nom) dans sa thèse en 1962 pour travailler sur la notion de concurrence dans les systèmes distribués (la légende dit qu'il les avait utilisé dès 1939 à 13 ans pour représenter des réactions chimiques). Ils sont depuis utilisés pour la modélisation dans de nombreux domaines scientifiques. Dans un article de synthèse, J. Peterson essaie d'expliquer leur succès : "The success of any model is due to two factors: its modeling power and its decision power. Modeling power refers to the ability to correctly represent the system to be modeled so that the model will be a faithful representation of the modeled system. Decision power refers to the ability to analyze specific versions of the model and determine properties of the modeled system." (J. Peterson, Computer Surveys, vol. 9, n. 3, 1977).

L'objectif de ce sujet est de faire une présentation des réseaux de Petri, en mettant en valeur les liens que vous trouverez avec la théorie et l'algorithmique des graphes. Voici quelques pistes pour vous guider :

Quelques références (pas exhaustif).

Retour à la page des sujets.