Séminaire des Doctorants (Semi-Doc)

Les séminaires des doctorants ou Sémi-Doc permettent aux doctorants de présenter leurs travaux de recherches devant une assemblée principalement constituée d’autres doctorants. Entre autres, ces exposés permettent aux doctorants de s’entrainer à la présentation orale (soutenance, conférence) et de montrer les problématiques abordées dans les autres équipes et thèmes de recherches du LaBRI. Ils se déroulent traditionnellement dans l'amphi du LaBRI un jeudi à 13h30.

Contacts: Rémi GIRAUD, Mathias Lacaud

Prochains séminaires


Précédents séminaires


Mercredi 08 novembre 2017
Une tortue avec un crayon 🐢
Résumé:
Je vais raconter comment nous sommes partis de la sémantique de LOGO

pour mettre au point la sémantique d'un langage de programmation qui permet grâce à une construction algébrique simple et uniforme de faire des dessins, des dessins en 3D, des animations, et de la musique.

27 Septembre 2017
A Model For Collaborative Blockchain-based Video Delivery Relying On Advanced Network Services Chains
Résumé:
The constant rise of Over-The-Top video consumption nowadays challenges the current Internet architecture. In this paper, we propose a user-centric approach that helps the necessary reshaping of the content delivery ecosystem. We study how Blockchain powered smart contracts and Network Service Chaining can be exploited to support such novel collaboration schemes. Finally, our findings suggest that the proposed solution can complement existing technologies by supporting a wide area of business cases while, at the same time, importantly reducing costs.
27 avril 2017
Caractérisation géométrique d'organes tubulaires à partir de plans orthogonaux
Résumé:
Cette thèse s’inscrit dans un contexte médical et s’attache plus particulièrement à l’étude des organes tubulaires (vaisseaux, bronches, neurones...). De nombreuses pathologies, telles que la BPCO pour les bronches, affectent la structure des organes tubulaires. L’objectif de la thèse est de proposer de nouveaux outils permettant la caractérisation automatique de ces organes, par exemple : estimation précise du rayon des tubes et de leur déformation. Les structures d'intérêt étant discrètes, une grande partie de l'état de l'art utilise des lissages afin d'approximer la géométrie "réelle" des organes. Le principal problème d'une telle approche est que les données initiales sont modifiées, ce qui peut induire des biais dans les mesures faites a posteriori.
Dans le cadre de la thèse, nous nous intéressons à la géométrie discrète de segmentations d'organes tubulaires. Pendant ce sémidoc, je présenterai le Voronoi Covariance Measure (VCM), estimateur de géométrie discrète qui nous permet d'estimer de façon robuste les plans orthogonaux. A partir des plans orthogonaux, un algorithme de calcul de squelette (ligne centrale 1D) a été mis au point. Ces deux contributions nous permettent de produire des mesures précises de l'organe.
25 novembre 2016
Content Delivery Networks as a Virtual Network Function: a Win-Win ISP-CDN Collaboration
The switch in video delivery from traditional medium to Over-The-Top (OTT) based services has been a game changer for stakeholders of the media delivery ecosystem. It has changed the value chain enabling Content Delivery Networks and Content Providers to take the lion’s share at the expense of Internet/Network Service Providers. Even if establishing collaboration between them naturally appears as the key to provide good Quality of Service to the end-users, they struggle in finding efficient and fair ways to do so.
This paper directly tackles this problem and proposes a new model for content delivery actors to collaborate over a Virtualized Infrastructure, fairly balancing the revenue stream created.
We list the main challenges and the new technical opportunities to solve them, among which the deployment of a distributed Network Function Virtualization (NFV) platform at the edge of the Internet Service Provider’s network where a virtual Content Delivery Network (vCDN) is proposed to be deployed. Furthermore, we apply a game-theoretic analysis to study different ISP-CDN collaboration models and identify optimality conditions for our proposed CDN-as-a-Virtual-Network-Function approach.
25 novembre 2016
Spatial Augmented reality in Light Field Microscopy
The use of light-field imaging techniques in microscopy enable the reconstruction of the 3D structure of a sample from a single image. The light-field is a function measuring irradiance of light rays. This function is acquired using specific optics like micro-lens arrays that separate light rays by their position and direction.
Thanks to these devices, microscopic samples can be observed from several viewpoints at the same time. Even though the images recorded by the system look different from the usual 2D images, specific algorithms can synthetize new viewpoints with a new focus or reconstruct the depth of the observed object. The system can be improved even more by lighting the sample with a video projector through a micro-lens array. This 4D control of the lighting opens new perspectives to explore, especially in Spatial Augmented Reality.
In this talk, I will present the implementation and the applications of these light-field devices for acquisition and illumination in the context of microscopy, as well as the experiment we wish to run.
22 juin 2016
Service Chain Modeling and Embedding for NFV-based Content Delivery
Increasing over-the-top video consumption endangers the sustainability of content delivery over the Internet. Internet Service Providers (ISP) face difficulties in competing on value-added services with content providers and Content Delivery Network (CDN) operators. In this respect, we propose a new model for the collaboration between content delivery actors, where CDN operators can deploy their software in ISP infrastructures using Network Function Virtualization (NFV) techniques.
As the ISP network topology and utilization is deemed confidential, we use a high-level Service Level Agreement (SLA) for the negotiation of both computing resources and connectivity, allowing the ISP to optimize server selection, while providing at the same time sufficient flexibility to the CDN operators for content delivery.
Furthermore, we present a linear programming formulation and an algorithm for service chain embedding. Our simulations results show significant gains of the algorithm in terms of request acceptance rate and resource consumption. Finally, we validate the efficiency of the proposed service chain model for Virtual CDN management.
19 mai 2016
Jeux-vidéo et classification : un système d'analyse automatique des flux audio-visuels pour aider à la compréhension de l'expérience joueur
En Nouvelle-Zélande, le système de classification des jeux-vidéo (interdisant un jeu aux moins de 12, 16 ou 18 ans) est basé sur les mêmes critères que ceux utilisés pour les films.
Ainsi, il n'est fait aucune distinction entre une expérience "spectateur" d'un jeu vidéo, et une expérience "joueur". L'OFLC (Office of Film and Literature Classification) a donc demandé à l'Université de Waikato, en 2011, de conduire des recherches afin de mettre en valeurs les spécificités d'une expérience "joueur", et adapter le système de classification en conséquence.
Cette présentation s'intéresse à expliquer ce que l'on entend par "expérience joueur", puis introduira différents travaux de recherche permettant de quantifier cette expérience.
Enfin, une nouvelle méthode d'analyse sera décrite, basée sur le traitement automatique des flux audio et vidéo produits par le joueur lorsque celui-ci interagit avec le jeu.
28 avril 2016
Partitionnement de carré pour le calcul parallèle du produit de matrices
Le problème de partition de matrices en un ensemble de sous-matrices a connu un certain intérêt ces dernières années. C'est en effet une opération cruciale lorsqu'on s'intéresse aux opérations d'algèbre linéaires sur des plate-formes hétérogènes.
Considérons par exemple le produit de matrices non-creuses basés sur l'algorithme de Canon. Pour simplifier restreignons-nous aux multiplications C=AB de deux matrices carrés A et B de taille n x n. Supposons de plus que ces matrices sont décomposées en blocs, la taille de ces derniers étant choisie afin de s'adapter à toutes les ressources disponibles (typiquement CPUs et GPUs). Alors, à l'étape k de l'algorithme, le produit diatique (outer-product) de la k-ème colonne de blocs de A et de la k-ème ligne de blocs de B est calculé.
Supposons que le processeur P possède un ensemble de s blocs à calculer dont les projections sur les différents axes ont une taille respectives de h et w. Alors le volume de calcul que P doit effectuer est proportionnel à s et le volume de communication que P reçoit est proportionnel à h+w. Pour équilibrer la charge de calcul, chaque processeur doit recevoir un nombre de blocs proportionnel à sa vitesse de calcul relative. Par ailleurs, le volume total de communication est proportionnel à la somme des projections des aires possédées par les différents processeurs sur les axes. Donc, pour minimiser le temps de calcul et la charge totale de communication, le problème d'optimisation peut se ramener à la partition d'un carré en un ensemble de zones d'aires prédéfinies (pour l'équilibrage des charges de calcul) telles que la somme de leurs projections sur les axes est minimisée (pour réduire autant que possible les communications).
24 mars 2016
Multi-Resolution Meshes for Feature-Aware Hardware Tessellation
Hardware tessellation is de facto the preferred mechanism to adaptively control mesh resolution with maximal performances. However, owing to its fixed and uniform pattern, leveraging tessellation for feature-aware LOD rendering remains a challenging problem.
We relax this fundamental constraint by introducing a new spatial and temporal blending mechanism of tessellation levels, which is built on top of a novel hierarchical representation of multi-resolution meshes. This mechanism allows to finely control topological changes so that vertices can be removed or added at the most appropriate location to preserve geometric features in a continuous and artifact-free manner.
We then show how to extend edge-collapse based decimation methods to build feature-aware multi-resolution meshes that match the tessellation patterns. Our approach is fully compatible with current hardware tessellators and only adds a small overhead on memory consumption and tessellation cost.


