Accueil des élèves de l'ENS Cachan

Ateliers pour la visite du LIRMM

29 janvier 2007

Agenda

9h-10h	Accueil (salle 2.57-séminaires)
10-11h	A16 (salle E.223)	A4 (salle 1.4)	A12 (salle 2.56)	A20 (salle E.217)
11h-12h	A5 (salle E.223)	A14 (salle 1.4)	A3 (salle 2.56)	A18 (salle E.217)
12h-13h30	Repas (salle 2.57)
13h30-14h30	A6 (salle E.223)	A22 (salle 1.4)	A17 (salle 2.56)	A10 (salle E.217)
14h30-15h30	A21 (salle E.223)	A9 (salle 1.4)	A2 (salle 2.56)	A7 (salle E.217)
15h30-16h30	A19 (salle E.223)	A13 (salle 1.4)	A8 (salle 2.56)	A11 (salle E.217)

Liste des ateliers

A1 - Acquisition de contraintes
participant : C. Bessiere, E. Bourreau, F. Koriche

A2 - Arithmétique de la cryptographie
participants : J.-C. Bajard, S. Duquesne, L. Imbert

A3 - Codage et tatouage d'images
participants : M. Chaumont, W. Puech, G. Subsol

A4 - Développement individuel et collectif de sociétés d'agents
participant : Jacques Ferber
Sujet: http://www.lirmm.fr/~ferber/M2R/Projet.developpement1.htm

A5 - Evolution des séquences biologiques
Laurent Brehelin, Stéphane Guindon, Olivier Gascuel
Sujet : http://www.lirmm.fr/~guindon/wordpress/?page_id=34

A6 - Extraction de motifs séquentiels dans de grandes bases de données
participants : Maguelonne Teisseire, Anne Laurent, Marc Plantevit, Chedy Raissi, Pascal Poncelet
http://www.lirmm.fr/~teisseir/cachan.html

A7 - Formalisation semantique des systèmes multi-agents et des services à état et persistents (GRID)
Stefano Cerri, Abdelkader Gouaich
http://www.lirmm.fr/~gouaich/cachan.html

A8 - Géométrie discrete : une approche combinatoire
participants : Valérie Berthé, Christophe Fiorio, Christian Mercat, Thierry Monteil, Patrice Séébold

A9 - Ingénierie des données dans les systèmes Distribuées
participants : Z. Bellahsène, M. Cart, J. Ferrié

A10 - Introduction à l'évaluation de performances avec perspectives sur les réseaux pair-à-pair
participants : Alain Jean-Marie
Sujet : http://www.lirmm.fr/~rgirou/ens/presentation.html

A11 - Médiation et chaînes de traitements pour les systèmes environnementaux
participante : Thérèse Libourel

A12 - Ordonnancement: complexité et approximation
participant : Rodolphe Giroudeau
Sujet : http://www.lirmm.fr/~rgirou/ens/presentation.html

A13 - Partitions et Clustering de graphes
participants : M. Hascoet et S. Thomasse
Sujet : http://www.lirmm.fr/~thomasse/Cachanpartition.html

A14 - Problèmes de routage dans les réseaux
participants : Jérôme Palaysi
Sujet : http://www.lirmm.fr/~rgirou/ens/presentation.html

A15 - Programmation par composants et tolérante aux pannes
participant : Christophe Dony
Sujet : www.lirmm.fr/~dony/research/r-exc.html

A16 - Représenter des connaissances et raisonner avec des graphes
participants : J.-F. Baget, M. Leclere, M.-L. Mugnier

A17 - Road Coloring
participants: Stéphane Bessy et Binh Minh Bui Xuan.
Sujet : http://www.lirmm.fr/~bessy/VisiteENSCachan.html

A18 - Sémantique institutionnelle de la communication dans les SMA
participants : Tiberiu Stratulat, Jacques Ferber
http://www.lirmm.fr/~stratula/m2r/SujetCommunication.html

A19 - Spécification et compilation efficace des langages à objets à classes, modules et héritage multiple.
participant : Roland Ducournau
Sujet : http://www.lirmm.fr/~ducour/Ducour/cachan07.html

