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 1999

 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 1999


RR-1999-01 About the Strong Perfect Graph Conjecture on circular partitionable graphs
A. PECHER
Date : 1999-01-14
Résumé Télécharger

RR-1999-02 Les journées LODEC de décembre 1998
S. ANANTHARAMAN, G. HAINS (éditeurs)
Date : 1999-01-06
Résumé

RR-1999-03 Un algorithme incrémental parallèle pour la maintenance des vues matérialisées
M. BAHMA, F. BENTAYEB, G. HAINS
Date : 1999-04-15
Résumé Télécharger

RR-1999-04 Algorithmes parallèles pour DyALog
I. DEBOURGES
Date : 1999-04-19
Résumé Télécharger

RR-1999-05 Triangulated neighbourhoods in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Date : 1999-03-02
Résumé Télécharger

RR-1999-06 Parallélisation d'algorithmes génétiques fondée sur le modèle BSP
A. BRAUD, C. VRAIN
Date : 1999-11-29
Résumé Télécharger

RR-1999-07 A Cost Model For Asynchronous and Structured Message Passing
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Date : 1999-04-12
Résumé Télécharger

RR-1999-08 Optimisation des synchronisations par réordonnancement des blocs de base data-parallèles pour des multiprocesseurs MIMD
M. DUPRE
Date : 1999-04-02
Résumé

RR-1999-09 Cutsets in perfect and minimal imperfect graphs
I. RUSU
Date : 1999-05-03
Résumé Télécharger

RR-1999-10 Confluence of the BS-lambda calculus
F. LOULERGUE
Date : 1999-07-22
Résumé Télécharger

RR-1999-11 Parallel Constraint Programming over BSP Vectors
A. LALLOUET, G. HAINS
Date : 1999-06-14
Résumé Télécharger

RR-1999-12 Loose vertices in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Date : 1999-08-25
Résumé Télécharger

RR-1999-13 Forbidden Subgraph Decomposition
I. RUSU, J. SPINRAD
Date : 1999-09-03
Résumé Télécharger

RR-1999-14 On pleasant vertices in graphs
J.-L. FOUQUET, F. ROUSSEL, P. RUBIO, H. THUILLIER
Date : 1999-11-22
Résumé Télécharger


Résumés des rapports de recherche


RR-1999-01 About the Strong Perfect Graph Conjecture on circular partitionable graphs
A. PECHER
Résumé : Un graphe partitionnable avec n sommets est dit circulaire s'il existe une numerotation de ses sommets de 0 a (n-1) telle que pour tout entier x compris entre 0 et n-1, toute clique maximum C et tout stable maximum S, l'ensemble C+x (modulo n) est une clique maximum et l'ensemble S+x est un stable maximum. En 1979, V. Chvatal, R.L. Graham, A.F. Perold et S.H. Whitesides ont defini un procede algorithmique pour construire une grande classe de graphes partitionnables circulaires. Pour cette classe, la conjecture forte des graphes parfaits est verifiee. Cependant, on ne sait toujours pas si cette classe recouvre entierement l'ensemble des graphes circulaires partitionnables. Nous montrons, en nous appuyant sur des travaux de G. Bacso, E. Boros, V. Gurvich, F. Maffray et M. Preissmann, que la conjecture forte des graphes parfaits est vraie pour les graphes circulaires partitionnables possedant deux cliques maximums C et C', deux stables maximums S et S', tels que: C et C' possdent en commun au moins la moitie de leurs sommets, S et S' possdent en commun au moins la moitie de leurs sommets.
Mot(s) Clé(s) : graphe; circulaire; partitionnable; parfait; pavage; entiers

RR-1999-02 Les journées LODEC de décembre 1998
S. ANANTHARAMAN, G. HAINS (éditeurs)
Résumé :
Mot(s) Clé(s) :

RR-1999-03 Un algorithme incrémental parallèle pour la maintenance des vues matérialisées
M. BAHMA, F. BENTAYEB, G. HAINS
Résumé : L'étude du problème de la maintenance de vues matérialisées dans les SGBD (SGBD : Systèmes de gestion de bases de données.) relationnels a connu un essor considérable ces dernières années, particulièrement à cause de son application dans le domaine du data-warehousing. Ce problème consiste à conserver la cohérence des contenus des vues matérialisées par rapport aux contenus des relations de base lorsqu'elles sont modifiées. Par conséquent, les requêtes émanant des utilisateurs peuvent alors être évaluées plus rapidement en utilisant ces vues à la place des relations. Ceci n'est possible que si les vues sont maintenues dans un état cohérent. Des algorithmes incrémentaux ont été proposés dans la littérature pour mettre à jour la vue en n'utilisant que l'information utile; autrement dit en évitant la réévaluation complète de la vue. Notons cependant que lorsque la vue contient des jointures, sa réévaluation même incrémentale peut malheureusement induire un coût important. Ainsi, la parallélisation de l'algorithme de maintenance incrémentale des vues devient une approche très prometteuse pour atteindre des performances acceptables. Dans cet article, nous présentons d'une part un algorithme parallèle pour le calcul de la jointure basé sur la duplication partielle des données et d'autre part un algorithme incrémental parallèle efficace pour la maintenance de vues matérialisées. Les deux algorithmes sont basés sur un modèle de redistribution dynamique des données pour les machines à mémoire distribuée. Ce modèle présente l'avantage d'un fort potentiel d'équilibrage dynamique d'une part, et d'autre part supporte un contrôle flexible des communications induites par le parallélisme intra-transaction. Les performances de ces deux algorithmes ont été étudiées en utilisant le modèle de coût BSP (Bulk Synchronous Parallelism). Ce modèle prévoit une accélération linéaire pour nos algorithmes.
Mot(s) Clé(s) : SGBD parallèle; Maintenance des vues matérialisées; Data-warehouse; Multi-jointure; déséquilibre des données; équilibrage dynamique des charges

RR-1999-04 Algorithmes parallèles pour DyALog
I. DEBOURGES
Résumé : Depuis une petite dizaine d'années, Eric Villemonte de la Clergerie (INRIA) travaille sur la réalisation d'un analyseur syntaxique géenéralisé:DyALog. Ce logiciel, qui a connu de nombreuses évolutions depuis sa naissance souffre encore d'un handicap: son temps de réponse dans le cas de grammaires ambiguës de grande taille reste trop important. L'étude de parallélisation de DyALog que nous présentons ici a donc pour but premier d'apporter une solution pour accélérer l'exécution de ce logiciel afin de l'utiliser pour des grammaires du Langage Naturel. Nous avons, pour cela, réalisé une étude complète des solutions envisageables: 8 algorithmes rédigés selon le modèle BSP [VALL90] [COLL96-1] sont proposés, et ce afin de garantir une bonne prévision des coûts. L'un d'entre eux annonce de bons résultats pour tous les types de grammaires (déterministes ou ambiguës). Quatre autres sont très prometteurs pour les grammaires de type Langage Naturel.
Mot(s) Clé(s) : Algorithmes; parallelisme; BSP; grammaires; analyseur syntaxique; compilateur

RR-1999-05 Triangulated neighbourhoods in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Résumé : Nous appellons T-sommet d'un graphe G=(V,E) un sommet z dont le voisinage N(z) dans G induit un graphe triangule, et nous montrons que tout graphe de Berge C4-libre ou bien est une clique, ou bien contient au moins deux T-sommets non-adjacents. Une consequence rapide de ce resultat est que tout graphe de Berge C4-libre admet un T-schema d'elimination, c.a.d. un ordonnancement [v_1, v_2, ..., v_n] des sommets tel que v_i est un T-sommet dans le graphe induit dans G par v_i, v_(i+1), ..., v_n.
Mot(s) Clé(s) : recherche en largeur lexicographique, graphe triangule, perfection

RR-1999-06 Parallélisation d'algorithmes génétiques fondée sur le modèle BSP
A. BRAUD, C. VRAIN
Résumé : Nous nous intéressons à l'apport des algorithmes génétiques dans le domaine de l'Extraction de Connaissances dans les Bases de Données. Ces algorithmes réalisent une exploration stochastique de l'espace de recherche ; ils sont donc adaptés à des problèmes pour lesquels cet espace est vaste, ce qui est notamment le cas dans ce domaine d'application. Néanmoins, le processus d'évolution permettant de faire émerger une bonne solution au problème est en général très long, ce qui représente une limite importante à leur application. Des solutions ont été proposées pour diminuer les coûts d'éxécution de ces algorithmes, mais le problème reste ouvert et nous étudions ici l'une d'elles, à savoir la parallélisation. Après une présentation des algorithmes génétiques, nous proposons trois algorithmes parallèles ne modifiant pas le fonctionnement de l'algorithme séquentiel. Ces algorithmes sont conçus selon le modèle BSP, ce qui permet d'étudier leur coût. Il est calculé dans le cadre d'une application classique d'Extraction de Connaissances dans les Bases de Données, à savoir l'apprentissage d'une description de concept à partir d'exemples stockés dans une base de données. Les résultats de cette étude théorique prédisent une accélération par rapport à l'algorithme séquentiel pour deux des trois algorithmes proposés. De plus l'un de ces algorithmes a été implanté et les expérimentations menées sur le prototype confirment ces prédictions.
Mot(s) Clé(s) : Algorithmes Génétiques Parallèles; Apprentissage de concepts à partir d'exemples; Fouille de Données; BSP

RR-1999-07 A Cost Model For Asynchronous and Structured Message Passing
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Résumé : Dans ce rapport, nous présentons un modèle de coût prenant en compte les caractéristiques des machines actuelles. Ce travail repose sur SCLchan, un modèle d'exécution parallèle et asynchrone permettant le passage de message explicite. Nous montrons qu'il est possible de définir une fonction de complexitépour les programmes SCLchan. Elle repose sur des dates symboliques attachées a chaque évènement de communication. Ces dates peuvent être ordonnées pour calculer une borne supérieur pour la charge du réseau. Contrairement aux approches classiques, ce coût rend compte de l'asynchronisme dans le passage de message ainsi que du recouvrement calcul communication.
Mot(s) Clé(s) : Modèle de coût; Dates symboliques; Langages de programmation parallèle; Exécution asynchrone; Horloges structurelles

RR-1999-08 Optimisation des synchronisations par réordonnancement des blocs de base data-parallèles pour des multiprocesseurs MIMD
M. DUPRE
Résumé : La compilation d'un programme data-parallèle pour une architecture MIMD multiprocesseurs à mémoire partagée génère un programme cible SPMD à exécution asynchrone. à partir de l'analyse des dépendances, Quinn Hatcher et Seevers ont proposé un algorithme de placement des barrières de synchronisation dans un bloc de base du programme cible. Cet algorithme ne prend pas en compte les possibilités offertes par le réordonnancement du code. Par réordonnancement, on peut obtenir un nombre inférieur ou égal de barrières de synchronisation qui peut être encore minoré par mise en assignation unique partielle du programme. Un algorithme déterminant les transformations à effectuer et l'ordonnancement des instructions entre les barrières de synchronisation est proposé.
Mot(s) Clé(s) : Compilation; langages data-parallèles; modèle d'exécution asynchrone; mémoire partagée; réordonnancement; synchronisation

RR-1999-09 Cutsets in perfect and minimal imperfect graphs
I. RUSU
Résumé : La notion d'ensemble deconnectant est l'une des plus importantes que la theorie des graphes parfaits connait aujourd'hui. Ses applications sont principalement de deux types: premierement, des conditions sufficientes pour qu'un graphe ne soit pas minimal imparfait peuvent etre trouvees; deuxiemement, des operations de composition/decomposition peuvent etre definies. Dans les deux cas, des algorithmes faciles (d'un point de vue theorique) et/ou efficaces (d'un point de vue pratique) peuvent etre envisages. Nous presentons dans ce papier ces aspects varies des ensembles deconnectants dans les graphes parfaits et minimaux imparfaits.
Mot(s) Clé(s) : graphe parfait; ensemble deconnectant; connexite

RR-1999-10 Confluence of the BS-lambda calculus
F. LOULERGUE
Résumé : Le BSlambda-calcul, base formelle pour des langages fonctionnels pouvant exprimer des algorithmes paralleles BSP est presente. Nous montrons ensuite sa confluence.
Mot(s) Clé(s) : BSP; programmation fonctionnelle

RR-1999-11 Parallel Constraint Programming over BSP Vectors
A. LALLOUET, G. HAINS
Résumé :
Mot(s) Clé(s) :

RR-1999-12 Loose vertices in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Résumé : Nous appelons sommet mal-attaché un sommet dont le voisinage induit un graphe P4-libre, et nous montrons que tout graphe de Berge C4-libre G (connexe) soit est cassable (c. à. d. G ou son complémentaire a une étoile déconnectante), soit possède au moins deux sommets mal-attachés non-adjacents. On en déduit que tout graphe minimal imparfait C4-libre a des sommets mal-attachés.
Mot(s) Clé(s) : recherche en largeur lexicographique ; graphe parfait ; graphe de Berge

RR-1999-13 Forbidden Subgraph Decomposition
I. RUSU, J. SPINRAD
Résumé : Nous definissons une nouveau type de decomposition, in interdisant qu'un sous-graphe biparti fixe soit induit dans le graphe donne par les aretes ayant une extremite de chaque cote de la partition. Nous montrons que certaines decompositions obtenues de cette maniere (dont l'union generalisee proposee par Hsu) sont NP-completes.
Mot(s) Clé(s) : decomposition de graphes; graphes totalement decomposables

RR-1999-14 On pleasant vertices in graphs
J.-L. FOUQUET, F. ROUSSEL, P. RUBIO, H. THUILLIER
Résumé : Dans ce rapport, nous généralisons des travaux antérieurs d'Olariu et de Hoàng, Maffray, Olariu, Preissmann sur les graphes parfaitement ordonnables. Chvátal a défini comme parfaitement ordonnable tout graphe dont il existe un ordre linéaire < sur l'ensemble de ses sommets tel qu'il n'existe pas de chemin induit abcd avec les arêtes ab, bc, cd et ayant a < b, d < c. étant donnés un graphe G et un sommet v de G tels que G - v soit parfaitement ordonnable, nous posons des conditions sur v pour pouvoir déduire que G est parfaitement ordonnable. Notre méthode nous permet d'obtenir une nouvelle classe de graphes parfaitement ordonnables, reconnaissable en temps polynomial, contenant les graphes quasi-fragiles, les graphes charmants et d'autres classes de graphes parfaitement ordonnables.
Mot(s) Clé(s) : graphe ; graphe parfaitement ordonnable ; temps polynomial