Archive for décembre 2007

Les réseaux de Petri

décembre 29, 2007

Le réseau de Petri est un outil de modélisation mathématique. Il a été introduit en 1962 dans la thèse de Carl Adam Petri. On le rencontre en informatique notamment dans les méthodes formelles et dans la modélisation des workflows.

Un réseau Petri est composé de deux types de noeuds : les places (notées S) et les transitions (notées T). Des arcs orientés (F) relient les places et les transitions. Il n’est pas possible de relier directement des places entre elles, même chose pour les transitions. C’est pourquoi on parle de graphe bipartite orienté.

En plus de S T et F, il faut ajouter trois autres éléments Mo, W et K à la définition du réseau de Petri. Mo est le marquage initial, le nombre de jetons dans les places. W est la consommation ou la production de jetons par un arc, consommation si l’arc va d’une place vers une transition et production dans le cas contraire. Attention au cours de l’évolution rien ne garantit que le nombre de jetons reste constant. Enfin K est la limite de capacité des places.

Même s’il est possible d’avoir une représentation graphique, le réseau de Petri est très formel. Le réseau est un 6 uplet (S,T,F,Mo,W,K). M est une fonction de S vers l’ensemble des entiers, W de F vers l’ensemble des entiers non nuls et K de S vers l’ensemble des entiers non nuls. Si à première vue tout cela peut paraître complexe, ce formalisme est très simple par rapport aux formalismes de modélisation des processus dans les outils de workflows.

Une simplification du modèle des réseaux de Petri aboutit aux automates finis. Une autre simplification est de ne tenir compte que des 4 premiers paramètre (S,T,F,Mo).

Je me place plus en tant qu’informaticien ou du moins utilisateur des mathématiques, je préfère donc la version graphique. J’ai trouvé une applet qui permet de construire et de simuler l’évolution des réseaux de Petri. Dans cette applet les transitions sont représentées par des carrés, souvent le formalisme est d’utiliser un trait.

L’exemple suivant est fait avec cette applet. J’appuie sur les transitions t1, t1, t2 et t2 pour obtenir ces résultats successifs.

Exemple d’utilisation de l’applet

Un blog en néerlandais sur Bruxelles

décembre 1, 2007

Si vous voulez lire un peu de néerlandais, je vous conseille le blog www.brusselblogt.be. Il s’agit d’un blog néerlandais concernant Bruxelles. Et oui, cette ville est (en théorie ?) bilingue. Sa petite région ne fait ni partie de la Flandre ni de la Wallonie mais forme la troisième région de la Belgique. Dans la pratique le néerlandais reste trop marginal. Bonne lecture !