Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > Les séminaires du LIFO

 English Version



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 70 11
Fax: +33 (0)2 38 41 71 37



Les séminaires du LIFO


Accès par année : 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017

Sauf exception, les séminaires se déroulent le lundi de 14h à 15h, Salle de réunion 1, bâtiment IIIA (voir plan du campus).


18/12/2006 : Propagation de contraintes sur les intervalles ; application à la robotique.
Luc Jaulin (ENSIETA) Résumé

06/11/2006 : Missions et activités du service du SUReO
Sylvie Legroux, Leila Equinet (SUReO) Résumé

02/10/2006 : La programmation par contraintes "stochastique" : une approche pour la gestion de l?incertain dans la resolution de problemes ?
Lucas Bordeaux (Microsoft Research) Résumé

19/06/2006 : Sémantiques, extensions et implantation d'un langage fonctionnel pour la programmation BSP
Frédéric Gava (Paris 12) Résumé

22/05/2006 : Méthodes de rendu hybrides basées image et géométrie pour l'affichage en temps réel de scènes complexes.
Damien Porquet (Université de Limoges) Résumé

16/05/2006 : Semi-local string comparison and maximum cliques in circle graphs
Alexandre Tiskin (Université de Warwick) Résumé
Attention : Mardi à 14h en salle de réunion 1

03/05/2006 : Approximations automatiques pour la vérification de protocoles de sécurité
Olga Kouchnarenko (LIFC, INRIA CASSIS) Résumé
Attention : Mercredi 11h45 SR1

19/04/2006 : Model-checking pour les ambients
Jean-Marc Talbot (LIFL) Résumé
Attention : Mercredi 11h SR1

11/04/2006 : Représentation condensée et Contraintes pour la découverte de règles d'associations: vers une approche méta-cognitive
Enjalbert Mephu Nguifo () Résumé
Attention : Mardi à 14h en salle de réunion 1!

10/04/2006 : Graphes colorés, définitions et complexité des problèmes d'optimisation
Marie-Emilie Voge (INRIA, Sophia) Résumé

10/04/2006 : à venir
Arnaud Giacometti () Résumé
Attention : 11h-12h en salle de réunion 1

07/04/2006 : ELISE : un algorithme évolutionnaire pour la recherche documentaire
Pierre Collet () Résumé
Attention : Vendredi à 14h salle de réunion 1

27/03/2006 : Fouille de données et visualisation
François Poulet () Résumé

20/03/2006 : ANR-STIC: bilan 2005 et programmes 2006
Gaétan Hains (ANR) Résumé

13/03/2006 : Reduction strategies for left-linear term rewriting systems
Yoshihto Toyama (RIEC, Tohoku Universty) Résumé
Attention : Partie 1

13/03/2006 : Dealing with Non-Orientable Equations in Rewriting Induction
Takahito Aoto (RIEC, Tohoku Universty) Résumé
Attention : Partie 2

06/03/2006 : Analyse, conception et réalisation d'un environnement pour le pilotage et la visualisation en ligne de simulations numériques paralléles
Aurélien Esnard (LABRI) Résumé

27/02/2006 : Cellular automata and communication complexity
Ivan Rapaport (Santiago, Chili) Résumé

13/02/2006 : Configuration sous contraintes de graphes couplés
Denys Duchier (LIFO) Résumé

06/02/2006 : Pavages auto-assemblants: présentation et effet d'échelle.
Eric Rémila (LIP - ENS Lyon) Résumé

30/01/2006 : Promenades dans un monde hyperbolique
Maurice Margenstern (LITA (Metz)) Résumé

16/01/2006 : FlowVR: calculs interactifs et visualisation sur grappe
Jérémie Allard (Laboratoire ID (IMAG)) Résumé


Résumés des séminaires


Propagation de contraintes sur les intervalles ; application à la robotique. Luc Jaulin, ENSIETA

