Nos tutelles

CNRS

Nos partenaires


Accueil > Actualités > Séminaires > Archives Séminaires

Séminaires passés 2014-2015


- M. Ahcene BOUNCEUR (Université de Brest) : Trouver l’enveloppe polygonale d’un réseau de capteurs sans fil.
Vendredi 3 juillet 2015 - 11 h 15 -Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Trouver la frontière d’un réseau de capteurs sans fil (RCSF) fait partie des problématiques les plus importantes aujourd’hui. Cette
frontière peut être utilisée, par exemple, pour surveiller une frontière, un endroit sécurisé ou un site sensible d’un pays. Une des méthodes
qui peut être utile pour ce type de problèmes est l’algorithme de Jarvis, qui doit être adaptée pour tenir compte des nœuds connectés
dans un graphe Euclidien. Pour ce type de réseaux, la complexité est réduite de O(nh) à O(kh^2), où n est le nombre de capteurs, k est le
degré maximum d’un capteur dans le réseau et h est le nombre des capteurs de la frontière. L’application de cet algorithme pour les
réseaux de capteurs permet à chaque itération de déterminer le nœud frontière voisin du nœud frontière courant. L’avantage de cette
procédure est que chaque nœud connaît son voisin en une seule itération.
Ensuite, chaque nœud envoie périodiquement un message à son voisin, qui devrait répondre. Si aucune réponse n’est reçue, une situation de
défaillance ou d’intrusion sera déclenchée et la restructuration du réseau sera lancée pour trouver une nouvelle frontière. Dans ce travail,
nous avons montré que l’application de cet algorithme en présence de sous-graphes spécifiques peut conduire à une situation de blocage.
Nous avons également montré comment surmonter cette situation. Pour une implémentation sur des vrais capteurs, la version distribuée de
l’algorithme sera présentée. Les algorithmes développés ont été validés à l’aide de la plateforme de conception et de simulation de réseaux de
capteurs CupCarbon.


- Adrien VAN DEN BOSSCHE - IRIT Toulouse : Prototypage rapide de protocoles pour le réseau de collecte dans l’IoT avec OpenWiNo.
Jeudi 2 juillet 2015 - 14 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

L’Internet des Objets est en train de révolutionner les usages grâce aux communications entre petites entités électroniques intelligentes. Parallèlement, les avancées récentes dans l’Open Hardware permettent le prototypage rapide de systèmes avancés.
Inscrite dans ce double contexte, OpenWiNo est une architecture matérielle et logicielle permettant le prototypage rapide des protocoles dans les réseaux de capteurs sans fil et l’Internet des Objets. Elle permet d’implémenter simplement et rapidement un protocole de communication original, quelque soit son niveau protocolaire (MAC, NWK ou APL), pour permettre son évaluation en environnement réel. OpenWiNo comprend un émulateur et un environnement réel basé sur Arduino. Grâce à la richesse des bibliothèques Arduino, il permet de compléter le test réel par de vrais capteurs, permettant une évaluation exhaustive du système, incluant l’usage.


- Philippe LENCA, professeur, Telecom Bretagne, Brest : Sur quelques propriétés des mesure de qualité des règles d’association.

Mardi 30 juin 2015 - 10h30 - Amphi Bruno Garcia - Bâtiment ISIMA

Nous présenterons une synthèse, nécessairement partielle, de travaux concernant les mesures de qualité des
règles d’association et des règles d’association de classe en présentant les principaux critères d’évaluation des mesures et en illustrant le rôle de chacun de ces critères dans le comportement des mesures. Nous illustrerons le lien qui existe entre les propriétés des mesures sur les critères retenus et leur comportement sur un certain nombre de bases de règles. Une attention particulière sera portée aux propriétés algorithmiques des mesures afin de pouvoir extraire les motifs intéressants en travaillant directement sur la mesure considérée, sans fixer de seuil de support, ce qui permet d’accéder aux pépites de connaissances. Nous exhiberons des conditions algébriques sur la formule d’une mesure qui assurent de pouvoir associer un critère d’élagage à la mesure considérée.


- Juliana Silva Bernardes (Université paris 6) : A multi-objective optimisation approach accurately resolves protein domain architectures
Jeudi 18 juin 2015 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Given a protein sequence and a number of potential domains matching it, what are the domain content and the most likely domain architecture for the sequence ? This problem is of fundamental importance in protein annotation, constituting one of the main steps of all predictive annotation strategies. On the other hand, when potential domains are several and in conflict because of overlapping domain boundaries, finding a solution for the problem might become difficult. An accurate prediction of the domain architecture of a multi-domain protein provides important information for function prediction, comparative genomics and molecular evolution.
We developed DAMA (Domain Annotation by a Multi- objective Approach), a novel approach that identifies architectures through a multi-objective optimisation algorithm combining scores of domain matches, previously observed multi-domain co-occurrence, and domain overlapping. DAMA has been validated on a known benchmark data set based on CATH structural domain assignments and on the Plasmodium falciparum proteome. When compared to existing tools on both data sets, it outperforms all of them.


