Sujets de projet 2016 automne

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.

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 :

• améliorer l'interface graphique (gestion des fichiers, animation, zoom …);
• gérer l'export d'images en différents format;
• améliorer le support du language SVG (remplissage, lien, …).

Le but de votre projet est d'implémenter un algorithme classique de construction d'une forêt.

Pour cela il faut :

1. implémenter la construction d'un arbre de décision à partir d'un jeu de données d'exemples;
2. implémenter un système permettant de générer un grand nombre d'arbres de décision;
3. mettre en place un système de test permettant de mesurer la qualité de vos algorithmes.

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.

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:

• une interface graphique pour manipuler les fichiers et visualiser le résultat;
• implémenter d'autres méthodes de calcul plus robustes;
• améliorer le temps de calcul et l'utilisation mémoire de votre programme

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 :

1. ajouter une interface graphique;
2. mettre en place un système de comparaison avec la représentation jpeg;
3. améliorer le temps de calcule et le cout mémoire de votre programme.

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 :

1. générer la clef;
2. chiffrer avec la clef publique et déchiffrer avec la clef secrète;
3. chiffrer avec la clef secrète et déchiffrer avec la clef publique (pour signer).

Comme amélioration vous pourrez :

• implémenter d'autres algorithmes de chiffrement;
• créer un petit logiciel de connexion à distance sécurisé.

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 :

• implémenter une autre méthode pour trouver la solution optimale ou une approximation et comparer les temps de calcul et la qualité de la solution;
• ajouter une interface graphique permettant de visualiser les évolution de l'algorithme et son résulat.

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 :

1. implémenter un petit système multi-agent très simple (un terrain, des patches d'intérêt, des agents qui se déplacent) fonctionnant de manière séquentielle;
2. implémenter pour ces agents une stratégie d'exploration aléatoire et une exploration suivant le vol de Lévy (en cherchant, dans ce dernier cas, les valeurs des paramètres pour lesquelles l'exploration est la plus efficace) ; le but étant de ramasser au plus vite tous les patches de nourriture;
3. comparer les résultats pour différentes configurations données (fréquence et tailles des patches, nombre d'agents).

Pour améliorer ce projet :

• il est possible de trouver les valeurs des paramètres de manière totalement expérimentales, en tâtonnant, mais d'autres méthodes sont utilisables
• proposer d'autres stratégies d'exploration et les comparer à celles déjà implémentées

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 :

• Dans “des avions ont décollé ce matin”, “avions” est un nom
• Dans “Nous avions déjeuné”, “avions est un verbe

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 :

• travailler les prétraitements permettant d'augmenter la performance (traitement des mots inconnus, correction de l'orthographe, …)
• ajouter des post traitements comme retrouver la forme canonique des mots (verbe à l'infinitif, nom au singulier, …)
• …

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.

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 :

1. Implémenter l’algorithme de partitionnement
2. Implémenter un système permettant de générer plusieurs arbres de partitionnement à partir d’un jeu de données non étiqueté
3. Implémenter le détecteur d’anomalies basé sur l’ensemble des arbres générés.

• Traitement des données séquentielles
• Comparaison avec d'autres algorithmes ( vous n'aurez pas à les implémenter, juste les utiliser pour la comparaison)
• Améliorer le temps de calcul et l'utilisation de mémoire
• Interface graphique

La photo numérique ouvre beaucoup de possibilités en terme de post-traitement d'image. Nous nous intéresserons ici à la gestion du contraste, avec plusieurs familles de traitements :

• La base : ajustement du contraste global. Il s'agit simplement d'appliquer une fonction affine à chaque pixel.
• Gestion des ombres et lumières : rehausser les parties sombres de l'image, assombrir les parties surexposées.
• Gestion du contraste local : faire ressortir les détails (les contours par exemple) sans modifier le contraste global

Le sujet est très libre, et pourra explorer plusieurs (mais pas forcément toutes) des pistes suivantes :

• Prototypage d'une solution en utilisant Python et les bibliothèques skimage, NumPy et SciPy.
• Développement des algorithmes en C++ (ou éventuellement C).
• Optimisations de performances (éviter de refaire plusieurs fois le même calcul, optimiser l'ordre de parcours des matrices pour limiter les défauts de cache), parallélisation.
• Interface graphique pour rendre le résultat agréable à utiliser par un utilisateur non-informaticien.

Le but du projet est de participer à un projet « de la vraie vie » (un logiciel activement développé, ayant déjà un bon nombre d'utilisateurs, …). Un bon moyen d'atteindre cet objectif est de contribuer à un logiciel libre.

Contribuer à un logiciel libre est en particulier un bon moyen d'aborder sur des cas réels les questions comme :

• La revue de code par des tiers,
• L'utilisation poussée d'un gestionnaire de versions,
• L'application stricte de styles de codage,
• Les tests automatisés,
• L'utilisation des mailing-lists comme outil de communication et d'entre-aide.

Un effet de bord intéressant est qu'avoir du code à soi dans un projet libre permet de briller en société .

Voir le sujet détaillé pour plus d'informations.