L'arithmétique des intervalles est un outil numérique permettant la résolution propre et efficace d'une grande classe de problèmes non-linéaires sur les domaines continus, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système d'équations non-linéaires. Contrairement aux méthodes numériques classiques (méthodes de Newton ou de MontéCarlo, par exemple), la solution est caractérisée avec une précision arbitraire, de façon globale et en un temps fini. Ceci s'applique même lorsque des fonctions trigonométriques ou non-continues apparaissent dans notre problème. Cependant, les méthodes par intervalles classiques deviennent difficilement applicables lorsque le nombre de variables devient élevé, (supérieur à 10 par exemple), principalement à cause de la complexité exponentielle des problèmes traités. L'utilisation de techniques de propagation de contraintes permet de repousser largement cette barrière et autorise ainsi le traitement de problèmes de plus grandes dimensions (supérieures à 1000 par exemple). Dans cet exposé je présenterai, tout d'abord, de façon brève et pédagogique les principes de base de l'arithmétique des intervalles et des techniques de propagation de contraintes sur les domaines continus. Ensuite, quelques applications du calcul par intervalles en robotique seront montrées, comme par exemple 1) la planification de chemin pour un robot mobile, 2) l'étude de la topologie d'un espace de configuration d'un robot, 3) et la localisation d'un sous-marin démineur.


Missions et activités du service du SUReO Sylvie Legroux, Leila Equinet, SUReO

à venir


La programmation par contraintes "stochastique" : une approche pour la gestion de l?incertain dans la resolution de problemes ? Lucas Bordeaux, Microsoft Research

La resolution de contraintes et l'optimisation (au sens, notamment, d' "optimisation combinatoire") sont des problemes fondamentaux en informatique - en fait la plupart des utilisations de l'ordinateur impliquant une forme d' « intelligence » reposent sur un probleme d'optimisation sous une forme ou sous une autre. L'expose commencera par un apercu de quelques domaines d'application de l'optimisation (scheduling, verification, vision, apprentissage). J'aborderai ensuite la gestion de l'incertain dans l'optimisation et la resolution de contraintes. Dans certaines applications, le processus de decision est rendu particulierement difficile par le fait que certaines donnees sont connues seulement de maniere estimee ou partielle. En particulier, raisonner sur certains problemes necessite de prendre en compte les consequences des decisions sur un futur qui, par definition, n'est pas totalement determine. Des donnes telles que « les ventes du produit au cours du prochain semestre », « le client acceptera notre offre », « la valeur du dollar samedi prochain » ou « l?heure a lequelle j?arriverai » sont des exemples de telles donnees imprecises car bases sur une prediction. La programmation par contraintes stochastique, proposee par Walsh, permet d?aborder ce type de problemes. Les recherches dans ce domaine manquent pour l?instant de maturite, et j?evoquerai un certain nombre de problemes que nous avons deceles dans cette approche, ainsi qu?un certain nombre de solutions a ces problemes. L'expose reposera sur des travaux menes en cooperation avec Youssef Hamadi, Claude-Guy Quimper et Horst Samulowitz


Sémantiques, extensions et implantation d'un langage fonctionnel pour la programmation BSP Frédéric Gava, Paris 12

Certains problèmes nécessitent des performances que seules les machines massivement parallèles peuvent offrir. L'écriture d'algorithmes pour ce type de machines demeure plus difficile que pour celles strictement séquentielles et la conception de langages adaptés est un sujet de recherche actif nonobstant la fréquente utilisation de la programmation concurrente. En effet, la conception d'un langage de programmation est le résultat d'un compromis qui détermine l 'équilibre entre les différentes qualités du langage telles que l'expressivité, la sûreté, la prédiction des performances, l'efficacité ou bien la simplicité de la sémantique. Ce travail s'inscrivait dans le cadre du projet ProPac (Programmation parallèle certifiée) de l'ACI « jeunes chercheurs » dont l'objectif est la conception et le développement d'outils pour la programmation parallèle certifiée. Dans cet exposé, nous présenterons différentes sémantiques d'un langage fonctionnel pour la programmation BSP (modèle structuré de parallélisme qui permet la portabilité des programmes tout en offrant une prévision réaliste de leurs performances sur une grande variété d'architectures), chacune avec ses propres avantages (de la preuve de programmes jusqu'à l'implantation modulaire) et propriétés. Nous étendrons ensuite le langage (et les sémantiques) avec une primitive de composition parallèle (qui permet aussi la programmation d'algorithmes «diviser-pour-régner» parallèles) et des les entrées/sorties parallèles. Nous discuterons aussi d'un exemple d'application via l'utilisation et l'implantation de structures de données parallèles.