-  Stéphane BESSY (LIRMM - Université Montpellier II) : Digraphes antistrong travail commun avec J. Bang-Jensen, B. Jackson et M. Kriessell.
Jeudi 28 mai 2015 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Motivés initialement par des questions algorithmiques autour de la subdivision de digraphes, nous définissons la notion de graphe
orienté antistrong (par opposition à strong -fortement connexe-). Un graphe orienté est antistrong si tout couple de points peut être relié
par un parcours orienté alternant. La (bonne) caractérisation d’un graphe antistrong est que son graphe biparti d’adjacence est connexe. On
s’est intéressé principalement à des questions algorithmiques autour de cette notion. Certaines découlent facilement de la caractérisation
précédente, d’autres sont plus difficiles à établir. Des techniques matroïdales ont notamment été utiles pour obtenir certains résultats. Au cours
de cet exposé, je motiverai et présenterai ces différents résultats.


- Allel HADJALI (Ecole Nationale Supérieure de Mécanique et d’Aérotechnique (Poitiers) : A Panorama of Data Uncertainty Models
Jeudi 30 avril 2015 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Uncertainty is one major aspect of imperfection of data. At least three causes of this kind of imperfection can be distinguished : (i) variability of phenomena which prevents to predicate their behavior, (ii) lack of information, (iii) conflicting/evolving information. Several models to represent uncertainty exist in the literature. It is well known that each model is insufficient to handle all facets of uncertainty. Some models are more general than others, some are more fitted to a given situation than others, some are more mature than others, some have interpretations better fitted to a particular situation or problem, some dispose of more convenient tools than others. In this talk, the aim is not to show "which is the best model" but rather "when, where, why and how each model should be used ?" Illustrations borrowing from Databases field are provided.


- Mme. Irena PENEV (LIP MC2 - Ens de Lyon) : Amalgams and chi-boundedness.
Jeudi 26 février 2015 - 15 h 30 - Salle A213 - Bâtiment ISIMA

Pas de possibilité de visio-conférence

A class of graphs is _hereditary_ if it is closed under isomorphism and induced subgraphs. A hereditary class GG is _chi-bounded_ if there exists a non-decreasing function f:N—>N (called a _chi-bounding function_ for GG) such that every graph G in GG satisfies chi(G) <= f(omega(G)), where chi(G) is the chromatic number of G, and omega(G) is the clique number (i.e. the maximum size of a clique) of G. For many hereditary classes of graphs, there is a decomposition theorem of the following form : every graph in the class either belongs to some class of well-understood basic graphs, or it admits one of several decompositions. This raises the following question : which graph decompositions preserve chi-boundedness ? Formally, we say that a graph decomposition D _preserves chi-boundedness_ if for all hereditary classes GG and GG* such that GG is chi-bounded and every graph in GG* either belongs to GG or admits the decomposition D, we have that GG* is chi-bounded (however, the optimal chi-bounding functions for GG and GG* need not be the same). This can be generalized to several decompositions : we say that graph decompositions D1,...,Dk _together preserve chi-boundedness_ if for all hereditary classes GG and GG* such that GG is chi-bounded and every graph in GG* either belongs to GG or admits at least one of D1,...,Dk, we have that GG* is chi-bounded. The fact that each of D1,...,Dk individually preserves chi-boundedness does not imply that D1,...,Dk together preserve it (this essentially follows from the fact that the preservation of chi-boundedness does not entail the preservation of the optimal chi-bounding function).

Our main result is that proper homogeneous sets, clique-cutsets, and amalgams together preserve chi-boundedness. This generalizes two earlier results : that proper homogeneous sets and clique-cutsets together preserve chi-boundedness (due to Chudnovsky, Penev, Scott, and Trotignon [1]), and that 1-joins preserve chi-boundedness (due to Dvorak and Kral [3]). As an application of this result, as well as of a decomposition theorem for "cap-free" graphs (due to Conforti, Cornuejols, Kapoor, and Vuskovic [2]), we show that the class of graphs that do not contain any subdivision of the "house" (i.e. the complement of the four-edge path) as an induced subgraph is chi-bounded.

References
[1] M. Chudnovsky, I. Penev, A.D. Scott, and N. Trotignon. Substitution and chi-boundedness. J. Combin. Theory Ser. B, 103(5):567-586, 2013.

[2] M. Conforti, G. Cornuejols, A. Kapoor, and K. Vuskovic. Even and odd holes in cap-free graphs. J. Graph Theory, 30(4):289-308, 1999.

[3] Z. Dvorak and D. Kral. Classes of graphs with small rank decompositions are chi-bounded. European J. Combin., 33(4):679-683, 2012.



- Michel GRABISCH (Université Paris I Panthéon-Sorbonne, Paris School of Economics) : Games on concept lattices.
Jeudi 5 févier 2015 - 14 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

We introduce cooperative TU-games on concept lattices, where a concept is a pair (S,S’) with S being a subset of players or objects, and S’ a subset of attributes. Any such game induces a game on the set of players/objects, which appears to be a TU-game whose collection of feasible coalitions is a lattice closed under intersection and a game on the set of attributes. We investigate the geometrical properties of the core (nonemptiness, boundedness, pointedness, extremal rays).



- Florent FOUCAUD (Post-doc LIMOS) : Problèmes d’identification dans les graphes : bornes et complexité.
Jeudi 29 janvier 2015 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
Mail : nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Nous présenterons quelques résultats récents dans le domaine des problèmes d’identification dans les graphes, en particulier le problème des ensembles dominants-localisateurs et celui des bases métriques. Ces problèmes consistent à trouver un (petit) ensemble de sommets du graphe tel que tous les sommets restants sont distingués (soit par leur voisinage dans l’ensemble sélectionné, soit par leurs distances aux sommets de cet ensemble). Cela correspond à des situations dans lesquelles on souhaite localiser certains éléments d’un réseau (feux dans un bâtiment, ordinateurs défectueux, etc).
Nous discuterons la taille d’une solution optimale à ces problèmes par rapport à l’ordre du graphe, ainsi que leur complexité algorithmique pour diverses classes de graphes. Les résultats présentés sont issus de collaborations avec George Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov ainsi que Michael Henning, Christian Löwenstein, Thomas Sasse.



- Prof. Mauricio CARDOSO DE SOUZA (UFMG Belo Horizonte) : Multicommodity flow problems in open queuing networks.
Jeudi 22 janvier 2015 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
Mail : nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Multicommodity flow problems subject to queuing effects appear frequently when dealing with the operation of communication or transportation networks. Commodities enter the network, receive service at one or more arcs and then leave the network. Average delay has been extensively used as a major system performance measure, leading to nonlinear problems. Exact performance evaluation is possible for the analysis of Jackson open queuing networks (OQN), where the arrival and service processes of the commodities are assumed to be Poisson. In this case the resulting multicommodity flow problem is convex. In this context we first review the cycle cancelling method for the convex multicommodity flow problem. Then, we address capacity expansion resulting in a piece-wise convex multicommodity flow problem. On the other hand, exact performance evaluation is not available when the Poisson processes’ hypotheses are not an acceptable assumption for the analysis of generalised OQN. So, in this case we have to cope with network routing decisions and approximate performance evaluation approaches for generalised OQN. Our aim here is to merge routing algorithms and approximate performance evaluation methods to solve difficult nonlinear multicommodity flow problems arising in generalised OQN.



- Joël FALCOU (LRI / Univ. Paris Sud / Orsay) : Software Abstractions for Parallel Architectures.
Jeudi 15 janvier 2015 - 16 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

Performing large, intensive or non-trivial computing on array like data structures is one of the most common task in scientific computing, video game development and other fields. This matter of fact is backed up by the large number of tools, languages and libraries to perform such tasks. If we restrict ourselves to C++ based solutions, more than a dozen such libraries exists from BLAS/LAPACK C++ binding to template meta-programming based Blitz++ or Eigen.

If all of these libraries provide good performance or good abstraction, none of them seems to fit the need of so many different user types. Moreover, as parallel system complexity grows, the need to maintain all those components quickly become unwieldy. This thesis explores various software design techniques - like Generative Programming, Meta-programming and Generic Programming - and their application to the implementation of various parallel computing libraries in such a way that abstraction and expressiveness are maximized while efficiency overhead is minimized.



- Michel CHEIN (LIRMM, Université Montpellier II) : Un problème d’identification d’entités nommées dans les bases bibliographiques.
Jeudi 11 décembre 2014 - 14 h 00- Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
Mail : nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

Deux identifiants représentant dans un système informatique des entités du monde extérieur au système représentent-ils la même entité ? Ce problème est étudié en informatique depuis les années 50 sous une grande variété de noms différents ("record linkage", "entity resolution", "reference reconciliation", "entity alignment","object identification", "coreference resolution", ...). L’une de ses particularités, soulignée depuis longtemps, est qu’il n’y a pas un unique paradigme pour aborder ce problème. Nous présenterons notre approche dans le cadre de deux problèmes particuliers concernant des bases bibliographiques.



- Boris ALBAR (I3M et LIRMM - Université Montpellier II) : Autour de la conjecture d’Hadwiger.
Jeudi 27 novembre 2014 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
Mail : nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

La conjecture d’Hadwiger affirme que tout graphe sans mineur K_t est (t-1)-coloriable.
Cette conjecture a été prouvée pour t <= 6. Dans cet exposé, nous nous intéresserons principalement au cas t = 7.
Nous donnerons un aperçu des problèmes ouverts et des techniques utilisés pour prouver certains résultats partiels sur les graphes sans
mineur K_7 ou K_7^-. Dans une deuxième partie, nous nous intéresserons à la conjecture d’Hadwiger doublement-critique introduite par
Kawarabayashi, Toft et Pedersen.



- Pierre TISSEUR (Univ. Brésil) : Quelques résultats et hypothèses à propos du comportement de créatures artificielles basiques évoluant dans le contexte des extensions du jeux de la vie.
Jeudi 20 novembre 2014 - 14 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

Pas de possibilité de visio-conférence

Le jeu de la vie est un cas particulier d’automate cellulaire bidimensionnel ou l’évolution d’une cellule en statut vivant ou mort dépend du statut de cette cellule et du nombre de plus proches voisins en vie.
En conservant un type similaire de règles et en prenant en compte un plus grand nombre de voisins on obtient des"larger than life cellular automata"..
Dans ce contexte apparaissent des créature artificielle dénommées "bugs" et qui représentent des extensions des objets glissant du jeu de la vie appelées "gliders".
Même si ces "bugs" ont quelques caractères en commun, ils présentent une certaine variété et leur existence semble être intimement liés aux paramètres du jeu de la vie.



- Pierre ABOULKER (Concordia University (Montréal) / ENS de Lyon - LIP) : The Chen-Chvátal Conjecture.
Jeudi 6 novembre 2014 - 14 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

Pas de possibilité de visio-conférence

A celebrated Theorem of de Bruijn and Erd®s [3] states that every noncol-linear set of n points in the plane determines at least n distinct lines. Line uv in the plane consists of all points p such that

– dist(p, u) + dist(u, v) = dist(p, v) or
– dist(u, p) + dist(p, v) = dist(u, v) or
– dist(u, v) + dist(v, p) = dist(u, p).

With this definition of line uv in an arbitrary metric space (V, dist), Chen and Chvátal [2] conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points. Although the conjecture has been proved in several special cases, it is still wide open. I’ll discuss this definition of lines in metric space, then I’ll survey the results supporting this conjecture and some variations of it and I’ll present in more details some of the most recent results [1] :
We prove that in any metric space with n points, either there is a line containing all the points, or else there are at least pn/2 distinct lines. This is the first polynomial lower bound on the number of lines in a general metric space, and also improves the previous (n2/7) lower bound on the number of lines in metric spaces induced by connected graphs. We also prove that the number of lines in a metric space is at least n/5w, where w is the number of di˙erent distances in the metric space.


Références

[1] P. Aboulker, X. Chen, G. Huzhang, R. Kapadia and C.Supko, Lines in metric spaces. Manuscript.
[2] X. Chen and V. Chvátal, Problems related to a de Bruijn - Erd®s theorem, Discrete Applied Mathematics 156 (2008), 2101 – 2108.
[3] N. G. De Bruijn, P. Erd®s, On a combinatorial problem, Indagationes Mathematicae 10 (1948), 421 – 423.



- Gwen SALAUN (Ensimag, Grenoble INP / INRIA, LIG) : Verification of Asynchronously Communicating Systems.
Jeudi 2 octobre 2014 - 14 h 00 - Salle A104 - Bâtiment ISIMA

Pas de possibilité de visio-conférence

Recent software is mostly constructed by reusing and composing existing components abstracted as finite state machines.
Asynchronous communication is a classic interaction mechanism used for such software systems. However, analyzing communicating systems interacting asynchronously via FIFO buffers is an undecidable problem. A typical approach is to check whether the system is bounded, and if not, the corresponding state space can be made finite by limiting the presence of communication cycles in behavioral models or by fixing buffer sizes. In this talk, we focus on infinite systems and we do not restrict the system by imposing any arbitrary bounds. We first present the synchronizability property and then introduce a notion of stability for non-synchronizable systems. We prove that once the system is stable for a specific buffer bound, it remains stable whatever larger bounds are chosen for buffers. Synchronizability and stability allow us to check certain properties on the system for specific bounds and to ensure that the system will preserve these properties whatever larger bounds are used for buffers. We will also overview several propeperties of interest that communicating systems must satisfy when obtained via projection from choreography specifications.