A20 - Traitement d'objets 3D
participants : G. Gesquières, R. Raffin, O. Strauss, G. Subsol, Philippe Amat

A21 - Tree-width et stratégies d'encerclement
participants : Stéphan Thomassé, Binh-Minh Bui-Xuan
Sujet http://www.lirmm.fr/~buixuan/Cachanjeupoursuite.html

A22 - Treillis de Galois (Analyse Formelle de Concepts)
participante : Marianne Huchard

Détails sur certains ateliers

Acquisition de contraintes

C. Bessiere, E. Bourreau, F. Koriche

En programmation par contraintes, on représente un problème
combinatoire sous forme de variables, leurs domaines, et de
contraintes qui portent sur des sous-ensembles de ces variables.
Une contrainte spécifie les combinaisons de valeurs autorisées
pour les variables qu'elle lie. Par exemple, la contrainte
X + Y = 4 spécifie que les variables X et Y doivent prendre
des valeurs dont la somme fait 4.
Une fois le problème représenté ainsi, la programmation par
contraintes permet de le résoudre efficacement grâce aux
algorithmes développés dans les solveurs. Les problèmes
d'affectation de taches, d'allocation de ressources, et
beaucoup d'autres sont résolus avec succès par les solveurs
à contraintes.
Mais la phase de "modélisation", c'est à dire la représentation
du problème en contraintes, n'est pas chose aisée pour un
non spécialiste. Ce travail continuera les travaux débutés
depuis trois ans dans l'équipe Kayou sur l'acquisition
semi-automatique de problèmes à contraintes.

Arithmétique de la cryptographie

J.-C. Bajard, S. Duquesne, L. Imbert

La cryptographie contemporaine, en particulier celle à clé publique, est basée sur
des propriétés arithmétiques d'objets mathématiques comme les corps finis, les
courbes elliptiques, voire hyperelliptiques, les anneaux de polynômes, les réseaux euclidiens...

Au sein du projet ARITH un groupe s'est spécialisé sur les aspects représentations-algorithmes des arithmétiques impliquées dans les protocoles cryptographiques. Les
chercheurs impliqués ont développé plusieurs approches comme, par exemple,
des arithmétiques basées sur le théorème des restes chinois, des systèmes multibases, des bases adaptées (où interviennent des algorithmes de réduction dans les réseaux)...
Dans leur collaboration avec l'équipe d'arithmétique géométrique du laboratoire de mathématique I3M, ils étudient des aspects plus théoriques sur les courbes hyperelliptiques, les couplages, les réseaux...

Nous comptons organiser cet atelier de la manière suivante.
Nous esquisserons dans un premier temps une rapide zoologie de systèmes de numération adaptés à ce type d'étude.
Puis nous évoquerons quelques exemples de développements   actuels sur lesquels nous nous appuierons au cours de cet atelier,
en essayant de donner une vision intuitive des objets concernés (courbes elliptiques, etc...)

- Les systèmes de numération (comme les bases adaptées) utilisés au sein du calcul sur les corps finis (GF(p) ou GF(2^k) voire GF(p^k)) font naturellement intervenir des réseaux :
nous montrerons l'intérêt de   développer des adaptations d'algorithmes de réduction comme LLL, voire de développer des algorithmes ad-hoc, vu les particularités des réseaux impliqués.

- D'autre part, il existe des systèmes de numération comme ceux basés sur les restes chinois, qui ont la particularité d'offrir une multiplication de très faible coût, mais où la réduction reste
onéreuse. L'idée est de réorganiser les expressions de l'addition sur les courbes elliptiques et hyperelliptiques, afin de minimiser le nombre de réductions, puis de comparer les coûts avec des arithmétiques plus classiques.
Les systèmes basés sur les restes chinois ont aussi la particularité de permettre un "comportement aléatoire" rendant difficile certaines attaques (pour par exemple trouver la clé secrète), dites par canaux cachés.
L'étude de cet aspect aléatoire du comportement des calculs doit être affinée afin de garantir la sécurité tout en maintenant l'efficacité des opérations.

