projet:sujets2018printemps

Sujets de projet, printemps 2018


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 programme 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 langages enseignés en licence : C, C++, Java, python ou php. Ces programmes doivent pouvoir compiler et être exécutés sur les ordinateurs de l'université, et le rendu devra contenir toutes les librairies nécessaires. Ils devront contenir un moyen simple de compiler les programmes ainsi qu'une petite documentation.

Domaines Synthèse d'images
Techniques et langages OpenGL / C++ ou webGL ou C#/Unity
Responsable du sujet
Alexandre Meyer
Informations à voir

Les deux grandes familles de techniques pour déformer un maillage sont le mélange de formes (blendshape) ou le skinning. A priori, dans ce sujet nous nous orienterons vers la technique de blendshape. La technique de blendshape consiste à mélanger des maillages 3D de visages afin d'obtenir des expressions différentes. Par exemple, à partir de 4 maillages représentants différents expression (joie, colère, peur, surprise) le blendshape créera un nouveau maillage en faisant la moyenne pondérée des 4 visages de références. Cette technique poura être mise en oeuvre en C++ en partant du code que vous avez utilisé en L2 “Introduction à l'informatique graphique” ou en utilisant le framework de jeu vidéo Unity (au choix par groupe).

Le pilotage de l'animation du visage se fera en capturant les mouvements de points caractéristiques d'un visage filmé avec une webcam en utilisant DLib (python ou C++).

