Mots-clés :
champ de données, GBF, monoïde, tableau, graphe, langage régulier.
Public visé : DEA Informatique, stage Polytechnique, stage IIE, stage ENS.
Le projet MGS développe un langage de programmation original dédié à la modélisation et la simulation de systèmes dynamique à 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 cellulaire, 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.
Dans le langage MGS, les structures de données sont vues comme un moyen d'associer une valeur à un ensemble de positions. Cet ensemble est muni d'une organisation topologique (un type MGS) qui spécifie les voisins d'une position. Une telle structure est appelée un champ de données.
Le langage MGS introduit la notion de GBF2. Acronyme de « Group Based Fields », les GBF sont des champs de données dont l'organisation topologique est spécifiée par un groupe mathématique. Ce groupe représente les déplacements permis d'une position à une autre. L'organisation produite peut se visualiser à l'aide du graphe de Cayley du groupe : les positions sont les sommets du graphe et un arc relie un sommet à un autre s'il existe un mot du groupe (= un déplacement), qui permet de passer de l'un à l'autre.
L'exemple le plus naturel est celui des tableaux à 
dimensions : ce
sont des GBF dont le groupe est
(le groupe des -uplets
d'entiers relatifs muni de l'addition). Un arbre binaire est un GBF
sur le groupe libre à 2 générateurs, etc. Des exemples sont donnés à
partir de la page http://mgs.lami.univ-evry.fr/ mgs .
Dans ce stage, il s'agit de développer une notion de champ de données indexé par les éléments d'un monoïde. La structure de monoïde présente moins de contraintes que la structure de groupe et permet de représenter des topologies nouvelles. On s'interessera aux monoïdes libres puis aux constructions de quotient et de restriction. On étudiera le lien avec les notions de langage régulier et de graphe 3. On validera les propositions étudiées en montrant qu'elles permettent de définir de façon élégante diverses structures de données et qu'elles permettent l'expression concise de plusieurs algorithmes sur les graphes et les tableaux. Suivant le temps disponible, ces propositions seront validées par une implémentation.
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