Sémidoc 24 mai

Eve Garnaud (LaBRI)

 

24 mai 2011
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.



 

Sémidoc 7 avril 2011

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.

Sémidoc 17 mars 2011

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.

 

Sémidoc 24 février 2011

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.

 

Sémidoc 27 janvier 2011

Quentin Godroy (LaBRI)

 

 

27 janvier 2011
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é.