Semindoc 2013-2014

Le Séminaire des Doctorants

Au cours de ce séminaire, les doctorants présentent leurs travaux de recherche aux autres thésards du département informatique du LIRMM. Ce moment social et convivial, en plus d'enrichir sa culture générale 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 fois par mois le mardi, de 11h précises (ouverture de la salle et café à 10h45) à midi, en salle des séminaires (sauf mention du contraire). Un courriel sera envoyé au moins 24h à l'avance à l'alias [thesards-info] afin de prévenir tous les doctorants en informatique de l'orateur et du sujet présenté.
Les orateurs sont principalement des doctorants ou post-docs 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.

Exposés à venir

11/07/14 - SEMIDOCTUS

Retrouvez les diapos du Semidoctus.

Le Sanskrit et l'informatique : Panini et le codage d’une grammaire de langage naturel :

La machine d'Anticythère : le plus ancien calculateur mécanique :

Les crypto-monnaies : l'exemple des Bitcoins :

Pour conclure cette année, le Semindoc (le séminaire des doctorants) organise le vendredi 11 juillet la 1ère édition des Semidocti, une demi-journée à but récréatif et culturel, avec des exposés traitant pour moitié d'informatique, pour moitié d'autre chose.

Cette demi-journée sera ouverte à tous !

semi affiche

Programme (English below) :

9h Petit déjeuner ;

9h30 Namrata Patel,
Le Sanskrit et l'informatique : Panini et le codage d’une grammaire de langage naturel ;

"L'Astadhyayi, un système grammatical du Sanskrit, a été développé par le grammairien Panini vers le V°s. Cette grammaire intéresse particulièrement les linguistes actuels, en effet il apparaît que les concepts de Panini contribuent à la formalisation et à l’analyse des langues naturelles, de plus certains modèles informatiques développés pour l'Astadhyayi permettent la génération automatique de phrases naturelles.
Dans cet exposé nous étudierons l'Astadhyayi sous le jour de la linguistique computationnelle moderne."

10h30 pause café ;

10h45 Mourad Gouicem,
La machine d'Anticythère : le plus ancien calculateur mécanique ;

"En 1901, des pécheurs grecs trouvent au large de l’île d'Anticythère, une épave datée du IIe siècle avant JC. Parmi les nombreuses reliques s'y trouvant, un étrange mécanisme va provoquer la curiosité de la communauté scientifique. Il aura fallu un siècle avant de percer les secrets de ce calculateur astronomique, de sa conception méticuleuse à son fonctionnement.
Dans cet exposé, nous survolerons l'histoire de cette énigme scientifique."

11h30 Bastien Vialla,
Les crypto-monnaies : l'exemple des Bitcoins ;

"Si vous souhaitez acheter des armes, de la drogue ou engager un tueur pour assassiner votre co-bureau, il est conseillé d'utiliser une crypto-monnaie pour rester anonyme. Le bitcoin est la crypto-monnaie la plus connue, elle est basée sur un système décentralisé afin d'éviter l'influence des banques et des états. Elle est donc réputée dans les médias pour son utilisation dans les marchés illégaux.
Dans cet exposé nous décrirons le fonctionnement d'une crypto-monnaie en prenant l'exemple du bitcoin."

12h15 clôture.

Les horaires sont donnés à titre indicatif. Nous avons prévu un large temps de question pour le cas où ces exposés provoqueraient des débats intéressants.


Program of friday 11th july:

9h breakfast;

9h30 Namrata Patel,
Sanskrit and Informatics: Modelling the Paninian Grammar System;

"This talk will presents a study of Astadhyayi, the grammatical system of the Sanskrit language as developed by the grammarian Panini in the light of modern-day computational linguistics. Using information gathered from various articles on the topic,
1) it sheds light on concepts in Paninian grammar which contribute to the effective formalisation and analysis of a natural language,
2) it explores the possibility of automating the process of sentence generation by looking at some of the models developed for the computer representation of the Paninian system."

10h30 coffee break;

10h45 Mourad Gouicem,
The Antikythera mechanism: the most ancient computing machine;

"This talk will present an overview of the history of the mysterious Antikythera mechanism. This is a relic found in 1901 by Greek fishermen, in a wreck dated from the II° century BC, off the coast of Antikythera island. It has aroused the curiosity of scientists: one century was needed in order to understand the meticulous conception and how to use this astronomical computer."

11h30 Bastien Vialla,
Crypt-currencies : the example of the Bitcoins;

"This talk will present how crypt-currencies work through the example of bitcoins. The bitcoin is the most famous crypt-currency, based on a decentralised system designed to elude governments and banks controls. Therefore it is presented by media for it use in illegal trade. It is an useful tool if you want to buy weapons, narcotic, or contract a killer to eliminate your co-worker and still remain anonymous."

12h15 closing.

We provide a approximate planning since we keep a lot of time for questions in the cases where interesting discussions start. Please notice that the talks will be in french.

Exposés passés