Domaines Images et machine learning (IA)
Techniques Détection de visage/points, conception de descripteurs, classification.
Langages C++ ou Python (préférable)
Responsable du sujet
Alexandre Meyer
Informations à voir
DLib détection de visages et de points caractéristiques ; Exemple en Python , Keras, surcouche des plateformes de deep learning classique (Tensorflow, CNTK, Theano

Les outils de vision et de synthèse d'images travaillant sur le visage deviennent assez rependus et simple d'utilisations pour être capable de coder des applications qui semblaient encore impressionnantes il y a quelques années.

  • La détection du visage et de ses points caractéristiques peut se faire avec DLib (C++ ou python)
  • La classification pour reconnaitre une personne spécifique. L'apprentissage se fera à partir d'une base données d'images comportant les noms des personnes.

Le travail portera sur deux points. Le premier sera la conception de données d'entrées pertinentes, des descripteurs, pour la reconnaissances. En effet, donner directement les points d'un visage n'est pas ce qu'il y a de plus efficaces. On pourra imaginer d'extraire des distances caractéristiques entre les points détectés : écartements des yeux, de la bouche, du nez, etc.

Le 2e point de travail sera d'implémenter des algorithmes de classification en suivant une progression. - Plus proche voisin : simple, pour comprendre le principe général du problème - Réseau de neurones en utilisant les plateforme de deep learning (Keras, Tensorlow) qui sont simple d'utilisation. Le réseau de neurones cherchera à différentier des personnes.

Une interface de gestion de utilisateur et de reconnaissance sera importante pour illustrer le concept. On peut imaginer que cette interface se fasse via un site web.

Domaines Images et machine learning (IA)
Techniques Réseaux de neurones
Langages Python
Responsable du sujet
Alexandre Meyer
Informations à voir
DLib détection de visages et de points caractéristiques ; Exemple en Python , Keras, surcouche des plateformes de deep learning classique (Tensorflow, CNTK, Theano

Les plateformes open source de deep learning de Google (TensorFlow), Facebook (Theano), Microsoft (CNTK) ou Keras rendent le codage de réseaux de neurone facile. Un réseau apprenant à classifier une image se code en quelques dizaine de lignes. A partir de données réelles le réseau peut “apprendre” pour ensuite être capable de traiter de nouvelles données.

La 1ere partie de ce sujet consistera à prendre en main Keras et à concevoir un réseau de neurone de convolution afin de classifier une image. Les 1er tests se feront sur la base de données MNIST qui comporte des images manuscrites de chiffres. Une fois que le réseau a appris, on lui soumet une image d'un chiffre (qu'il n'a pas vu lors de son apprentissage) et il doit produire en sortie le chiffre reconnu. On pourra imaginer ensuite tester ce réseau sur la base de données de visage CelebA http://mmlab.ie.cuhk.edu.hk/projects/CelebA.html pour reconnaitre par exemple si une personne porte des lunette ou non.

La 2e partie de ce sujet sera de concevoir un réseau qui fait le travail inverse : on lui donne en entrée un chiffre et il produit en sortie l'image de ce chiffre : ce sera l'image moyenne des chiffres qu'il a utilisé lors de son apprentissage. Les deux réseaux mis ensemble s'appelle un auto-encodeur.

Domaines Image
Techniques Toutes les facettes d'un jeu vidéo
Langages C#/Unity
Responsable du sujet
Alexandre Meyer
Informations à voir TuxRacer pour les ressources

Unity est un framework devenu hyper classique pour le développement de jeux vidéo. Ce sujet se propose de vous faire développer un jeu vidéo complet en allant si possible jusqu'à la publication sur l'Android store. Après une prise en main d'Unity, nous vous proposons de redévelopper un jeu similaire à tuxracer mais en multi joueur sur le même écran coupé en deux sous partie. TuxRacer est un jeu OpenSource développé en C++ dont les ressources sont disponibles (terrain, modèle 3D, musique, etc.). La tâche demandé est donc un portage sous Unity, en ajoutant une interaction entre les 2 pingouins lors d'une descente.

Domaines data mining, visualisation
Librairies (proposées) scikit-learn, bootstrap
Langages (proposé) Python, javascript, html/css…
Responsable du sujet
Rémy Cazabet
Informations à voir Sujet complet; API Enedis

Les compteurs électriques intelligents (Linky) permettent de suivre notre consommation électrique demi-heure par demi-heure. Vous développerez des outils de data mining et de visualisation web pour permettre à chacun de comprendre (et idéalement de réduire…) sa consommation électrique.

Domaines data mining, visualisation, scientometrie
Librairies (proposées) scikit-learn, bootstrap, jsnetworkx
Langages (proposé) Python, javascript, html/css…
Responsable du sujet
Rémy Cazabet
Informations à voir Sujet complet; Portail de l'université de Lyon

Les informations des publications scientifiques des chercheurs de Lyon sont accessibles en ligne. Vous développerez des outils de data mining et de visualisation web pour aider les chercheurs à trouver de nouveaux travaux pertinents et de nouveaux collaborateurs potentiels.

Domaines Graphes, visualisation
Librairies (proposées) d3, networkx, jsnetworkx, bootstrap
Langages (proposé) Python, javascript, html/css…
Responsable du sujet
Rémy Cazabet
Informations à voir Sujet complet; Projet du semestre precedent

L'analyse de réseaux dynamiques est un de mes sujets (data mining) de recherche principaux. Il n'existe pas à l'heure actuelle de bons outils pour visualiser des données formant de tels réseaux. Vous développerez une interface web pour répondre à ce problème. Pour joindre l'agréable à l'utile, vous utiliserez des données réelles d'interactions entre personnages de séries télé. Un projet précédent à exploré ce problème sans aller aussi loin, vous pourrez le réutiliser ou repartir de zéro, au choix.

Domaines Machine learning, visualisation
Librairies (proposées) scikit-learn, bootstrap
Langages (proposé) Python, javascript, html/css…
Responsable du sujet
Rémy Cazabet
Informations à voir Sujet complet; Exemple de méthode

A partir des résultats sportifs des années précédentes, vous mettrez en place plusieurs algorithmes de machine learning (sans les recoder) pour prédire les résultats futurs. Une interface web ergonomique devra permettre de comparer les prédictions des algos testés. Un projet précédent à exploré ce problème sans aller aussi loin, vous pourrez le réutiliser ou repartir de zéro, au choix.

Domaines Open data, visualisation, web
Librairies (proposées) API de grands sites, beautiful soup, bootstrap
Langages (proposé) Python, javascript, html/css…
Responsable du sujet
Rémy Cazabet
Informations à voir Sujet complet; Projet du semestre dernier qui peut servir de base à améliorer

L'objectif est de développer un site web basé sur une carte permettant d'explorer l'offre de restaurants/bars de Lyon. Une étape importante consistera à faire de la collecte de données, à travers des API (Google maps, Yelp…) ou du crawling de sites pour constituer une base intégrée et à jour. Une interface web ergonomique pourra être développée de zéro ou reprendre les bases d'un projet précdent en l'améliorant.

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 :

  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.

Améliorations

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, compression
Responsable du sujet
Fabien Rico
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). À partir de cette matrice plus petite (compressée), on peut reconstruire l'image de départ avec quelques déformations dépendant du taux de compression utilisé.

Votre programme devra être capable 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.

Améliorations

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 calcul et le coût mémoire de votre programme.
Techniques administration système
Responsable du sujet
Fabien Rico
Information à voir
https://www.docker.com/
http://spark.apache.org/

Pour gérer de grands volumes de données, plusieurs framework ont été développés. Spark est l'un d'entre eux, il permet de définir des programmes dont les calculs seront facilement et efficacement distribués sur un cluster. Vous devez créer un système capable de mettre en place un cluster spark et de lui soumettre des tâche de calcul.

Le système que vous allez développer pourra utiliser un outil comme docker-machine pour créer des machines virtuelles dans une plateforme de cloud computing (celle du département), puis les conteneurs dockers pour lancer les différentes parties du cluster. Enfin, il soumettront les tâches au cluster pour obtenir leurs résultats.

Amélioration

  • utilisation de plusieurs plateformes de cloud computing (AWS, Azure, …)
  • utilisation d'autres frameworks (hadoop)
  • interface web de gestion
Techniques administration système et web
Responsable du sujet
Fabien Rico
Information à voir
http://symfony.com/

Le but de ce sujet est de mettre en place un site web avec une partie visible (front) et une partie d'administration (backend). Le sujet du site est encore indéterminé (et des idées sont les bienvenues). Il devra comporter une part de programmation importante (ne pas uniquement installer un CMS). Il devra comporter un système de gestion des utilisateurs, des droits, de modification du front…

Le langage de programmation est laissé libre, mais le site se basera sur la technologie des dockers pour être mis en place de manière simplifiée.

Amélioration

Selon la difficulté technique de certaines parties du site :

  • authentification web basée sur openid connect, ou CAS;
  • lien avec les réseaux sociaux
Domaines Cryptographie
Techniques et langages C++ et Sage (pour les tests)
Responsable du sujet
Fabrice Mouhartem
Sujet Complet https://perso.ens-lyon.fr/fabrice.mouhartem/LIFProj1-fr.html
Informations à voir
Identity-Based Encryption (en); Public-Key infrastructures (en); Chiffrement hybride; Attaque par canal auxiliaire

Pour garantir un échange sécurisé de messages, la cryptographie repose sur des schémas de chiffrements (symétriques ou asymétriques). Ceux-ci sont décrits comme un ensemble de trois algorithmes : la génération de clef(s), le chiffrement et le déchiffrement.

Si dans les applications critiques, il est possible d'organiser un échange physique de clefs pour garantir l'identité des différents partis, dans une utilisation quotidienne de la cryptographie, d'autres méthodes sont mises en place. Par exemple, GnuPG repose sur le mécanisme de la toile de confiance; c'est-à-dire que chaque personne qui a pu vérifier physiquement l'identité d'une clef, peut décider de la certifier à l'aide d'une signature cryptographique sur cette clef. Ainsi plus une clef a de signatures de confiance (i.e., une identité elle-même signée par de nombreuses clefs), plus la confiance qu'on peut y accorder est grande.

Bien entendu, cette méthode ne garantit rien vis-à-vis des collusions qui peuvent se produire entre des utilisateurs malicieux. Une autre technique consiste à déléguer cette tâche à un tiers de confiance, qui s'occupera de certifier les clefs. C'est ce qu'il se passe par exemple dans le protocole SSL (le cadenas vert dans votre navigateur favoris). L'identité de l'université Lyon 1 est donc assurée par l'association TERENA.

Une solution alternative, mais qui n'est pas encore déployée, consiste à utiliser le chiffrement fondé sur l'identité. Pour faire simple, il s'agit d'un système cryptographique où un paramètre publique est disponible (au lieu d'une clef publique par individu), et où tout un chacun est en mesure de générer à partir de celle-ci la clef publique de la personne à qui elle souhaite envoyer un message, à partir de l'identité de celle-ci (par exemple une adresse e-mail).

Cette méthodologie devient ainsi résistante aux attaques de l'homme du milieu.

Objectifs: Le but de ce projet est ainsi d'implanter une mécanique de chiffrement par identité (couplée à un chiffrement hybride), cryptographiquement sure. L'implantation devra donc être résistante aux attaques par canaux auxiliaires, et une possible intégration à un client lourd pour les e-mails.

Domaines Cryptographie
Techniques et langages C++ et Sage (pour les tests)
Responsable du sujet
Fabrice Mouhartem
Sujet complet https://perso.ens-lyon.fr/fabrice.mouhartem/LIFProj1-fr.html
Informations à voir
Crible algébrique (en)

Ce projet propose l'implémentation d'attaques contre l'algorithme RSA, largement déployé, par exemple pour la sécurisation de sites web (SSL/TLS).

La sécurité de ce protocole repose sur le fait que la clef publique, qui est le produit de deux grands nombres premiers, est difficile à factoriser. Le but est donc d'utiliser les méthodes récentes pour la résolution de ce problème, et de les déployer sur des exemples assez gros à l'aide des ressources informatiques de l'Université.

Thématiques abordées:

  • Manipulation de grands entiers
  • Algèbre linéaire creuse
  • Calcul distribué
Domaines Cryptographie/Sécurité + Web
Techniques et langages C++/Web
Responsable du sujet
Fabrice Mouhartem
Sujet Complet https://perso.ens-lyon.fr/fabrice.mouhartem/LIFProj1-fr.html
Informations à voir
Bélénios Anonize

L'ANSII a annoncé qu'à l'heure actuelle, le vote électronique n'était pas assez mature pour être utilisé dans le cadre d'élections nationales.

Néanmoins, pour les étudiants, il est parfois utile de pouvoir faire des sondages anonymisés (pour l'évaluation des enseignements par exemple) tout en respectant les règles de l'ANSSI afin d'éviter que la Russie ne manipule un vote aussi important.

Ce projet propose de concevoir une interface web frontale liée en arrière-plan à un système de vote anonyme protégé à l'aide de méthodes cryptographiques récentes. Dans ce contexte, l'ergonomie de l'interface est aussi importante que la conception du moteur cryptographique.

Domaines Traitement automatique de la Langue, Fouille de texte, apprentissage
Techniques et langages Python
Responsable du sujet
Hussein Al-Natsheh
Fabien Rico
Informations à voir
Scikit-learn, Gensim
SpaCy, flask
ElasticSearch, BabelNet

Le but du projet est de créer un outil capable d'assigner à des articles journalistiques un ou plusieurs labels correspondant à leur sujet. Cela permettrait ainsi de fournir un outil pour aider les journalistes à trier et traiter ces articles. Ce projet se base sur un logiciel actuellement en développement et pourra éventuellement s'y intégrer. Ce projet demande d'apprendre à utiliser plusieurs techniques de traitement automatique de la langue récentes (TAL/NLP), comme par exemple le word embedding (plongement lexical). Il vous familiarisera aussi avec l'apprentissage automatique et l'utilisation de services web.

Amélioration

  • ajouter une interface (web) au logiciel
  • permettre de récolter et intégrer des retours humain sur la classification afin d'améliorer l'algorithme.
Domaines Traitement automatique de la Langue, Fouille de texte, apprentissage
Techniques et langages Python
Responsable du sujet
Hussein Al-Natsheh
Fabien Rico
Informations à voir
Scikit-learn, Gensim
SpaCy, flask
Polyglot, API twitter
Projet Lié https://prismoji.com/2017/02/06/emoji-data-science-in-r-tutorial/

On peut facilement utiliser l'API Twitter pour télécharger des tweets sur des sujets particuliers. Si on est capable d'analyser les sentiments exprimés dans les tweets, on peut alors mesurer la popularité d'un produit, d'une personne ou d'un sujet. Pour cela il est nécessaire de construire un ensemble d'apprentissage, ce qui peut être fait en utilisant les émoticones. En effet, on peut généralement supposer que les tweets contenants des émoticones souriants sont positifs et ceux contenants des émoticones tristes sont négatifs.

Vous devez faire un projet capable de construire un jeu de données suffisamment important pour entraîner des classifieurs. Ces derniers utiliseront des techniques de NLP récentes et des algorithmes d'apprentissage pour générer des modèles capables de reconnaître la polarité d'un tweet.

Amélioration

  • construire une interface web de démonstration
  • construire un système capable de mesurer la qualité de ce système.
Domaines Fouille de texte, recherche d'information et visualisation de données textuelles
Techniques et langages Python, Javascript, Service web
Responsable du sujet
Hussein Al-Natsheh
Fabien Rico
Informations à voir
Angular2, Sent2Vec
Sensim, flask
ISTEX

Ce projet vise à développer une interface web interactive pour détecter les paraphrases dans les résumés d'articles scientifiques. Il s’appuiera sur la base de données ISTEX qui contient des millions d'articles et devra être capable de lire les résumés et utiliser un modèle de similarité de phrases pour trouver et visualiser les phrases similaires entre des résumés.

Amélioration

  • Permettre d'obtenir un retour des utilisateurs et l'intégrer au modèle dans le but d'améliorer son résultat.
  • Utiliser la détection de périphrase pour effectuer une recherche d'un document dans la base de donnée ISTEX à partir d'un document fourni.
Domaines Compréhension du Langage Naturel (NLU), IA, Reconnaissance d'entités nomées
Techniques et langages Python, Javascript, Dialogflow
Responsable du sujet
Hussein Al-Natsheh
Fabien Rico
Informations à voir
Angular2, flask
Dialogflow, HotelCombined
Scikit-learn, SpaCy
Développement Facebook

Le but est de développer un robot capable de comprendre une requête de réservation exprimée en langage naturel. Il sera donc nécessaire de reconnaître dans la phrase les mots importants représentant, les lieux, les dates, … C'est ce qu'on appelle les entités nommées. Pour cela, il sera possible d'utiliser l'API dialogflow qui permet d'utiliser le français. Il faudra ensuite exécuter des requêtes sur une plateforme de réservation comme HotelCombined.

Amélioration

  • Une meilleure reconnaissance du langage naturel.
  • Une intégration à facebook via la création d'un chatbot avec Messenger.
Domaines Métaheuristique, Graphes
Responsable du sujet Aurélie Kong Win Chang
Informations à voir
Une présentation de l'algorithme et quelques améliorations

Étudié de longue date, le problème dit de la coloration de graphe consiste en trouver un moyen d'attribuer une couleur à chaque sommet d'un graphe donné de sorte à ce que jamais deux sommets reliés entre eux par une arête ne soient de la même couleur. Bien que le principe soit simple, sa résolution est en fait difficile pour plus de trois couleurs (problème NP-complet), et à plus forte raison l'est aussi la recherche du nombre minimal de couleurs nécessaires pour faire une telle coloration. Diverses méthodes de recherche de solutions approximatives ont ainsi été proposées, au nombre desquelles figure celle qui nous intéresse ici, inspirée d'un processus de métallurgie : le recuit simulé.

Le projet consistera dans un premier temps 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. Il vous sera demandé dans un deuxième temps une petite étude de cet algorithme (influence de différents paramètres de l'algorithme et/ou comparaison avec d'autres algorithmes…).

Domaines Métaheuristique, Algorithme bio-inspiré
Responsable du sujet Aurélie Kong Win Chang
Informations à voir
Une description détaillée du problème et de l'algorithme
Le papier séminal de l'algorithme ABC

Ce projet consiste en l'implémentation et l'étude d'un algorithme bio-inspiré, l'Artificial Bee Colony (ABC) Algorithm, dans le cadre d'un problème d'ordonnancement de flow-shop.

Les problèmes d'ordonnancement consistent en, étant donné un ensemble de tâches à effectuer et un ensemble de machines pouvant les effectuer, trouver une attribution de ces tâches à ces machines de sorte à atteindre un ou plusieurs objectifs. Nous nous plaçons ici dans le cas d'un problème de flow-shop : nous disposons d'un nombre défini de tâches, chacune d'entre elles devant passer par une série de machines dans un ordre donné pour être effectuée. Ces tâches peuvent être subdivisées en sous-tâches qui, dès qu'elles ont été effectuées par une machine, peuvent passer à la suivante. La solution recherchée devra exécuter toutes les tâches en le moins de temps possible. Étant donné la complexité du problème, diverses méthodes permettant de trouver une approximation de la solution ont été proposées, dont l'utilisation de l'algorithme ABC. Ce dernier propose de s'inspirer des méthodes de recherche de nourriture d'une ruche d'abeilles, alternant recherches locales et exploration pour converger vers notre solution.

Il vous sera demandé d'implémenter l'algorithme ABC pour ce problème, puis d'en faire une petite étude (influence des différents paramètres…).

  • projet/sujets2018printemps.txt
  • Dernière modification : 2018/01/30 14:33
  • de aurelie.kong-win-cha