Méthodes de rendu hybrides basées image et géométrie pour l'affichage en temps réel de scènes complexes. Damien Porquet, Université de Limoges

Le cadre de cet exposé est le rendu en temps réel de scènes composées de modèles 3D non déformables composés d'un très grand nombre de polygones. De tels modèles sont coûteux à utiliser, tant en terme d'espace mémoire que de temps de calcul, mais permettent d'obtenir un grand réalisme visuel, dont la demande est sans cesse croissante. Parmis les nombreux travaux ayant pour cadre cette problématique, je décrirai succinctement les principales approches du problème (rendu à base de points, la simplification de maillages géométriques et le rendu à base d'images). Je présenterai ensuite mes travaux tentant de concilier ces différentes approches par le développement de méthodes hybrides, notamment entre le rendu à base d'images et le rendu conventionnel.


Semi-local string comparison and maximum cliques in circle graphs Alexandre Tiskin, Université de Warwick

Given two strings A, B of length n, the length of their longest common subsequence LCS(A,B) can be computed in time O(n2) by dynamic programming. In 1980, Masek and Paterson showed that the LCS length can be computed in subquadratic time. We show that even more is possible: the lengths of all the LCS(A,B'), where B' is a substring of B, can still be computed in subquadratic time, producing an efficient implicit representation of the Theta(n2) outputs. Such "semi-local" string comparison has relevance for computational biology, and also implies an improved algorithm for the following well-known problem: given a circle and n chords, find the maximum-size subset of pairwise intersecting chords. In 1973, Gavril gave the first polynomial-time algorithm for this problem, and in 1983 Rotem and Urrutia gave an O(n^2) algorithm. We show that this latter problem can be solved in time O(n^1.5).


Approximations automatiques pour la vérification de protocoles de sécurité Olga Kouchnarenko, LIFC, INRIA CASSIS

De nos jours, les protocoles de sécurité (ssh, https,...) sont intensivement utilisés. Nous nous intéressons à la vérification de tels protocoles d'un point de vue symbolique : même si l'on suppose que les primitives cryptographiques utilisées sont parfaites, des failles peuvent néanmoins intervenir à cause de la parallelisation des sessions. C'est ce qu'on appelle par exemple les "man in the middle attacks". Nous avons pour objectif de vérifier qu'un protocole ne comporte pas de telles failles. D'un point de vue général, même dans des cas très restreints, ce problème est indécidable pour un nombre non borné de sessions. Nous améliorons alors une méthode introduite par Genet et Klay utilisant des approximations et des abstractions. Nous montrerons comment cette méthode peut être automatisée pour fournir, en pratique, des résultats concluants. Nous expliquons comment des propriétés algébriques peuvent être prises en compte dans cette même méthode. Nous présenterons aussi l'outil TA4SP développé dans ce cadre et utilisant un langage de spécification (HLPSL) de haut niveau.


Model-checking pour les ambients Jean-Marc Talbot, LIFL

Formellement, le problème de model-checking pour une logique L et une classe de structures C est de savoir si une formule donnée de L est vraie pour une certaine structure de C. Ce problème de décision revêt différentes formes selon la thématique dans laquelle il est étudié : dans le cadre de la vérification, il s'agit de tester si un système vérifie une spécification logique. En base de données, ce problème consiste à vérifier que la base satisfait un certain nombre de contraintes, comme, par exemple, la conformité d'un document XML vis-à-vis d'une DTD. Dans cet exposé, j'exposerai mes travaux de recherche concernant le model-checking pour le calcul des ambients qui m'ont conduit de la problématique de la vérification dans les algèbres de processus à celle des requêtes pour les documents semi-structurés. Je développerai plus précisément les aspects de vérification lorsque les systèmes décrits possèdent un nombre infini d'états en montrant (malheureusement) essentiellement des résultats négatifs. En conclusion, je tenterai de dégager des perspectives de recherche, principalement dans le cadre de la vérification.


Représentation condensée et Contraintes pour la découverte de règles d'associations: vers une approche méta-cognitive Enjalbert Mephu Nguifo,

La recherche de règles d'association est un problème d'optimisation combinatoire, central en fouille de données. De nombreux travaux y sont consacrés apportant des avancées significatives. Néanmoins le problème de la réduction du nombre considérable de règles engendrées reste un probleme ouvert donnant lieu à celui connu sous le nom de fouille de connaissances ("knowledge mining"). Après un bref apercu des techniques de résolution existantes, les approches par contraintes et par représentation condensée seront presentées et discutées. Nous verrons que les solutions apportées ne sont pas complètement satisfaisantes pour un expert-metier. Partant du postulat que celui-ci joue un rôle primordial dans le processus de découverte de connaissances, nous proposons une approche complémentaire basée sur la construction d'une méta-connaissance à partir des règles générées. Cette approche anthropocentrée utilise les bases génériques des règles d'association. Nous discuterons les propriétés des différentes bases génériques de règles ainsi que l'approche proposée pour une exploration des règles. Mots-clés : itemsets fermés, itemsets contraints, bases génériques, métaconnaisance, visualisation de règles d'association


Graphes colorés, définitions et complexité des problèmes d'optimisation Marie-Emilie Voge, INRIA, Sophia

Les graphes colorés ont été introduits pour répondre à un besoin de modélisation des réseaux multiniveaux dans une optique de planification de la tolérance aux pannes. Ils découlent du concept de Shared Risk Resource Group (SRRG) ou groupe de ressources partageant un risque d'indisponibilité. Par exemple dans un réseau de telecom, deux connections routées via un même cable tombent en panne simultanément lorsque ce cable est coupé, ces deux connections partagent donc un risque et ainsi forment un SRRG. Un graphe coloré est un graphe dont les arêtes sont partitionnées en couleurs. Dans les graphes classiques de nombreux problèmes consistent à trouver des ensembles d'arêtes vérifiant certaines propriétés (chemin, coupe ...). Or dans un graphe coloré les arêtes sont liées entre elles par leur couleur et non plus indépendantes et la donnée des arêtes ne suffit plus à déterminer la structure du graphe. C'est pourquoi dans les graphes colorés, les problèmes etudiés consistent à trouver des ensembles de couleurs. En particulier, on definit un chemin coloré entre deux sommets comme un ensemble de couleur tel que le sous graphe induit par ses arêtes contient un chemin au sens classique entre ces sommets. De la même façon on definit une st-coupe colorée, une coupe colorée et un arbre couvrant coloré. Nous verons que la complexité et l'approximabilité des problèmes d'optimisation associés (coupe coloré minimum ...) sont très différentes de celles de leurs équivalents classiques.


à venir Arnaud Giacometti,

à venir


ELISE : un algorithme évolutionnaire pour la recherche documentaire Pierre Collet,

Trop d'information tue l'information. Ce cliché résume bien la question de la recherche d'information dans de grandes bases documentaires, où les outils les plus performants renvoient des centaines de réponses similaires à une requête, même bien formulée et très précise. Cependant, de nombreux moyens de discrimination restent inexploités, car trop complexes à décrire ou trop spécifiques. C'est ce qui a conduit Novartis Pharma à rechercher une approche plus individuelle dans l'exploitation de ses bases documentaires. ELISE (Evolutionary Learning Interactive Search Engine) fait évoluer interactivement un profil pour chaque utilisateur (composé de modèles de transformation de requêtes), selon l'Approche Parisienne. Ce procédé fournit une formulation implicite des besoins de recherche de l'utilisateur, permettant de fournir des résponses plus adaptées, et d'accéder à des documents à la croisée de plusieurs recherches, délaissés par les outils classiques.


Fouille de données et visualisation François Poulet,

Une approche récente (fin des années 90) en fouille de données vise à donner une part plus importante à la visualisation, on parle alors de fouille visuelle de données (Visual Data Mining) dont une définition est : la stratégie de la fouille visuelle de données consiste à coupler fortement la visualisation et les processus analytiques dans un outil de fouille de données bénéficiant des avantages de chacun. Dans les approches usuelles de fouille de données, la visualisation n'intervient en général que lors de deux étapes particulières du processus de fouille de données : - dans l'une des toutes premières étapes pour "voir" les données ou leur distribution, - dans l'une des toutes dernières étapes du processus pour prendre connaissance des résultats. Entre ces deux étapes il y a en général exécution d'un algorithme automatique de fouille de données. Le but de nos travaux de recherche est d'augmenter le rôle de la visualisation et de l'utilisateur dans ce processus. Ceci peut être mené à bien de plusieurs façons : - en faisant collaborer des méthodes visuelles avec les méthodes automatiques soit en pré-traitement soit en post-traitement, - en remplaçant l'algorithme automatique de fouille de données par un algorithme graphique interactif, - en créant de nouvelles méthodes de fouille utilisant simultanément une approche graphique et une approche automatique (en tirant partie des avantages de chacune), - en augmentant les interactions. L'augmentation du rôle de l'utilisateur dans le processus en remplaçant l'algorithme automatique par un algorithme interactif présente au moins les avantages suivants : - la confiance et la compréhensibilité du modèle sont accrues puisque l'utilisateur a participé à sa création, - on peut utiliser les capacités humaines en reconnaissance de formes. De plus, dans ce cas, l'utilisateur du système peut être un spécialiste des données et non plus un spécialiste de fouille / analyse de données, ce qui permet d'utiliser les connaissances du domaine des données tout au long du processus de fouille. Par ailleurs, face à la quantité sans cesse grandissante de données stockées, les problèmes de "passage à l'échelle" font aussi partie de nos préoccupations. Pour pouvoir traiter de très grandes quantités de données plusieurs solutions peuvent être envisagées : - la parallélisation ou distribution des algorithmes de fouille, - une réduction de la taille des données (en nombre de dimensions ou nombre d'individus). La parallélisation des algorithmes de fouille est une solution prometteuse pour pouvoir traiter de grands ensembles de données. Dans le cas de la classification supervisée, nous avons développé plusieurs algorithmes de SVM (Séparateur à Vaste Marge ou Support Vector Machine) incrémentaux et parallèles. L'autre solution pour traiter de grands ensembles de données est d'effectuer un pré-traitement permettant la réduction de la dimension des données. Plusieurs solutions peuvent être envisagées : - l'utilisation d'une représentation de plus haut niveau des données par exemple une représentation symbolique des données (comme des intervalles ou des variables taxonomiques), il faut alors créer des outils de classification capables de traiter de telles données, - l'utilisation de méthodes coopératives centrées utilisateur (utilisant à la fois des méthodes graphiques interactives et des méthodes automatiques) dans le but de réduire la taille (en nombre d'individus ou de variables) des ensembles de données à traiter, et bien entendu la coopération entre les différentes solutions citées.


ANR-STIC: bilan 2005 et programmes 2006 Gaétan Hains, ANR

Tout est dans le titre ...


Reduction strategies for left-linear term rewriting systems Yoshihto Toyama, RIEC, Tohoku Universty

Huet and Levy (1979) showed that needed reduction is a normalizing strategy for orthogonal (i.e., left-linear and non-overlapping) term rewriting systems. In order to obtain a decidable needed reduction strategy, they proposed the notion of strongly sequential approximation. Extending their seminal work, several better decidable approximations of left-linear term rewriting systems, for example, NV approximation, shallow approximation, growing approximation, etc., have been investigated in the literature. In all of these works, orthogonality is required to guarantee approximated decidable needed reductions are actually normalizing strategies. We extend these decidable normalizing strategies to left-linear overlapping term rewriting systems. The key idea is the balanced weak Church-Rosser property. We prove that approximated external reduction is a computable normalizing strategy for the class of left-linear term rewriting systems in which every critical pair can be joined with root balanced reductions.


Dealing with Non-Orientable Equations in Rewriting Induction Takahito Aoto, RIEC, Tohoku Universty

Rewriting induction (Reddy, 1989) is an automated proof method for inductive theorems of term rewriting systems. Reasoning by the rewriting induction is based on the noetherian induction on some reduction order. Thus, when the given conjecture is not orientable by the reduction order in use, any proof attempts for that conjecture fails; also conjectures such as a commutativity axiom are out of the scope of the rewriting induction because they can not be oriented by any reduction order. In this talk, we give an extension of rewriting induction which can deal with non-orientable conjectures. We also present an extension which enables an incremental use of the rewriting induction so that non-orientable lemmas can be used.


Analyse, conception et réalisation d'un environnement pour le pilotage et la visualisation en ligne de simulations numériques paralléles Aurélien Esnard, LABRI

Le domaine de la simulation interactive ou computational steering a pour but d'améliorer le processus de simulation numérique (modélisation, calcul, analyse) en le rendant plus interactif. Dans cette approche, le scientique n'attend plus passivement les résultats de la simulation ; il peut visualiser « en ligne » l'évolution des données calculées et peut interagir à tout moment en modifiant certains paramètres à la volée ou plus gé- néralement en pilotant le déroulement des calculs. Un tel outil peut s'avérer très utile pour la compréhension des phénomènes physiques modélisés et la détection d'erreurs dans le cas de simulations longues. L'objectif de cette thèse est de concevoir et de développer une plate-forme logicielle, appelée EPSN (Environnement pour le Pilotage des Simulations Numériques), permettant de piloter une application numérique parallèle en s'appuyant sur des outils de visualisation eux-mêmes parallèles. En d'autres termes, il s'agit de mettre au service des scientifiques les capacités de la visualisation parallèle et plus largement de la réalité virtuelle (environnement immersif, murs d'images), une étape aujourd'hui cruciale pour la conception et l'exploitation de simulations numériques complexes en vraie grandeur. La mise en oeuvre d'un couplage efficace entre simulation et visualisation soulève deux problèmes majeurs, que j'ai étudié dans ma thèse : le problème de la coordination efficace des opérations de pilotages en parallèle et le problème de la redistribution pour des données complexes (grilles structurées, ensembles de particules, maillages non structurés).


