Le but de ces projets est de vous initier à la programmation mathématique. Chaque sujet contient un exemple de résolution mathématique. Cela signifie que vous devez programmer des solutions à ces problèmes et (sauf mention contraire) vous ne devez pas utiliser de librairie qui implémente les solutions standards.
Tous les projets demandent de faire un programe avec un minimum de caractéristiques pour avoir la moyenne. Chacun propose une série d'améliorations possibles qui permettront d'augmenter la note. Il faut utiliser l'un des 3 langages principalement enseignés en licence : C, C++ ou Java. Ces programmes doivent pouvoir compiler et être éxécutés sur les ordinateurs de l'université, et le rendu devra contenir toutes les librairies necessaires. Ils devront contenir un moyen simple de compiler les programmes ainsi qu'une petite documentation.
Techniques | Lecture XML , Courbe de Bézier, dessin. |
---|---|
Responsable du sujet | |
Fabien Rico |
Vous devez créer un logiciel capable de lire un fichier SVG. C'est un langage de description de dessin vectoriel issu du web. Il se présente sous la forme d'un fichier XML que vous devrez lire en utilisant une librairie existante du langage utilisé. Ce fichier contient des descriptions d'objets géométriques (rectangles, cercles …) mais aussi des chemins (*path*) qui permettent de définir des figures complexes nottament grâce à des courbes de Bézier cubiques et des arcs elliptique.
Votre logiciel ne doit pas forcement être capable d'afficher tous les fichiers SVG existants, mais il ne doit pas faire d'erreur lorsqu'il rencontre une commande non gérée. De plus, il doit implémenter l'ensemble des possibilités des chemins.
Pour améliorer le rendu vous pouvez de plus :
Techniques | Classification, statistiques |
---|---|
Responsable du sujet | |
Fabien Rico | |
Informations à voir | |
Ensembles de cours datamining (cf *Arbre de décision* et *Random Forest*) |
Le but de votre projet est d'implémenter un algorithme classique de construction d'une forêt.
Pour cela il faut :
Votre logiciel devra être capable à partir d'un fichier d'exemple dans un format simple (CSV) de construire un modèle. Puis à partir d'un modèle et d'un fichier de test dans le même format de trouver les classes des objets.
Les améliorations possibles de votre travail pouront porter sur les différentes optimisations ou adaptations de l'algorithme à des cas spécifiques, sur l'amélioration du temps temps de calcul et du coût mémoire de votre programme. Vous pourrez aussi ajouter des prétraitements pour résoudre les cas ou les données sont lacunaires ou ajouter une interface graphique au programme.
Techniques | calcul de valeur propres, visualisation de données |
---|---|
Responsable du sujet | |
Fabien Rico | |
Informations à voir | |
Alain Baccini et Philippe Besse, Exploration Statistique, chapitre 7 |
Votre programme devra implémenter la construction MDS de donnée utilisant l'algorithme classique qui se résume à calculer des valeurs propres d'une matrice obtenue à partir de la matrice de distances. Il devra a partir d'un fichier contenant la liste des points et leur distance, fournir un fichier contenant les coordonnées calculées ce ces points.
Pour améliorer le programme, vous pourrez faire:
Techniques | calcul de valeur propres, compression |
---|---|
Responsable du sujet | |
Julia Sanchez | |
Information à voir | |
Description détaillée |
On cherche ici à implémenter un algorithme de compression d'image avec perte (comme jpeg). L'image que l'on utilise (ou une partie de celle-ci) peut être vue comme une matrice. On peut utiliser sur cette matrice des techniques de réduction de dimension, c'est à dire obtenir une matrice de dimension plus petite qui contient l'essentielle de l'information de départ. C'est le rôle de l'analyse en composante principale (PCA). A partir de cette matrice plus petite (compréssée), on peut reconstruire l'image de départ avec quelques déformations dépendant du taux de compression utilisé.
Votre programme devra être capacle de lire une image sous un format simple (sans perte), et produire un fichier compressé. Il devra bien sur permettre d'appliquer le traitement inverse.
Pour améliorer ce dernier vous pourrez :
Techniques | calcul sur des entiers de taille quelconque, authentification, signature |
---|---|
Responsable du sujet | |
Fabien Rico |
Les algorithmes de chiffrement asymétrique sont devenus très importants dans le domaine informatique. RSA est l'un des plus connus et se base sur l'utilisation de grand nombres premiers. L’intérêt de ces algorithmes est qu'ils permettent un échange d'informations chiffrées entre des entités qui ne partagent aucun secret au départ.
En effet, les algorithmes symétriques sont bien plus robustes (pour une même taille de clef), mais il nécessite avant de commencer d'échanger un secret entre les acteurs. Pour un serveur public dont le nombre de clients est très important, il n'est pas possible de mettre en place un canal pour échanger ce secret autrement qu'en utilisant le réseau internet. On utilise donc les algorithmes a clef publique pour sécuriser les premiers échanges et mettre en place une session sécurisée.
Vous devez implémenter l'algorithme RSA, c'est à dire :
Comme amélioration vous pourrez :
Techniques | coloration de graphes, métaheuristique |
---|---|
Responsable du sujet | |
Aurélie Kong Win Chang | |
Informations supplémentaires | |
Quelques mots sur les protocoles expérimentaux |
Le projet consistera en l'implémentation d'une structure permettant de représenter un graphe et sa coloration, un algorithme simple permettant de trouver une coloration quelconque valide, et l'algorithme de recuit simulé pour trouver une approximation de la solution. Votre programme devra être capable de trouver une approximation acceptable de la solution du problème.
Il y a plusieurs moyens d'améliorer ce projet :
Techniques | Informatique bio-inspiré |
---|---|
Responsable du sujet | |
Aurélie Kong Win Chang | |
Information à voir | |
Une description détaillée | |
Un article sur le sujet | |
Tirage suivant une distribution gaussienne en java | |
Quelques mots sur les protocoles expérimentaux | |
Remarque | Sujet issu du cours de M2 : informatique bio inspirée |
L'informatique bio-inspirée consiste à se baser sur des observations tirées de la nature pour, entre autres, créer de nouveaux algorithmes. Ainsi une stratégie d'exploration observée chez de nombreux animaux (albatros, humains chasseurs-cueilleurs…) a-t-elle été reprise pour des robots sous-marins. Ce projet propose d'implémenter différentes stratégies de recherche de ressources et de les comparer pour différentes configurations :
Pour améliorer ce projet :
Technique | Part Of Speech, maximisation d'entropie |
---|---|
Responsable du sujet | |
Fabien Rico | |
Info à voir | |
Un article expliquant la méthode | |
Un exemple de déroulement de l'algorithme présenté dans l'article |
Reconnaitre la nature gramaticale d'un mot, ou Part Of Speech (POS), est un point de départ dans beaucoup de tâches de traitement du langage naturel. Il s'agit de reconnaitre automatiquement la nature d'un mot dans une phrase. Par exemple :
Le but de l'algorithme est d'être capable d'affecter un label (la nature) à chaque mot d'une phrase en considérant le contexte (c'est à dire la phrase). Une des technique utilisée pour faire cela est basé sur de l'apprentissage automatique. Elle apprend à partir d'exemples un modèle statistique qui est capable de donner une probabilité d'affecter un label en fonction du contexte. Pour mettre au point ce modèle, on utilise un série d'exemples et un algorithme de maximisation d'entropie.
Votre projet doit être capable de créer ce modèle à partir d'exemples de la litérature et de les tester pour mesurer leurs performances.
Pour améliorer le travail vous pouvez aussi :
Technique | analyse de text, manipulation de grandes matrices |
---|---|
Responsable du sujet | |
Fabien Rico | |
Info à voir | |
Global Vectors for Word Representation | |
Article expliquant l'algorithme |
Le word embedding est une méthode à la base de nombreux travaux d'analyse du langage naturel. Il consiste à vouloir transformer les mots de la langue en un ensemble de vecteur mathématiques. Le but est de le faire en conservant une certaine notion du sens des mot.
Le moyen de faire cela est de travailler à partir d'une matrice de co-occurences des mots dans les phrases trouvées dans un grand corpus de texte (par exemple wikipedia). Cette matrice contient une partie du sens des mots car le sens dépend du contexte. Mais cette matrice est trop grande pour être utilisée. Il faut alors appliquer une technique de réduction de dimension de la matrice pour obtenir les vecteurs souhaités.
C'est un projet plutôt exploratoire, vous allez devoir faire cette opération : lecture des textes; création de la matrice; réduction de la dimension… Ce projet n'étant pas assez maitrisé, il n'y a pas de minimum proposé. On notera en fonction de l'état d'avancement final.
Techniques | apprentissage non supervisé, apprentissage statistique |
---|---|
Responsable du sujet | |
Seif Benkabou | |
Informations à voir | |
Un article sur la détection d'anomalies |
La détection d’anomalies vise à identifier, dans un ensemble de données, celles qui diffèrent significativement des autres, qui ne se conforment pas à un comportement attendu, et qui indiquent un processus de génération différent. Plusieurs domaines d’application font appel à la détection d’anomalies comme la détection de fraude (ex : paiement en ligne), la détection d’intrusion (tentatives de piratage, connexions frauduleuses), la vidéosurveillance ou encore la bio-informatique.
Plusieurs techniques ont été proposées pour détecter efficacement les anomalies dans un mode non supervisé (contrairement à la classification où on ne dispose d’aucune information concernant la normalité des données).
Une technique parmi les plus efficaces, consiste à construire un grand nombre d’arbres de partition (un partitionnement récursif des données) et de détecter comme anormales les données ayant des chemins relativement courts par rapport aux racines dans la majorité des arbres.
Le but de votre projet est d’implémenter l’algorithme Isolation Forest. Votre logiciel devra être capable, à partir d’un fichier de données quelquonques, de détecter les les données anormales.
Pour cela il faut :