Sémi-docs
Eve Garnaud (LaBRI)
24 mai 2011
Dépendances fonctionnelles et matérialisation partielle des cubes de données
Dépendances fonctionnelles et matérialisation partielle des cubes de données
La sélection de vues à matérialiser dans des entrepôts de données de plus en plus volumineux est une nécessité. Nous verrons qu’il existe un lien très étroit entre recherche des vues à matérialiser dans un cube de données afin d’optimiser les traitements et les dépendances fonctionnelles sur celui-ci. La contrainte que nous imposons sur les vues que l’on matérialise porte sur le facteur de performance f que celles-ci vérifient. Nous souhaitons également utiliser le moins d’espace mémoire possible pour atteindre cet objectif. Nous caractériserons formellement toute solution optimale (en terme d’espace mémoire) répondant à ce critère.
Cédric Lachat (Equipe BACCHUS, INRIA Bordeaux – Sud-Ouest)
7 avril 2011
Adaptation et partitionnement parallèles de maillages : PaMPA
Les simulations d’écoulements de fluides en trois dimensions nécessitent des maillages de plus en plus conséquents ; il est alors nécessaire de manipuler des maillages distribués. Durant le calcul, il peut être intéressant de modifier le maillage afin d’accroitre la précision des simulations. Le problème est que les algorithmes de remaillage parallèle sont coûteux et non scalables. Après une description de l’état de l’art, nous présenterons un algorithme de remaillage parallèle sous la forme d’une collection de remaillages séquentiels. Nous représenterons les maillages par des graphes, sur lesquels nous appliquerons des algorithmes de contraction et de coloration. Notre approche permettra d’avoir une bibliothèque scalable et de réutiliser des modules existants tels que des remailleurs séquentiels.
Adaptation et partitionnement parallèles de maillages : PaMPA
Les simulations d’écoulements de fluides en trois dimensions nécessitent des maillages de plus en plus conséquents ; il est alors nécessaire de manipuler des maillages distribués. Durant le calcul, il peut être intéressant de modifier le maillage afin d’accroitre la précision des simulations. Le problème est que les algorithmes de remaillage parallèle sont coûteux et non scalables. Après une description de l’état de l’art, nous présenterons un algorithme de remaillage parallèle sous la forme d’une collection de remaillages séquentiels. Nous représenterons les maillages par des graphes, sur lesquels nous appliquerons des algorithmes de contraction et de coloration. Notre approche permettra d’avoir une bibliothèque scalable et de réutiliser des modules existants tels que des remailleurs séquentiels.
Marc Sylvestre (LaBRI)
17 mars 2011
Bounded rewriting for words and terms.
We study a rewriting strategy called the bounded stategy. First, we introduce this stategy for semi-Thue rewriting systems and linear term rewriting systems and we show that several termination problems are decidable for this stategy. Then, we extend it to left-linear term rewriting systems, and we show that bounded rewriting effectively inverse-preserves recognizability.
Bounded rewriting for words and terms.
We study a rewriting strategy called the bounded stategy. First, we introduce this stategy for semi-Thue rewriting systems and linear term rewriting systems and we show that several termination problems are decidable for this stategy. Then, we extend it to left-linear term rewriting systems, and we show that bounded rewriting effectively inverse-preserves recognizability.
Youssouf Oualhadj (LaBRI)
Computing Optimal Strategies for Markov Decision Processes with Parity and Positive-Average Conditions.
We study Markov decision processes (one-player stochastic games) equipped with parity and positive-average conditions. In these games, the goal of the player is to maximize the probability that both the parity and the positive-average conditions are fulfilled. We show that the values of these games are computable. We also show that optimal strategies exist, require only finite memory and can be effectively computed.
Quentin Godroy (LaBRI)
27 janvier 2011
Quelques résultats sur les spanneurs de graphes.
Quelques résultats sur les spanneurs de graphes.
Un spanneur H d’un graphe G est un sous graphe couvrant qui approxime la distance moyennant une économie sur le nombre d’arêtes. Après avoir rappelé la définition et leur motivation, il sera montré quelques algorithmes standards de spanneurs. Par la suite nous montrerons qu’il est possible d’étendre la définition afin de fournir plus de garanties telle que la résistance aux fautes ou la multiconnexité.
Thomas Morsellino (LaBRI)
25 novembre 2010
Puissance des réseaux radio anonymes : caractérisations.
Puissance des réseaux radio anonymes : caractérisations.
Nous traitons des problèmes de l’énumération et de l’élection sur les réseaux radio multi-sauts. Nous considérons un modèle asynchrone de communication radio dans lequel chaque processus émet un message et tous ses voisins l’entendent après un temps fini, mais inconnu. Ce délai dépend du temps pris par les couches réseau inférieures pour assurer l’acheminement des messages.
Dans cette présentation, nous caractérisons les graphes où nous pouvons résoudre ces problèmes et nous présentons un algorithme d’énumération et un autre d’élection. Pour ces deux problèmes, nous soulignons l’importance de la connaissance initiale. Pour le problème de l’énumération, chaque processus connait seulement la taille du graphe et, contrairement aux résultats connus jusqu’à présent, le nombre de ses voisins lui est inconnu. Tandis que pour le problème de l’élection, nous montrons que cette connaissance n’est pas suffisante ; notre algorithme suppose que chaque processus connait initialement une carte du réseau. Étant donné un graphe de degré maximum ∆ avec n noeuds et m arêtes, nos algorithmes émettent O(mn ²) messages de taille O(∆ log n) bits.
