TER de semestre 2 de Master (année 2007-08)

23 sujets I2A

Mention : Informatique

Spécialité : Informatique professionnelle et Recherche en Informatique

1. Les aventuriers du rail

Rémi Coletta

Résumé : Les aventuriers du rail est un jeu de société, dont le plateau est une carte d'europe sur laquelle sont représentées des villes et des routes ferroviaires. Chaque joueur tire des cartes "objectif" spécifiant deux villes à relier. En termes informatiques, le plateau est un graphe, dont les villes sont les sommets, les routes sont les arrêtes, etc... Dans un premier temps vous réaliserez une interface graphique pour ce jeu, en utilisant des outils existants de visualisation de  graphe.Puis vous créerez un joueur IA capable de réaliser les objectifs qui lui sont fournis.

Parcours concerné : GL, I2A

Remarques (UE conseillées, langage…) : Bonne connaissance Java

2. Représentation des résultats de recherche Web sur carte géographique GoogleMaps

Jean-Yves Delort

Résumé : L'objectif de ce projet est de développer un système permettant l'insertion automatiquement de liens hypertextuels dans des cartes géographiques (GoogleMaps). Les cartes seront produites dynamiquement, en réponse à des recherches de l'utilisateur.

Parcours concerné : DIWEB, GL, I2A

Remarques (UE conseillées, langage…) : l'expérience des systèmes d'information géographique (SIG) est un atout.

7. Mise en oeuvre d'une plateforme logicielle d'évaluation des sigles

Mathieu Roche et Violaine Prince

Résumé : Le travail consiste à évaluer un ensemble de mesures de qualité pour déterminer le choix de la meilleure définition pour un sigle non défini dans une page Web. The work consists in evaluating a set of quality measures to determine the choice of the best expansion for an acronym not defined in a Web page.

Parcours concerné : DIWEB, I2A

Remarques (UE conseillées, langage…) : Intérêt pour le TAL

8. Estimation d’un arbre de recherche

Eric Bourreau

Résumé : Nous chercherons à utiliser des techniques d’estimation d’un arbre d’énumération pour à la fois mieux guider l’exploration (intensification/diversification) mais aussi pour améliorer la découpage d’un problème (grid computing).

Parcours concerné : CASAR, I2A

Remarques (UE conseillées, langage…) : Résolution de problèmes NP-difficiles

9. Voulez vous partager 2 000 000 avec moi ?

Eric Bourreau

Résumé : Eternity2 est un challenge mathématique. Le premier à le résoudre gagne 2 000 000 $... nous proposons d’essayer de le résoudre.

Parcours concerné : CASAR, I2A

Remarques (UE conseillées, langage…) : Algorithmique de l’IA, Résolution de problèmes NP-difficiles, voire Algorithmique Géométrique. Langages de programmation : Java

10. Un peu d’IA dans un cerveau de robot humanoïde

Eric Bourreau

Résumé : Nous cherchons à connecter une plateforme logicielle (théorique) simulant l’autonomie d’un robot sur plusieurs modèles physiques du LIRMM (surtout HOAP de Fujitsu, robot humanoïde de 80 cm).

Parcours concerné : CASAR, I2A

Remarques (UE conseillées, langage…) :

11. Environnement de démos pour Choco

Eric Bourreau

Résumé : La librairie Choco possède déjà quelques démos, nous souhaitons homogénéiser et mettre en valeur les différentes contributions (tant visuellement que programmatiquement) à partir d’une librairie de problèmes : la CSPLIB.

Parcours concerné : CASAR, DIWEB, GL, I2A

Remarques (UE conseillées, langage…) : Langages de programmation : Java

12. Cartographie de mots : application à la visualisation de noms de marque

Mountaz Hascoët, Mathieu Roche, Anne Laurent

Résumé : De plus en plus souvent, les utilisateurs cherchent des moyens visuels d'organiser leurs connaissances. En particulier, les utilisateurs désireux de connaître comment s'articulent un grand nombre de données souhaitent souvent les voir affichées sous forme de graphes. Dans ce projet, il s'agit d'aider les créateurs de noms de marque à visualiser les noms existants les plus proches. Il faudra donc concevoir et développer des méthodes de visualisation des similitudes entre un nom de marque saisi par un utilisateur et les noms les plus proches, sous la forme d'une cartographie.

