Accéder aux Rapports de l'année :
1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018
Les rapports de recherche du LIFO en 2005
RR-2005-01
Visualisation de larges terrains multi-modaux dans les environnements multi-écrans pilotés par grappe de PC
Valérie Gouranton, Sébastien Limet, Souley Madougou, Emmanuel Melin, Cyril Nortet
Date : 2005-04-29
Résumé Télécharger
RR-2005-02
Solving First Order Formulae of Pseudo-Regular Theory
Sébastien Limet and Pierre Pillot
Date : 2005-03-09
Résumé Télécharger
RR-2005-03
A Fully Dynamic Recognition Algorithm for weak bisplit graphs
Jean-Marie Vanherpe and Soumia Ziti
Date : 2005-03-14
Résumé Télécharger
RR-2005-04
Minimal interval completions
Pinar Heggerness, Karol Suchan, Ioan Todinca, and Yngve Villanger
Date : 2005-04-13
Résumé Télécharger
RR-2005-05
Abstract geometrical computation 1 : embedding Black hole computations with rational numbers
Jérome Durand-Lose
Date : 2005-12-07
Résumé Télécharger
RR-2005-07
Représentation des langages de n-uplets d'arbres par des programmes logiques et applications
Sébastien Limet
Date : 2005-12-07
Résumé Télécharger
Résumés des rapports de recherche
RR-2005-01 Visualisation de larges terrains multi-modaux dans les environnements multi-écrans pilotés par grappe de PC
Valérie Gouranton, Sébastien Limet, Souley Madougou, Emmanuel Melin, Cyril Nortet
Résumé : Le rendu de larges terrains à des taux de rafraîchissement interactifs
révêt une importance capitale dans nombre de domaines. Dans les Systèmes
d'Information Géographiques, par exemple, les données d'élevation sont
souvent associées à diverses autres informations telles que le rivières,
les forages, les routes, les maines. Le problème est alors de trouver le
bon algorithme de gestion de niveaux de détail qui soit non seulement
scalable mais aussi qui préserve les attributs importants des données
annexes. Comme une contribution à ce domaine de recherche, nous
présentons une méthode de mipmap générique qui intègre intrinsèquement
un support de morphing et qui est applicable à tout type de donnée lié
aux sommets. La méthode est intégrée dans un environnement de LOD
distribué dirigé par la géométrie et spécifique aux height fields. Nous
basant sur les récentes avancées en calcul sur grappe de PC, nous
distribuons de manière consistante aussi bien la géométrie que les
données annexes. Notre algorithme de LOD est combiné à la méthode de
mipmap pour les traiter en parallèle. Pour optimiser l'utilisation de la
bande passante, une structure de onnées compacte est définie pour le
transfert des données. Comme résultat, notre système est capable de
rendre interactivement des modèles de terrain de l'ordre du giga-octet
tout en préseravant leur apparence.
Mot(s) Clé(s) : LOD, rendu parallèle, parallélisme, Gestion de grands, volumes de données
RR-2005-02 Solving First Order Formulae of Pseudo-Regular Theory
Sébastien Limet and Pierre Pillot
Résumé : Dans ce rapport nous étudions la classe des relations pseudo-régulières
qui est une extensions des relations régulière qui affaiblit quelques restrictions
sur la "synchronisation" entre les composant d'un nuplet de la relation.
Nous choisissons le formalisme de la programmation logique pour représenter
les langages de nuplets d'arbres (c'est à dire les relations) et nous utilisons des
techniques de transformation de programmes pour calculer les opérations sur
les langages. Nous montrans que même si les programmes pseudo-régulier sont
syntaxiquement moins restrictifs que les réguliers, ils définissent la même classes
de langages de nuplets d'arbres. Malgré cela, les relations pseudo régulières
permettent de définir une classe de système de réécriture dont la clotûre transtive
est un relation régulière. Nous appliquons ce résultat pour définir un classe de formules
du 1er ordre basées sur le prédicat de joignabilité d'un système de réécriture pseudo-regulier.
Mot(s) Clé(s) : langages d'arbres; programmation logique; système de réécriture; décidabilité
RR-2005-03 A Fully Dynamic Recognition Algorithm for weak bisplit graphs
Jean-Marie Vanherpe and Soumia Ziti
Résumé : Nous présentons dans ce papier un algorithme dynamique de reconnaissance qui correspond à l?insertion ou la suppression d?un sommet ou d?une arête pour la classe des graphes weak bisplits, cette classe contient les graphes bipartis ayant une relation avec les cographes et les splits graphes.
Mot(s) Clé(s) : Module; Décomposition; Décomposition Canonique; Arbre; Cographe; Graphe Biparti; Graphe K+S; Graphe Weak Bisplit; Algorithme Dynamique.
RR-2005-04 Minimal interval completions
Pinar Heggerness, Karol Suchan, Ioan Todinca, and Yngve Villanger
Résumé : Nous étudions le problème d'ajout d'arêtes à un graphe
quelconque pour que le graphe obtenu soit un graphe d'intervalles.
Notre objectif est d'ajouter un ensemble minimal d'arêtes. Ce qui signifie qu'aucun sous-ensemble propre des arêtes
supplémentaires ajoutées au graphe de départ ne peut donner un
graphe d'intervalles. Ce problème est proche du problème
d'ajout d'un ensemble minimal d'arêtes à un graphe
pour obtenir un graphe triangulé. Il s'agit d'un problème bien étudié
qui motive une étude analogue des complétions d'intervalles
minimales. Cependant, tandis qu'il existe des propriétés agréables qui
ont pour résultat des algorithmes efficaces pour obtenir un graphe
triangulé de cette façon, le problème analogue d'obtention d'un graphe
d'intervalles est plus difficile, et sa complexité
était ouverte jusqu'à présent. Dans ce papier,
nous donnons un algorithme en temps polynômial pour obtenir une
complétion d'intervalles minimale d'un graphe quelconque, ainsi nous
résolvons la complexité de ce problème.
Mot(s) Clé(s) : graphe, triangulation, intervalle, complétion, online, algorithme, polynômial, décomposition, ordre, partition, raffinement
RR-2005-05 Abstract geometrical computation 1 : embedding Black hole computations with rational numbers
Jérome Durand-Lose
Résumé : Le modèle de calcul du trou noir permet des calculs super-Turing
car il permet de décider en temps fini (pour l'observateur) tout
langage récursivement énumérable.
Dans ce papier, nous définissons un modèle géométrique de calcul,
le Calcul géométrique abstrait, qui, bien que basé sur des
nombres rationnels (et non des réels) a la même propriété : il peut
simuler toute machine de Turing et décider tout problème r.e. grâce
à la création d'une accumulation.
Seul un nombre fini de signaux peut sortir d'une accumulation et on
peut savoir si quoi que ce soit en est sorti.
Ceci correspond à l'effet trou noir.
Mot(s) Clé(s) : Calcul géométrique abstrait;
Modèle du trou noir ;
Conservation de l'énergie ;
Espace-temps de Malament-Hogarth ;
Calcul Super-Turing ;
Universalité au sens de Turing ;
Phénomène de type
RR-2005-07 Représentation des langages de n-uplets d'arbres par des programmes logiques et applications
Sébastien Limet
Résumé : Dans le domaine de l'informatique théorique, on manipule très souvent des relations sur les termes du 1er ordre. Par conséquent, il est important d'avoir des représentations finies de ces relations, encore appelées langages de n-uplets d'arbres. Nous avons étudié différentes représentations possibles pour une classe de langages appelée langages synchronisés. Nous avons plus particulièrement étudié une représentation sous forme de programmes logiques et présenté un algorithme basé sur les techniques de transformation de programmes pour calculer les opérations sur les langages. Dans ce cadre, nous avons montré des propriétés intéressantes des langages synchronisés et de certaines de leurs sous-classes. Puis, nous avons appliqué les résultats obtenus à des problèmes liés aux domaines de la démonstration automatique et de la vérification. Ces résultats s'appuient sur une procédure de construction d'un programme logique qui décrit la clôture réflexive transitive de la relation induite par un système de réécriture.
Mot(s) Clé(s) :