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

Lifo > Les rapports de recherche du LIFO en 2005

 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 99 29
Fax: +33 (0)2 38 41 71 37



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) :