Semindoc : le séminaire des doctorants

 Le mercredi, généralement en fin d'après-midi au bât 4, notez que science, vulgarisation, ouverture d'esprit, bonne ambiance et collation (plus souvent connue sous le nom de free food) sont garantis ! Goodies semindoc offerts aux intervenants !

Tous les post-docs, aters, doctorants (jeunes et moins jeunes), stagiaires et étudiants de licence/master intéressés sont joyeusement conviés :).

Avis à la population estudiantine du Lirmm : une envie de parler d'un sujet scientifique qui vous tient à coeur ? Une pensée pour une personne qui travaille sur des choses amusantes ? Une idée révolutionnaire à exposer ? N'hésitez plus et envoyez un mail à semindoc@lirmm.fr ! N'hésitez pas également à venir nous rencontrer à tout moment :). Plus d'informations sur la participation ou les modalités de présentation sont disponibles en bas de cette page.

 man semindoc

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 la 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. C'est également un exercice intéressant pour les orateurs qui, au-delà d'une nouvelle expérience de présentation scientifique, devront faire un réel effort de vulgarisation et d'esprit de synthèse.
Ce séminaire a lieu régulièrement le mercredi après-midi dans les salles de réunion du premier étage du bâtiment 4. Un mail est envoyé à 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 les jeunes chercheurs du Lirmm. 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.

Prochain événement : Semindoc du mercredi 17 Juin 2015

Nous avons le plaisir d'accueilir Adel Ferdjoukh de l'équipe Marel à 16h30 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" Ingénierie Dirigée par les Modèles: Codera-t-on toujours demain ? "

Résumé :
Cet exposé se compose de deux parties principales. Dans la première, je présenterai une des spécialités du génie logiciel, l'Ingénierie Dirigée par les Modèles (IDM). La deuxième partie sera plus spécifique à ma thèse. Je vous décrirai une approche de génération automatique de modèles basée sur la programmation par contraintes (CSP).

 Semidoctus du jeudi 4 Juin 2015

"La demi-journée demi-science demi-fun de la fin d'année"

Repas de midi prévu pour les inscrits --> Inscription :)

En cas de problème, contactez-nous à semindoc@lirmm.fr.

accueil : 9h00

début : 9h30

pause café : 11h

fin et repas : 12h30 (rappel : repas pour les inscrits --> Inscrivez-vous vite !)

Affiche

Semindoc du mercredi 20 Mai 2015

Nous avons le plaisir d'accueilir  Sabrina Ouazzani de l'équipe Escape à 16h30 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" Introduction aux machines de Turing à temps infini "

Résumé :

Au travers de cet exposé, je compte vous présenter un aspect, tout aussi passionnant qu'amusant, des fondements de l'informatique sur lequel s'appuie mon travail de thèse : la calculabilité à temps infini.

Les machines de Turing à temps infini sont un modèle introduit en 2000 par Hamkins et Lewis qui généralise le processus de calcul des machines de Turing au temps ordinal. En particulier, les entrées peuvent être des réels. On voit alors apparaître des propriétés particulières. Par exemple, le problème de l'arrêt sur entrée 0 et le problème de l'arrêt général deviennent différents.

Lors de ce semindoc, je commencerai par vous rappeler les bases des machines de Turing classiques ainsi que le problème de l'arrêt classique. Je vous définirai également les ordinaux puis, naturellement, les machines de Turing à temps infini. Ces notions introduites, je pourrai vous montrer quelques propriétés intéressantes de ces machines et vous présenter un rapide aperçu de pistes de recherche du domaine.

Semindoc du mercredi 6 Mai 2015

Nous avons le plaisir d'accueilir  Swan Rocher de l'équipe GraphiK à 16h30 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" Raisonnement avec des Règles Existentielles "

Résumé :