14 janvier 2016
Dynamic Adaptive Streaming over HTTP (DASH) assisté par une approche multi-description: une solution de streaming pragmatique visant à maximiser la qualité d'expérience utilisateur.
Le déploiement récent et à large échelle des techniques de streaming adaptatifs (telles que DASH) a pu améliorer la qualité d'expérience utilisateur perçue lors du visionnage de vidéos sur technologies IP.
Au cours de ce Sémi-doc je vais, dans un premier temps, vous présenter ces techniques utilisées tous les jours par les acteurs industriels du streaming vidéo sur internet. Les activités de recherche visant à améliorer constamment la qualité d'expérience utilisateur seront également abordées, pour enfin vous exposer une partie de mes travaux de recherche: une solution de streaming, multi-source, multi-chemin, pragmatique et à faible coût d'intégration maximisant la qualité d'expérience utilisateur.
Cette proposition de solution a été conçue pour être agnostique des codecs utilisés et compatible avec les technologies de streaming standardisés dans l'objectif de faciliter son adoption dans des cas d'utilisation réels. Dans cette présentation, je vous expliquerai les tenants et aboutissants des innovations apportées aux codecs, aux protocoles de streaming et aux mécanismes d'adaptation (adaptation du contenu délivré et sélection des meilleurs serveurs de streaming au cours de la session de streaming). Je vous présenterai également quelques résultats sur l'amélioration de la qualité d'expérience par rapport aux solutions existantes ainsi que l'impact que pourrait avoir notre solution sur les acteurs industriels du streaming vidéo.
10 décembre 2015
Traitement d'images par méthodes basées-patch non-locales : Applications à la segmentation d'images médicales et à l'étiquetage de visages
Les images et vidéos naturelles prises par des appareils récents (smartphones, etc.) souffrent de plusieurs problèmes tels que les changements d'illumination, le bruit d'acquisition ou les occlusions. Afin de réduire ces problèmes, plusieurs méthodes existent : homogénéisation de la couleur, débruitage, recalage, inpainting, etc. Ces dernières années, l'utilisation de patchs de pixels dans des approches non-locales s'est révélé plus efficace que de considérer uniquement un voisinage local de pixels. Durant ma thèse, nous proposons de développer de nouvelles méthodes générales et rapides, basées-patch non-locales, appliquées au traitement d’images et de vidéos.
Dans ce sémi-doc, je vais présenter le concept général des algorithmes basés-patch non-locaux et les méthodes développées jusqu'ici durant ma première année de thèse. Nous avons principalement travaillé sur la segmentation d'images médicales 3D et sur comment construire des patchs de superpixels appliqués à l'étiquetage de visages sur des images naturelles.