--Enfin, nous évoquerons la numération dans des bases multiples. Cette numération redondante
consiste à développer les entiers comme des sommes de   produits de puissances de 2 et 3.
Elle suscite de nombreuses questions ouvertes et connaît   des développements récents et prometteurs en cryptographie.

Géométrie discrete : une approche combinatoire

Valérie Berthé, Christophe Fiorio, Christian Mercat, Thierry Monteil, Patrice Séébold

url : http://www.lirmm.fr/~berthe/Cachan.pdf

Introduction

La géométrie discrète est apparue dans les années 70. Elle a pour objectif
de définir des modèles discrets de représentation du continu et de fournir
un cadre théorique à l'étude des objets géométriques et de leurs
transformations dans un espace discret. La contrainte naturelle qui
s'impose à cette étude est que la géométrie discrète se rapproche au plus
près de la géométrie euclidienne. Une telle contrainte n'est pas (pour
l'instant ?) complètement satisfaite. Cependant, il a déjà été montré que
des propriétés classiques de la géométrie euclidienne possèdent une
formulation équivalente en géométrie discrète.

Afin d'atteindre ce but, il est nécessaire, non seulement de fournir une
définition discrète analogue à une notion euclidienne, mais aussi
d'étudier et décliner, dans le domaine discret, toutes les propriétés
associées à la notion euclidienne. Ces définitions doivent bien sûr
permettre un aller-retour entre le monde discret et le monde continu.

Deux grand types de discrétisations se complètent :
- l'espace lui-même est discret, il n'y a pas de points, de lignes ou de surfaces mais des ensembles d'éléments de volumes, des petis cubes appelés voxels.
On se pose alors la question d'identifier un ensemble de voxels à une ligne, une surface...
- l'objet géométrique est représenté par un nombre fini d'éléments. Par exemple une triangulation remplace une surface lisse.
On s'intéresse alors à donner à cette surface discrète des caractéristiques géométriques proches de celles de la surface lisse
qu'elle représente et qui s'en approchent quand on raffine la surface discrète.
Nous évoquerons ces deux approches lors de cet atelier.

Un des intérêt majeurs de la géométrie discrète est de s'affranchir des
problèmes d'approximation et d'interpolation posés par l'approche
classique du plongement des objets euclidiens sur la grille discrète en
proposant des codages compacts exact.
La géométrie discrète permet alors de raisonner juste à partir de calculs
justes qui se terminent, même si les figures obtenues restent fausses.
Deux approches de cette problématique sont possibles :
--une approche purement combinatoire étudiant les configurations des
points composant les objets, approche souvent liée à la combinatoire des
mots et aux systèmes dynamiques ;
--une approche analytique et arithmétique, introduite par Jean-Pierre Réveilles en
1991, basée sur l'arithmétique diophantienne, consistant à définition les
objets à l'aide d'un système d'inéquations.

Un des buts de cet atelier est de montrer qu'il existe de nombreux liens entre ces deux
approches et qu'elles peuvent parfois se compléter et permettre de
démontrer des résultats et propriétés intéressants. Un des points
clefs de notre approche (développée au sein du Projet ARITH) est ainsi la notion de fonctionnalité qui consiste à
projeter bijectivement certains objets discret 3D sur
un réseau euclidien de rang 2. Cette bijection nous permet de munir les
objets d'un codage indexé par Z² et d'en extraire
des propriétés géométriques à l'aide des outils de la géométrie discrète
2D ou hérités de la dynamique symbolique et de la combinatoire des mots.

Étude proposée

Les premiers objets étudiés d'un point de vue théorique furent
naturellement les droites discrètes 2D.
Jean-Pierre Reveillès fut le premier à donner une
définition analytique d'une telle droite en proposant de définir une
droite comme les points solutions d'une double inégalité diophantienne, ce
qui géométriquement revient à prendre les points entiers compris dans une
bande délimitée par deux droites euclidienne. La largeur de la bande est
appelée l'épaisseur de la droite. De nombreux liens existent entre l'approche combinatoire et l'approche
arithmétiques. Ainsi la droite arithmétique naïve
est représentable par des mots de
Christoffel ou des mots sturmiens.