Avec l'émergence du web sémantique, il devient important de pouvoir raisonner sur des données incomplètes, et une approche permettant d'y arriver est la déduction logique. Les *Règles Existentielles* représentent un fragment de la logique du premier ordre généralisant les *Logiques de Description* dites ``légères'', et ayant la même forme syntaxique que les *Tuple Generating Dependencies* des bases de données, permettant de représenter des connaissances implicites sur des individus non connus initialement.
Dans cet exposé, on verra tout d'abord que le raisonnement logique dans ce fragment est indécidable. On s'intéressera alors à des restrictions syntaxiques permettant de garantir un raisonnement fini, tout en limitant ``le moins possible'' l'expressivité de ces règles. Enfin on présentera les mécanismes qui sont utilisés pour répondre à ce problème.

 Semindoc du mercredi 15 Avril 2015

Nous avons le plaisir d'accueilir  Anaël Grandjean de l'équipe Escape à 16h30 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" Automates cellulaires : 1D et 2D "

Résumé :

Les automates cellulaires servent à représenter un systeme complexe, à partir de cellules simples (des automates finis).
De fait, ils peuvent être vus comme des systèmes dynamiques, ou comme des modèles de calcul.
Mon exposé se concentrera sur le point de vue calculatoire, et plus précisement sur deux classes de languages : ceux reconnus en temps réel, et ceux reconnus en temps linéaire.
Je présenterai des constructions classiques en 1D, avant de montrer les difficultés qui se posent quand à la généralisation aux automates cellulaires en 2 dimensions.

Événement spécial : Semindoc pré-thèse du vendredi 20 Mars 2015

Nous avons le plaisir d'accueilir  Dinh Danh LE de l'équipe Maore à 16h30 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" All-optical multicast routing under optical constraints "

Résumé :

Pré-soutenance de thèse. TBA

Résumé détaillé :

TBA

Semindoc du mercredi 18 Mars 2015

Nous avons le plaisir d'accueilir  Bastien Vialla de l'équipe Eco à 17h00 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" Introduction au Calcul Haute Performance Exact "

Résumé :

Ce semindoc se veut un tutoriel d'introduction au calcul haute performance. Le but du calcul haute performance est de créer des algorithmes ou des structures de données en tenant compte de la machine sur laquelle on va exécuter l'algorithme, avec pour seul objectif la rapidité d’exécution.
Pour des calculs qui peuvent prendre plusieurs mois sur des milliers cœurs, la moindre optimisation au niveau de l'algorithme, de la structure de données ou de l'implémentation peut faire gagner des jours calculs.

Résumé détaillé :

Dans un premier temps nous verrons quels sont les points importants dont il faut tenir compte lors du design d'une structure de données ou d'un algorithme afin que celui-ci puisse exploiter au mieux le potentiel de votre ordinateur.
Ensuite nous appliquerons ses principes à la multiplication d'une matrice creuse avec un vecteur. C'est une opération cruciale dans la résolution de systèmes linéaires intervenant dans des applications allant des attaques contre RSA, à la simulation de l'univers en passant par le calcul de pliage de protéines.
Nous verrons comment optimiser la structure de données représentant la matrice, comment améliorer les accès mémoire à l'aide de partitionnement d'hypergraphe, et finalement designer une arithmétique multi-précision efficace pour les matrices venant de cryptanalyse.

Semindoc du mercredi 4 Mars 2015