10 septembre 2015
Migrating to a NFV-based Home Gateway: introducing a Surrogate vNF approach
Virtualizing network functions is becoming a major trend in today's research on cloud computing. Among networking elements, the Home Gateway appears to be one with the most diverse functions to handle and hus, with great potential for virtualization. To this end, the paper proposes a solution to ease adoption by Service Providers of the latest breakthroughs in cloud computing technologies towards a virtualized Home Gateway.
Although the NFV approach globally pretends bringing operational advantages in terms of CAPEX and OPEX, it is essential to prove them for Home Gateways scenarios where compatibility and versatility are strong requirements. To achieve this goal, we introduce the concept of Surrogate vNF, which makes Home Gateways NFV aware. The paper highlights a migration path towards full Home Gateway virtualization and proves its concept through a real implementation and a simulated evaluation on a practical use case related to video content distribution.

2014-2015

28 mai 2015
Classification de graphes dynamiques
Étant donné un graphe dynamique, donné sous la forme d’une séquence de graphes statiques ou bien comme une succession d’évènements topologiques (apparitions/disparitions de liens de communication), on s’intéresse à tester automatiquement certaines propriétés temporelles sur le graphe. Les propriétés qui nous intéressent correspondent à des conditions nécessaires et/ou suffisantes pour la réalisation de tâches distribuées classiques (élection, diffusion, comptage, etc.)
Nous avons répertorié à ce jour une vingtaine de propriétés. Par exemple, le réseau est-il temporellement connexe ? (existence d’un trajet, i.e. d’une succession d’arêtes dont les dates d’existence sont temporellement croissantes, depuis chaque sommet vers chaque autre sommet) ; certaines arêtes réapparaissent-elles dans un temps borné ou de manière périodique ? Leur ensemble vérifie-t-il certaines propriétés ? Être capable de vérifier ce type de propriété automatiquement nous permettrait de déterminer dans un contexte de mobilité donné (p. ex. drones, robots, voitures, dont on peut obtenir ou générer des traces de connexité), les tâches réalisables par l’ensemble des entités.
12 mars 2015
Simulation en aveugle
Nous appelons simulation en aveugle le fait de simuler une distribution de probabilité qui dépend d'un paramètre inconnu n à partir d'un générateur aléatoire qui renvoie un élément de manière uniforme d'un ensemble de taille n. Cette question émerge dans un contexte de maintenance de réseaux logiques, lorsque les nœuds n'ont pas accès à la taille du réseau.
Dans cet exposé accessible, nous verrons dans un premier temps comment simuler des lois simples (Bernoulli, Géométrique, Binomiale, ...) dépendantes de n. Dans un second temps, nous présenterons un critère nécessaire et suffisant à la simulabilité en aveugle, avec quelques idées des preuves sous-jacentes.
12 février 2015
Rook-drawing for planar graphs
We propose a new type of graph drawing called "rook-drawing". A rook-drawing of a graph G is obtained by placing the n nodes of G on the intersections of a regular n*n grid, such that each line and column of the grid supports exactly one node. We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs. We then show that there exist planar graphs which do not have a planar straight-line rook-drawing. Finally, we give a linear algorithm to compute a planar rook-drawing for planar graphs with at most n-2 bended edges.
29 janvier 2015
Distributed computing with a majority of faulty processes : renaming and splitters


