Nombre d'étudiants : 1 binôme
Mots-clés :
vertex-vertex systems, modèles déclaratifs de calcul, subdivision de surface, algorithmique graphique.
Public visé : stage ENS, stage IIE, TER de maîtrise, stage Polytechnique.
Le projet MGS développe un langage de programmation original dédié à la modélisation et la simulation de processus biologiques à structure dynamique. Pour ce faire, MGS permet la représentation d'organisations complexes entre des entités variables et hétérogènes, ainsi que leur transformation par des règles locales. Ces travaux trouvent leurs inspirations dans les travaux de J. Von Neuman sur les automates cellulaires, A. Lindenmayer sur les L systèmes, G. Paun sur les P systèmes, G. Berry et al. sur la CHAM et la réécriture de multi-ensembles.
La structure de données fondamentale en MGS est la collection topologique. Une collection topologique est un ensemble d'éléments organisés par une relation de voisinage. Une transformation permet de spécifier de nouvelles fonctions sur les collections par des cas filtrant des sous-collections. Ces notions permettent d'unifier dans le même cadre formel les différents modèles de calculs cités plus haut. Pour chacun des modèles il suffit de choisir le bon voisinage pour la collection utilisée. Un point remarquable est l'existence d'un langage de filtres, utilisé pour écrire les règles d'une transformation, qui est commun à tous les types de collection. Ce langage de filtres se fonde sur la notion de voisinage et de chemin.
Les vertex-vertex systems sont une structure de données introduites par PRZEMEK PRUSINKIEWICZ pour spécifier et implémenter des algorithmes de subdivision de surfaces. Traditionnellement, les algorithmes de subdivisions de surfaces sont des algorithmes globaux et impératifs qui nécessitent une manipulation très complexes de schémas d'indices. Grâce à la définition des vv-systems, on peut prendre un point de vue local sur les transformations qui conduisent à grandement simplifier l'expression des algorithmes de subdivision.
La structure de données sous-jacente aux vv-systems est un graphe dont les
arêtes 
adjacentes à un sommet 
sont orientées : du sommet , une
relation suivant permet de passer d'une arête à une arête
. MGS disposant déjà de la structure de données de graphe,
l'intégration des vv-systems en MGS ne devrait pas poser de problèmes majeurs. Le
travail consiste en l'intégration de la structure de données des
vv-systems dans MGS ainsi que des algorithmes de subdivision classiques
(Polyhédrale, Loop, Butterfly, 
).
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 sujet.tex
The translation was initiated by A.SPICHER (These Specif) on 2003-12-02
@ReMoVeMeFIRST.lami.univ-evry.fr.
Des informations supplémentaires sont disponibles à partir de
la page : http://mgs.lami.univ-evry.fr