Nous avons le plaisir d'accueilir  Guillaume Guégan de l'équipe Algco à 17h00 en salle de séminaire (bâtiment 4, rdc derrière l'accueil).

Titre :
" Tri multidimensionnel "

Résumé :

Cet exposé tournera autour de la présentation et de la discussion d'un article au titre énigmatique :

Multidimensional Sorting, de Goodman et Pollack

Cet article date de 1983, et a fortement influencé ma recherche, depuis mon stage de M2.

Résumé détaillé :

Je vous parlerai de tri, l'opération que vous connaissez tous très bien depuis votre plus tendre enfance, mais on s'amusera à l'appliquer à des ensembles de points dans le plan, et en dimension supérieure.
Trier les points d'un espace, qu'est-ce que ça signifie, quel en est l'intérêt ? Et surtout, quelle a été (et sera) ma modeste contribution à ce problème ?
Après avoir expliqué ce «tri multidimensionel», et expliqué pourquoi il généralise l'opération de tri, je vous parlerai de mon travail de recherche. Je vous montrerai ensuite l'importance de la question, en décrivant quelques applications pratiques, et j'essaierai de plus de lier le problème à d'autres questions théoriques importantes (entre
autres, l'existence de systèmes de Steiner, l'existence de dessins de graphes satisfaisant certaines contraintes, etc, etc).
J'espère réussir à partager mon enthousiasme pour un problème qui intéresse à la fois des théoriciens «purs» et des chercheurs plus «appliqués».
Mon exposé sera didactique, aucune culture théorique ne sera demandée, au-delà des notions algorithmiques de base (tris, complexité). Ce sera l'occasion pour chacun d'étendre ses connaissances et de parfaire sa culture en combinatoire, en géométrie algorithmique et en théorie des graphes (orientés).

Semindoc du mercredi 11 Février 2015

Nous avons le plaisir d'accueilir  Guilhem Gamard de l'équipe Escape à 17h00 en salle 3.23 (bâtiment 4, premier étage).

Titre :
" Couvrabilité en deux dimensions "

Résumé :
Combinatoire des mots.

Résumé détaillé :

 
Un «mot rectangulaire» se définit comme une chaîne de caractères à deux dimensions, autrement dit une matrice de lettres. Un «mot à deux dimensions» est un mot rectangulaire infini. On dit qu'un mot rectangulaire u *couvre* un mot à deux dimensions w si toute lettre dew fait partie d'une occurrence de u. Il s'agit d'une notion analogue à la périodicité, excepté que les périodes peuvent se chevaucher partiellement. Un mot à deux dimensions est *couvrable* s'il est couvert par au moins un mot rectangulaire.
Après les rappels et définitions fondamentales, nous explorerons la couvrabilité. Nous verrons que, malgré des définitions très proches, la périodicité et la couvrabilité sont en fait très différentes. Nous tenterons de mieux comprendre ce paradoxe, et nous proposerons une solution pour le résoudre.

Semindoc du mercredi 4 Février 2015

Nous avons le plaisir d'accueilir  Guillerme Duvillie de l'équipe Maore à 16h30 en salle 3.23 (bâtiment 4, premier étage).

Titre :
" Complexité, (in)approximation et réductions polynomiales. "

Résumé :
Cette présentation s'adresse avant tout aux néophytes intéressés par les domaines de la complexité et de l'approximation mais est aussi susceptible d'offrir des perspectives nouvelles à des initiés dans ces domaines.

Résumé détaillé :

En complexité, malgré une prédominance forte des réductions de Turing et de Karp (visant à démontrer la NP-complétude d'un problème), il existe une multitude de réductions polynomiales. Chacune de ces réductions a pour but de préserver l'appartenance à une classe de complexité donnée.
Cette présentation sera articulée autour des grands axes suivants :
* Introduction aux notions de complexité et de classes de complexité
* Présentation des réductions de Karp et Turing
* Réductions strictes, linéaires et (in)approximabilité
* Applications de ces réductions à Vertex Cover et aux problèmes de type Wafer-to-Wafer Integration

Semindoc du mercredi 28 Janvier 2015

Nous avons le plaisir d'accueilir  Julien Pagès de l'équipe Marel à 14h30 en salle 3.24 (bâtiment 4, premier étage).

Titre :
" Une Machine Virtuelle pour un Langage à Objets en Héritage Multiple. "

L'affiche de l'événement est disponible ici.

Résumé :

Dans cet exposé nous présenterons un projet de recherche consistant à étudier et développer une machine virtuelle pour un langage à objets en héritage multiple : Nit.

Résumé détaillé :

Un machine virtuelle est un système d'exécution de langages de programmation qui est aujourd'hui utilisé pour de nombreux langages de programmation populaires de ces dernières années : Java, C#...

Les performances de ces systèmes sont souvent bonnes mais les mécanismes d'optimisations pendant l'exécution sont souvent très complexes et/ou assez peu décrits dans la littérature scientifique.

Nous commencerons par présenter les outils et techniques choisis pour ce projet ainsi que les enjeux de recherche.
Ensuite nous aborderons les perspectives prévues, à savoir l'étude des protocoles d'optimisations dans les machines virtuelles.

Semindoc du mercredi 10 Décembre 2014

Nous avons le plaisir d'accueilir Yannick Francillette de l'équipe Smile à 10h30 en salle de séminaire (bâtiment 4, derrière l'accueil).

Titre :
" Modèle adaptatif d'activités pour les jeux ubiquitaires "

Résumé :

"Dans ce semindoc nous allons nous intéresser à une activité qui est pratiquée par énormément de personnes : « les jeux ». Nous allons découvrir les apports de l'informatique mobile dans ce domaine et comment faciliter le développement de jeux ubiquitaires."

Résumé détaillé :

Les technologies et services mobiles font aujourd’hui partie de notre vie quotidienne grâce notamment aux ordiphones et ardoises numériques. Nous vivons actuellement la réalisation de la vision de Marc Weiser. Les fonctionnalités et les services rendus prennent le dessus sur les objets techniques.

Dans ce sémindoc, nous allons nous intéresser à un type particulier d’applications informatiques : les jeux vidéo. Comme d’autres secteurs, les jeux vidéo doivent prendre en compte la révolution mobile, pour se réinventer et intéresser des joueurs. Cependant, les jeux sur support mobiles doivent faire face au problème du changement des conditions de jeu du joueur. Nous pouvons parler de contexte du joueur.

Au cours de ce séminaire, je vais présenter mes travaux de thèse qui portent sur la proposition d'un modèle permettant la conception de jeu auto-adaptatif au contexte du joueur.

 Romain Endelin : Semindoc du mercredi 19 Novembre 2014

Nous avons le plaisir d'accueillir Romain Endelin de l'équipe IDH à 10h30 en salle E3.23 (bâtiment 4, dernier étage).

Titre :
"Assistance ambiante aux personnes âgées"

Résumé :

"Nous décrirons une solution d'Assistance Ambiante aux personnes âgées.
Nous commencerons par les technologies nécessaires à sa mise en place.
Puis nous nous concentrerons sur les algorithmes utilisés pour la
reconnaissance d'activité humaine à partir de données capteur."

Résumé détaillé :

Face à une population toujours vieillissante, en France et ailleurs, deux solutions se proposent pour les personnes âgées : le maintien à domicile (seul ou au sein de leur famille), ou le placement en établissement spécialisé. Ces solutions présentent toutes les deux des contraintes énormes, en terme de danger pour les personnes âgées, et de stress pour les aidants.
En parallèle, notre vision de la technologie vit un grand changement de paradigme, où un nombre toujours croissant d'objets sont connectés à l'Internet, et où la technologie devient de plus en plus pervasive.
Nous pensons que, tirant profit de cette informatique pervasive, des solutions d'Intelligence Ambiante (et plus spécifiquement d'Assistance Ambiante) peuvent être proposées pour faciliter la condition des personnes âgées et de leurs aidants

Dans la première partie de cette présentation, nous décrirons la mise en place concrète d'une telle solution. Nous commencerons par introduire les mouvements et paradigmes dont nos travaux s'inspirent. Puis, en prenant pour fil rouge un déploiement de notre système, nous listerons les composants, protocoles et plates-formes que nous utilisons.
La seconde partie de la présentation sera plus algorithmique, et se concentra sur le principal challenge de cette discipline : la reconnaissance d'activité à partir de signaux capteurs. Nous y décrirons les 2 grandes approches du domaine, dîtes Data-Driven et Knowledge-driven, ainsi que leurs faiblesses et leurs forces.

Semidocti du 17 Octobre 2014

"La journée demi-science demi-fun de la rentrée"

9h30 : Accueil

10h : Présentation et exposés

Guilhem Gamard, "Les langages de programmation de l'extrème"

 Résumé :
Dans cet exposé, je présenterai quelques langages de programmation ésotériques. Certains sont relativement connus, d'autres moins. Au menu : un langage ayant uniquement des instructions randomisées, un langage dont le code source se lit en deux dimensions et… une surprise ! Ces langages ont tous une bonne puissance de calcul (certains sont turing-complets, pour les connaisseurs) mais sont tous inutilisables en pratique. Pour celles et ceux qui veulent relever le défi, des compilateurs seront disponibles en téléchargement. :)

Guillaume Guégan, "Calculer avec son corps"

 Résumé :
« Heureux Nestor, qui, ayant dépassé la centaine, compte déjà les années sur la main droite. »
 Juvénal, Satires (90-127 ap. J.-C.)

En comptant sur vos doigts avec votre méthode préférée, quel nombre pouvez-vous atteindre ? Avec une seule main ? avec vos deux mains ?

Vous serez sans doute surpris d'apprendre que nos ancêtres utilisaient des méthodes élaborées dès l'Antiquité, leur permettant de compter avec leurs deux mains jusqu'à dix-mille, voire un million, et même dix milliards.

Si la main a été la première machine à compter, elle a aussi été la première machine à calculer, utilisée pour des opérations simples comme l'addition et la multiplication, ou la mise en œuvre d'algorithmes plus complexes, comme le calcul de la date de Pâques.

L'exposé que je me propose de vous donner sera un tour d'horizon des méthodes de calcul digital, à travers l'histoire et les cultures. Comme il serait dommage de s'arrêter à la théorie, l'audience sera invitée à faire usage de ses mains tout au long de la présentation.

Guillaume Bagnolini, "Matrice, rêve ou réalité ?"

 Résumé :
Au coeur du propos du film Matrix, il y a des questions aux accents de philosophie adolescente ; le film est rempli de lieux communs philosophiques et de références ouvertes ou occultes à toute la tradition: de Platon à Baudrillard en passant par Descartes. Matrix serait donc une machine de réflexions philosophiques ? Même si nous en doutons, le film permet par son univers de science-fiction d'introduire une question, comment savoir si la réalité n'est pas une vaste illusion ? Nous réfléchirons sur cette question en parlant de la limite entre le virtuel et la réalité qui devient de plus en plus floue.

13h : Repas (pour les inscrits --> Inscrivez-vous !)

13h30 : Présentation par les doctorants des équipes du département informatique

Mon équipe du Lirmm en 180 secondes

 Résumé :

3 minutes, c'est le temps imparti à un doctorant pour présenter son équipe.
Cet événement, inspiré du concours "ma thèse en 180 secondes", a pour vocation de donner à tous un aperçu du département informatique du Lirmm.
3 ou 4 slides axés sur la vulgarisation permettront aux intervenants de décrire les membres et principaux thèmes de recherche de leur équipe.

Précédentes éditions des Semidocti

11/07/14 - Premier Semidoctus

 Résumé :

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 !

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/2014

Modalités

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

  • on demande d'envoyer aux organisateursau moins 5 jours avant, un titre, un résumé, ainsi qu'une estimation de la durée de l'exposé,
  • on demande un exposé axé sur la vulgarisation de travaux scientifiques (les vôtres ou un autre thème qui vous tient à coeur). Celui-ci devra donc être compréhensible par tout l'auditoire. Les définitions et le contexte doivent en particulier être posés clairement. Des sessions humouristiques ou historiques en lien avec l'informatique peuvent également être programmées (semidoctus de demi-journée ou semidoctus le temps d'un exposé).
  • on demande un temps d'exposé environ compris entre 20 et 50 minutes, et de prévoir que celui-ci sera suivi de questions de l'auditoire.

Pour proposer l'invitation à ce séminaire d'un doctorant extérieur au LIRMM :

  • on demande d'envoyer dès que possible aux organisateurs le nom de ce doctorant ainsi que son thème de recherche;

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 :

Mots-clés

vulgarisation scientifique, séminaire inter-doctorants, bonne ambiance et petit-dèj offert !

Dernière mise à jour le 12/06/2015