Distributed computing is a vast domain that studies the interaction of several independent entities (called ``processes'') communicating with each other to work locally towards some global objective. There are many different models used in this context, some of which assume that some processes may suddenly crash and stop doing anything, without warning. The study of fault-resilient algorithms (i.e. algorithms that take into account the possibility of crashes) is rather extensive, including in the asynchronous model I consider, but most of the results in this domain only consider a strict minority of faulty processes (no more than n/2 processes may crash during any execution). The object of my phd thesis is to study what can be done, and which results can be extended, in the case where a majority of processes may crash.
The renaming problem has been introduced by Attiya et al. [1], and consists on the following : Each process start with a unique name in a large namespace (such as an IP address), and each process tries to acquire a new name such as, at the end of the algorithm, each process has a new unique name in a much smaller namespace. This problem was first solved in asynchronous message-passing systems with a strict minority of processes that might crash, and later largely studied in wait-free shared memory systems, which can themselves be simulated in the former model (as explained in [2]). Splitters are basic shared memory objects that were introduced in [3] in order to build a fast renaming algorithm, and extending the renaming to a ``long-lived'' version. A splitter is an object that can be accessed through one operation Split(), and returns a direction in {right, down, stop}, with the property that not all processes return right, not all return down, and at most 1 process may return stop.
In asynchronous message-passing systems with a majority of faulty processes, the renaming problem cannot be solved, and splitters cannot be implemented. But we extended these notions to k-renaming and k-splitters, both for one-shot and long-lived versions. Instead of having unique name for each process, each new name (in a small namespace) may be acquired by at most k processes, and at most k processes accessing a k-splitter may return stop. We developed an optimal algorithm for implementing k-splitters, i.e. the algorithm implements them with k = floor(n/(n-f)), where n in the number of processes and f the maximal number of faulty processes among them, and it is not possible to implement k'-splitters with k' < floor(n/(n-f)). Although the namespace is not optimal, especially in the long-lived version, k-renaming based on these k-splitters is optimal for the same reason that k=floor(n/(n-f)) is both a lower bound, and a reached upper bound.
[1] H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk. Renaming in an asynchronous environment. J. ACM, 37(3):524–548, July 1990.
[2] H. Attiya, A. Bar-Noy, and D. Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124–142, 1995.
[3] M. Moir and J. H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming, 25(1):1 – 39, 1995.


2013-2014

12 juin 2014
Service Discovery for Highly Volatile Swarms of Unnamed Autonomous and Communicating Systems


Service discovery in MANETS (Mobile ad-hoc Networks) consists for an entity in locating a service hosted by another entity of the newtork. Such a system is very useful in swarms of autonomous unnamed systems like drones or ground robots. A service is actually a capacity provided by one or several vehicles (heat sensor, motion sensor, decision making, long range antenna, telescopic arm, etc.).
Existing discovery solutions depend on the mobility of the nodes and require particular connectivity patterns between them. Moreover, these previous works focus on the location part without addressing the access problem (i.e. the way to use a service once it has been discovered). To the best of our knowledge, no discovery mechanism has been designed that would be dedicated to autonomous swarms and solve these problems. A state of the art about existing service discovery models will be introduced in this talk.
AMiRALE (Asynchronous Missions Relay for Autonomous and Lively Entities) is a service discovery model dedicated to swarms of unnamed and communicating systems. This model is independent of both nodes mobility and connectivity patterns and addresses the problems introduced here-before. In this talk, the design of the AMiRALE model and its different versions will be developed. An illustration of a park cleaning scenario with the help of this system will be presented at the end of the talk.
27 février 2014
Markovianity of the invariant distribution of probabilistic cellular automata


A probabilistic cellular automaton (PCA) with neighborhood of size 2 on the line is a probabilistic algorithm that maps a bi-infinite word w at time t on an alphabet A onto an other bi-infinite word w' at time (t+1) such that the probability of the letter w'(i) depends only on letters w(i) and w(i+1). Moreover, the transformations of the letters are synchronous, independent and identically distributed. So, when we start with a random (or not) configuration, we can iterate our PCA. A natural question is to ask for the random (or not) configurations that stay invariant by the iteration of our PCA. A classical result on PCA, due to Toom & al., claims that a Markov chain with transition kernel M is invariant iff M satisfies a system of equations depending on the automaton. In the case of a two letters alphabet, this condition simplifies: the data of the automata is just needed to know if it owns an invariant Markov chain (the condition is only about the automaton, and not about M) [Beliaev & al.]. A question appears so: could we obtain a similar condition for an alphabet with more letters? We will show that the answer is yes. Moreover, this answer gives also the invariant Markov chain algorithmically.
30 janvier 2014
Simulating a weak shared memory in message-passing systems