11/06/14 - Dinh Dan Le (équipe MAORE) : Layered graph model for solving MC-RWA problem in wavelength-routed optical networks

 Résumé :

Dinh

06/05/14 - Ziad Sultan Université Joseph Fourier de Grenoble : Calcul parallèle de formes échelons

 Résumé :

La résolution de système linéaire est au centre de nombreux domaines (cryptographie, bio-informatique, simulation physique, ...), il est donc important de savoir la faire efficacement. De plus, les coeurs sur les processeurs sont de plus en plus nombreux, pour pouvoir profiter de cette avantage il faut exhiber du parallélisme lors de la résolution.

L'algorithme le plus souvent utilisé est la décomposition LU, nous verrons comment la faire efficacement en parallèle.

Cependant en cryptographie, les applications ont souvent besoin d'informations sur le rang (profile de rang en ligne) de la matrice sans avoir besoin des solutions du système. Pour cela nous introduirons un algorithme dérivé de la décomposition LU mais dont la complexité dépend du rang qui produit des matrices sous forme échelon. Finalement, nous verrons comment bien le paralléliser..

08/04/14 - Valentin Garnero (équipe ALGCO) : Dénoyautage de graphes

 Résumé :

Le dénoyautage est une technique standard en horticulture (en particulier en ce qui concerne les cerisiers et les oliviers; au printemps, lorsqu'il fait bon lézarder à l'ombre) qui consiste à extraire le noyau du fruit : en effet pourquoi conserver la chair du fruit alors que le noyau à lui seul contient toute l'information génétique nécessaire pour reconstituer un arbre entier (lequel produira de nouveaux fruits, eux même dénoyautables). Pour les graphes c'est la même chose, on peut supprimer toutes les parties qui n’apportent pas d'information pour la résolution d'un problème.

Je commencerai mon exposé par quelques rappels élémentaires sur les graphes, les algorithmes, la complexité.

Je ferai ensuite une introduction à la complexité paramétrée et aux noyaux. Ces deux domaines sont des formalisations de méthodes déjà existantes comme la réduction de données ou le pré-calcul. D'une part, la complexité paramétrée cherche à faire une analyse plus précise de la complexité d'un problème: le temps calcul est compté en fonction de la taille des données et d'un paramètre à choisir ; c'est une façon de contourner le problème posé par la NP-complétude. D'autre part, l'extraction de noyaux est une méthode qui consiste a réduire les données (les transformer en données équivalentes) tout en garantissant la taille des données réduites ; cette méthode fournit en particulier de bons algorithmes paramétrés, mais peut avoir d'autres applications.
 
En fonction du temps qu'il me restera je ferai un exemple simple d'extraction de noyau, basé sur une méthode standard proposée par Alber Fellows et Niedermeier.

Bien sûr je ferai en sorte que l'exposé soit accessible aux personnes non-initiées aux sciences ésotériques et j’espère qu'il pourra se faire de façon interactive.

11/03/14 - Bastien Cazaux (équipe MAB) : Arbres des suffixes et applications

 Résumé :

Avec l'accroissement des volumes de données numériques, il est important de pouvoir rechercher une sous-chaîne qui nous intéresse parmi celles-ci. Actuellement, une des solutions pour la recherche d'une sous-chaîne dans un texte est d'utiliser une structure d'indexation pour représenter ce texte. La plus connue est l'arbre des suffixes, nous allons nous y intéresser.

Dans un premier temps, je définirai ce qu'est un arbre des suffixes et comment l'utiliser pour la recherche d'une ou plusieurs sous-chaînes. Dans un second temps, on verra comment utiliser les informations de l'arbre des suffixes pour répondre à d'autres problèmes sur les mots comme le chevauchement entre deux mots.

11/02/14 - Vincent Itier (équipe ICAR) : Sécurité des objets 3D

 Résumé :

Les objets 3D, au sens de maillages, sont de plus en plus utilisés que ce soit dans l'industrie (CAD, prototype...) et dans les loisirs numériques (jeux, films...). Ces objets sont en général créés par une personne, diffusés par divers moyen (internet), partagés, modifiés, imprimés etc...

Dans cette présentation, je vais aborder la sécurité multimédia en général, puis le cas spécifique des objets 3D et les nouveaux challenges qu'ils impliquent.

23/01/14 - Bruno Paiva Lima da Silva (équipe GRAPHIK) : Data Access over Large Semi-Structured Databases

 Résumé :

L'accès aux données en présence d'ontologies est un problème qui vise à répondre à des requêtes conjonctives en utilisant des inférences rendues possibles par une ontologie. Les deux grandes familles de langages utilisées pour coder une telle ontologie sont les logiques de description et les langages à base de règles.

L'émergence de très grandes bases de connaissances, souvent peu structurées, complexifie aujourd'hui ce problème, d'autant plus que les données peuvent être stockées sous de nombreux formats.

