Ce séminaire permet aux doctorants de présenter leurs travaux de recherche devant
les autres thésards du département informatique
du LIRMM. Ce moment convivial est aussi un moyen
de se tenir au courant des problématiques abordées dans
les différentes
équipes du département,
qui représentent divers domaines de l'informatique.
Ce séminaire a lieu en moyenne une semaine sur deux
le mercredi de 11h précises (ouverture
de la salle et café à 10h45) à midi en salle 2.57 (sauf mention du contraire).
Un courriel sera envoyé au moins 24h à l'avance à l'alias [di-thes] afin de prévenir
tous les doctorants en informatique de l'orateur et du sujet présenté.
Les orateurs sont principalement des doctorants en informatique du LIRMM,
occasionnellement des doctorants invités d'autres laboratoires.
Les exposés concernent les travaux de l'orateur ou bien peuvent être
des états de l'art sur un sujet donné.
Aucun prérequis n'est nécessaire pour assister à ces exposés,
les notions abordées sont définies en début de présentation.
27/05/2009 -
Zafar Shahid
(ICAR) :
Collusion-resistant Fingerprinting for Multimedia
Digital fingerprinting is a
technique to identify users who might try to
redistribute multimedia content. These fingerprints are embedded in the
multimedia content using robust watermarking techniques which are
resistant to variety of attacks. A simple attack against such
fingerprints is collusion where several users combine their copies of
the content either linearly or non-linearly. Anti collusion codes
(codes) have been designed to withstand such attacks. This lecture
introduces the basic collusion attacks and collusion resistant
fingerprint codes which withstand these attacks.
20/05/2009 -
Raluca Uricaru
(MAB) :
Alignement global de séquences génomiques
Le terme séquence génomique désigne en général l'enchaînement de
nucléotides le long d'une macromolécule d'ADN. Cette séquence peut être
représentée par une chaîne de caractères utilisant un alphabet de quatre lettres
A, C, G et T.
La comparaison de séquences génomiques est une des tâches informatiques la plus
fréquemment exécutée par les biologistes. Il s'agit de déterminer dans quelle
mesure deux ou plusieurs séquences génomiques se ressemblent. La motivation
première est d'inférer des connaissances sur une séquence à partir des
connaissances attachées à une autre.
Plus précisément pour comparer des séquences de génomes, on regarde les parties
conservées entre les génomes (la partie dénommée la colonne vertébrale)
qui indiquent les composants biologiques communs entre plusieurs espèces ou
souches. De plus, les différences entre les séquences (régions appelées
variables) sont vraisemblablement responsables de ce qui les distingue.
Grâce à l'alignement global de séquences génomiques on peut directement
obtenir ces deux types de régions. Par contre, cette tâche est extrêmement
complexe.
La raison principale de cette complexité est la combinatoire engendrée par
l'énorme taille des séquences. En effet, la taille du génome (c.a.d. le nombre de
nucléotides qu'il contient) peut varier de quelques milliers de nucléotides (chez
les virus) jusqu'à plusieurs centaines de milliards. C'est pourquoi les nombreux
outils d'alignement existants utilisent des méthodes heuristiques. La méthode la
plus commune dans ce domaine s'appelle la stratégie basée sur des ancres et
opère en plusieurs phases.
Notre travail a pour objectif principal l'évaluation de la qualité des alignements
génomiques produits par des outils qui utilisent cette heuristique. Suite à cette
évaluation, nous avons décidé de tester des différentes variations sur cette
heuristique, parmi lesquelles une méthode basée sur des graines espacées
(Yass). Cette méthode
n'avait jamais été utilisée dans le cadre de l'alignement global de génomes et
elle s'est avérée comme étant très performante sur des cas considérés
difficiles.
06/05/2009 - Philippe Gambette
(AlGco/MAB) :
Visualiser un texte par un nuage arboré.
Les nuages de tags se sont popularisés sur internet pour fournir un aperçu rapide
du contenu d'un site web ou d'un texte. Le nuage arboré est une nouvelle méthode
de visualisation d'un texte, plus informative, inspirée des arbres
phylogénétiques. Comme un nuage de mots, le nuage arboré
représente les mots les plus fréquents d'un texte avec une taille
qui reflète leur fréquence, mais ils sont disposés autour d'un arbre qui
reflète leur proximité sémantique d'après le texte. Je présenterai les différentes
étapes algorithmiques de construction de ces nuages arborés, et les résultats de la
comparaison de diverses formules de distance sémantique basées
sur la cooccurrence. Je dévoilerai également quelques exemples qui illustreront
les multiples applications de cette visualisation.
Pour finir, une démo du logiciel libre TreeCloud vous permettra
d'apprendre comment construire vos propres nuages arborés
(à partir d'articles, thèse, blog, ou encore logs MSN...).
Cette présentation sera précédée d'un amuse-bouche à 10h50, sur
l'estimation, par une approche mêlant combinatoire et statistiques,
du nombre de citations de papillotes et de blagues Carambar.
Ce mini-exposé sera accompagnée d'une distribution
de Carambars pour augmenter la taille du jeu de données
et la précision des résultats.
22/04/2009 -
Joel Pinho Lucas
(doctorant invité par l'équipe TATOO),
Building Recommendations by means of Classification Based on Fuzzy Association.
At the present time there is a diversity of methods, including data mining techniques,
available to be used in recommender systems. However, such systems still present
numerous limitations. An alternative data mining technique is the classification
based on association, which combines concepts from classification and association.
In this way, association rules perform a predictive role.
In order to provide recommendations more effectively,
in this work we suggest that associative classifiers can be also used in these type
of systems. Therefore, we present a revision about recommender systems
and associative classification. In addition, we describe a case study,
in which traditional and associative classifiers are evaluated
and compared using real data from two recommender systems.
Moreover, in order to enhance classification’s accuracy,
we propose to employ fuzzy logic in the recommendation process.
08/04/2009 - Guillaume Artignan
(équipe IHMH),
Visualisation multi-échelle de graphes.
L'apparition de nouvelles technologies comme Internet a permis la
création de bases de données contenant de très grandes quantités
d'informations. Un grand nombre de ces informations peuvent se
caractériser par des acteurs reliés entre eux par des relations. La
visualisation de graphes s'intéresse à ces types de données. Pour cela,
de nombreuses méthodes ont été développées, algorithmes de placement,
clustering... La visualisation multi-échelle constitue une de ces
méthodes.
Cet exposé présentera dans un premier temps la visualisation
multi-échelle, ainsi que les travaux existants.
Dans un second temps il sera exposé notre contribution dans ce domaine.
25/03/2009 - Mathilde Bouvel de
l'équipe Algorithmique et combinatoire
du LIAFA (Paris VII),
Analyse en moyenne du tri parfait par renversement
(travail en commun avec Cédric Chauve, Marni Mishna et Dominique Rossin).
Le but du tri parfait par renversements de permutations signées est de
transformer une permutation signée en la permutation identité, grâce à
une séquence de renversements qui ne cassent aucun intervalle de la
permutation de départ. Ce problème combinatoire et algorithmique trouve
ses motivations en biologie, dans les études de réarrangements de
génomes. Je commencerai par présenter ces motivations, puis décrirai un
algorithme de S. Bérard, A. Bergeron, C. Chauve et C. Paul qui, étant
donnée une permutation σ, calcule un scénario parcimonieux
(c'est-à-dire faisant le moins de renversements possible) de
renversements qui trie σ. Cet algorithme utilise les arbres de
décomposition des permutations, qui sont des analogues des arbres de
décomposition modulaire des graphes. Par une analyse de la forme en
moyenne des arbres de décomposition, nous avons montré que :
l'algorithme de S. Bérard, A. Bergeron, C. Chauve et C. Paul est
polynomial en moyenne (alors qu'il est a priori exponentiel),
cet algorithme est polynomial avec probabilité 1 quand la taille des
permutations traitées tend vers l'infini.
Si on se restreint à la sous-classe des permutations commutantes (ou
séparables), on sait déjà que l'algorithme décrit est polynomial. Dans
ce cas, nous avons utilisé des séries génératrices et des techniques
d'analyse de singularité pour donner :
le nombre moyen de renversements dans un scénario calculé par
l'algorithme,
la taille moyenne d'un tel renversement.
Au menu donc : un peu de bio-info, un peu d'algorithmique, un peu de
combinatoire, pour un résultat qui vient confirmer les intuitions et les
simulations.
04/03/2009 - Michael Bergeret
(SMILE),
Analyse d'architectures d'agent hybride pour une modélisation de
comportement d'avatars.
Les différentes taxonomies effectuées sur les architectures
multi-agents existantes ont montré que l'on pouvait classer
les agents dans deux grandes catégories, les agents réactifs
et les agents cognitifs. En effet, un agent peut avoir des
comportements uniquement basés sur la réaction aux perceptions
immédiates, ou des comportements apportant une certaine
rationalité, lui permettant de prendre en compte ses états
mentaux. Cependant, il est parfois nécessaire que l'agent
puisse avoir simultanément ces deux niveaux de comportements.
Des travaux ont été menés pour fournir des architectures le
permettant, appelées architecture hybrides. Dans cette
discussion seront présentées quelques unes de ces architectures,
ainsi qu'un cas d'application de l'une d'elle dans le cadre
d'une modélisation de comportement d’avatars pour une
simulation d'évacuation de foule.
18/02/2009 - Nicolas Moreau
(RCR) :
Interroger une base de connaissance en graphes conceptuels.
Les graphes conceptuels sont un formalisme de représentation de
connaissance et de raisonnement, similaire au formalisme du web
sémantique RDF. L'utilisation de telles bases de connaissance au sein de
systèmes de question/réponse soulève un certain nombre de problèmes
nécessitant une étude formelle, pour la définition d'un langage
d'interrogation pertinent. Nous aborderons en particulier le problème de
redondance entre réponses et la difficulté de définir des opérations
d'aggrégation (sommes, etc).
04/02/2009 - Julien Rabatel
(TATOO) :
Enjeux et problématiques de la fouille de données.
L'évolution des technologies de l'information permet désormais
de rassembler et d'emmagasiner de grandes quantités de données.
Cependant, cette masse de données est devenue telle qu'il est impossible
de l'analyser manuellement. La fouille de données est une discipline à
l'intersection de nombreux domaines : bases de données, intelligence
artificielle... Cette présentation me permettra de vous expliquer les
bases de la fouille de données, les nombreux problèmes associés, les
solutions actuelles ainsi que les domaines dans lesquels ces solutions
sont appliquées. Je terminerai en exposant de manière générale les
divers travaux passés et actuels de mon équipe.
21/01/2009 - Floréal Morandat
(DOC) :
Evaluation des implémentations de l'héritage multiple en typage
statique.
La programmation par objets présente une apparente incompatibilité
entre trois termes : l'héritage multiple, l'efficacité et l'hypothèse
du monde ouvert - en particulier, le chargement dynamique. Après une
introduction sur les langages objets, cet
exposé présente des résultats d'expérimentations exhaustives comparant
l'efficacité de différentes techniques d'implémentation (coloration,
BTD, hachage parfait, ...) dans le contexte de différents schémas de
compilation (de la compilation séparée avec chargement dynamique à la
compilation purement globale). Les tests sont effectués avec et sur le
compilateur du langage Prm. Ils confirment pour l'essentiel les
résultats théoriques antérieurs tout en montrant une sur-additivité
marquée des surcoûts.
07/01/2009 - Nadia El-Mrabet
(ARITH) :
Implémentation des couplages de Weil, Tate et Ate à l'aide du logiciel SAGE.
Durant mon exposé, j'introduirai les couplages, ainsi que la cryptographie
basée sur les courbes elliptiques. Puis je vous présenterai un exemple
d'implémentation des couplages en utilisant le logiciel Sage.
10/12/2008 - Jean-Rémy Falleri
(DOC) :
Alignement de méta-modèles pour de la génération automatique de transformation de modèles.
L'application du paradigme de conception Ingénierie Dirigée par les
Modèles implique la création d'un grand nombre de méta-modèles, car
l'IDM recommande un usage intensif de modèles définis par des
méta-modèles. De ce fait, des méta-modèles ayant des objectifs
similaires sont créés. Un problème récurrent devient donc de rendre
compatible des modèles qui sont conformes à des méta-modèles similaires,
par exemple pour pouvoir les utiliser dans le même outil. Ce problème
est usuellement résolu par l'écriture manuelle d'une transformation de
modèle. Dans cette présentation, nous proposons une approche qui permet de
détecter automatiquement des correspondances entre les éléments de deux
méta-modèles. Ces correspondances sont ensuite utilisées pour calculer
en alignement entre ces deux méta-modèle. Cet alignement doit être
vérifié manuellement et peut servir à générer le squelette d'une
transformation de modèles entre ces deux méta-modèles. Notre approche
repose sur l'algorithme Similarity Flooding, utilisé dans des domaines
tels que l'alignement d'ontologies et le schema matching. Nous
fournissons des résultats expérimentaux qui comparent l'efficacité de
différentes versions de cette approche sur des méta-modèles du "vrai" monde.
19/11/2008 -
Celine Scornavacca
(MAB) :
Des arbres de gènes à l'arbre des espèces... un long long chemin...
Les arbres de gènes sont des arbres étiquetés, inférés à partir de
séquences moléculaires, où chaque étiquette représente une espèce. Quand
l'histoire d'un gène contient un événement de duplication, l'arbre
inféré par ce gène contrera plusieurs copies de certaines étiquettes.
On appellera ces arbres arbres MUL (pas de blagues, ça veut dire
MULTI-LABELED !!!).
Dans cet exposé je présenterai des algorithmes pour essayer de
bidouiller les arbres MUL pour obtenir des arbres qui contiennent une
seule copie de chaque espèce ! Voilà, vous êtes les bienvenus !
12/11/2008 -
Gilles Simonin
(APR) :
Problèmes d'ordonnancement de tâches-couplées en présence d'un graphe de
compatibilité.
L'étude du problème d'ordonnancer des tâches-couplées soumises à des
contraintes de compatiblité est motivée par le problème d'acquisition de
données par une torpille en immersion. Cette torpille doit recueillir des
données puis les traiter, ainsi elle envoie un écho, attend un temps
d'inactivité incompressible et indilatable, puis reçoit l'écho. Pendant ce
temps d'inactvité, la torpille peut envoyer d'autres échos afin d'employer
le temps d'inactivité. Cependant, la localisation trop proche des ondes
provoque des perturbations et des interférences. Sachant que nous
souhaitons traiter des informations exemptes d'erreur, nous construisons
un graphe dit de compatibilité entre les tâches.
Dans cet exposé, je présenterai une vulgarisation de la théorie de
l'ordonnancement, puis la modélisation du problème. Je proposerai ensuite
un survol de la complexité des problèmes rencontrés, et des différentes
heuristiques adaptées pour ce type de problème.
29/10/2008 -
Nicolas Tournier
(ICAR) :
Tatouage informé hiérarchique d'un message hiérarchisé.
Nous entendons parler des problèmes de protection de droit d'auteur, en particulier
dans la lutte contre le téléchargement illégal. La sécurisation de données
numériques devient une priorité pour les maisons de production. Le tatouage est une
discipline très récente (années 90) qui permet de dissimuler des informations et de
protéger des documents numériques.
Nous nous intéresserons ici à des applications de traçabilité et d'enrichissement
sur des images hiérarchiques par des méthodes de tatouage informé basées sur QIM
(Chen et Wornell, 2001). Chaque terme sera défini le plus clairement possible lors
de la présentation, suivi des méthodes développées, et des résultats obtenus.
15/10/2008 -
Anthony Perez
(VAG) :
Noyaux polynomiaux pour des problèmes d'édition de graphes (3-leaf power).
Dans cet exposé, nous nous intéresserons à des problèmes d'édition de
graphes et à l'existence de noyaux et d'algorithmes paramétrés pour ces
problèmes (FPT). Un algorithme paramétré par un entier k présente
l'avantage de fournir une solution exacte au problème, tout en étant
rapide en pratique (puisque sa vitesse dépend d'un nombre k petit en
général). Afin de rendre ces algorithmes aussi efficaces que possible,
la recherche de noyaux (transformation polynomiale réduisant la taille
d'une instance) constitue un enjeu primordial. Il est notamment connu
que tout problème FPT admet un noyau (de taille exponentielle par
défaut), permettant d'efficacement orienter les recherches.
Je vous présenterai donc l'intérêt de ces concepts, ainsi que des noyaux
polynomiaux pour des problèmes d'édition de graphes particuliers :
3-leaf power edition, 3-leaf power completion et 3-leaf power deletion,
connus pour appartenir à la classe FPT (Dom et al, 05).
envoie aux organisateurs, au moins 72h à l'avance,
un titre, un résumé, ainsi qu'une estimation de la durée de l'exposé.
l'exposé concernera ton thème de recherche, mais devra être compréhensible
par tous les auditeurs. En particulier, un petit état de l'art sur le domaine
sera apprécié, des liens avec les autres domaines de l'informatique
étudié dans les diverses
équipes du département également.
prépare un transparent pour te présenter et te
situer dans le laboratoire (équipe, thèmes de recherche, encadrant de thèse, enseignements...).
l'exposé devra durer entre 25 et 45 minutes et sera suivi de questions
de l'auditoire.
Pour proposer l'invitation à ce séminaire d'un doctorant extérieur au LIRMM :
envoie dès que possible aux organisateurs
le nom de ce doctorant ainsi que son thème de recherche.
précise quelle équipe du LIRMM serait principalement intéressée par son exposé,
et quelles autres équipes travaillent sur des thèmes reliés ou proches.
le choix des invités parmi cette liste de propositions sera faite de manière
à représenter de façon équilibrée les thèmes des équipes du LIRMM.
Les conférences pour jeunes chercheurs
Les équipes du département informatique du LIRMM potentiellements intéressées
par la conférence sont indiquées entre parenthèses.
Contactez-nous pour compléter ou corriger cette liste de
conférences destinées aux jeunes chercheurs, en précisant les équipes potentiellement concernées.
Contact
Pour toute suggestion, remarque, demande, les organisateurs peuvent être contactés
à semindoc-AT-lirmm.fr.