Parcours concerné : DIWEB, GL, I2A

Remarques (UE conseillées, langage…) : Conception et Développement des IHM

13. Pathfinding polygonal dans les environnements 3D

Frédéric Koriche

Résumé : La recherche de chemins dans les jeux vidéo est un problème fondamental ; en effet, une grande partie du CPU est utilisée pour déplacer des agents ou unités dans le jeu. L'objectif de ce projet est de construire un algorithme de recherche de chemins dans un environnement 3D. L'environnement est un paysage (donjon, prairie, etc.) composé de mailles et de textures. Le personnage à animer doit se déplacer d'un point à un autre de la surface du sol. Dans ce cadre, le projet se décompose en trois parties: "Navigation Mesh": Construction d'une partition polygonale de l'environnement: la structure obtenue est un graphe de poygones convexes permettant la recherche de chemins sans collision,  "Pathfinding": Choix et implémentation d'un algorithme de recherche de chemins à partir du graphe des polygones (A*, RTA*, ...), - "Smoothing": Lissage du chemin obtenu afin d'obtenir un rendu réaliste de l'animation du personnage.

Parcours concerné : I2A

Remarques (UE conseillées, langage…) : Algorithmique de l'IA, Programmation orientée agents, algorithmique géométrique

14. Algorithme min-max dans un jeu de stratégie tour-par-tour

Frédéric Koriche