Cellular automata and communication complexity Ivan Rapaport, Santiago, Chili

A cellular automaton (CA) is a grid of communicating cells. During the evolution information flows through the whole grid. Suppose that we divide the grid into two parts (x and y). Then one can view the dynamics as a two inputs boolean function f(x,y). The communication complexity of f(x,y) measures the number of exchanged bits required by two actors (one knowing only x and the other knowing only y) in order to compute together f(x,y). This work represents a first step towards the use of the communication complexity measure of f as a tool to "undertand" the underlying CA. Joint work with Christophe Durr (CNRS, Ecole Polytechnique) and Guillaume Theyssier (Ecole Normale Superieure de Lyon)


Configuration sous contraintes de graphes couplés Denys Duchier, LIFO

Dans ce séminaire, je parlerai de descriptions de graphes et de leurs modèles: comment décrire des familles de graphes grace à un language de contraintes, et comment en énumérer les modèles (les configurations) de manière efficace grace à la propagation des contraintes. Je montrerai que les contraintes ensemblistes sont très avantageuses dans ce contexte. Je décrirai ensuite une généralisation bien utile de cette idée: à savoir la configuration simultanée de plusieurs graphes couplés, c'est à dire des graphes dont les modèles ne sont pas choisis indépendemment, mais doivent satisfaire des contraintes de couplage. Pour illustrer mon propos, je me placerai dans un domaine d'application qui m'est cher, à savoir la modélisation des structures linguistiques pour le traitement de la langue naturelle, mais aucune connaissance, ou intéret particulier, en linguistique n'est nécessaire pour cette présentation. Dans cette application au TAL, l'analyse procède entièrement par propagation des contraintes. Je montrerai comment des phénomènes linguistiques macroscopiques assez compliqués peuvent s'expliquer simplement par le couplage de plusieurs graphes correspondants à différents niveaux de représentation linguistique (e.g. ordonnancement des mots, phénomènes de contrôle/montée, reconstruction sémantique). L'approche que je décris est réalisée dans l'outil XDG qui utilise le language de programmation par contraintes Mozart/Oz (dont je suis l'un des concepteurs/implanteurs) et je ponctuerai ma présentation avec des petites démos utilisant cet outil.


Pavages auto-assemblants: présentation et effet d'échelle. Eric Rémila, LIP - ENS Lyon

L'auto-assemblage est un modèle issu de la biologie. Les composantes de base sont des tuiles carrées. Ces tuiles flottent dans le plan, sans rotation possible. Chaque côté de la tuile est muni d'une "colle" spécifique. Pour que deux tuiles puissent être liées par un côté, les côtés en question doivent porter la même colle. On ne peut coller une tuile à un motif précédemment formé que si la somme des forces des colles utilisées est supérieur à un seuil fixé appelé température (on prend souvent la valeur 2). La "dynamique" d'un jeu de tuiles est l'ordre des motifs obtenus avec ce jeu de tuiles, en partant d'une tuile fixée appelée "racine"; Nous commencerons par présenter en détail le modèle. Puis nous nous focaliserons plus précisément sur le problème suivant: Etant donné un jeu de tuiles, peut on construire un jeu de tuiles ayant la même dynamique, à une échelle supérieure ?


Promenades dans un monde hyperbolique Maurice Margenstern, LITA (Metz)

Après avoir fait un bref rappel de géométrie hyperbolique, nous aborderons l'exploration des (très) nombreux pavages qui existent dans le plan hyperbolique par une méthode simple dont nous illustrerons les résultats sur quelques exemples. Nous y verrons des connexions très intéressantes entre géométrie et arithmétique élémentaire. Il en résulte des algorithmes permettant une implantation efficace des automates cellulaires dans ces grilles. Nous ferons également une petite visite aux dimensions 3 et 4 et, si nous en avons le temps, nous reviendrons au plan avec une catégorie de pavages tout à fait surprenants.


FlowVR: calculs interactifs et visualisation sur grappe Jérémie Allard, Laboratoire ID (IMAG)

Cette thèse combine le calcul haute performance à la réalité virtuelle pour permettre la conception de méthodes de couplage de composants parallèles à l'intérieur d'applications distribuées et interactives. Un nouveau modèle de couplage est présenté, conçu selon des critères de modularité, simplicité, efficacité et extensibilité. La construction des applications repose sur une séparation entre la programmation de modules parallèles réutilisables et la définition de l'application sous forme de graphe de flux de données contenant des mécanismes de filtrage et de synchronisations, permettant d'exprimer des schémas de communication collective et des politiques de couplage avancées. Ce travail sur le couplage interactif est complété par une extension haut niveau concernant le rendu distribué. En exploitant une description modulaire de la scène 3D en primitives indépendantes basées sur l'utilisation de shaders, des réseaux de filtrage permettent de combiner plusieurs flux pour acheminer efficacement les informations aux machines de rendu. Ce système est très extensible et permet la création de nouvelles applications exploitant la puissance des cartes graphiques pour décharger certains calculs des processeurs et réduire les transferts réseau. De nombreuses applications nouvelles sont ainsi développées, combinant des algorithmes de vision parallélisés immergeant l'utilisateur dans l'environnement virtuel, et des interactions avec des objets contrôlés par des simulations physiques distribuées (poterie, collisions, fluides).