In distributed computing, there are 2 main communication abstractions considered : message-passing (processes directly send messages to one another), and shared memory (processes communicate through some shared object).
Under some conditions, it is possible for processes using a message-passing system to implement (or simulate) some shared memory objects. This is useful because it is often easier to write distributed algorithms using those shared objects. Thus, any problem that can be solved using shared memory, could also be solved in message-passing systems. If some conditions are not verified in the message-passing system, it is impossible to simulate usual shared memory objects (with good properties). My work is about the simulation of some new (extended) shared objects, with weaker properties, but that can still be implemented under those circumstances.
12 décembre 2013
Une brève introduction aux algorithmes d'optimisation discrète


Dans cet expose nous allons présenter un survol de l'optimisation combinatoire et discrète. Apres une introduction générale du domaine ainsi que de quelques-uns de ses exemples phares, les paradigmes majeurs de l'optimisation discrète seront abordés. Pour chacun un exemple de modélisation sera présenté.
  • Carlos Carvajal (INRIA)
28 novembre 2013
Modeling the early visual system: The story of the Olivier salad


The secret recipe of how the visual system works has been one of the utmost sought discoveries in neuroscience during the last decades. Considering that it uses around 50% of the resources of the brain (directly or indirectly), the massive initiatives studying the brain nowadays are expected to help unraveling also this mystery. However, there is much more than the brain in the visual system. For instance, the retina not only transduces light, and the thalamus not only relays information: the early visual system is a complex network of sub-networks interacting with each other. This complexity has resulted in expensive computational models with many parameters. Here, parallelizing with the story of the Olivier salad, we show how a functional recipe can include both new knowledge and hypotheses to explain visual treatment, phenomena, and their links to cognition and behavior, using simple bio-inspired algorithmic implementations that do not require the complexity of existent computational models.
This presentation starts with the classical recipe of human vision, to explain what this view is missing, and how we try to understand such distributed dynamical asynchronous system. Then, it develops the difficulties in the process and how, if we focus on functionality, we can implement a cheaper and simpler systemic computational model that allows us to bind knowledge and hypotheses, so cognition and behavior can be studied without losing taste.
14 novembre 2013
Optimizing BRDF orientations for the Manipulation of Anisotropic Highlights


We introduce a system for the direct editing of highlights produced by anisotropic BRDFs, which we call anisotropic highlights. We first provide a comprehensive analysis of the link between the direction of anisotropy and the shape of highlight curves for arbitrary object surfaces. The gained insights provide the required ingredients to infer BRDF orientations from a prescribed highlight tangent field. This amounts to a non-linear optimization problem, which is solved at interactive framerates during manipulation. Taking inspiration from sculpting software, we provide tools that give the impression of manipulating highlight curves while actually modifying their tangents. Our solver produces desired highlight shapes for a host of lighting environments and anisotropic BRDFs.
31 octobre 2013
Image Retrieval with non-regular pyramid partitioning via Graph-Cuts


We present a nouvel approach to addresses the well-known problem of adding spatial information to the standard bag-of-visual-words (BoVW) model for Image Retrieval.
To that end, a set of graphs descriptors are constructed for the entire image or for local image regions via graph-cuts based methods. These descriptors are then incorporated into a bag-of-visual-words approach, leading to a method called bag-of-bag-of-visual-words (BBoVW).
In experimental results for Caltech101 benchmark, our proposed method performs better than SPM(Spatial Pyramid Matching) for 19 objects categories.
11 juillet 2013
Energy Conservation in Collaborative Applications in Wireless Sensor Networks


Wireless Sensor Networks (WSN) consist on tiny nodes that cannot support big batteries which imposes the use of small-capacity batteries and energy optimization in the software layer. These nodes are densly deployed to accomplish collaborative applications such as Target Tracking and Area Monitoring by reporting collected data with "acceptable" quality while preserving scarce energy resources. To do this, we try to take profit from the collected data to optimize the communications and organize the network to reduce useless energy consumption in sensing operations.
In the first part of this talk, we address these methods of energy conservation by giving a classfication of them. Next, we describe our contributions to resolve this problem and discuss the obtained results. The first contribution is about target tracking schemes based on data filtering prediction algorithm (EKF). The second contribution consists of dynamic clustering for data collection and the last contribution is an ongoing work about energy consumption modeling under the constraints of data precision.
14 juin 2013
Let's talk about Drones


For some time, medias have strongly linked drones with army forgetting their important growth in the civil scope. It results in a highly negative image and a kind of global fear of drones in spite of all the benefits they provide in various fields.
This presentation aims to make a state of the art on drones usages, especially in France. We will talk about the different drone types, usages, related french law and also actual and future intrinsic projects. Finally, we will discuss about positions and research topics of the LaBRI MUSe theme in this scope.
This presentation is a preview of an event organized by Cap Sciences, therefore it will be very accessible.
10 avril 2013
Calcul of global functions and information broadcasting applied to compact routing


I'll present two distributed algorithms which can be used in compact routing algorithm.
Routing is usually achieved by calculation of routing tables that store shortest path in a given graph/network. It is known that shortest path routing requires a linear memory. Compact routing use routing table of sub-linear size by relaxing the «shortest path constraint».
The first algorithm is a generic algorithm that allow calculation of a global function on a network (for example a function that computes the lowest node identifier of the graph). The second one, is used to broadcast efficiently some information to a (distinguishable) subset of nodes from any source node.
7 février 2013
Playing (combinatorially) with dominoes