Résumé : Les jeux de stratégie tour-par-tour (comme Civilisation) font intervenir deux aspects : l’économie et le combat. L’économie comprend plusieurs types d’objets : les ressources (ex: l'or, le temps), les bâtiments (ex : écurie), les unités (ex : explorateurs, guerriers). Les règles de l’économie sont spécifiées par un arbre de technologies ; par exemple, la construction d’une écurie requiert 150 pièces d’or, 5 unités de temps, et permet la création de chevaliers. Le combat intervient dès lors qu’au moins deux unités ennemies se rencontrent; l’issue de chaque unité est alors analysée en comparant son état (niveau, nombre, condition, position) avec celui de l’unité adverse. La différence essentielle entre un jeu tour-par-tour et un jeu temps réel réside dans le fait que le tour-par-tour laisse une période de réflexion à la machine et au joueur. L'objectif de ce projet est d'implémenter un algorithme de type Min-Max dans les jeux de stratégie tour-par-tour afin de prendre des décisions efficaces. Le projet se décompose en deux parties: - Jeu de stratégie tour-par-tour: construire un jeu de stratégie simple faisant intervenir une économie et des règles de combat entre unités. On pourra imaginer deux bases (ou villes) initiales: celle du joueur et celle de la machine. Les règles d'économie et de combat seront conçues par les auteurs du projet,  Min-max: implémenter l'algorithme min-max pour les décisions de la machine. Comme le tour-par-tour ne laisse qu'un temps de reflexion limité pour la machine, les auteurs seront amenés à analyser des heuristiques et méthodes de coupure.

Parcours concerné : I2A

Remarques (UE conseillées, langage…) : Algorithmique de l'IA, Programmation orientée agents

15. Evaluation de différentes implémentations de déduction à base de graphes

Michel Leclère

Résumé : De nombreux langages de modélisation (graphes conceptuels, RDFS, Topic Map, Modèles Entité-Association, diagrammes UML...) sont basés sur des représentation par graphes. La déduction sur cette famille de langages peut se faire par une opération d'homomorphisme de graphes (il s'agit de rechercher un pattern correspondant à un graphe source dans un graphe cible). L'objectif de ce TER est d'implanter et tester différents algorithmes de calcul de ces homomorphismes. On pourra au choix prototyper ces algorithmes dans un langage fonctionnel, les développer intégralement en Java (une reprise d'antériorité peut être faite sur ce langage) ou utiliser la bibliothèque Choco de résolution de problèmes de satisfaction de contraintes.

Parcours concerné : I2A

Remarques (UE conseillées, langage…) : Représentation des connaissances, Algorithmique de l'IA.

16. Un logiciel pour rechercher les cycles aromatiques d'une molécule

Philippe Vismara

Résumé : Il s'agit de concevoir un logiciel permettant de visualiser les cycles aromatiques d'une molécule. On dispose pour cela d'un algorithme basé notamment sur la recherche de cycles comportant une suite alternée d'arêtes (liaisons) simples ou doubles. Le logiciel s'appuiera sur des bibliothèques de traitement des graphes moléculaires écrites en Java, ainsi que sur des librairies d'affichage de graphes moléculaires. Un des enjeux consiste à concevoir un mode d'affichage pertinent des solutions.

Parcours concerné : CASAR, GL, I2A

Remarques (UE conseillées, langage…) : Programmation en Java, conception d'interfaces graphiques. Aucune connaissance en Chimie n'est nécessaire.

22. Modélisation et implémentation d'un robot joueur à JeuxDeMots

Mathieu Lafourcade

Résumé : concevoir un programme autonome (dit "bot") capable de jouer aussi correctement que possible à JeuxDeMots (http://www.lirmm.fr/jeuxdemots). Le bot a accès à la base de relations de JeuxDeMots, mais doit trouver des stratégies (évolutives) pour maximiser le nombre de points et sa position dans le classement. Le bot doit non seulement finir des parties proposées par les autres joueurs, mais aussi proposer des parties intéressantes (à la fois pour les autres joueurs, mais aussi pour la pertinence de la base de relations). Pour un aperçu de la base de relations voir http://www.lirmm.fr/jeuxdemots/rezo.php.

Parcours concerné : DIWEB, I2A

Remarques (UE conseillées, langage…) :

23. Modélisation et implémentation d'un jeu de type devinette à JeuxDeMots

Mathieu Lafourcade

Résumé : Le jeu de devinette est un jeu asymétrique ou le joueur A compose une devinette à partir d'un terme cible proposé par le système. Le joueur B doit lui trouvé le mot cible le plus rapidement possible au fur et à mesure de l'affichage des indices. La conception de la devinette ce fait à partir de shémas de fonctions lexicales à completer (par exemple : est produit par xxx, contient yyy, se trouve souvent avec zzz). Il faudra tenter de déterminer sur n parties quelles sont les indices pertienents, ceux-ci alimentant la base de relations de JeuxDeMots (http://www.lirmm.fr/jeuxdemots) avec des relations spécifiques pour lesquelles la lexicalisation est faible. Le jeu ne doit pas être aisément falsifiable (c'est-à-dire qu'il existe une stratégie pour que les joueurs gagnent qui ne soit pas pertienente pour la base).

Parcours concerné : DIWEB, I2A

Remarques (UE conseillées, langage…) :

24. Modélisation et implémentation de stratégies d'identification d'usage de termes devant être validé par les joueurs

Mathieu Lafourcade

Résumé : Il s'agit de concevoir un module pour JeuxDeMots (http://www.lirmm.fr/jeuxdemots) permettant à partir de la base de relations entre termes d'identifier les termes polysémiques ou ayant des usages multiples. Il est nécessaire de faire valider les hypothèse via l'activité des joueurs, mais sans pour autant leur demander directement. Les hypothèses validées induisent la création de nouveaux usages du termes qui sont introduits dans la base de relations. Des hypothèses qui s'avèrerait finalement fausses peuvent conduire à une opération de fusion de sens. On pensera à une approche de type "hystéresis" afin que le système ne soit pas amené à séparer et fusionner en boucle un même terme. Pour un aperçu de la base de relations voir http://www.lirmm.fr/jeuxdemots/rezo.php.

Parcours concerné : DIWEB, I2A

Remarques (UE conseillées, langage…) :

25. Calcul de vecteurs conceptuels à partir d'un réseau lexical étiqueté pondéré

Mathieu Lafourcade

Résumé : Pour chaque terme et sens du réseau de JeuxDeMots (http://www.lirmm.fr/jeuxdemots et http://www.lirmm.fr/jeuxdemots/rezo.php), on souhaite calculer de façon itérative un vecteur conceptuel. Pour le vecteur d'un noeud donné du réseau, son calcul se fait comme une fonction des vecteurs des termes auxquels ce noeud est relié (les relations étant orientées, étiquetées et pondérées). Si aucun vecteur n'est disponible pour un noueud voisin, ce dernier est tiré au hasard. Une opération de séparation (sur la base d'un modèle de particules se repoussant via une force en 1/d**2) est ensuite appliqué de façon à "écarter" les vecteurs accidentellement proches. Il s'agira de modéliser précisément ce modèle et de l'expérimenter en grandeur réelle.

Parcours concerné : DIWEB, I2A

Remarques (UE conseillées, langage…) :

31. Fouille de données floue : règles séquentielles

Anne Laurent et Maguelonne Teisseire

Résumé : La fouille de données vise à extraire de manière la plus efficace possible des règles pertinentes à partir de bases de données volumineuses. Cette discipline connaît de très nombreuses applications, notamment dans le domaine marketing ou pour l'analyse du comportement utilisateur (sites web par exemple). Typiquement, les règles trouvées sur les sites marchands du type « les internautes ayant été intéressés par cet article ont également regardé tel et tel autre produit » permettent de guider les clients tout en optimisant le rendement des sociétés commerciales. Cependant, les comportements trouvés dans la vie réelle sont rarement « blancs ou noirs », et on se trouve par exemple souvent confrontés à des cas où un internaute a par exemple été « plutôt intéressé ». La modélisation de ces comportements intermédiaires est alors assez facilement représentable en utilisant la théorie des sous-ensembles flous, qui a déjà été appliquée pour la recherche de règles. Dans ce TER, nous visons à étendre ces méthodes au contexte des règles séquentielles où la relation de causalité est accompagnée par une relation temporelle. Par exemple, on étudiera les règles du type « les internautes ayant été plutôt intéressés par cet article ont plus tard été très intéressés par tel autre ». Cette extension s'effectuera en utilisant les implications floues. Il sera également possible de réfléchir à la recherche de règles graduelles permettant de rendre compte d'une influence positive ou négative continue d'un attribut sur un autre, pour par exemple exhiber des règles du type : « plus les internautes ont été intéressés par ce produit, plus/moins ils ont été intéressés par tel autre ».

Parcours concerné : DIWEB, GL, I2A

Remarques (UE conseillées, langage…) : BD, Programmation

32. Fouille de données médicales basée sur une ontologie

Paola Salle et Sandra Bringay

Résumé : La fouille de données médicales s'avère complexe et difficile. En effet, ces données sont particulières car hétérogènes, imprécises et complexes. Dans ce contexte, la fouille de données classique donne des résultats imprécis et en trop grande quantité. L'objectif de ce TER est de mettre en oeuvre une méthode d'extraction de connaissances qui soit pertinente et adaptée aux utilisateurs experts de ce domaine. De façon plus précise, il s'agit de mettre en œuvre un algorithme proposé au sein de notre équipe de recherche mettant en correspondance les informations d'une ontologie de référence et les données médicales réelles. Il s'agira de réaliser des évaluations aussi bien en terme de performance qu'en terme de qualité.

Parcours concerné : DIWEB, GL, I2A

Remarques (UE conseillées, langage…) : BD, Programmation

33. Segmentation de noms de propriétés

Clémentine Nebut, Mathieu Lafourcade, Jean-Rémy Falleri et Xavier Dolques

Résumé : La plate-forme Galatea est développée au sein de l'équipe D'OC, dans le cadre d'un contrat de recherche avec France Telecom. Elle permet d'analyser et de restructurer des modèles de conception ou du code source de logiciels (UML, Ecore, Java). Une extension de cette plate-forme a été développée pour permettre l'analyse et la restructuration d'ontologies au format OWL. L'analyse effectuée par Galatea est pour le moment uniquement basée sur la structure des modèles. Nous souhaitons l'étendre en utilisant des techniques de traitement du langage pour améliorer les résultats.

Parcours concerné : GL, I2A

Remarques (UE conseillées, langage…) : Traitement Automatique du Langage, Ingénierie des Modèles, OWL, Re-structuration, Refactoring, Java, Eclipse, Wordnet