TER de semestre 2 de
Master (année 2005-06)
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.
-
Algorithmes Exponentiels exacts
Groupe :
4places
disponibles
Résumé
: Obtenir une solution exacte à un
problème NP-difficile peut s'avérer important.
Pour cela, le "prix à payer" est d'accepter une complexité exponentielle pour
l'algorithme de résolution. Comme pour tout algorithme, sa complexité peut
être plus ou moins optimisé. Le but de se projet est de s'intéresser aux
différentes méthodes existantes pour des problèmes de graphes classiques tels
l'ensemble dominant minimum ou la couverture minimum et de comparer leur
efficacité.
Spécialités concernées : ACR
Remarques (modules conseillés, langage…)
:
Algorithmique (UMIN111), Résolution de problèmes
NP-difficile (UMIN207)
-
Conception d'outils
pour des machines de Turing
Groupe :
4 places
disponibles
Résumé : Les machines de Turing ont
plusieurs domaines d'utilisation : étude de fonctions, de langages, déterminer
si un problème est décidable... L'objectif de ce TER est de construire des
machines de Turing élémentaires et de réaliser une interface pour que
l'utilisateur puisse concevoir une machine pour son problème.
Spécialités concernées : TOIL, CODA
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Résumé :
Etude et réalisation d’un Schéma XML pour la
représentation de fichiers d’accords. Développement d’un éditeur de saisie
paramétré pour ce schéma, de transformateurs paramétrés XSLT de formats
d’éditions de sortie, d’éditeurs d’impression et de visualisation, de
transcodeurs vers d’autres formats (XML ou non).
Spécialités concernées : IDI, IICW
Remarques (modules conseillés, langage)
: Galaxie XML (UMIN212) REQUIS
Groupe :
4 places
disponibles
Résumé :
Réalisation de représentations spatiales des
accords de musique en temps réel : visualisation simultanée à l’écoute d’un
arrangement de ces accords.
Spécialités concernées : IDI, IICW
Remarques (modules conseillés, langage)
: algo géométrique (UMIN215), traitement du signal
et de l'image, conception et développement des IHM (UMIN209)
-
Participation au défi fouille de texte
Groupe :
4 places
disponibles
Résumé : Comme l'an passé, l'équpe
TAL du lirmm va participer au défi fouille de
texte. L'objectif de ce défit n'est pas encore précisé, mais il s'agira : soit
de segmenter un texte en paragraphe sémantiquement homogène, soit de
rechercher une partie sémantiquement différente, plongée à l'intérieur d'un
texte. Le but de ce TER consistera à réaliser des évaluations à partir des
algorithmes utilisés dans l'équipe et ainsi de sélectionner la meilleure
approche possible pour participer au défi. Ce travail nécessitera une partie
programmation en QT (C++) ou java avec une préférence pour
QT.
Spécialités concernées : IDI
Remarques (modules conseillés, langage)
: TALN niveau 1 (UMIN
206), base de données (UMIN132), réseaux
et communication (UMIN133), Service et qualité des
réseaux(UMIN214).
Groupe :
4 places
disponibles
Denis Bertrand et Alexis
Criscuolo
Résumé : Une des branches les plus
importantes en bioinformatique est la représentation de l'histoire évolutive
du vivant sous forme d'arbre (ou phylogénie) à partir d'un unique gène. Une
méthode simple consiste à calculer la distance évolutive entre chaque paire
d'espèces puis d'y appliquer un algorithme de construction d'arbre. Durant ce
stage, ces techniques classiques d'inférence d'arbres phylogénétiques seront
adaptées au cas de plusieurs matrices de distance correspondant à une
collection de gènes.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111)
Groupe :
4 places
disponibles
Denis Bertrand et Alexis
Criscuolo
Résumé : Un arbre phylogénétique est un
arbre (i.e. graphe connexe sans cycle) qui ne contient pas de noeud de degré
2. Les noeuds externes (i.e. de degré 1) sont appelés feuilles. Etant donnée
une collection C de k > 2 arbres phylogénétiques, le problème MAST consiste à
rechercher le plus grand sous-arbre commun aux
arbres dans C. Durant ce stage, un algorithme pour résoudre le problème MAST
sera développé en se basant sur les propriétés de certaines feuilles composant
les arbres de C.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111)
Groupe :
4 places
disponibles
Denis Bertrand et Alexis
Criscuolo
Résumé : Un arbre phylogénétique est un
arbre (i.e. graphe connexe sans cycle) qui ne contient pas de noeud de degré
2. Les noeuds externes (i.e. de degré 1) sont appelés feuilles. Etant donnée
une collection C de k > 2 arbres phylogénétiques, le
superarbre est un arbre représentant le plus fidèlement possible la
structure des arbres dans C. Le but de ce stage consiste à implémenter deux
algorithmes de construction de superarbre puis
d'en améliorer les performances en utilisant la longueur des branches des
arbres de C.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111)
Groupe :
4 places
disponibles
Denis Bertrand et Alexis
Criscuolo
Résumé : Une signature génomique est une
représentation graphique de l'information structurale d'un génome. Sa
structure fractale fractale permet d'identifier de
manière unique une espèce à partir de son génome. Le premier but de ce stage
est l'implémentation d'un logiciel de représentation graphique des signatures
génomiques. Son deuxième but est la construction d'arbres de l'évolution à
partir de signatures génomiques.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111)
Groupe :
4 places
disponibles
Résumé : Pour ce stage, nous proposerons
plusieurs stratégies d'ordonnancement et nous utiliserons des algorithmes de
recherche locale pour améliorer les solutions.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: rapport en Latex
Groupe :
4 places
disponibles
Résumé : Le but de TER est d'étudier dans
un premier temps, les divers approches théoriques (algorithmes approchés, les
schémas polynomiaux, les schémas totalement
polynômiaux )
pour résoudre ce problème. Dans un second temps, il vous sera demandé une
étude pratique pour mesurer la qualité des divers
solutions proposées par les diverses méthodes vues dans la première partie.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Résolution de problèmes NP-difficiles (UMIN207)
fortement conseillé, rapport en Latex
-
Construction de « benchmark » de bases de
connaissances à partir de textes
Groupe :
4 places
disponibles
Mathieu
Lafourcade et Michel Leclère
Résumé : On cherche à construire des
bases de connaissances expérimentales à partir d’outils d’analyse de textes et
d’encyclopédies. On dispose de prototypes de construction de réseaux
sémantiques entre termes trouvés dans un corpus encyclopédique et d’outils
d’analyse de textes. On cherche à compléter la chaîne par un outil de
transformation du réseau trouvé en une ontologie « graphes conceptuelles » et
un outil de transformation du résultat de l’analyse d’une phrase en un
« graphe conceptuel ».
Spécialités concernées : IDI, IICW
Remarques (modules conseillés, langage)
: Introduction à l’IA (UMIN203), TALN Niveau 1
(UMIN206),Galaxie XML (UMIN212)
Groupe :
4 places
disponibles
Michel Leclère et
Rallou Thomopoulos
Résumé : On souhaite étendre un outil de
représentation des connaissances existant pour permettre l'expression
d'informations imprécises ou incertaines. Plus précisément, le formalisme de
représentation des connaissances considéré est le modèle des graphes
conceptuels. L'outil utilisé est l'interface CoGUI,
qui fait appel à la bibliothèque de classes CoGITaNT. Les informations
imprécises ou incertaines sont exprimées en utilisant des ensembles flous.
L'objectif de ce TER est de permettre le dessin de ces ensembles flous dans
CoGUI et d'étendre l’algorithme de projection de
CoGITaNT pour permettre la prise en compte de ces
ensembles.
Spécialités concernées : TOIL, CODA
Remarques (modules conseillés, langage)
: Introduction à l’IA (UMIN203), Conception et
développement des IHM (UMIN209)
-
Expérimentation d’algorithmes de test d’inclusion
de requêtes conjonctives
Groupe :
4 places
disponibles
Michel Leclère et
Marie-Laure Mugnier
Résumé : Les requêtes conjonctives
peuvent être vues comme des conjonctions de littéraux positifs et négatifs ou
comme la conjonction de relations n-aires (ou de
négation de relations n-aires) dans la partie
WHERE d’une requête SQL. Le test d’inclusion de requêtes consiste à vérifier
si quelque soit la base de données considérée, les réponses à une requête Q1
sont incluses dans les réponses à une requête Q2.
L’objectif de ce TER est d’implanter et d’évaluer différents algorithmes
d’inclusion de requêtes.
Spécialités concernées : TOIL, CODA, ACR
Remarques (modules conseillés, langage)
: Introduction à l’IA (UMIN203), Algorithmique
(UMIN111)
-
Réalisation d’une interface graphique de
construction de base de connaissances
Groupe :
4 places
disponibles
Résumé : On dispose d’une plateforme de
manipulation de bases de connaissances représentées en graphes conceptuels et
d’une interface graphique permettant de définir des interactions avec cette
base de connaissances. On voudrait définir plusieurs fonctionnalités
d’interactions avec cette base : (1) la construction de hiérarchies de termes
(ontologie) permettant de définir un ensembles de primitives de modélisation,
(2) la construction de graphes conceptuels sur un vocabulaire donné permettant
d’indexer des documents, (3) la construction et la mise en œuvre de requêtes
sur une base de connaissances. L’interface graphique est développée en Java et
communique par une relation client/serveur avec la base de connaissances qui
est développée en C++. Les échanges sont faits en XML.
Spécialités concernées : TOIL, IDI, CODA
Remarques (modules conseillés, langage)
: Introduction à l’IA (UMIN203), Conception et
développement des IHM (UMIN209), Galaxie XML (UMIN212)
-
Réalisation d’un itérateur
de projection
Groupe :
4 places
disponibles
Résumé : CoGITAnT
est une plateforme de manipulation de graphes conceptuels développée en C++ et
disponible sur
http://cogitant.sourceforge.net. Elle dispose d’une méthode de recherche
d’un « sous-graphe motif G » dans un autre graphe
H appelé la projection. Cette opération est réalisée par un algorithme de « backtrack »
qui explore « en profondeur » un arbre de recherche à la recherche des
différents sous-graphes de H « correspondant » à
G. Son implémentation actuelle permet de s’arrêter dès que l’on trouve un
sous-graphe ou lorsqu’on les a tous. On
souhaiterait disposer d’une fonctionnalité « d’itérateur
de projections » permettant au premier appel à la méthode d’obtenir le premier
sous-graphe, puis à chaque appel successif
d’obtenir les sous-graphes suivants.
Spécialités concernées : TOIL, CODA, ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111), Introduction à l’IA
(UMIN203)
Groupe :
4 places
disponibles
Résumé
: MadKit est une plate-forme de développement de
systèmes multiagents fonctionnant en Java. Il
s'agit d'améliorer le Chat de MadKit en liaison
avec le logiciel de partage de documents (Share)
de manière à en faire un logiciel complet de causerie simultané et de partage
de documents permettant de créer un petit réseau personnel de messagerie
instantané.
Spécialités concernées : TOIL, CODA
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Résumé
:
MadKit
est une plate-forme de développement de systèmes
multiagents fonctionnant en Java.
Le sujet porte la réalisation de la chaîne complète de
gestion des plugins, allant de création de
plate-forme spécifiques ou de plugins associés à
ces plate-formes, jusqu'au téléchargement de ces
plate-formes et plugins.
Elle passe par la modification du site MadKit pour
en faire un site permettant à des utilisateurs de créer leurs propres pages
pour décrire leusr application, d'ajouter et de
gérer des ressources de type plate-forme spécifique ou
plugins.
Spécialités concernées : TOIL, CODA
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Jacques
Ferbe, Jean-François Pons, Richard
Terrat
Résumé : Ce projet consiste à réaliser un
atelier multiagent musical sous
MadKit. On utilisera une adaptation de
l'environnement Warbot que l'on adaptera à la
réalisation de systèmes musicaux évolutifs.
Spécialités concernées : TOIL, IDI
Remarques (modules conseillés,
langage)
: Savoir (bien) programmer en Java, connaître (un peu) le principe de la norme
Midi dans les systèmes d'informatique musicale, aimer les systèmes à base
d'agents, aimer la musique et notamment la musique informatique.
-
Partitionnement
d'un graphe orienté en chemins
Groupe :
4 places
disponibles
Résumé : Un problème classique en
algorithmique de graphes est de chercher dans un graphe (orienté ou non) un
chemin qui passe une et une seule fois par tous les sommets du graphe
(typiquement, on cherche à visiter tous les sites d'un réseau en parcourant
celui-ci suivant ses liens et en ne repassant pas deux fois au même endroit).
Cependant, suivant le graphe de départ, un tel chemin n'existe pas forcément.
Une variante du problème est de déterminer, pour un graphe donné, un nombre
minimal de chemin (et plus forcément un seul) qui partitionne le graphe. Pour
les graphes orientés, un algorithme récursif construisant une partition en
chemins du graphe (en fonction d'un de ses paramètres) est connu depuis une
quarantaine d'année. Récemment, une version itérative de cet algorithme a été
proposée. Le but du TER est de comprendre le fonctionnement de ces
algorithmes, d'assurer la validité de la version itérative et de l'implémenter
dans un langage à déterminer.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111), Résolution de problèmes
NP-difficile (UMIN207)
Groupe :
4 places
disponibles
Mathieu Roche et
Violaine Prince
Résumé : Le but du stage est de concevoir
une interface permettant de normaliser des corpus textuels issus de sources
très différentes qui nécessitent divers prétraitements.
Spécialités concernées : IDI, IICW
Remarques (modules conseillés, langage)
: TALN Niveau 1 (UMIN206), Conception et développement des IHM (UMIN209)
Groupe :
4 places
disponibles
Mathieu Roche et
Jacque Chauché
Résumé : Le stage
propoposé consiste à implanter l'algorithme PM-IR
de Peter Turney puis de mettre en oeuvre des
mesures plus complexes pour améliorer la qualité des résultats obtenus.
Spécialités concernées : IICW, IDI
Remarques (modules conseillés, langage)
: TALN Niveau 1 (UMIN206)
Groupe :
4 places
disponibles
Anne-Elisabeth Baert
et Vincent Boudet
Résumé : Le but du TER est de concevoir
un simulateur permettant de comparer différentes politiques de distribution de
calculs selon plusieurs critères : équilibrage de charge, temps de réponse,
congestion...
Spécialités concernées : ACR, ASR
Remarques (modules conseillés, langage)
: Réseaux et communications (UMIN131), Service et qualité des réseaux
(UMIN214)
Groupe :
4 places
disponibles
Anne-Elisabeth Baert
et Vincent Boudet
Résumé : Le but du TER est de concevoir
un simulateur permettant d'étudier l'impact de la variation des capacités de
traitement des esclaves sur le temps de réponse global du système.
Spécialités concernées : ACR, ASR
Remarques (modules conseillés, langage)
: Réseaux et communications (UMIN131), Service et qualité des réseaux
(UMIN214)
Groupe :
4 places
disponibles
Anne-Elisabeth Baert
et Vincent Boudet
Résumé : Le but du TER est d'étudier les
logiciels libres SimGrid et
Pajé.
Spécialités concernées : ACR, ASR
Remarques (modules conseillés, langage)
: Réseaux et communications (UMIN131), Service et qualité des réseaux
(UMIN214)
Groupe :
4 places
disponibles
Résumé : Le but du stage consiste à concevoir et programmer
un système de repérage automatique d'unités textuelles spécifiques, dans les
textes numérisés.
Spécialités concernées : IDI, IICW
Remarques (modules conseillés, langage)
: TALN Niveau 1 (UMIN206), Conception et développement des IHM (UMIN209)
Groupe :
4 places
disponibles
Anne Laurent et
Maguelonne Teisseire
Résumé : Les bases de données
multidimensionnelles sont réputées pour leur aspect très peu dense. Il s'agit
donc dans ce projet de définir et de mettre en oeuvre des méthodes de
détection de ces cellules potentiellement intéressantes. Des méthodes existent
déjà, il s'agit : de les implémenter, de proposer des améliorations. Ce projet
s'inscrit dans un projet plus large ayant déjà donné lieu à des
implémentations d'algorithmes, les étudiants auront donc à leur disposition un
programme pouvant leur servir de point de départ.
Spécialités concernées : IDI, CODA, IICW
Remarques (modules conseillés, langage)
: bases de données (UMIN132), introduction à l'IA
(UMIN203)
Groupe :
4 places
disponibles
Bénédicte Laurent et Maguelonne Teisseire
Résumé : L'enjeu commercial et financier
autour des noms de marque déposés est de plus en plus grand. Des corrélations
(exprimées sous forme de règles comme par exemple "les noms commençant par le
son 'ch' contiennent également le son 'a'") ont
été extraites grâce à des méthodes de fouille de données. Le travail à
réaliser est le suivant : proposer des mesures de comparaison entre ensemble
de règles (certaines mesures sont très simples, comme par exemple le taux de
règles en commun, d'autres pourront être plus complexes), implémenter les
propositions, tester les propositions sur les données réelles de l'INPI qui
seront mises à votre disposition.
Spécialités concernées : IDI, CODA, IICW
Remarques (modules conseillés, langage)
: bases de données (UMIN132), introduction à l'IA
(UMIN203)
Groupe :
4 places
disponibles
Pascal Poncelet (EMA), Chedy
Raissi (EMA, LIRMM) et Anne Laurent (LIRMM)
Résumé : Weka
est un logiciel libre, open source, développé en java. Il fournit un certain
nombre d'outils d'apprentissage automatique et de fouille de données comme les
arbres de décision ou les règles d'association. Le travail à faire dans le
cadre de ce TER consiste à implanter l'algorithme de construction de motifs
séquentiels en java dans WEKA.
Spécialités concernées : IDI, CODA, IICW
Remarques (modules conseillés, langage)
: bases de données (UMIN132)
Groupe :
4 places
disponibles
Céline
Fiot et Maguelonne Teisseire
Résumé : Dans de nombreux domaines, la
recherche de connaissances temporelles est très appréciée. Le travail proposé
consiste à étudier la faisabilité d’un algorithme qui permettrait de prendre
en compte la gestion les contraintes de temps dans la recherche de motifs
séquentiels flous et éventuellement à le mettre en œuvre.
Spécialités concernées : IDI, CODA, IICW
Remarques (modules conseillés, langage)
: bases de données (UMIN132), algorithmique
(UMIN111)
Groupe :
4 places
disponibles
Résumé : Les données du monde réel sont
souvent entâchées d’imperfection. En particulier,
il est très courant de disposer de nombreuses données incomplètes. Le travail
proposé consiste à étudier les différentes techniques de complétion des
valeurs manquantes dans les domaines des statistiques, de la fouille de
données et de l’apprentissage automatique afin de proposer une ou plusieurs
solutions dans le cadre d’une technique particulière de fouille : l’extraction
de motifs séquentiels.
Spécialités concernées : IDI, CODA, IICW
Remarques (modules conseillés, langage)
: bases de données (UMIN132), algorithmique
(UMIN111)
Groupe :
4 places
disponibles
Vincent Ranwez,
Denis Bertrand et Alexis Criscuolo
Résumé : Les méthodes de reconstruction
phylogénétique cherchent à reconstruire l’histoire évolutive des espèces à
partir de séquences biologiques. Le principe général de ce type de méthode est
de définir un critère que l’on peut estimer pour un arbre et de rechercher
l’arbre le meilleur au sens de ce critère. L’objectif de ce stage est de
réaliser un logiciel utilisant le critère de maximum de parcimonie qui tire
partie des heuristiques développées dans le cadre du maximum de vraisemblance.
Spécialités concernées : TOIL, ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111), Résolution de problèmes
NP-difficile (UMIN207), langages objets
Groupe :
4 places
disponibles
Résumé : L’objectif de ce stage est de
développer un outil permettant de faire des opérations simples sur des arbres
étiquetés. Il faudra par exemple implémenter des méthodes pour le calcul de
distances entre 2 arbres, d’arbres consensus, de
ré-enracinement et de filtrage des feuilles. Ce logiciel devra pouvoir
être utilisé au sein de notre laboratoire et pouvoir être diffusé sur
Internet. Ce qui implique une validation importante du logiciel notamment au
travers de tests unitaires automatiques.
Spécialités concernées
: TOIL, ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111), langages objets, C++, graphes
Groupe :
4 places
disponibles
Résumé : Les méthodes de reconstruction
phylogénétique cherchent à reconstruire l’histoire évolutive des espèces à
partir de séquences biologiques. Le principe général de ce type de méthodes
est de définir un critère que l’on peut estimer pour un arbre et de rechercher
l’arbre le meilleur au sens de ce critère. De plus en plus d’études
phylogénétiques s’appuient non plus sur un seul gène mais sur un ensemble de
gènes. L’objectif de ce stage et d’essayer de prendre en compte le fait que
les données sont issues de plusieurs gènes afin d’améliorer l’heuristique
d’optimisation.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111), Résolution de problèmes
NP-difficile (UMIN207), langages objets
Groupe :
4 places
disponibles
Pascal
Dugénie et Philippe Lemoisson
Résumé :
Spécialités concernées :
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Pascal
Dugénie et Philippe Lemoisson
Résumé :
Spécialités concernées :
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Pascal
Dugénie et Philippe Lemoisson
Résumé :
Spécialités concernées :
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Pascal
Dugénie et Philippe Lemoisson
Résumé :
Spécialités concernées :
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Pascal
Dugénie et Philippe Lemoisson
Résumé :
Spécialités concernées :
Remarques (modules conseillés, langage)
:
Groupe :
4 places
disponibles
Résumé : Le principal problème de la communauté de
Résolution de Réseaux de Contraintes Distribués est qu'elle ne dispose pas de
plateforme commune. Aussi chaque nouvel algorithme est expérimenté dans un
cadre différent, interdisant de la sorte toute possibilité de comparaison.
L'idée de ce projet est d'étendre Choco un
solveur de contraintes centralisé (écrit en JAVA)
en lui adjoignant des capacités de communication réseaux (Interface
Socket, ou autre...) afin de le rendre distribué.
Spécialités concernées : TOIL, CODA, ACR
Remarques (modules conseillés, langage)
: Introduction a l'IA
(UMIN203), Savoir coder en Java, Problème NP-difficile
(UMIN207 facultatif)
Groupe :
4 places
disponibles
Résumé : Dans le problème de satisfaction
de contraintes, un des facteurs essentiels pour l'efficacité d'une recherche
en arbre de type "backtrack" est le critère
utilisé pour sélectionner la prochaine variable à instancier (càd.
l'heuristique d'ordonnancement des variables). L'idée de ce projet est
d'utiliser des techniques d'apprentissage automatiques (telles des les arbres
de décisions, les réseaux de neuronnes ou les
algorithmes génétiques) pour inferer la bonne
heuristique.
Spécialités concernées : TOIL, CODA, ACR
Remarques (modules conseillés, langage)
: Introduction a l'IA
(UMIN203), Savoir coder en Java, Problème NP-difficile
(UMIN207 facultatif)
Groupe :
4 places
disponibles
Résumé : Ce projet a pour objectif de créer un outil
générique de comparaison des différentes méthodes de cryptage basées sur les
courbes elliptiques.
Spécialités concernées : TOIL, ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111)
Groupe :
4 places
disponibles
Résumé : Ce projet a pour objectif d'implanter le protocole
de cryptage RSA en utilisant un système de représentation des grands nombres:
le Residue Number
System.
Spécialités concernées : TOIL, ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111)
Groupe :
4 places
disponibles
Christophe
Fiorio et Fabrice Philippe
Résumé : Ce sujet émane d'un début de
collaboration avec deux chercheurs de l'Institut Européen des Membranes, A.
van der Lee et M. Rolland. L'objectif final du projet est de définir et
implanter un algorithme permettant la détermination du groupe d'espace d'un
composé cristallin. Les objectifs intermédiaires de ce sujet de TER sont la
compréhension préalable du contexte et la mise en oeuvre d'algorithmes simples
dans un programme (modulaire)
permettant une première résolution du problème. Une deuxième étape consistera
à rechercher des algorithmes plus efficaces, et pourra être complétée lors du
stage de M2R le cas échéant.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: (utiles mais pas vitaux) Algorithmique (UMIN111), Modèles aléatoires
(UMIN210)
-
Calcul
de la valeur d'information d'un arbre ; exploration du voisinage d'un arbre
pour l'optimisation de ce critère
Groupe :
4 places
disponibles
Vincent Berry
et Vincent Ranwez
Résumé : en reconstruction de phylogénies
on modélise l'histoire des espèces vivantes sous la forme d'un arbre. Depuis
un ensemble d'arbres partageant des feuilles en commun, on essaye de
construire un "super-arbre" regroupant l'ensemble
de ces feuilles et dont la structure reflète autant que possible la structure
des arbres de départ. Dans ce TER il s'agira d'implémenter une mesure
permettant d'évaluer la quantité d'information présente dans un
super-arbre et de proposer des petits changements
dans le super-arbre de façon à améliorer sa
quantité d'information.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: aucune notion de biologie n'est nécessaire, Perl, C/C++ ou Java,
Algorithmique (UMIN111), Résolution de problème
NP-difficile
Groupe :
4 places
disponibles
Résumé : On considère un problème d'ordonnancement dynamique qui est de la famille des problèmes d'empaquetage (bin packing). Une suite d'objets arrivent au cours du temps, de façon aléatoire. Chaque objet a une certaine taille, aléatoire également. À chaque objet O correspond aussi une date limite de validité. Il s'agit de placer les objets dans des boites à raison d'une boite chaque unité de temps. Il y a des contraintes: la taille totale des objets ne peut pas dépasser celle de la boite. Il ne peut pas y avoir plus de deux objets par boite. Et les objets doivent être placés avant leur date limite respective. Si un objet n'a pas pu être placé à temps, il est perdu. L'objectif est donc d'étudier des stratégies pour résoudre ce problème.
Spécialités concernées : ACR
Remarques (modules conseillés, langage)
: Algorithmique (UMIN111), Résolution de problème
NP-difficile
Groupe :
4 places
disponibles
Résumé : VoiceXML est une technologie permettant le développement rapide et efficace d 'applications vocales. Cette technologie a récemment été standardisée par le W3C. L'objectif de ce stage est double : (1) Explorer l'ensemble des possibilités offertes par VoiceXML (un TER de master 2 a déjà pas mal déblayé le terrain), (2) Concevoir un logiciel permettant d'exécuter du code VoiceXML sur une machine distante.
Spécialités concernées : TOIL, IDI
Remarques (modules conseillés, langage)
: