TER de semestre 2 de
Master (année 2006-07)
Mention : Informatique,
Mathématiques, Statistiques
Spécialité : Informatique
professionnelle (IUP) et Recherche en Informatique
Liste des sujets
Liste des
sujets et des encadrants et des inscrits. Sauf contre-indication explicite,
les encadrants sont au LIRMM. Une présentation plus ou moins détaillée des
sujets est donnée par un
clic sur les noms
des sujets ci-dessous.
Pour plus de détails, contactez les encadrants. Les spécialités (et parfois
modules) de master correspondants au sujet du stage sont indiqués.
Résumé : Le sac à dos est un problème NP-complet mais qui possède une structure très intéressante, permettant de développer des algorithmes très efficace en terme d'approximation (programme dynamique,ptas, ftpas,...). Le but est étudier de façon théorique et pratique ce problème.
Parcours concerné : ACR
Remarques (UE conseillées, langage…)
: au moins 1 UE
parmi
Algorithmique (UMIN111), Complexité/Calculabilité (UMIN112),
Résolution de problèmes NP-difficile (UMIN207)
Résumé : Les problèmes d'ordonnancement font parties des problèmes fondamentaux en informatique. Ici nous allons proposer plusieurs stratégies pour tenter de résoudre au mieux divers problèmes.
Parcours concernés : ASR, ACR
Remarques (UE conseillées, langage…)
: au moins 1 UE
parmi
Algorithmique (UMIN111), Complexité/Calculabilité (UMIN112),
Résolution de problèmes NP-difficile (UMIN207)
Résumé : Les problèmes de flots ont été très largement étudiés dans les réseaux. Nous allons nous intéresser au cas où l'on prend en compte la notion de temps sur les arcs. Le but de ce stage est de mesurer l'impact de l'introduction du temps sur les résultats connus sur les flots.
Parcours concernés : ACR, ASR
Remarques (UE conseillées, langage…)
:
Algorithmique (UMIN111)
Résumé : La méthode du simplexe est une méthode très utilisée dans l'industrie afin d'obtenir la solution optimale d'un problème modéliser par un programme linéaire. Le but est de développer une application de visualisation en 2D et 3D de la succession des étapes issues de la méthode du simplexe afin de voir le déplacement sur l'enveloppe convexe des solutions intermédiaires.
Parcours concernés : TOIL
Remarques (UE conseillées, langage…) : Etre bon en programmation
Roland Ducournau, Floréal Morandat
Résumé : L'objectif de ce stage est la réalisation d'un générateur d'analyseur syntaxique et lexical en PRM exploitant les nouveaux concepts proposés par ce langage.
Parcours concernés : TOIL,CODA
Remarques (UE conseillées, langage…) : Analyse syntaxique (UMIN123), Evaluation des langages (UMIN121), Génération de code (UMIN122), Langages objets à typage statique (UMIN202)
Ehoud Ahronovitz, Clément Saad
Résumé : La simulation d'algorithmes de routage associés à BGP, permettant de résoudre des oscillations. L'objectif de ce stage est de valider nos algorithmes en les implémentant dans le simulateur, réaliser plusieurs simulations sur des topologies réalistes, apporter des corrections et analyser les résultats.
Parcours concernés : ASR, ACR
Remarques (UE conseillées, langage…) : Réseaux et communication (UMIN131), Service et qualité des réseaux (UMIN214)
Eric Bourreau, Guillaume Verger
Résumé : Ce TER se propose de comprendre, coder et expérimenter un algorithme novateur et très performant servant de socle à plusieurs modules de Programmation Par Contraintes
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111), Résolution de problèmes NP-difficile (UMIN207), Introduction à l'IA (UMIN203)
Résumé : Ce TER se propose de réunir la Programmation Par Contraintes et la Planification de Taches, deux domaines importants de l'Intelligence Artificielle.
Parcours concernés : CODA
Remarques (UE conseillées, langage…) : Introduction à l'IA (UMIN203)
Résumé : L'objectif de ce TER est de concevoir un moteur de recherche de blogs par similarité.
Parcours concernés : IICW, IDI, CODA, TOIL
Remarques (UE conseillées, langage…)
: Connaissances de JAVA et XML
Résumé : Le logiciel SYGMART permet de faire des analyses syntaxiques de très bonne qualité. Votre travail consistera à combler une grande lacune actuelle d'OpenOffice en réalisant un plugin pour OpenOffice qui utilisera le système SYGMART pour vérifier si des phrases sont bien construites.
Parcours concernés : IICW, IDI, CODA, TOIL
Remarques (UE conseillées, langage…) : TALN 1 (UMIN206)
Résumé : L'histoire de l'évolution des organismes est représentée par un arbre dont les feuilles sont étiquetées par les noms des espèces actuelles. On dispose souvent non pas d’un seul arbre mais d’un ensemble d’arbres. L’objectif de ce stage est de développer un outil de visualisation basé sur le Multi Dimensionnal Scaling qui permettra d’avoir une vue globale de cet ensemble d’arbres. Chaque arbre sera alors représenté par un point sur une « carte 2D», et cela en respectant autant que possible les distances entre les arbres associés aux différents points.
Parcours concernés :
TOIL, IDI, ACR, CODA, IICW
Remarques (UE conseillées, langage) : Conception et développement des IHM (UMIN209), Algorithmique (UMIN111), Galaxie XML (UMIN212)
Cécile Bonnard et Vincent Berry
Résumé : Un arbre phylogénétique représente les relations d’évolution entre différentes espèces. La méthode du consensus multipolaire permet de construire plusieurs arbres à partir d'un ensemble de données biologiques. Cette méthode correspond à une recherche de cliques maximales recouvrantes dans un graphe représentant l’information dispensée par la collection d’arbres, mais souffre néanmoins de quelques inconvénients. L'objectif de ce TER est d'améliorer cette méthode en introduisant une optimisation conjointe du nombre d'arbres et de la pertinence du consensus vis-à-vis des données.
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111)
Résumé : L’objectif de ce stage est de faire un état de l’art clair et concis des turbo-codes et d’implémenter un codeur-décodeur de turbo-codes. Une grande partie du travail effectué pour ce stage sera consacré à la compréhension de la théorie des codes correcteurs et en particulier des turbo-codes.
Parcours concernés : ACR, CODA
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111), Théorie de l’information (UMIN211), Architectures réseaux et couches basses (UMSIE250)
- Etude et réalisation d'un système Maître(s)-Esclaves de partage de charge
Anne-Elisabeth Baert et Vincent Boudet
Résumé : Le but de ce TER est de concevoir une application générique d'un système Maître(s)-Esclaves de partage de charges. Après une étude de différents protocoles, les étudiants devront implémenter une application distribuée et s'en servir pour comparer différentes politiques selon des critères définis.
Parcours concernés : ASR
Remarques (UE conseillées, langage…) : Réseaux et Communication (UMIN131), Service et Qualité des Réseaux (UMIN214)
- Sur le problème du MINVAR
Anne-Elisabeth Baert et Vincent Boudet
Résumé : Ce projet consiste en l'étude bibliographique de bibliothèques multiprécisions et en l'implémentation d'heuristiques. Le problème MINVAR porte sur la minimisation d'une fonction objective sur des graphes bipartis.
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111)
- Réalisation d'un simulateur de partage de charge dans un réseau pair-à-pair
Anne-Elisabeth Baert et Vincent Boudet
Résumé : Un réseau pair-à-pair peut-être modélisé par un graphe où les noeuds sont en même temps maître et esclaves. Le but du TER est d'étudier par simulation la répartition des charges de travail en fonction des protocoles implémentés.
Parcours concernés : ASR, ACR
Remarques (UE conseillées, langage…) : Réseaux et Communication (UMIN131), Service et Qualité des Réseaux (UMIN214)
- Etude de propriétés de graphes aléatoires
Anne-Elisabeth Baert et Vincent Boudet
Résumé : La topologie des réseaux pair-à-pair est non prédictible. C'est pourquoi, on utilise fréquemment des graphes aléatoires pour les modéliser. Le but de ce TER est d'implémenter différents générateurs de graphes aléatoires et d'en étudier les propriétés (degré moyen, diamètre...).
Parcours concernés : ASR, ACR
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111), Modèles Aléatoires (UMIN210)
Résumé : Programmer un interprète LOGO
Parcours concernés : TOIL, IDI, CODA
Remarques (UE conseillées, langage…) : Analyse syntaxique (UMIN123), Génération de code (UMIN122)
Résumé : Programmer un éditeur XML.
Parcours concernés : TOIL, IDI, CODA
Remarques (UE conseillées, langage…) : Analyse syntaxique (UMIN123), Génération de code (UMIN122)
Jean-Claude Konig et Clément Saad
Résumé : L'équipe APR en collaboration avec l'université d'Avignon a développé un ensemble de stratégies de positionnement dans des réseaux dont seul certains noeuds, appelés ancres, possèdent un système de positionnement précis. Les autres noeuds se positionnent à l'aide d'échange d'informations avec les "ancres". Le but du TER est de simuler (et/ou expérimenter sur une plateforme réelle de capteurs sur le campus Triolet, laboratoire IES) ces stratégies et éventuellement des techniques de routage à déterminer.
Parcours concernés : ASR, ACR
Remarques (UE conseillées, langage…) : Réseaux et Communication (UMIN131), Service et Qualité des Réseaux (UMIN214)
- Outil de gestion de l'offre de formation du département informatique
Résumé : Il s'agit d'analyser et réaliser un outil de gestion administrative (en ligne) des UE du département informatique. L'objectif étant de permettre au responsable de l'UE de gérer les intervenants et les interventions d'une UE proposée par le département.
Parcours concernés : TOIL
Remarques (UE conseillées, langage…) : PYTHON, Postgres (SGBD), Apache
Stéphane Bessy et Stéphan Thomassé
Résumé : Le problème du 'Road Coloring', étudié depuis 1970, peut se résumer de la façon suivante: étant donné un graphe orienté dont chaque sommet est début d'un arc rouge et d'un arc bleu, existe t-il un sommet cible x et une suite d'instructions du type ('prendre l'arc rouge', 'prendre l'arc rouge ', 'prendre l'arc rouge'...) telle que si on l'applique à n'importe quel sommet du graphe, on arrive en x ? Le but de ce TER est d'implémenter les cas de résolutions existants et de faire un état de l'art du sujet.
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (bonne maîtrise) et éventuellement Calculabilité-complexité
Stéphane Bessy et Stéphan Thomassé
Résumé : Introduit par Conway en 1996, ce jeu se joue sur la grille et oppose un joueur (Ange) qui se déplace à chaque tour, à un autre joueur (Démon) qui supprime des cases de la grille. Plusieurs solutions ont été très récemment trouvées. Le but de ce TER est d'implémenter les stratégies existantes et de faire un état de l'art du sujet.
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (bonne maîtrise) et éventuellement Calculabilité-complexité
Résumé : Les Java beans sont des composants assemblables interactivement et graphiquement, selon un protocole écouteur/écouté, pour permettre soit à des non spécialistes de programmation de produire de véritables applications sans écrire de code soit à des spécialistes de développer du code plus rapidement. Le projet consiste en l'implantation dans la version de votre choix du langage Smalltalk (Squeak par exemple) d'un modèle de composant identique à celui des "java-beans" et d'un environnement d'assemblage directement inspiré des environnements d'assemblage pour Java Beans comme l'environnement netbeans.
Parcours concernés : TOIL
Remarques (UE conseillées, langage…) : Langages applicatifs
Abdelkader Gouaïch, Cheddy Raïssi, Marc Plantevit
Résumé : L'objectif de ce TER est de mettre en oeuvre un ensemble de techniques permettant la détection d'attaques sur des serveurs HTTP en conjuguant des approches de fouilles de données, d'apprentissage symbolique couplées à des ontologies.
Parcours concernés : CODA, IICW, ASR
Remarques (UE conseillées, langage…) : C/C++/Java, Analyse Syntaxique (UMIN123), Introduction à l’IA (UMIN203)
Abdelkader Gouaïch et Lylia Abrouk
Résumé : RAS est un outil d’annotation de documents basée sur une approche de propagation des annotations des documents références. L’objectif du travail est de sélectionner une base de documents déjà annotés qui serviront de base pour la propagation des annotations. Plusieurs techniques seront utilisées afin d’effectuer cette première annotation : calcul de la similarité avec le document citant, calcul de l’importance des citations (par exemple les documents qui sont le plus cités)...
Parcours concernés : CODA, IICW
Remarques (UE conseillées, langage…) : Python, PhP, MySQL, Introduction à l’IA, Semantic Web
Pascal Dugénie et Philippe Lemoisson
Résumé :
Parcours concernés :
Remarques (UE conseillées, langage…) :
Pascal Dugénie et Philippe Lemoisson
Résumé :
Parcours concernés :
Remarques (UE conseillées, langage…) :
Résumé : Les textes en ancien français constituent des corpus de textes très volumineux que les experts ont du mal à explorer manuellement. Dans ce contexte, il est intéressant de leur proposer des outils automatiques capables de retrouver des motifs pertinents. Un premier outil a déjà été implémenté afin d'étiqueter les textes en ancien français et de retrouver la terminologie (ensemble des termes utilisés). D'autre part, des outils capables de retrouver des motifs à l'intérieur de données textuelles existent. Il s'agira donc d'étudier la compatibilité de ces outils face aux textes en ancien français et de les adapter et les étendre afin de fournir aux experts littéraires des outils faciles à utiliser pour extraire de leurs textes des motifs intéressants.
Parcours concernés : IDI, CODA, IICW
Remarques (UE conseillées, langage…) : Bases de données (UMIN132), TALN (UMIN206)
Maguelonne Teisseire et Federico Del Razo Lopez
Résumé : Actuellement XML est devenu le standard pour l'échange, le stockage et la diffusion de données. Une des caractéristiques principales de ces données est l'hétérogénéité. Les données sous le format XML sont représentées par des arbres ordonnés qui constituent des "bases de données arborescentes" (BDA). Au sein de notre équipe nous avons appliqué les techniques de fouille de données transactionnelles sur des BDA pour réaliser l'extraction de structures arborescentes fréquentes maximales. Dans un premier temps, nous proposons l'application et l'optimisation de nos algorithmes sur des données XML réelles (plus spécifiquement sur des collections de données INEX- Initiative for the Evaluation of XML Retrieval). Dans un second temps, il s'agit de construire un schéma médiateur à partir des résultats obtenus.
Parcours concernés : IDI, CODA, IICW
Remarques (UE conseillées, langage…) :
Résumé : On souhaite mettre au point un outil visuel et interactif permettant de manipuler à la souris différentes structures qui sont reliées entres elles. La modification d'une structure doit entraîner la mise à jour en temps réel des autres structures. Nous voulons que cet outil permettent l'intégration ultérieure de structures supplémentaires.
Parcours concernés : ACR, CODA, IICW, TOIL, IDI
Remarques (UE conseillées, langage…) : conception objet, programmation, interface graphique
Benoit Darties et Sylvain Durand
Résumé : Afin de fournir un accès haut débit en milieu "rural", nous cherchons à satisfaire les demandes de noeuds "clients" à partir de noeuds "sources". Les communications se font en utilisant des technologies sans fil, soit directement, soit en utilisant des noeuds relais. Ce problème se modélise naturellement comme un problème de flot. Ce problème a déjà été résolu en utilisant des techniques de programmation linéraire. L'objectif de ce TER est de le résoudre en utilisant une méthode exacte de type Branch & Bound.
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111), Résolution de problèmes NP-difficile (UMIN207), goût pour la programmation
Alain Jean-Marie, Ehoud Ahronovitz, Eric Alemany
Résumé : Le stage comporte deux volets: d'une part l'étude des protocoles de synchronisation des horloges en réseau; et d'autre part les réseaux CPL: Courants Porteurs en Ligne. L'objectif final est la combinaison de ces deux volets.
Parcours concernés : ASR
Remarques (UE conseillées, langage…) : réseaux et communication (UMIN131), Service et qualité des réseaux (UMIN214), Architectures réseaux et couches basses(UMSIE250)
Résumé : Le mur-écran est une surface d'affichage composée d'une part d'un mur d'image (un ou plusieurs grands écrans de quelques m2 sur lesquels sont projetées des informations de toutes sortes issues d’un ou plusieurs ordinateurs) et d'un écran traditionnel (portable, ou machine de bureau classique. L'objectif du TER est d'étudier les systèmes actuels en termes de compatibilité avec les surfaces, résolution, coût, ergonomie, robustesse, ...En s'appuyant sur cette étude, il s'agira de faire une étude de faisabilité et un cahier des charges pour la production d'outil de pointage plus performant. Si le temps le permet, il s'agira de participer avec des électroniciens à la réalisation d'un prototype de système de pointage ultrasonore
Parcours concernés : ACR, TOIL, IDI, IICW
Remarques (UE conseillées, langage…) : Conception et développement en Java, Interface Homme-Machine (UMIN209), Visualisation d'information
Résumé : Les techniques de visualisation orientées pixel constituent une manière de représenter de grandes quantités de données multidimensionnelles. Leur principal objectif est d’offrir des vues d’ensemble à des fins d’exploration. Elles permettent de détecter des tendances, des régularités, des corrélations ou même éventuellement des erreurs dans les données. On étudiera, implémentera et appliquera ces techniques aux statistiques de fréquentation des modules par les étudiants de l'UM2.
Parcours concernés : ACR, TOIL, IDI, IICW
Remarques (UE conseillées, langage…) : Conception et développement en Java, Interface Homme-Machine (UMIN209), Visualisation d'information
Résumé : L’environnement ECLIPSE est un environnement de développement ouvert, facilement extensible par des plugins. Il existe en particulier des plugins concernant les formalismes de modélisation et de spécification EMF, et les plugins de spécification et de génération d’interfaces graphiques GMF. Ces plugins permettent entre autre de faire générer d’autres plugins pour Eclipse directement à partir de leur spécification formelle. Dans le cadre d'un projet entre le LIRMM et l’Institut National de l’Audiovisuel, on vous propose de développer pour Eclipse, au moyen de EMF / GMF un plugin spécifique pour faciliter l’édition et la gestion de base de règles de transformation.
Parcours concernés : TOIL, IDI, IICW
Remarques (UE conseillées, langage…) : Java, XML, Environnement : Eclipse
Résumé : On s'intéresse aux pavages, c'est à dire aux manières de couvrir un ensemble avec des copies d'un de ses sous-ensembles. Dans ce projet, pour un entier n on étudie les pavages de l'intervalle d'entiers [0,n]. L'objet du stage est triple : implémenter un algorithme de reconnaissance d'un sous-ensemble qui pave [0,n], de concevoir un algorithme de visualisation du pavage, et d'étudier les sous-ensembles pavant lorsqu'on rend [0,n] circulaire.
Parcours concernés : ACR
Remarques (UE conseillées, langage…) : Algorithmique (UMIN111)
Résumé :
Parcours concernés : TOIL, CODA
Remarques (UE conseillées, langage…) : programmation par objets, développement par composants, génie logiciel objet
Résumé :
Parcours concernés : TOIL, CODA, IDI
Remarques (UE conseillées, langage…) : interprétation et compilation de langages, programmation par objets concurrents, interface graphique, conception et développement des IHM, agents
Résumé :
Parcours concernés : TOIL, CODA, IDI
Remarques (UE conseillées, langage…) : programmation par objets concurrents, interface graphique, conception et développement des IHM, musique, agents
Résumé : L'objectif de ce stage est la réalisation d'un environnement sur le web mettant les utilisateur à contribution sous forme de jeux pour la collecte d'informations lexicales (en particulier de collocations). Quelques agents logiciels seront également conçus afin d'alimenter en parallèle la base de données lexicale. (nb : aucune expertise particulière n'est nécessaire en TALN)
Parcours concernés : IICW, IDI, CODA, TOILI
Remarques (UE conseillées, langage…) : connaissances de PHP, MySQL