Au contraire, aucune des définitions existantes de droites discrètes 3D,
algorithmiques ou arithmétiques ne s'est imposée.
Nous axerons en particulier cet atelier autour de l'étude d'une définition des droites 3D comme
intersection de plans discrets afin d'essayer d'en dégager une définition
générale.

Ingénierie des données dans les systèmes Distribuées

Réconciliation des copies dans les environnements collaboratifs, mobiles et P2P

Jean FERRIÉ, Michelle CART

Les systèmes P2P qui autorisent la mise à jour des copies d’un objet (i.e. Freenet, P-Grid,..) restreignent la mise à jour à ne provenir que du site origine de l’objet. L’objectif de la recherche consiste à étudier les méthodes qui permettent d’obtenir la convergence des copies, sans imposer cette importante restriction. Plus précisément, il s’agira d’approfondir, d’étudier le passage à l’échelle, de mettre en œuvre (en Java) et d’évaluer l’algorithme MOT2 conçu par l’équipe, qui est bâti autour des Transformées Opérationnelles et qui permet de réconcilier deux copies quelconques, sans en privilégier aucune.

URL : http://www.lirmm.fr/~bella/SujetMOT2.pdf

Optimisation de requêtes XQuery à l’aide de vues à matérialisées

Z. Bellahsène

Le processus de matérialisation de vues permet d'améliorer les
performances d'un système de gestion de données. L'objectif de cette
thèse est de proposer des algorithmes et des méthodes de sélection vues
à matérialiser pour optimiser des requêtes XQuery. L’étude sera réalisée dans le contexte du projet ANR FORUM.

URL : http://www.lirmm.fr/~bella/SujetXMLViews.pdf

Médiation et chaînes de traitements

Thérèse Libourel