A combinatorial game is a finite two-player game with perfect knowledge and no chance. There exist several combinatorial games played with dominoes. We will present some of them played by toppling dominoes that are set on a row. In particular, we will speak about winning strategies and mention the values of some games.
20 décembre 2012
Jeu de coloration sur les graphes


Nous présenterons, au cours de cet exposé, le jeu de coloration sur les graphes, quelques propriétés de ce jeu, différentes approches permettant de l'étudier, et enfin quelques variantes.

Soient un graphe G donné et un ensemble de couleurs K. Deux joueurs, Alice et Bob, colorient (proprement) à tour de rôle un sommet non-colorié de G avec une couleur de K, construisant ainsi une coloration propre partielle du graphe de plus en plus étendue. Le jeu se termine par une victoire d'Alice quand tout le graphe est colorié, ou par une victoire de Bob quand continuer la coloration est devenu impossible. Le "nombre chromatique ludique" d'un graphe G est le plus petit entier k tel que k couleurs suffisent à Alice pour s'assurer la victoire.
25 octobre 2012
Network Emulator : Une plate-forme virtuelle réseau pour l'aide à la recherche et à l'enseignement


L'expérimentation est généralement une phase importante dans l'élaboration d'une application, mais aussi dans un enseignement de type pratique, particulièrement quand ceux-ci touchent de prés ou de loin aux réseaux.
Malheureusement, il est assez difficile, voir impossible, de posséder une infrastructure physique contrôlée et suffisante, en terme de taille et de performance, afin de réaliser cette tâche.
Ainsi, la virtualisation est une technique à portée de main pour jouer le rôle de plate-forme de test. Nous proposons un outil appelé NEmu ayant pour but de générer des réseaux virtuels dynamiques à la demande afin de tester et de valider des prototypes d'applications réseaux avec un contrôle complet de la topologie et des propriétés des liens. NEmu fournit une infrastructure virtuelle jouant le rôle d'un overlay en utilisant des émulateurs tels que QEMU. NEmu permet la création et la gestion de réseaux virtuels avec des ressources matérielles limitées et sans aucun droit d'accès particulier sur l'infrastructure physique.
21 Juin 2012
Packing rectangles within a rectangle.


Let V be a set of rectangular items and C a rectangular container. The two-dimensional Orthogonal Packing Problem (OPP-2) consists in deciding whether the set V can be packed in C without overlapping and without rotating the items. If the set V can be packed in C, then V is called a feasible set. This problem is NP-complete and can be seen as a sub-problem of the well known two-dimensional Orthogonal Knapsack Problem. Fekete and Schepers introduced a powerful characterization of feasible packings, based on interval graphs. Using this characterization they designed an efficient algorithm to solve OPP by enumerating the interval graphs with a certain number of constraints. We present a new algorithm for solving OPP-2 based on a more compact representation of interval graphs. One of the main advantages is having a reduced number of "symmetrical" solutions.


31 Mai 2012
Abstractions for timed automata.


Timed automata are finite automata extended with clocks. Clocks can be used to constrain transitions of the automaton. Additionally, they can be reset to zero along a transition. As the clocks range over reals, the state space of a timed automaton is uncountable. A finite abstraction of this state space is necessary for algorithmically verifying essential properties of the automaton.
In this talk, we present some recent results on how to efficiently handle abstractions for timed automata, and to what extent can one abstract the state space for correctly verifying some of the fundamental properties.

.

01 Mars 2012
Connexité dans les graphes de genre $g$ avec obstacles: un schéma d'étiquetage.


Nous présenterons une méthode d'étiquetage compact d'un graphe $G$ de genre $g$ de façon à ce qu'on puisse répondre à une requête de connexité entre le sommet $u$ et $v$ dans $G \setminus X$ à partir des étiquettes de $u$, de $v$ et de celles des sommets de $X$.

16 février 2012
Linguistique Computationelle : extraction et utilisation d'une grammaire catégorielle à partir du corpus de Paris VII


Cet exposé traitera de l'utilisation des grammaires catégorielles dans le cadre de l'apprentissage automatique. Il sera divisé en trois parties. En premier lieu, une brève explication sur les outils utilisés sera donnée, du corpus de Paris VII qui nous sert de base aux transducteurs d'arbres.Ensuite, on détaillera l'extraction d'une grammaire catégorielle simple à partir du corpus de Paris VII, en utilisant un transducteur généralisé. Dans une dernière partie, présentant les travaux en cours, on approfondira l'utilisation possible de la forêt de dérivations obtenue, principalement par rapport à 'analyse de phrases.

26 janvier 2012
Beyond Bringing Life to Computer-Generated Character


