Stage de Master 2 au LIP6
Forum 'Stages' - Sujet créé le 2008-11-24
Sujet de stage de Master M2 : Evaluation du débit maximum pour un réseaux à choix libres.
Responsables : Alix MUNIER KORDON, Alix.Munier@lip6.fr et Olivier MARCHETTI, Olivier.Marchetti@lip6.fr
Sujet : Les réseaux de Petri T-temporisés ou P-temporisés permettent de modéliser le comportement de nombreux systèmes dynamiques. A titre d'exemple, ils peuvent être utilisés pour la modélisation de l'exécution d'une application temps réel embarquée qui interagit avec son environnement physique.
Résoudre efficacement le problème de la vivacité et du calcul du débit maximum est un point crucial pour tout outil de conception de ces systèmes. Ces deux problèmes sont polynomiaux dans le cas d'un graphe d'évènements (il s'agit d'une sous-classe de réseau de Petri où toute place a exactement une transition en entrée et une transition en sortie)[1]. Cependant, cette sous-classe de réseau de Petri est très restrictive par rapport aux applications visées.
Le but de ce stage est d'étudier un algorithme pour évaluer la vivacité et calculer le débit maximum d'un réseau de Petri à choix libre : il s'agit d'une sous-classe plus large de réseau de Petri qui permet de modéliser la notion de choix et qui a été largement étudiée [2]. Un algorithme a récemment été publié pour évaluer le débit maximum de cette classe de réseau en utilisant un formalisme algébrique [3]. Le but de ce stage est de plonger ce résultat dans un formalisme de graphes si cela est possible et d'en déduire un algorithme de complexité minimale.
Pré-requis : de bonnes connaissances en algèbre, théorie des graphes et algorithmique sont indispensables.
Conditions du stage : le stage doit avoir lieu au département SoC du LIP6, 4 place Jussieu, 75252 Paris cedex 05. Sa durée est de 4 à 6 mois.. Une rémunération de l'ordre de 800 Euros par mois est envisagée.
Bibliographie :
[1] Philippe. Chrétienne, . Les Réseaux de Petri Temporisés, thèse d'état, université Paris VI, Paris, 1983.
[2] Jorg Desel, Javier Esparza, Free Choice Petri Nets, Cambridge Tracts in Theoretical Computer Science, number 40, september 2005.
[3] Anne Bouillard, Brune Gaujal et Jean Mairesse, Extremal throughputs in free-choice nets, Journal of Discrete Event Dynamic Systems, Vol 16(3), 2006, p.327-352.
Responsables : Alix MUNIER KORDON, Alix.Munier@lip6.fr et Olivier MARCHETTI, Olivier.Marchetti@lip6.fr
Sujet : Les réseaux de Petri T-temporisés ou P-temporisés permettent de modéliser le comportement de nombreux systèmes dynamiques. A titre d'exemple, ils peuvent être utilisés pour la modélisation de l'exécution d'une application temps réel embarquée qui interagit avec son environnement physique.
Résoudre efficacement le problème de la vivacité et du calcul du débit maximum est un point crucial pour tout outil de conception de ces systèmes. Ces deux problèmes sont polynomiaux dans le cas d'un graphe d'évènements (il s'agit d'une sous-classe de réseau de Petri où toute place a exactement une transition en entrée et une transition en sortie)[1]. Cependant, cette sous-classe de réseau de Petri est très restrictive par rapport aux applications visées.
Le but de ce stage est d'étudier un algorithme pour évaluer la vivacité et calculer le débit maximum d'un réseau de Petri à choix libre : il s'agit d'une sous-classe plus large de réseau de Petri qui permet de modéliser la notion de choix et qui a été largement étudiée [2]. Un algorithme a récemment été publié pour évaluer le débit maximum de cette classe de réseau en utilisant un formalisme algébrique [3]. Le but de ce stage est de plonger ce résultat dans un formalisme de graphes si cela est possible et d'en déduire un algorithme de complexité minimale.
Pré-requis : de bonnes connaissances en algèbre, théorie des graphes et algorithmique sont indispensables.
Conditions du stage : le stage doit avoir lieu au département SoC du LIP6, 4 place Jussieu, 75252 Paris cedex 05. Sa durée est de 4 à 6 mois.. Une rémunération de l'ordre de 800 Euros par mois est envisagée.
Bibliographie :
[1] Philippe. Chrétienne, . Les Réseaux de Petri Temporisés, thèse d'état, université Paris VI, Paris, 1983.
[2] Jorg Desel, Javier Esparza, Free Choice Petri Nets, Cambridge Tracts in Theoretical Computer Science, number 40, september 2005.
[3] Anne Bouillard, Brune Gaujal et Jean Mairesse, Extremal throughputs in free-choice nets, Journal of Discrete Event Dynamic Systems, Vol 16(3), 2006, p.327-352.