Les chercheurs des domaines environnementaux (information biologique, géographique) doivent concevoir des applications d’aide à l’analyse diffusables à large échelle.
Le sujet porte sur l’apport de l’approche ingénierie des modèles pour concevoir de telles applications.
Les experts des domaines concernés disposent de modèles de représentation de connaissances (que nous pouvons désigner comme modèles ontologiques). A partir de ces modèles ils doivent concevoir des bases de données puis construire des modèles de traitements. La traçabilité des données manipulées est cruciale. Enfin bases de données et traitements peuvent être considérés comme des « services » accessibles et composables à demande selon le profil d’usage visé.
Concevoir une application accessible sur le Web (dans un contexte d'infrastructure de médiation) nécessite plusieurs étapes :
créer ou réutiliser des modèles « ontologiques »
créer ou réutiliser des modèle de base de données
créer le modèle de traitements
assurer l'exécution des chaînes de traitements à partir de données et traitements élementaires distribués
assurer la « traçabilité des données manipulées »
L’ingénierie des modèles suppose que l’on puisse à l’aide de transformations explicites passer d’un modèle à un autre. Le travail repose sur l’explicitation des règles de transformations entre les divers modèles évoqués précédemment pour faciliter la conception et la capitalisation des connaissances.
Si les modèles « ontologiques » et de bases de données existent, une réflexion supplémentaire doit porter sur le modèle des traitements (voir modèles de tâches, workflow). La traçabilité des données doit découler du modèle des traitements. Travail autour de l'exécution automatique des chaînes de traitements dans le contexte "médiation" avec mise en oeuvre de la traçabilité (via les métadonnées par exemple).

Tatouage d'images

Tatouage sécurisé et robuste aux déformations géométriques, dans des régions d’intérêt.

William PUECH et Marc CHAUMONT

Nous nous intéressons à l’insertion de données cachées au sein d’une image dans des régions d’intérêt préalablement définies par un opérateur. Ces régions d’intérêt peuvent être par exemple des objets contenus dans une BDD images. L’insertion de données cachées dans les régions d’intérêt doit supporter des traitements courants sur les images tels que le découpage, le changement d’échelle et les rotations. De tels traitements sont appelés des attaques non malveillantes et les données cachées doivent être extractibles après ces attaques. L’objectif de ce stage est de prolonger une étude précédemment menée [Lo-Varco et al. 2005]. Pour le moment l’approche repose sur le calcul des 2 axes principaux (Analyse en Composantes Principales) de la RI et ensuite en une insertion de données effectuée sur des blocs et ceci en prenant en compte le repère formé par les 2 axes. Une telle approche reste insuffisamment robuste lorsque la forme de la RI (le masque) obtenue par une segmentation automatique n’est pas la même que la forme utilisée lors de l’insertion.

[Lo-Varco et al. 2005] “ Based Color and Content Watermarking for Safe Image ”, JIST, Journal of Imaging Science and Technology, G. Lo-varco, W. Puech et M. Dumas. vol. 49 , n° 4, pp.450-459, septembre 2005.

Implémentation d’un schéma de tatouage robuste

Marc CHAUMONT

La compétition BOWS (Break Our Watermarking System) qui s’est terminée le 15 juin 2006 avait pour objectif d’attaquer le système de tatouage proposé dans [M.L Miller, G. J. Doerr and J. Cox 2004]. Le système a été assez bien “ cassé ” ; l’équipe gagnante a obtenu des attaques dont les PSNRs images étaient supérieurs à 38.46 dB. Malgré la fragilité avérée de la technique de tatouage de [M.L Miller, G. J. Doerr and J. Cox 2004] celle-ci reste intéressante théoriquement (c’est l’une des approches les plus robustes de l’état de l’art) et de plus elle peut être améliorée. L’objectif de ce stage est de comprendre et d’implémenter l’algorithme de tatouage et d’en proposer des extensions.

[M.L Miller, G. J. Doerr and J. Cox 2004] “ Applying Informed Coding and Embedding to Design a Robust, High capacity Watermark ”, M.L Miller, G. J. Doerr and J. Cox, IEEE Trans. On Image Processing, 13, 6, 792-807, June 2004.

Etude des systèmes de tatouage visible

William PUECH et Marc CHAUMONT

Le tatouage visible sur une image consiste à sur-imprimer un logo de manière visible. Cette technique protège de l’utilisation frauduleuse d’images propriétaires. La technique doit donc rendre inutilisable commercialement une image tatouée de manière visible. Le tatouage visible doit donc répondre aux deux contraintes suivantes : l’image ayant subit le tatouage doit conserver une bonne lisibilité et la suppression du logo doit être impossible. L’objectif du stage est d’évaluer la robustesse des techniques actuelles [C.-H. HUANG et J.-L. WU 2004] et de proposer des approches plus robustes. Un “ cocktail ” de technique de tatouage pourra également être envisagé : tatouage visible robuste + tatouage invisible non robuste (contenant l’information permettant de retirer le logo).

[C.-H. HUANG et J.-L. WU 2004] “ Attacking visible watermarking schemes ” HUANG Chun-Hsian, WU Ja-Ling, IEEE Transaction on multimedia, 2004, vol6, n°1, pp 16-30.

Marquage de maillages 3D : application à des objets industriels ou artistiques

William PUECH et Gérard SUBSOL

On a un maillage surfacique d’un objet 3D dans un format "standard" (par exemple, la liste des sommets et liste des facettes) et on cherche à introduire des informations cachées dans le maillage à des fins de
protection ou d'enrichissement de données.

Ce procédé d’intégration de données cachées se nomme “ watermarking ” ou “ data-hiding ” en anglais et tatouage ou filigranage en français. En effet, comme dans un filigrane, l’information doit être imperceptible, autrement dit le maillage 3D doit être très peu modifié par l’introduction des données. D’autre part, le filigranage doit résister aux traitements classiques subis par un maillage 3D, à savoir la conversion de format ou la compression. On peut même imaginer des modifications plus importantes comme la découpe d’un petit morceau ou un rééchantillonnage du maillage.

Images 3D

Extraction de caractéristiques différentielles 3D pour la caractérisation de la forme de structures anatomiques : application à la paléo-anthropologie et à l'aide au diagnostic médical

Olivier STRAUSS et Gérard SUBSOL

La morphométrie a pour but d’obtenir une évaluation quantifiée de la forme d’un objet. Dans le cas de structures anatomiques (par exemple, un crâne), la forme peut être très complexe et ne peut être décomposée en primitives simples comme dans le cas des objets manufacturés qui sont souvent polyédriques.
Une approche du problème consiste à calculer les caractéristiques différentielles de la surface et à les utiliser pour quantifier la forme locale de la structure. Par exemple, le calcul des courbures principales différencie les parties concaves et convexes ; les directions principales de courbure paramètrent localement la surface suivant un maillage orthogonal et les dérivées des courbures suivant leurs directions principales associées permettent d’extraire des “ lignes de crête ” qui mettent en évidence les zones saillantes de la structure.

Déformations spatiales 3D : application à la médecine légale et à la paléo-anthropologie

Gérard SUBSOL, Gilles GESQUIERE et Romain RAFFIN

Le but du travail est d'étudier des modélisations mathématiques de déformations spatiales qui respectent un certain nombre de contraintes géométriques (appariements de points) ou de régularité. Ces déformations seront utilisées pour deux types d'applications :
- la reconstruction faciale en médecine légale : ou comment "reconstituer" automatiquement le visage d'une personnes disparue à partir de son crâne ?
- la compensation des déformations taphonomiques en paléo-antrhopologie : ou comment "redresser" automatiquement un crâne fossile qui a été déformé, après l'enfouissement, par les mouvements des couches géologiques environnantes.

Reconstruction tridimensionnelle à base de silhouette

Olivier Strauss, Philippe Amat

http://www.lirmm.fr/~huchard/CACHAN/Silhouette.pdf

Treillis de Galois (Analyse Formelle de Concepts) et leur application au génie logiciel

Marianne Huchard

Les treillis de Galois permettent de découvrir des similarités et de construire des abstractions dans des ensembles d'entités décrites par des propriétés.

Le treillis de Galois associé à une relation binaire (encore appelé treillis de concepts) a pour éléments un ensemble de concepts extraits de la relation grâce à deux opérateurs de fermeture. Si l'on considère que la relation associe des propriétés à des entités, chaque concept est un couple de deux ensembles, un ensemble d'entités et un ensemble de propriétés, tels que les entités partagent toutes (et au maximum) les propriétés, et réciproquement que les propriétés soient partagées par toutes (et au maximum) les entités. L'ordre entre les concepts est donné par l'inclusion entre ensembles d'entités.

Les treillis de Galois sont utilisés depuis longtemps en apprentissage ou en fouille de données et plus récemment pour le génie logiciel. Dans ce dernier cadre ils permettent de dériver ou d'améliorer des modèles de conception, de programmation, de découvrir des structures récurrentes dans les modèles et les programmes. Toutes ces applications ont un retentissement sur la théorie de base qu'il faut sans cesse étendre pour prendre en compte la réalité du domaine. Par exemple l'intégration dans des outils de génie logiciel demande des algorithmes construisant de la manière la plus efficace possible les treillis ou certaines de leurs sous-structures ; autre problème posé, les données descriptives des logiciels sont complexes et ne se réduisent pas à de simples relations binaires. L'équipe travaille à la fois sur les aspects théoriques et les aspects pratiques de cette problématique et a récemment proposé une extension de l'Analyse Formelle de Concepts (l'Analyse Relationnelle de Concepts) sur laquelle de nombreux problèmes restent ouverts.

Développement individuel et collectif de sociétés d'agents

Jacques Ferber

Analyse de la co-évolution des capacités cognitives individuelles et collectives dans des sociétés artificielles à base d'agents.
Le but de cette recherche est d'analyser l'impact des architectures évolutives sur le collectif, et inversement d'étudier l'impact d'organisations sociales multi-agent sur le développement des capacités cognitivies individuelles des agents, au travers de la coordination et des interactions entre agents.
Détail du projet: http://www.lirmm.fr/~ferber/M2R/Projet.developpement1.htm