Over thirty years have been required in the field of Computer Graphics and Computer Vision to be mature enough, from the first use of computer-generated three dimensional graphical model to the first accomplished photorealistic 3D movie. There is no doubt that Computer-based Imagery Technologies have significantly influenced our everyday life and the industry, as well. Nowadays highly-detailed animations of live-actor performances are increasingly easier to acquire using an existing capturing device like optical motion capture, multiple views camera platforms, 3D laser scanner or new low-cost sensors. At first glance, a serious challenge is to achieve plausible skeletally or boneless deformations while preserving global and local captured properties of the body surface or the pose with a limited number of controllable, flexible and reusable parameters. Secondly, the problem of reusing captured data is a new outstanding problem for researchers. In this talk, I will present a wide variety of advanced animation techniques and promising opportunities to deal with.

2 décembre 2011
Partitionnement dans les réseaux mobiles : conception et évaluation de protocoles auto-stabilisants robustes


Cette présentation résume mes travaux de thèse qui portent sur l'algorithmique distribuée tolérante aux pannes adaptée aux réseaux mobiles à grande échelle.
Je présenterai l'approche auto-stabilisation robuste, que nous avons introduit, visant à améliorer la garantie de service au sein de l'approche classique auto-stabilisation. Je présenterai ensuite mes contributions : deux protocoles pour résoudre les problèmes de partitionnement, et l'établissement et le maintien de la connaissance des clusters voisins, ainsi qu'une comparaison expérimentale des deux approches.

26 octobre 2011
Adaptation au repartitionnement de graphes d'une méthode d'optimisation globale par diffusion au moyen d'arêtes fictives


La résolution parallèle efficace de simulations numériques dont les coûts de calcul évoluent au cours du temps (telles que celles mettant en oeuvre un remaillage dynamique) nécessite des méthodes efficaces de redistribution des données attribuées à chaque processeur. L'objet de cet article est d'étudier l'adaptation au repartitionnement de graphes, qui est un modèle courant du problème de redistribution des données, d'un ensemble d'algorithmes utilisés avec succès dans le cadre du partitionnement parallèle de graphes, et tout particulièrement d'un algorithme d'optimisation globale de la forme des partitions par diffusion.
Le modèle expérimental exposé ici est séquentiel, mais les algorithmes présentés peuvent facilement être transposés en parallèle.
Afin de valider notre approche, nous comparons nos résultats, implémentés au sein du logiciel SCOTCH, à la routine de repartitionnement mise en oeuvre au sein du logiciel ParMetis.

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.

  • 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.

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.
24 février 2011
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.
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é.
25 novembre 2010
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.
28 octobre 2010
Introduction au "Edge Bundling" : une technique pour réduire les problèmes d'occlusion dans la visualisation de grands graphes.


La visualisation de graphes contenant un grand nombre de sommets et d'arêtes soulèvent différents problèmes. En effet, les dessins de tels graphes souffrent généralement d'occlusions visuelles dues au grand nombre d'arêtes et de leurs croisements. Par conséquent, il est difficile d'identifier les connexions ainsi que les principaux flux d'échange entre sommets. Les techniques de "Edge bundling" ont récemment été introduites afin de répondre à ces problèmes. A partir du dessin d'un graphe, leur principe consiste à rerouter les arêtes en faisceaux afin d'améliorer la lisibilité de la visualisation. Dans cet exposé, je commencerai par faire un état de l'art des différentes techniques de "Edge bundling". Je détaillerai ensuite l'algorithme de "Edge bundling" que j'ai présenté lors de la conférence EuroVis 2010. J'introduirai également des techniques de rendu graphique qui peuvent être appliquées à ce type de représentation. Je terminerai en présentant différentes techniques d'interaction qui peuvent être combinées à ce type de visualisation pour faciliter l'exploration du graphe.
  • Waffa Ben Jaballah (Unité de Recherche PRINCE, Hammam Sousse, Tunisie)
1er juillet 2010
Authentification de la source dans les réseaux de capteurs.


Un Réseau de capteur sans fil (RCSF) est composé d'un grand nombre de nœuds de capteurs qui communiquent à l’aide d’un réseau ad hoc sans fil. Ces nœuds de capteurs ont de contraintes de ressources très sévères et ils sont largement déployées dans les domaines de militaire, la santé, le transport et les environnements commerciaux. Puisque les réseaux de capteurs peuvent circuler des données sensibles et fonctionner dans des environnements hostiles sans surveillance, il est impératif que des soucis de sécurité soient adressés dès le début de la conception du système. Ainsi, il est important de s'assurer que les informations transmises dans les réseaux de capteurs sans fil sont en cours de validité et émises par la source prétendue. Nous avons conçu deux schémas d'authentification de la source basés sur la clé symétrique. Nous montrons que ces schémas d'authentification sont très efficaces en termes de consommation d'énergie liée à la fois au calcul et à la communication. En outre, nous avons évalué ces schémas d’authentification selon plusieurs métriques en utilisant TINYOS et TOSSIM.
  • Présentations de travaux réalisés dans le cadre du Master Recherche au LaBRI.
8 juin 2010


-Eve Garnaud (LaBRI)
Version à deux joueurs du jeu du Solitaire.
On s'intéressera à des configurations de jeu particulières sur un chemin pour démontrer quelques propriétés. Encadrement : P. Dorbec et E. Sopena.
-Clément Charpentier (LaBRI)
Degré minmax, décomposition d'arêtes et jeu de coloration dans les graphes planaires.
Ces trois problèmes, fortement liés, mobilisent de nombreux chercheurs à l'heure actuelle. Nous les aborderons tous les trois et présenterons quelques résultats originaux sur le degré minmax de certaines classes de graphes planaires. Encadrement : M. Montassier et A. Raspaud.
27 mai 2010
Analyse et génération dans les ACG avec effacement.


Les grammaires catégorielles abstraites (ACG) furent créées en 2001 en tant que formalisme grammatical formalisant l'interface entre syntaxe et sémantique des langues naturelles; elles peuvent être vues de manière plus générale comme des grammaires de lambda-termes. L'un des nombreux avantages de ces grammaires fut démontré par l'élaboration d'algorithmes d'analyse et de génération de la langue naturelle de complexité faible (LOGCFL) dans le cas où la copie ne se fait que sur des termes d'ordre 1, et où l'effacement est interdit (Kanazawa 2007).
Je vous présenterai les différents concepts évoqués et une extension de ces méthodes d'analyse à des grammaires avec effacement ainsi que les problèmes de typage dans le lambda-calul liés à cette technique.
29 avril 2010
Approche discrète pour la reconstruction tomographique à partir de données incomplètes.


Les méthodes de reconstructions tomographiques s'appuient sur le théorème de Radon (1919) ou son équivalent dans l'espace de Fourier. Ces théorèmes sont exacts en continu, mais leur discrétisation entraîne des approximations sur les images. Le fer de lance de la recherche en tomographie des dernières décennie a donc été le développement de méthodes permettant d'améliorer la qualité des reconstructions. On peut principalement les classer en deux grandes familles. D'une part, les méthodes directes s'appuient sur une inversion optimisée des théorèmes. D'autre part, les méthodes itératives modélisent le problème sous la forme d'un système linéaire y = Rx + b (y : le vecteur projections, x : l'image à reconstuire et b : le bruit) à résoudre (méthodes algébriques, stochastiques, programmation linéaire, ...).
Dans un premier temps, je présenterai ces différentes familles pour arriver jusqu'à une classification qualitative (qu'appelle-t-on une bonne qualité de reconstruction?) et quantitative (complexité, temps de calculs, implémentations) des méthodes.
Cette comparaison nous amènera à constater l'efficacité des méthodes dans des cas d'utilisations "standard". Nous verrons toutefois leurs limites face à un problème encore ouvert de la tomographie : la reconstruction à partir de données incomplètes. Lorsqu'un angle de projections successives n'est pas disponible, l'image reconstruite subit des déformations (missing wedge effect).
En imposant une géométrie aux projections en fonction de la géométrie de l'image (taille, forme des pixels), je montrerai qu'il existe une transformée discrète exacte de Radon, appelée transformée Mojette, dont l'inversion est insensible à l'effet du missing wedge. Toutefois, cette reconstruction n'est pas adaptée a une acquisition classique et elle est extrêmement sensible au bruit.
Je mettrai donc d'abord en place un système de mappage continu-discret entre une acquisition modélisé par la transformée de Radon et une reconstruction par Mojette. Je détaillerai ensuite une optimisation de l'inversion moins sensible au bruit. Des premiers résultats, je déduirai comment cette méthode pourrait être une amorce de solution au problème du missing wedge.
25 mars 2010
Impact des architectures multiprocesseurs sur les communications dans les grappes de calcul.


Depuis plusieurs années, le calcul haute performance s'appuie majoritairement sur l'utilisation de grappes de machines multiprocesseurs. La démocratisation du "multicoeurs", avec un nombre croissant de coeurs, conduit à une augmentation significative de la complexité interne des machines de calcul. Des coeurs vont ainsi partager non seulement de la mémoire, des ressources réseaux, ... , mais aussi une partie de la hiérarchie de cache. Pour obtenir de bonnes performances, les applications parallèles doivent tenir compte des caractéristiques matérielles de ces architectures complexes. Dans cet exposé, je ferai un point sur ces caractéristiques avant de présenter les stratégies actuellement mises en place dans les bibliothèques de communication pour conserver de bonnes performances.
25 février 2010
Un environnement de preuve des calculs locaux.


Prouver la correction d'un algorithme distribué est une tache longue et complexe, de par la nature même des systèmes étudiés. Le modèle des calculs locaux, ayant pour fondement la théorie des graphes, permet - en travaillant à un niveau élevé d'abstraction - de simplifier ces preuves, tout en restant implémentable de manière distribuée. Nous présenterons dans ce séminaire l'effort actuel de formalisation de cette théorie à l'aide de l'assistant de preuve COQ. Nous montrerons que le système de type riche de COQ nous permet de prouver la correction d'algorithmes, aussi bien que des résultats plus abstraits, comme des résultats d'impossibilité ou des inclusions de classes d'algorithmes.
Page mise à jour le 27/02/2018 à 17:57