projet:2019:pri:sujets [Cours de Fabien Rico]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
===== FR1. Classification par arbre de décision et forêt aléatoire =====
^Domaine | Classification, Machine Learning |
^Langage (proposé) | C++, java |
^Responsable du sujet                            ||
|                     | Fabien Rico                      |
^Informations à voir                                  ||   
|    [[http://eric.univ-lyon2.fr/%7Ericco/cours/supports_data_mining.html | Ensembles de cours datamining (cf *Arbre de décision* et *Random Forest*)]]  ||
   
La classification automatique est un domaine où on cherche à apprendre à reconnaitre la classe d'individus à partir d'exemples. Une technique parmi les plus efficaces est basée sur la construction d'un grand nombre d'arbres de décision (ce qu'on appelle forêts aléatoires). En effet, l'expérience montre que si on construit suffisamment de classifieurs différents entre eux mais efficaces, le fait de décider en fonction de la majorité des classifieurs permet d'obtenir résultat très bon.

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

Pour cela il faut :
  - implémenter la construction d'un arbre de décision à partir d'un jeu de données d'exemples;
  - implémenter un système permettant de générer un grand nombre d'arbres de décision;
  - 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 pourront porter sur les différentes optimisations ou adaptations de l'algorithme à des cas spécifiques, sur l'amélioration du 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.

===== FR2. Site de travail colaboratif =====
^ Domaine | administration système |
^ Technologie | Docker |
^ Responsable du sujet | Fabien Rico                                          | 
^ Information à voir                                                      ||
|     https://owncloud.org/  ||
|     https://rocket.chat/    ||
|     https://fr.wordpress.org/ ||

Le but de ce travail est de créer un script d'installation d'un site de travail collaboratif. Ce site est basé sur plusieurs composant 
  * [[https://owncloud.org/|owncloud]] qui permettra le partage de documents;
  * [[https://rocket.chat/|rocketchat]] qui permettra les discussions en lignes.
  * [[https://fr.wordpress.org/|wordpress]] (ou autre chose) qui permettra de créer un site web classique;
Ces composants devront de plus s'appuyer sur un système d'authentification unique (ldap?).

Pour simplifier l'installation automatique de l'ensemble, vous devrez utiliser des conteneurs //docker//. Le résultat de votre travail doit être une archive et un script dont l'exécution permettra d'installer l'ensemble des composant et de les faire communiquer.

==Amélioration==
Il y a un grand nombre de composants annexes pouvant être ajouter : webmail, forge, système d'authentification CAS/OpenIDConnect ... Il est aussi possible d'ajouter des modules utiles au composants proposé : conférence vidéo pour rocketchat, édition de documents pour owncloud ... 
  
===== FR3. Mise en place de cluster de calcul parallèle =====
^ Domaine | administration système|
^ Techniques | Docker, machines virtuelles |
^ 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. Mais ces cluster doivent être créés. Vous devez créer un système capable de mettre en place un cluster spark et de lui soumettre des tâches 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 de calcul. Enfin, il soumettront les tâches au cluster pour obtenir leurs résultats.

===Amélioration===
  * utilisation d'une plateformes de //cloud computing// publique (AWS, Azure, ...)
  * utilisation d'autres //frameworks// (hadoop)
  * interface web de gestion


===== FR4. Mise en place d'un site web =====
^ Domaine | web |
^ Langage | php |
^ Responsable du sujet | Fabien Rico                                          | 
^ Information à voir                                                      ||
|     http://laravel.com/    ||
|     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...


==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

===== FR5. Algorithme évolutioniste =====
^ Domaine | méta heuristiques |
^ Langage | C, python ? |
^ Responsable du sujet | Fabien Rico et Alexandre Meyer                                         | 
^ Information à voir                                                      ||
| [[http://jvf.free.fr/550_Articles_LinuxMag/GLMF_076_034_041.pdf]]  ||
| [[https://www.youtube.com/watch?v=JBgG_VSP7f8]]    ||

Les algorithmes évolutionnistes ou génétiques sont des méta-heuristique d'optimisation c'est à dire des méthodes globales pour résoudre des problèmes de toutes sorte qu'il faut adapté à un problème particulier. Comme leur nom l'indique, ils sont basés sur le concepts d'évolution. On génère une famille aléatoire d'individu dont on conserve les plus performant, que l'on mélange pour générer une nouvelle famille ...

===Travail à faire===
Vous devez construire des individus composés de polygone reliés entre eux et animé par un mouvement aléatoire. Vous devez faire en sorte qu'ils parcourent une distance maximale. Pour cela vous utiliserez //unity// afin de faire la simulation.
  


===== SA1. Modélisation distribuée d’un jeu stratégique=====
^ Domaine | Intelligence Artificielle|
^Langage (proposé) | C++, java |
^ Responsable du sujet | Samir AKNINE                                          | 
L’objectif de ce projet est de proposer une modélisation distribuée d’un jeu stratégique. Nous prendrons comme exemple une version proche du jeu de dames. Nous considérerons un ensemble de pions qui évoluent sur un plateau. Les pions sont répartis en deux groupes. Plusieurs pions d’un même groupe peuvent se déplacer en même temps selon des règles préétablies. L’objectif de chaque groupe est de remporter la partie en capturant les pions du groupe adverse.
Nous implémenterons une méthode de résolution distribuée dans laquelle chaque pion est représenté par une entité autonome dotée de comportements intelligents. Nous commencerons par définir des stratégies de résolution simples dans lesquelles les pions effectuent des déplacements uniquement sur la base de leur perception de l’occupation des cases voisines. Dans une deuxième étape, nous définirons des stratégies de résolution plus fines permettant aux pions de construire des stratégies de jeu collectives en interagissant avec leur voisinage.

===== SA2. Véhicule autonome : Gestion automatique de la traversée d’une intersection intelligente=====
^ Domaine | Intelligence Artificielle|
^Langage (proposé) | C++, java |
^ Responsable du sujet | Samir AKNINE                                          | 
Les récentes évolutions technologiques des dernières années ont permis d’améliorer le niveau d’équipement des véhicules rendus de plus en plus connectés, voire autonomes, ce qui permet de proposer de nouvelles réponses aux problèmes du trafic urbain. Les véhicules sont, à présent, capables de communiquer et de se coordonner. Avec notre projet, nous proposons une approche de régulation du trafic s’appuyant sur des méthodes distribuées pour améliorer les conditions de mobilité des véhicules.

Dans le cadre ce travail, nous implémenterons la méthode de régulation que nous avons définie à l’échelle de l’intersection tirant parti des capacités de communication des véhicules, et dans laquelle les véhicules autonomes négocient leur droit de passage dans chaque intersection. Cette négociation s’effectue en utilisant des mécanismes prédéfinis en s’appuyant sur les données de mobilité de chaque véhicule et en permettant ainsi de prendre en compte différents critères pour la prise de décision locale, comme l’état général du trafic, la localisation d’éventuelles congestions, ou encore la circulation des bus, les trajets programmés par les véhicules, etc.

===== SA3. Problème du covoiturage=====
^ Domaine | Intelligence Artificielle|
^Langage (proposé) | C++, java |
^ Responsable du sujet | Samir AKNINE                                          | 
Nous allons développer un système automatique pour le partage efficace de tâches entre des individus souhaitons collaborer. Nous prendrons comme exemple le covoiturage.  Le système devra prendre en compte les préférences et les contraintes des voyageurs pour formuler les meilleures solutions. 
L’objectif de la coordination entre les voyageurs est de minimiser les coûts des transports. Ce problème est intéressant du fait que les préférences sont diverses et les contraintes sont multiples. De plus les individus ne partagent pas nécessairement toutes leurs informations. Nous considérerons une résolution distribuée et nous testerons ainsi différentes méthodes.


===== SA4. Partage dynamique d’énergie verte entre des ilots autonomes et des véhicules connectés=====
^ Domaine | Intelligence Artificielle|
^Langage (proposé) | C++, java |
^ Responsable du sujet | Samir AKNINE                                          | 
Plusieurs projets urbains innovants d’ilots autonomes tels que le projet du groupe Bouygues-construction pour la gestion intelligente de l’énergie traitent du problème du partage dynamique de l’énergie avec son réseau de communication énergétique et un système de stockage par des batteries de nouvelle génération directement installées dans les bâtiments. Ce projet vise à équiper les foyers avec de nouveaux dispositifs intelligents pour éprouver des solutions originales pour les futurs réseaux de distribution.  Il cible l’ouverture des  réseaux  et l’exploitation automatique des îlots. L’évolution actuelle de ces ilots est renforcée grâce au développement de nouvelles batteries de stockage à fort potentiel et à faibles coûts, et au transfert intelligent de l’énergie entre les ilots avec un câblage interne indépendamment des systèmes de distribution classiques. Ce transfert permet d’envisager une adaptation de la consommation de manière locale, i.e., à l’échelle d’un quartier, en réduisant les coûts et les pertes du transport de l’énergie. 

Pour accompagner le développement de ce projet, une solution pour la gestion du surplus d’énergie s’est inscrite en direction des véhicules autonomes solution de stockage et d’usage intelligent de l’énergie renouvelable. Ce modèle de fonctionnement requière l’installation de bornes de rechargement communicantes au niveau des ilots autonomes permettant aux résidents et aux non-résidents de l’ilot d’accéder au surplus d’énergie produite dans ces ilots moyennant une participation financière mais avec un coup d’achat de cette énergie relativement inférieur à celui appliqué par les fournisseurs standards. La gestion de l’énergie doit ainsi être reformulée comme un problème de planification où l’énergie fournie est considérée comme une ressource partagée et intermittente dont l’usage doit être régulé et optimisé par ce nouveau système intelligent. 
L’objectif de ce projet est ainsi d’implémenter une méthode de résolution qui permet aux véhicules de se recharger auprès des bornes intelligentes et de contrôler dynamiquement les interactions entre les véhicules autonomes et les bornes. 





===== AM1. Capture et transfert d'animation d'un visage vers un autres par image warping et Deep Learning (GAN) =====

^ Domaines                                                                                | Image Processing / Deep Learning |
^ Techniques et langages                                                                  | Python  |
^ Responsable du sujet                                                                    | Alexandre Meyer   |
^ Difficulté                                                                              | Sujet raisonnable et progressif |


L'objectif de ce projet est de developpé un algorithme capable de modifier/éditer le visage d'une personne filmé : par exemple rendre son discours plus joyeux, piloter le visage d'une autre personne, etc. La capture de l'animation du visage source se fera en detectant les points caractéristiques d'un visage filmé avec une webcam en utilisant DLib (python ou C++). 

Un premier prototype se fera en générant une nouvelle position de marqueurs de visage puis en réalisant un warping (déformation) de l'image du visage cible. Une interpolation par RBF (ou autre) semble une solution réalisable.

Le deuxième aspect porte sur l'apprentisasge profond dont certains algorithmes (GAN, autoencoder) sont capables d'apprendre à générer de nouvelles données. Ces algorithmes ont montré de très bonnes capacités pour la génération de nouveau visage : vieillissement, modification de l'expression, de la couleur des cheveux, etc.

[[https://medium.com/@jonathan_hui/gan-some-cool-applications-of-gans-4c9ecca35900|GAN — Some cool applications of GANs.]] 


===== AM2. Edition interactive de nouvelles images d'objets par une série d'auto-encodeurs locaux =====

^ Domaines                                                                            | Image Processing / Deep Learning / Interaction |
^ Techniques et langages                                                              | Python  |
^ Responsable du sujet                                                                | Alexandre Meyer   | 
^ Niveau de difficulté                                                                | difficile  |    

L'objectif de ce projet est de developpé une application capable de proposer des curseurs pour éditer la photo d'une classe d'objet (par exemple des visages d'une personne) en se basant sur des auto-encodeurs. 

Les auto-encoders sont une classe d'algorithme basée sur les réseaux de neurones profonds qui transforment un jeu de données (des images pour nous) en une représentation latente (cachée) que l'on nomme un code. Ils sont composés d'un encodeur qui produit le code et d'un décodeur qui repasse du code à la données d'origine (l'image). L'objectif de ce sujet est de construire cet auto-encoder sur une classe d'images puis d'offrir à l'utilisateur des curseurs pour éditer le code tout en lui montrant l'image décodé. 

Dans un 2e temps, par exemple pour l'édition d'un visage, nous pouvons imaginer construire un auto-encoder pour chaque partie du visage : nez, yeux, bouche. L'utilisateur pourra ainsi éditer chaque partie du visage séparément.










===== AM3. Unity et Apprentissage Par Renforcement =====

^ Domaines                                                   | IA et Image/Jeu vidéo |
^ Techniques                                                 | Apprentissage par renforcement   |
^ Langages                                                   | C# / Unity et éventuellement python |
^ Responsable du sujet                                       | Alexandre Meyer                                           |
^ Difficulté                                                 | Intermédiaire |

Unity est un framework devenu hyper classique pour le développement de jeux vidéo. Ce sujet se propose de vous faire explorer trois aspects.
   * La création d'un ou des mini jeu avec Unity.
   * Les algorithmes classique d'apprentissage par renforcement (QLearning, etc.) pour qu'un programme joue automatiquement aux mini jeux.
   * Et les outils mise à disposition des développeurs Unity pour qu'une "IA" apprenne à jouer à un jeu via tout une série d'algorithmes d'apprentissage par renforcement déjà codés mais si évident à entrainer sans une bonne compréhension du problème (ML-Agent). 

C'est un sujet assez exploratoire et demandant une bonne capacité à aller se documenter seul sur les différents algorithmes qu'il sera possible de mettre en place. Vous viserez un mini jeu déjà développé et dans un 1er temps vous mettrez en place une IA très basique, voir même jouant au hasard en ne gardant que les meilleurs actions.

   * [[https://medium.freecodecamp.org/an-introduction-to-q-learning-reinforcement-learning-14ac0b4493cc|An introduction to Q-Learning: reinforcement learning]]
   * [[https://becominghuman.ai/teaching-ai-to-play-flappy-bird-with-unity-70f7b661663d| Teaching AI to play Flappy Bird with Unity]]
   * [[https://skymind.ai/wiki/deep-reinforcement-learning| A Beginner's Guide to Deep Reinforcement Learning]]
   * [[ https://unity3d.com/fr/machine-learning | ML-Agent : Unity et Apprentissage Machine ]]                                



===== AM4. Développement d'un jeu vidéo sous Unity piloté par les mouvements du corps =====

^ Domaines                                                                                | Capture de mouvement/Interaction/Jeu vidéo |
^ Techniques et langages                                                                  | C# / Unity  |
^ Responsable du sujet                                                                    | Alexandre Meyer |
^ Difficulté                                                                              | Raisonnable / Intermédiaire |

La capture de l'animation d'un visage ou du corps via une webcam peut facilement être réalisé avec OpenPose (il faut néanmoins une machine avec un GPU Nvidia), ou DLIb pour juste le visage. Ce projet ce propose de developper un (ou des mini jeux) sou Unity pensés pour que l'interaction se fasse avec son corps filmé par la webcam de son ordinateur. On peut imaginer dans un premier temps un mini jeu avec des ballons qui tombent du ciel et qu'il faut attrapper soit avec les mains (corps), soit avec la tête (DLib). Puis si ces outils sont bien maitrisés, libre à vous d'imaginer tout type de jeu : voir les jeux basés sur la Kinect ou Wii avec le même type d'interaction.



=====RC1. Application web de visualisation et d’interprétation de consommation électrique personnelle  =====

^ Domaines                | data science, visualisation, web               |
^ Librairies (proposées)  | scikit-learn, bootstrap                        |
^ Langages (proposé)      | Python, javascript, html/css…                  |
^ Responsable du sujet    | Rémy Cazabet                                   |
^ Informations à voir     | http://cazabetremy.fr/Teaching/LIFPROJET.html  |
|                                                                         ||

Les compteurs électriques intelligents (Linky) permettent de suivre notre consommation électrique demi-heure par demi-heure. Vous développerez une application web pour permettre à chacun de comprendre (et idéalement de réduire...) sa consommation électrique. Un projet précédent a accompli les premières étapes (script de récupération des données...), mais n'a pas mis en place d'outils de fouille de données ni de visualisation avancé. Vos objectifs seront notamment de convertir la consommation en kw/h collectée en une information compréhensible (euros par heure, ..), d'essayer de détecter automatiquement des patterns d'utilisation (ballon d'eau chaude, consommation lors des repas, etc.) et de permettre à l'utilisateur d'explorer les données le concernant.

=====RC2. Plateforme d’exploration de l’activité de recherche à Lyon   =====

^ Domaines                                                  | data science, visualisation, traitement automatique de la langue  |
^ Librairies (proposées)                                               | scikit-learn, bootstrap   |
^ Langages (proposé)                                                   | Python, javascript, html/css… |
^ Responsable du sujet                                              | Rémy Cazabet                   |                                                                            
^ Informations à voir                                          | [[https://hal-udl.archives-ouvertes.fr |  Portail de l'université de Lyon]]                                                                                     ||
|                                                           ||

Les informations des publications scientifiques des chercheurs de Lyon sont accessibles en ligne via un site web qui offre une API. Vous développerez une application (web ou non) utilisant des outils de fouille de données (Clustering, analyse de réseaux, traitement automatique du language ...) pour permettre d'exploiter ces données. Par example, l'application permettra de détecter automatiquement les sujets "à la mode" (Deep learning...), de visualiser des graphes thématiques, des collaborations entre laboratoires, etc.

=====RC3. Kaggle Challenge    =====

^ Domaines                                                  | Machine Learning ("Intelligence Artificielle") |
^ Librairies (proposées)                                               | scikit-learn, keras, tensor-flow...    |
^ Langages (proposé)                                                   | Python, autre |
^ Responsable du sujet                                              | Rémy Cazabet                   |                                                                            
^ Informations à voir                                        | [[https://www.kaggle.com/competitions | Challenges Kaggle en cours]]                                                                                     ||
|                                                           ||
[[https://www.kaggle.com/competitions | Kaggle]] est le site web le plus connu de challenges en machine learning. En 2 mots: des entreprises proposent des challenges auxquels n'importe qui peut tenter de proposer une solution. La meilleure solution gagne. Mais là où Kaggle est particulièrement intéressant, c'est qu'il propose des tutoriels pour résoudre certains problèmes classiques, en utilisant différentes méthodes. Votre objectif: 1) Suivre un/des tutoriels pour résoudre un problème tout fait, 2)Choisir un challenge en cours et appliquer ce que vous avez appris

=====RC4. Restaurants à Lyon    =====

^ Domaines                | Visualisation, exploitation de données                |   |
^ Librairies (proposées)  | mapbox, leaflet, d3                                   |   |
^ Langages (proposé)      | javascript, html/css, language back-end (python?...)  |   |
^ Responsable du sujet    | Rémy Cazabet                                          |   |
^ Informations à voir     | [[http://lif.sci-web.net:2018]]                          ||
|                                                                                ||   |
Le but de ce projet est de créer une carte interactive des restaurants/bars (et/ou autres lieux) de Lyon, avec pour objectif de faire un vrai site utile.
Attention ! Ce projet est réservé à une équipe motivée, car il est INDISPENSABLE de faire mieux que le travail précédent, qui est déjà le résultat de 3 projets successifs. Il est donc obligatoire de réutiliser une partie du travail déjà effectué (tous les codes sont disponibles). Plusieurs éléments sont à travailler: amélioration de l'interface, ajout de données de sources différentes (actuellement: Google maps et un peu Yelp), solution pour supprimer les temps de chargement, ajout de quelques fonctionnalitées de "fouille de données" (exploitation des commentaires, notes, textes descriptifs, ...).

=====RC5. Librairie de clustering de graphe    =====

^ Domaines              | Machine Learning (IA), génie logiciel, logiciel libre  |   |
^ Librairies            | - la votre :)                                          |   |
^ Langages (proposé)    | python, interfacage avec du c                          |   |
^ Responsable du sujet  | Rémy Cazabet                                           |   |
^ Informations à voir   | http://cazabetremy.fr/Teaching/LIFPROJET.html             ||
|                                                                               ||   |
Nclib (Network Community Library) est une librairie de machine learning, développé en python pour le problème du clustering de graphe, aussi appelé detection de communautés. Il s’agit d’une librarie encore en phase bêta, donc non publique, dont le but est de rassembler un ensemble d’algorithmes pour répondre à ce problème. Elle est pour l’instant développé par 2 chercheurs au sein du projet européen SoBigData (http://sobigdata.eu/index).
Dans le cadre de ce projet, vous contribuerez en ajoutant des algorithmes publiés mais non présents dans la librairie (d'autres contributions sont possibles). Selon votre intérêt et vos compétences, il pourra s’agir de faire le pont avec des librairies existantes, par exemple: https://graph-tool.skewed.de, d’intégrer des méthodes récentes basées sur les réseaux de neurones, voire de ré-implémenter des méthodes existantes dont le code ne serait pas disponible ou non-compatible.

Une attention particulière sera portée à produire un code propre et standard, (tests unitaires, commentaires adaptés à une génération automatique de documentation, etc.) pour qu’il soit intégré à une libraire de recherche publique.
Il s’agit également d’une bonne introduction au machine learning/ intelligence artificielle.

=====MM1. Amélioration de contraste d'images =====

^ Techniques                                                                               | Manipulation d'images (matrices), interface graphique  |
^ Responsable du sujet                                                                                                                             ||
|                                                                                          | Matthieu Moy                                           |
^ Informations à voir                                                                                                                              ||
|                                                          [[https://matthieu-moy.fr/cours/lifprojet/contraste.html|Sujet et consignes détaillés]] ||

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éveloppement 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.

=====MM2. Contribution à un logiciel libre =====

^ Techniques                                                                               | Génie logiciel, gestion de version  |
^ Responsable du sujet                                                                                                                             ||
|                                                                                          | Matthieu Moy                                           |
^ Informations à voir                                                                                                                              ||
|                                                          [[https://matthieu-moy.fr/cours/lifprojet/libre.html|Sujet et consignes détaillés]] ||


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é ;-) (c'est un vrai point important sur un CV).

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

======CAPES======
Ces sujets sont réservés aux étudiants de CAPES math option info.

===== MM11. Algorithme de cryptographie à clef publique RSA =====
^ 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. [[https://fr.wikipedia.org/wiki/Chiffrement_RSA|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 ils nécessitent 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 :
  - générer la clef;
  - chiffrer avec la clef publique et déchiffrer avec la clef secrète;
  - chiffrer avec la clef secrète et déchiffrer avec la clef publique (pour signer).

==Améliorations==
Comme amélioration vous pourrez :
  * implémenter d'autres algorithmes de chiffrement;
  * créer un petit logiciel de connexion à distance sécurisé.

=====MM12. Tests de connexité=====
^ Techniques                                                                               | Parcours de graphes, connexité  |
^ Responsable du sujet                                                                                                                             ||
|                                                                                          | Fabien Rico                                           |
^ Informations à voir                                                                                                                      ||
| [[https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model]] ||
| [[https://fr.wikipedia.org/wiki/Union-find]] ||

===Objet du projet===
Pour savoir si un graphe (non orienté, non pondéré) est connexe, on peut utiliser différents algorithmes :
  - si on dispose de la matrice d’adjacence, on peut utiliser un algorithme de type Warshall ;
  - si le graphe est fourni par listes d’adjacences, on préférera un parcours du graphe en profondeur ;
  - si le graphe est donné par une suite d’arêtes (éventuellement de façon dynamique), on peut également utiliser l’algorithme union/find qui permet de gérer à la volée le nombre de composantes connexes.

===Les attendus===
  - Implémenter deux des trois points de vue présentés plus haut (mais les trois, c’est mieux !).
  - Être capable d’exposer ces algorithmes à l’oral, en particulier leur(s) complexité(s).
  - Présenter des tests convaincants de petite taille.
  - Tester le programme sur un grand nombre de graphes générés aléatoirement avec N sommets et N ln N arêtes. Estimer la proportion de graphes connexes.

=== En bonus ===
Voici divers points que vous pourrez choisir de développer :
  - Une interface utilisateur (en console, ou graphique) permettant d’entrer un graphe.
  - La possibilité de lire un graphe dans un fichier texte, sous un format que vous aurez spécifié.
  - Comparer les différentes méthodes sur des tests à grande échelle.
  - Après être allé consulter la littérature sur le sujet, faire des tests permettant d’illustrer les résultats d'Erdös et Rényi sur les seuils de connexité pour un graphe aléatoire : si on place $\frac{N(K+\ln N)}{2}$ arêtes dans un graphe à $N$ sommets, alors la probabilité d'être connexe tend vers $e^{-e^{-K}}$ lorsque $N$ tend vers $+\infty$.


===== MM13. Problème du voyageur de commerce =====
^ Techniques                                                                               | complexité, arbre couvrant minimum  |
^ Responsable du sujet                                                                                                                             ||
|                                                                                          | Fabien Rico                                           |
^ Informations à voir                                                                                                                      ||
| [[https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce]] ||
| [[https://fr.wikipedia.org/wiki/Algorithme_de_Christofides]] ||

=== Objet du projet ===

Le problème du [[https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce|voyageur de commerce]] est un problème d'algorithmique très connu où à partir d'un graphe des villes et de routes reliant ces villes, on recherche un chemin qui passe une et une seule fois par chacune des villes et dont la longueur est minimale.

Ce problème est NP-complet ce qui signifie qu'il ne peut sans doute pas être résolut efficacement en temps raisonable, mais (dans certains cas) il existe des moyens de calculer une approximation par exemple, si les distances entre les villes obéïssent à l'inégalité triangulaire, il est possible d'utiliser l'algorithme de [[https://fr.wikipedia.org/wiki/Algorithme_de_Christofides|Christofides]] qui donne une solution au pire égale à 3/2 de la solution optimale.

=== Les attendus ===

Vous devez implémenter l'algorithme de Christofides. Votre logiciel doit partir d'un fichier contenant les villes et le coût des liaisons directes entre les ville et fournir le chemin trouvé. 

=== En bonus ===
Pour améliorer l'algorithme vous pouvez :
  - Développer un interface graphique pour présenter les résultats (et leur différentes étapes)
  - Utiliser d'autres méthodes de résolution, par exemple la solution naive (pour calculer la solution optimale), l'utilisation des méthodes d'optimisation ...