Nous avons ainsi développé ALASKA, une architecture logicielle générique dédiée à ce problème. ALASKA permet la manipulation (insertion, interrogation) des données indépendamment du système de stockage utilisé, et peut donc être vu comme la couche abstraite requise pour notre problème. Nous avons utilisé ALASKA pour tester l'efficacité de différents systèmes de stockages (bases de données relationnelles, bases de graphes, triple stores), que ce soit quant à la rapidité de l'insertion de nouvelles connaissances dans une base ou quant à l'efficacité des opérations élémentaires requises par les systèmes de requêtage.

18/12/13 - Mourad Gouicem (équipe ARITH) : Arithmétique réelle sur machine : entre imprécisions et bogues

 Résumé :

Sur machine, arithmétique réelle et arithmétique à virgule flottante sont souvent synonymes. Cependant, l’arithmétique flottante possède des propriétés bien différentes. Entre autres, l’addition est non associative, et la plupart des nombres réels et rationnels ne sont pas représentables de manière exact, ce qui induit une propagation d’erreurs lors des calculs.

Je présenterai lors de ce Semindoc les spécificités de l’arithmétique flottante, ce qui en est normalisé, ce qui ne l’est pas, et différentes méthodes permettant de contrôler la propagation d’erreurs.

Pour illustrer l’importance d’une bonne utilisation de cette arithmétique, cet exposé se fera au travers de nombreux exemples et bogues ayant marqués l’histoire.

20/11/13 - Manel Zarrouk (équipe TEXTE) : Consolidation de réseau lexico-sémantique par inférence et réconciliation

 Résumé :

La construction et la validation des réseaux lexicaux sémantiques est un enjeu majeur en TAL. Indépendamment des stratégies de construction utilisées, inférer automatiquement de nouvelles relations à partir de celles déjà existantes est une approche possible pour améliorer la couverture et la qualité globale de la ressource. Dans ce contexte, le moteur d’inférences a pour but de formuler de nouvelles conclusions (c’est-à-dire des relations entre les termes) à partir de prémisses (des relations préexistantes).

Dans cet article, nous concevons un moteur d’inférences pour le réseau lexical JeuxDeMots qui contient des termes et des relations typées entre ces termes. Dans le projet JeuxDeMots, le réseau lexical est construit à l’aide d’un GWAP (Game With A Purpose) et quelques milliers de joueurs. Les termes polysémiques peuvent être raffinés en divers usages (le terme figure peut faire référence à figure>géométrie ou figure>visage). Mais étant donné que le réseau est indéfiniment en construction certains sens peuvent être manquants. L’approche que nous proposons est basée sur une méthode de triangulation impliquant la transitivité sémantique avec un mécanisme de blocage pour éviter de proposer des relations douteuses. Les relations inférées sont proposées aux contributeurs pour être validées. Dans le cas d’invalidation, une stratégie de réconciliation est engagée pour identifier la cause de l’inférence erronée : une exception, une erreur dans les prémisses, ou une confusion d’usage causée par la polysémie.

23/10/13 - Guillaume Guégan (équipe ALGECO) : Théorème des quatre couleurs et objets de Catalan

Théorie des graphes et combinatoire.

En mathématiques, les théorèmes les plus fascinants sont ceux dont l'énoncé est «enfantin», cachant en fait un problème subtil et difficile. Le théorème des quatre couleurs, théorème roi de la théorie des graphes, est l'un de ceux-ci : étant donné une carte représentant des pays, si l'on souhaite colorer chacun d'eux de sorte que deux pays adjacents reçoivent des couleurs différentes, combien de couleurs a-t-on besoin dans le pire des cas ? La réponse est quatre, et il aura fallu attendre plus d'un siècle entre la première mention de ce problème et sa résolution en 1976.

Deux preuves de ce célèbre théorème existent, empruntant deux voies différentes (méthodes de déchargement et théorie des mineurs, exposés dans des sémindocs précédents). L'une d'elle est encore largement non publiée, et toutes les deux dépendent du traitement d'un nombre de cas faramineux, nécessitant l'aide de l'ordinateur pour en vérifier la correction. Ce dernier point laisse de nombreux théoriciens des graphes sur leur faim : on aimerait obtenir une preuve plus éclairante.

Dans ce séminaire, j'exposerai dans une première partie l'histoire de ce théorème et de ses preuves. La seconde partie sera consacrée à la présentation d'une «troisième voie» qui n'a pas encore porté ses fruits, mais que j'estime prometteuse. Cette voie permet de faire des liens surprenants entre notre théorème, et de multiples énoncés ressemblant à des jeux sur des objets fascinants de la combinatoire : les objets de catalan, qui interviennent dans de nombreux domaines de l'informatique et des mathématiques.

Archives 2003/2013

Modalités

Pour faire une présentation à ce séminaire :

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

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.
L'adresse du Semindoc étant saturée de publicités nous vous prions d'utiliser vos adresse "@lirmm" ou de préciser "semindoc" dans l'objet sans quoi votre message sera rejeté.

Aux manettes cette année :

Dernière mise à jour le 23/03/2017