• Programmation numérique par agents mobiles proposé par Fabrice MOURLIN (LACL / université Paris 12 - Créteil)
• Dynamiques de graphes proposé par Matthieu LATAPY (LIP6 - CNRS et UPMC - Paris)
• Modélisation des graphes de terrain proposé par Matthieu LATAPY (LIP6 - CNRS et UPMC - Paris)
• Leveraging multiple experimentation methodologies to study P2P broadcast proposé par Lucas NUSSBAUM (LORIA - Nancy)
• Real-time online emulation with Simterpose proposé par Lucas NUSSBAUM (LORIA - Nancy)
• Evaluation des outils de mutation proposé par Lydie DU BOUSQUET (Laboratoire d'informatique de Grenoble - Grenoble)
• Energy- and Thermal-Aware Scheduling on clusters proposé par Georges DA COSTA (IRIT, Université de Toulouse - Toulouse)
• Energy Aware Co-Scheduling CPU/GPU proposé par Georges DA COSTA (IRIT, Université de Toulouse - Toulouse)
• Mathematical modeling of energy consumption of Cloud applications proposé par Georges DA COSTA (IRIT, Université de Toulouse - Toulouse)
• Fluid models for energy savings in clouds using VM migration proposé par Georges DA COSTA (IRIT, Université de Toulouse - Toulouse)
• Faster (HPC), Higher (energy-efficiency), Stronger (characterization): DVFS for HPC proposé par Georges DA COSTA (IRIT, Université de Toulouse - Toulouse)
• Compilation de circuits sécurisés pour la cryptographie sur les courbes elliptiques proposé par Arnaud TISSERAND (IRISA - LANNION)
• Isolation de racines complexes de polynomes proposé par Paul ZIMMERMANN (INRIA/LORIA - Nancy)
• Trnasformations LOCC en theorie quantique de l'information proposé par Ion NECHITA (LPT Toulouse - Toulouse)
• Comparaison des outils d'analyse pour les programmes numeriques proposé par Radu IOSIF (VERIMAG - Grenoble)
• Code based signature schemes with special properties proposé par Pierre-Louis CAYREL (Laboratoire Hubert Curien - SAINT-ETIENNE)
• Physical attacks and code-based cryptosystems proposé par Pierre-Louis CAYREL (Laboratoire Hubert Curien - SAINT-ETIENNE)
• Machines de Matiyasevich proposé par Alexis BES (LACL, UPEC - Créteil)
• Étiquetage Compact de la Logique du Premier Ordre dans les Graphes d\\\'Expansion Bornée proposé par Mamadou KANTÉ (LIMOS - Clermont-Ferrand)
• Algorithmes parallèles pour l\'optimisation de la transmission en IRM proposé par Jean-Christophe PESQUET (Laboratoire d\'Informatique Gaspard Monge - Champs sur Marne)
• Elaboration et développement d’un algorithme évolutionnaire pour l’optimisation de performances d’un système embarquée temps réel : Application à une architecture complète d'un véhicule équipée de technologie X-by-wire proposé par Khaled CHAABAN (ESTACA, Equipe Systèmes Emabrqués - LAVAL (FRANCE))
• Communautés d’individus et dynamique de mots-clefs sur Twitter proposé par Bertrand JOUVE (IXXI/ERIC/ENS Lyon - Lyon)
• Triangulating the Klein bottle and other manifolds proposé par Jean-Daniel BOISSONNAT (INRIA Sophia Antipolis Equipe Geometrica - Sophia Antipolis)
• Aspects numériques de l'algorithme LLL proposé par Damien STEHLE (LIP - LYON)
• PDL Model-Checking on Parse Trees proposé par Sylvain SCHMITZ (LSV, ENS Cachan - Cachan)
• Etude de la complémentarité entre différentes modélisations informatiques pour l'analyse de la traduction du cycle cellulaire chez l'oursin proposé par Olivier ROUX (IRCCyN - Nantes)
• Nearest Neighbor Searching proposé par Mariette YVINEC (INRIA - Sophia Antipolis)
• Formal proof of decision procedures for the combinations of equational theories proposé par Pierre WEIS (INRIA - Rocquencourt ou Pekin)
• Analyse de descripteurs d'images pour GPU proposé par Charles-Edmond BICHOT (LIRIS (Lyon) - Lyon)
• Algorithmes évolutionnaires pour la création de descriteurs d'image performants proposé par Charles-Edmond BICHOT (LIRIS - Lyon)
• Sélection d'équilibre dans des jeux et processus de revision proposé par Bruno GAUJAL (inria - Montbonnot)
• Problèmes proies-prédateurs proposé par Corinne TOUATI (Inria - Grenoble - Montbonnot)
• Algorithme de calcul de la dimension d'un ordre partiel proposé par Vincent LIMOUZY (LIMOS - Université Blaise Pascal - Clermont Ferrand)
• Problème de partitions de graphes: résolution par la méthode des plans-coupants proposé par Vincent LIMOUZY (LIMOS - Clermont Ferrand)
• Performance des arbres rouge/noir Performance des arbres "rouge/noir" proposé par Nicolas BROUTIN (Inria Paris-Rocquencourt - Le Chesnay)
• Complexité de la factorisation des polynômes lacunaires proposé par Bruno GRENET (LIP, ENS Lyon - Lyon)
• Etude des 2-générateurs minimaux proposé par Guillaume FERTIN (LINA, UMR CNRS 6241 - Nantes (44000))
• Fonctions élémentaires efficaces proposé par Florent DE DINECHIN (LIP - Lyon)
• Une machine chimique universelle proposé par Herve GRALL (Ecole des mines de Nantes - NANTES)
• Analyse textuelle de scripts de films pour ameliorer le reperage d'actions dans les videos de ces films proposé par Marie CANDITO (Alpage - Paris 7 - Paris) (choisi par Thimothee BERNARD)
• Les groupes d’automates proposé par Ines KLIMANN (LIAFA - Paris) (choisi par Quentin BOLLE)
• Mise en place une application en PHP ou C++ qui compl�te automatiquement � partir de l�API de twitter les fichiers de donn�es fournis par Datasift. proposé par Bertrand JOUVE (ERIC/IXXI - ) (choisi par Hadrien CROUBOIS)
• G�n�ration de Javascript par d�compilation dirig�e par les types proposé par Vincent BALAT (PPS - Paris) (choisi par Raphaelle CRUBILLE)
• Relaxation de certaines configurations bidimensionnelles dans le modèle du tas de sable. proposé par Yvan LE BORGNE (LaBRI - Talence (voisine de Bordeaux)) (choisi par Henri DERYCKE)
• Parallélisation du partitionnement de graphe sur GPU proposé par Charles-Edmond BICHOT (LIRIS - Lyon) (choisi par Xavier DUMONT)
• Apprentissage d'équilibres optimaux dans les jeux de potentiels proposé par Corinne TOUATI (Inria - Grenoble - Montbonnot) (choisi par Stephane DURAND)
• Recherche de preuves compilée en logique intuitionniste proposé par Didier GALMICHE (LORIA - Nancy) (choisi par Adrien DURIER)
• Intégration de Z3 en Coq proposé par Chantal KELLER (LIX - Palaiseau) (choisi par Gaetan GILBERT)
• Approximation numerique dans un dictionnaire de fonctions speciales produit automatiquement proposé par Marc MEZZAROBBA (LIP, ENS de Lyon - Lyon) (choisi par Thomas GREGOIRE)
• Fonction d'Ackermann et automates à compteurs relationnels proposé par Philippe SCHNOEBELEN (Dept. Computer Science, Univ. Oxford - Oxford, Angleterre) (choisi par Benjamin HADJIBEYLI)
• Algortihme BKZ (Block Korkin-Zolotarev) proposé par Guillaume HANROT (LIP - Lyon) (choisi par William LOCHET)
• Linéarité des graphes proposé par Christophe CRESPELLE (LIGM (Marne-la-Vallée) ou LIP (Lyon) - Marne-la-Vallée ou Lyon) (choisi par Oreste MANOUSSAKIS)
• Reconnaissance de la main en pose ouverte / non-ouverte proposé par Pierre FILLARD (equipe Parietal, INRIA Saclay - Sophia Antipolis) (choisi par Gautier MARTI)
• proposé par Emmanuel BEFFARA (IML - Marseille) (choisi par Antoine MOTTET)
• Formal proof of decision procedures for the combinations of equational theories proposé par Frederic BLANQUI (INRIA - Rocquencourt ou Pekin) (choisi par Remi NOLLET)
• Transformation de preuves en logique bi-intuitionniste proposé par Didier GALMICHE (LORIA - Nancy ) (choisi par Louis PARLANT)
• Jeu du gendarme et du voleur et delta-hyperbolicite proposé par Victor CHEPOI (LIF - Marseille) (choisi par Timothee PECATTE)
• Analyse des usages de Twitter : d�tection du registre de langue et influence sur le choix de la langue. proposé par Jean-Philippe MAGUE (ICAR - Lyon) (choisi par Luc ROCHER)
• Phénomènes de diffusion sur les grands réseaux : mesure et analyse pour la modélisation proposé par Matthieu LATAPY (LIP6 - CNRS et UPMC - Paris) (choisi par Matthieu ROSENFIELD)
• Hash functions based on the syndrome decoding problem proposé par Pierre-Louis CAYREL (Laboratoire Hubert Curien - SAINT-ETIENNE) (choisi par Quentin SANTOS)
• Structure Multi-échelles des Grands Graphes proposé par Matthieu LATAPY (LIP6 - CNRS et UPMC - Paris) (choisi par Maxime SAVARO)
• Dynamique d'un mouvement articul� et reconnaissance de gestes proposé par Guillaume CHARPIAT (Stars - INRIA Sophia Antipolis - Sophia Antipolis) (choisi par Bertrand SIMON)
• Algorithme de Llyod dans l'espace périodique 3D proposé par Monique TEILLAUD (INRIA - Sophia Antipolis) (choisi par Mathieu SCHMITT)
• On Morse-Smale decomposition of cryo-electron microscopy density maps proposé par Frederic Cazals (INRIA Sophia-Antipolis-Mediterranee - Sophia Antipolis) (choisi par Romain TETLEY)
• Un radar pour l\'internet proposé par Matthieu LATAPY (LIP6 - CNRS et UPMC - Paris) (choisi par Weiyang WU)

Encadrement   Encadrant : Fabrice MOURLIN Labo/Organisme : LACL / université Paris 12 Ville : Créteil

Description   Une plateforme logicielle, nommée MCA a déjà été développé au LACL. Elle offre la possibilité par l\'emploi d\'agents mobiles de faire de la reprise d\'exécution en cas d\'anomalie. Des cas de calcul ont déjà été réalisés pour des algorithmes de référence: calcul de Choleski, méthode de résolution de Cardan. Si ces cas permettent de confirmer la validité de l\'approche, il est nécessaire d\'enrichir ces étude de cas afin de montrer qu\'une architecture de calcul peut être partagée et reconfigurer en cours d\'exécution si nécessaire. Pour cela, il est important d\'étudier des cas plus importants tels que: calcul de différence finie, résolution d\'équation de Maxwell (schéma leap frog) sur des volumes discrétisés. Les résultats sont à comparer avec d\'autres plateforme de calcul telle que Salomé ou d\'autres outils tels que scilab. Les critères communs sont la maintenabilité des calculs de calcul, la gestion des données de calcul mais aussi leur sécurité. Remarques: indemnité forfaitaire fournie par le laboratoire. Co encadrement avec Cyril Dumont

Encadrement   Encadrant : Matthieu LATAPY Labo/Organisme : LIP6 - CNRS et UPMC Ville : Paris

Description   L\'étude des grands graphes apparaissant en pratique a connu ces dernières années un essor hors du commun. Les objets étudiés sont d\'origines diverses, comme par exemple la topologie de l\'internet (machines et câbles), les graphes du web (pages et liens), les échanges pair-à-pair (qui échange des données avec qui), mais aussi les réseaux sociaux, les réseaux biologiques ou les réseaux linguistiques. La plupart de ces graphes ne sont pas fixes. Au contraire, ils évoluent au cours du temps : des sommets et/ou des arêtes apparaissent et disparaissent. Cette dynamique joue un rôle essentiel dans de nombreux cas. Par exemple, la dynamique du web peut permettre d\'identifier des thèmes émergents, celle des échanges permet d\'étudier les comportements des utilisateurs (et d\'utiliser ces résultats pour optimiser les protocoles), la dynamique de l\'internet permet d\'étudier sa fiabilité, etc. Or, il est en général délicat de capturer ces dynamiques et, même lorsque des données sont disponibles, il est non-trivial de les décrire et de les analyser. Cette problématique, bien qu\'identifiée comme essentielle, reste donc encore aujourd\'hui largement à défricher. Le but de ce stage sera d\'explorer quelques idées émergentes pour ce faire, sur la base de cas concrets. Accéder au sujet détaillé

Encadrement   Encadrant : Matthieu LATAPY Labo/Organisme : LIP6 - CNRS et UPMC Ville : Paris

Description   Dans de très nombreux contextes applicatifs, on rencontre de grands graphes n'ayant aucune structure simple apparente, que nous appellerons graphes de terrain (par opposition aux graphes explicitement contstruits par un modèle ou une théorie). Citons par exemple la topologie de l'internet (routeurs et câbles entre eux), les graphes du web (pages web et liens hypertexte entre elles), les échanges divers (pair-à-pair, e-mail, etc), mais aussi les réseaux sociaux, biologiques ou linquistiques. Il est apparu récemment que la plupart de ces grands graphes ont des propriétés statistiques en commun, et que ces propriétés les différencient fortement des graphes aléatoires utilisés jusqu'alors pour les modéliser. Depuis, une intense activité a été développée pour proposer des modèles plus adapté. L'état de l'art reste toutefois largement insuffisant. Nous proposons dans ce stage d'explorer deux nouvelles voies particulièrement prometteuses (voir le pdf). Accéder au sujet détaillé

Encadrement   Encadrant : Lucas NUSSBAUM Labo/Organisme : LORIA Ville : Nancy

Description   L\'objectif de ce stage est de combiner différentes méthodologies expérimentales (simulation avec SimGrid, expérimentation en conditions réelles sur Grid\'5000) pour répondre à une question relativement simple (l\'aptitude de BitTorrent à être utilisé pour de la diffusion de données sur des réseaux à hautes performances). Le principal résultat attendu n\'est pas la réponse à la question, mais plutôt le cheminement méthodologique ayant permis d\'y arriver. Voir le sujet détaillé pour plus d\'informations. Accéder au sujet détaillé Remarques: Co-encadré avec Martin Quinson ( http://www.loria.fr/~quinson/ )

Encadrement   Encadrant : Lucas NUSSBAUM Labo/Organisme : LORIA Ville : Nancy

Description   Simterpose a pour objectif de permettre l'exécution d'applications réelles dans un environnement virtuel simulé par le simulateur SimGrid, afin de pouvoir étudier des applications distribuées (Cloud, grilles, HPC, P2P, ...). L'objectif de ce stage est de poursuivre le développement de Simterpose (en C sous Linux) en levant les différents verrous scientifiques et techniques qui se présenteront au fur et à mesure. Voir le sujet détaillé pour plus d'informations. Accéder au sujet détaillé Remarques: Co-encadré avec Martin Quinson ( http://www.loria.fr/~quinson/ )

Encadrement   Encadrant : Lydie DU BOUSQUET Labo/Organisme : Laboratoire d'informatique de Grenoble Ville : Grenoble

Description   Tester est la méthode de validation la plus utilisée dans l'industrie. C'est une approche souvent empirique : le choix des tests est toujours un peu aléatoire et il est donc difficile de garantir la qualité des tests obtenus. Dans le monde de la recherche, une approche a été proposé pour évaluer les tests : l'analyse mutationnelle. Le principe consiste à injecter des fautes dans le programme sous test et de s'assurer que les tests découvrent ces fautes. Il existe plusieurs outils (essentiellement universitaires) pour insérer les fautes et jouer les tests. Le but du stage est de recenser les outils qui existent pour la mutation de programmes Java (et éventuellement autres) et de les essayer pour répondre aux questions suivantes : 1) quelles fautes peuvent être introduites dans le programme ? 2) quelles sont les caractéristiques que doit avoir le programme sous test pour utiliser l'outil ? 3) quelles sont les caractéristiques que doivent avoir les tests pour utiliser l'outil ? 4) quelles fonctionnalités de l'outil ? 5) quelle documentation ? Quelle performance ? 6) autres questions à déterminer. Le plan de travail consistera à (1) faire une étude bibliographique sur la mutation et sur la conduite d'analyse empirique, (2) télécharger et installer les outils (3) mettre en place et conduire l'expérimentation (4) rédiger le rapport et un article. Remarques: Le stage sera co-encadré par un post-doc de l'équipe. Si le travail avance bien, une seconde analyse empirique pourra être menée pour déterminer la faciliter à découvrir les fautes introduites (pour l'outil le plus classique, à savoir MuJava).

Encadrement   Encadrant : Georges DA COSTA Labo/Organisme : IRIT, Université de Toulouse Ville : Toulouse

Description   At IRIT-University of Toulouse (one of the largest and best computer science laboratory in France: more than 600 researchers), our group (7 permanent researchers, 1 PostDoc, 9 PhD) is currently working on Energy Efficiency for Large Scale Distributed Systems. CoolEmAll project, funded by the European Commission under the STREP FP7 program aims at providing advanced planning and optimization tools for modular data centre environments. In this Internship we will study techniques for the placement and scheduling of tasks in such modular environments, going beyond the traditional load factor, taking into account the dissipated heat with the final goal of minimizing the overall energy consumption of the centre, including cooling infrastructure as well. The student will have to choose either theoretical foundations or practical implementations: * The formalization of the overall problem in linear programming, its optimal or relaxed solutions will be evaluated. Heuristics can be proposed to solve the problem. In order to compare solutions a first step will be obviously to define appropriate metrics extending existing ones (PUE, ERE) for our specific case. * The practical approache will be to design a simulator to simulate actual environments under several workload conditions.

Encadrement   Encadrant : Georges DA COSTA Labo/Organisme : IRIT, Université de Toulouse Ville : Toulouse

Description   At IRIT-University of Toulouse (one of the largest and best computer science laboratory in France: more than 600 researchers), our group (7 permanent researchers, 1 PostDoc, 9 PhD) is currently working on Energy Efficiency for Large Scale Distributed Systems. IT consumption accounts for 2% of the total energy consumption (at the same level of airline industry) while data centers alone account for 14% of the ICT footprint. It is projected that by 2020 the energy demand of data centers will represent 18% of the ICT footprint, the carbon footprint increases at an annual 7% pace, doubling between 2007 and 2020. Our goal is to reduce this energy consumption using currently available GPGPU accelerators. A large part of data center computing is related to HPC (High Performance Computing) that can benefit from using such accelerators. However, their benefit depends on the workload and the most efficient usage is to use at the same time CPU and GPU, allocating applications or part of application on the best computing element. The goal of this Internship is to design/implement/evaluate scheduling of HPC tasks on hybrid CPU/GPU architectures that takes into account energy and performance. The student will first use a simulator we developed for hybrid (CPU/GPU) architectures. Then, using this simulator, the student will evaluate several co-scheduling approaches, assessing the relationship between energy and performance for optimal scheduling. Once interesting scheduling algorithms are found, experiments will be done on real hybrid platforms for validation.

Encadrement   Encadrant : Georges DA COSTA Labo/Organisme : IRIT, Université de Toulouse Ville : Toulouse

Description   As computers are ubiquitous, people use large amount of computing power without even realizing the complexity of their requests. Computing infrastructures follow the same trend. By packing more and more computing power in less space, by being blind to application running on those infrastructures, clouds' providers consume large amount of energy while being unable to manage their infrastructure smartly. Knowledge is power. In order to efficiently manage Cloud infrastructures applications behavior have to be known precisely. Although there is large body of works done in the area of the energy efficient management of virtual and physical machines, energy efficiency at the application level is still an open issue. In this internship we will develop mathematical models linking energy consumption of applications and systems values of those applications (such as performance counters, I/O, network counters,...). These models are necessary as there exist no hardware able to measure energy consumption of one particular application running on one computer. Current models lack precision (current state of the art is between 5 to 10\% precision, depending on context) or generality (some particular applications or the simplest elements of a computer). Once the models more precise, they will allow cloud providers to explicitly advertise energy consumption of users' application. Users will know better their impact and will change their behaviour for the better.

Encadrement   Encadrant : Georges DA COSTA Labo/Organisme : IRIT, Université de Toulouse Ville : Toulouse

Description   Energy consumption of cloud infrastructure starts to be problematic. A good way to improve energy efficiency is to manage in a precise way tasks running on this infrastructure. One key problematic is to choose which task to move, and where to move them. It is even more complex as this decision is done to satisfy opposite constraints: Performance and Energy consumption. As it is difficult to test and evaluate designed decision algorithms managing VM, we will focus on designing models of tasks migration. These models will help testing and comparing different decision algorithms. This internship will explore mathematical models based on differential equation techniques, known as Fluid models. Such model will be efficient and fast to manage large number of tasks. The mathematical model comes from a formal macroscopic limit derived from a particular task description. Classical simulation of such system is linear in the number of tasks whereas this mathematical model execution time is constant.

Encadrement   Encadrant : Georges DA COSTA Labo/Organisme : IRIT, Université de Toulouse Ville : Toulouse

Description   HPC Applications are following a simple moto: Faster is better. Considering this point of view, only few researchers are trying to reduce energy consumption as it may reduce raw performance. Depending on the application, during some phases it is possible to reduce frequency without impacting performance, leading to improvement of energy efficiency. The student will model HPC applications using several type of parameters (system one, performance counters, energy, ...). Using this knowledge, performance and energy models of applications or phases of applications will be created. This models will lead to a characterization of HPC application. It will make possible to detect in an indirect way what application is running at any time. Then, using those models, kernel (Linux) governors will be designed in order to reduce energy consumption while keeping performance at its maximum.

Encadrement   Encadrant : Arnaud TISSERAND Labo/Organisme : IRISA Ville : LANNION

Description   Un compilateur de circuits intégrés numériques pour la cryptographie sur les courbes elliptiques (ECC) est développé dans l'équipe CAIRN de l'IRISA. À partir d'une description mathématique des calculs requis pour une application ECC et d'une description de haut niveau de l'architecture du circuit, il produit le code VHDL optimisé d'un (co-)processeur autonome. Il utilise une bibliothèque d'algorithmes arithmétiques et de représentations des nombres et des points de la courbe. Différents objectifs peuvent être spéciés pour orienter les phases de compilation : - vitesse, débit, latence (niveau de parallélisme interne, pipeline) ; - taille du circuit (pour le coût silicium) ; - consommation d'énergie (choix des algorithmes et des représentations) ; - sécurité par rapport à des attaques physiques. Le stage portera sur la sécurisation du processeur face à certaines attaques par canaux cachés en analyse de la consommation d'énergie. Ces attaques utilisent la corrélation entre le secret (valeur des bits de la clé) et l'activité électrique du circuit (transitions des données ou parasites). Deux pistes sont envisageables : rendre l'activité du circuit indépendante du secret (courbes particulières, randomisation) ou bien limiter les variations d'activité (équilibrage des calculs, codages physiques spéciques). Notre approche se situera au niveau des algorithmes arithmétiques et des représentations des données (aux niveaux du corps ni et de la courbe utilisés) et puis de leur codage physique dans le circuit. En particulier, les compromis entre la taille des opérateurs et le nombre d'unités de calcul disponibles en parallèle seront étudiés (multiples petites unités contre quelques unités très larges). Les résultats seront analysés expérimentalement en utilisant le banc d'attaques (sondes, oscilloscope numérique rapide et machine de traitement) et des cartes FPGA disponibles dans notre équipe. Les meilleurs algorithmes et représentations seront intégrés au compilateur. Remarques: Une indemnité de stage sera possible au tarif fixé par l'IRISA. Compétences espérées Prole recherché : informaticien(ne) avec un intérêt pour la micro-électronique. Connaissances de base en cryptographie asymétrique, en arithmétique (corps nis) et en compilation. Des connaissances sur les circuits intégrés (FPGA en particulier) serait un avantage, mais elles peuvent être acquises pendant le stage.

Encadrement   Encadrant : Paul ZIMMERMANN Labo/Organisme : INRIA/LORIA Ville : Nancy

Description   En calcul formel, l'objet le plus simple que l'on puisse construire avec une variable symbolique est le polynôme. Les opérations sur les polynômes sont donc des briques de base du calcul formel, et il est crucial qu'elles soient effectuées efficacement. L'une de ces opérations est l'approximation des racines (réelles ou complexes) d'un polynôme. On distingue deux classes d'algorithmes pour résoudre ce problème~: ceux qui fournissent une borne rigoureuse sur la qualité de l'approximation renvoyée, et les autres... On s'intéresse ici à la première classes d'algorithmes. Un exemple de "borne rigoureuse" consiste à isoler les racines du polynôme, dans des intervalles pour les racines réelles, ou dans des "boîtes" pour les racines complexes. L'objectif du stage est d'obtenir une implantation efficace du nouvel algorithme CEVAL proposé par Sagraloff et Yap, pour l'isolation des racines complexes d'un polynôme. On pourra reprendre les astuces algorithmiques utilisées dans le cas réel dans l'article [RoZi03]. L'idée principale est d'isoler les racines complexes dans des boîtes de la forme $\frac{c}{2^k} \leq x < \frac{c+1}{2^k}$, $\frac{d}{2^{\ell}} \leq y < \frac{d+1}{2^{\ell}}$ o\`u $c, d, k, \ell$ sont des entiers (éventuellement avec $k=\ell$). L'avantage d'une telle représentation est qu'elle permet d'obtenir directement l'arrondi de la partie réelle $x$ et de la partie imaginaire $y$ de la racine complexe $z=x+iy$ considérée. Pour obtenir une implantation efficace, il pourra \^etre nécessaire de modifier ou d'améliorer l'algorithme proposé par Sagraloff et Yap. L'implantation sera faite à l'aide des bibliothèques GNU MP [Granlund10] et GNU MPFR [FoHaLePeZi07] de calcul en précision arbitraire, et sera intégrée à GNU MPFR. On validera l'implantation en la comparant (à la fois en précision et en efficacité) aux implantations concurrentes (Maple, Mathematica, Sage, PARI/GP). Ce stage donnera lieu à une publication scientifique. Accéder au sujet détaillé

Encadrement   Encadrant : Ion NECHITA Labo/Organisme : LPT Toulouse Ville : Toulouse

Description   Le stage comportera deux parties. Dans un premier temps, l'etudiant devra se familiariser avec les notions de base de mecanique quantique et de theorie quantique de l'information (TQI). La TQI est un domaine recent, avec des resultats exceptionnels (cryptographie quantique) et des promesses encore plus extraordinaires (ordinateur quantique, capable de factoriser des entiers exponentiellement plus rapide que les algorithmes classiques connus a ce jour). Une fois les notions mathematiques de base de la discipline acquises, dans la deuxieme partie de stage on va s'interesser aux transformations LOCC: comment Alice et Bob, travaillant dans deux laboratoires differents, peuvent agir sur un etat quantique ? Differents protocoles de communications seront etudies, ainsi que les statistiques des etats finaux possibles. Remarques: Le stage ne sera pas remunere.

Encadrement   Encadrant : Radu IOSIF Labo/Organisme : VERIMAG Ville : Grenoble

Description   Lors de ce stage on étudiera, dans un premier temps, certaines techniques pour l'analyse des programmes numeriques et on essayera de comparer leur efficacite, en developpant une librairie d'etudes de cas communs. Dans un deuxieme temps on developpera des outils de traduction entre de differents formats de representation, utilisant la plate-forme NTS-LIB: \texttt{http://richmodels.epfl.ch/ntscomp/ntslib} Accéder au sujet détaillé Remarques: possibilite de renumeration

Encadrement   Encadrant : Pierre-Louis CAYREL Labo/Organisme : Laboratoire Hubert Curien Ville : SAINT-ETIENNE

Description   Domain : Cryptography and coding theory Presentation : Most of the cryptographic schemes used and studied today are based on number theory problems as factorisation or discrete logarithm. In 1994, Shor proposed an algorithm which can factorise in polynomial time using a quantum computer. So RSA and several others schemes are threatened by the quantum computer. Code-based cryptography is one of the branches of post-quantum cryptography with lattice-based, multivariate-based and hash-based cryptography. Schemes based on problems as syndrome decoding or decoding random codes are well studied for years and there doesn't exist polynomial time algorithm to solve those problems even in a post quantum world. McEliece was the first to propose a code-based cryptosystem and several improvements and derivation have been proposed so far. There exists dierent code-based signature schemes (Stern identication and signature scheme, Courtois Finiasz and Sendrier signature scheme) and several schemes proposed additional properties like identity-based constructions or threshold ring signatures. Purpose : After a state of the art of code-based signature schemes, the different properties that a signature scheme can oer and the generic constructions in each context, the student will have to propose a code-based signature scheme with one of this property (undeniable, designated verier or timereleased for example). A proof of security of the scheme in the random oracle model or in the standard model would be appreciate. The student will have to write an article on his research in a LATEX format and give an english presentation to the team. Goals : The outcome of the thesis is supposed to be a publishable result on code-based signature scheme with a special property. Accéder au sujet détaillé

Encadrement   Encadrant : Pierre-Louis CAYREL Labo/Organisme : Laboratoire Hubert Curien Ville : SAINT-ETIENNE

Description   Domain : Cryptography, coding theory and secure implementation Presentation : Most of the cryptographic schemes used and studied today are based on number theory problems as factorisation or discrete logarithm. In 1994, Shor proposed an algorithm which can factorise in polynomial time using a quantum computer. So RSA and several others schemes are threatened by the quantum computer. Code-based cryptography is one of the branches of post-quantum cryptography with lattice-based, multivariate-based and hash-based cryptography. Schemes based on problems as syndrome decoding or decoding random codes are well studied for years and there doesn't exist polynomial time algorithm to solve those problems even in a post quantum world. McEliece was the first to propose a code-based cryptosystem and several improvements and derivation have been proposed so far. To consider the use of code-based cryptosystems in the real life, they must be resistant to physical attacks as power analysis or fault injection. To date, the study of such attacks on such schemes are rare and there is a lot of work to do in this area. Purpose : After a state of the art of code-based schemes and side-channel attacks the student will implement an attack even on smart card, graphic card or CPU. Both practical and theoretical, this thesis proposes to study the physical attacks also called side-channel attacks like Simple Power Analysis, Differential Power Analysis, Higher-Order-Differential Power Analysis or Fault Attack and show how we can apply these patterns to attack code-based cryptosystems like Courtois-Finiasz-Sendrier signature scheme, Stern's zero-knowledge identification scheme or McEliece public key cryptosystem. We have a laboratory for the implementation and the application of the attacks. The student will have to write an article on his research in a LATEX format and give an English presentation to the team. With specialists in physical attacks and code-based cryptography, the student could work with different teams and improve his background in the two areas. Goals : The outcome of the thesis is supposed to be a publishable result on physical attacks on code-based cryptosystems. Accéder au sujet détaillé

Encadrement   Encadrant : Alexis BES Labo/Organisme : LACL, UPEC Ville : Créteil

Description   Thèmes: calculabilité, décidabilité, automates, logique. L'étude de questions relatives aux monoïdes partiellement commutatifs a conduit Yuri Matiyasevich à introduire un modèle de calcul, appelé k-machine, et à étudier les problèmes de décision associés. Etant donné un entier k>1 fixé, une k-machine peut être vue comme une extension des automates à un compteur, dans laquelle on dispose d'un seul registre entier R (initialisé à 0), et de transitions permettant d' incrémenter/décrémenter R, multiplier/diviser R par k (en prenant la partie entière), tester si R vaut 0, et tester si k divise R. Olivier Teytaud a démontré que le problème de l'arrêt pour les k-machines déterministes est décidable. L'objectif du stage est, dans un premier temps, d'étudier et comprendre la preuve de ce résultat. Puis, suivant le temps, on pourra considérer une ou plusieurs des questions soulevées par ce travail: simplification de la preuve, complexité de l'algorithme de décision, variantes et extensions du modèle, liens avec les automates finis, avec la logique (arithmétique de Presburger)... Référence: O.Teytaud, "Decidability of the halting problem for Matiyasevich deterministic machines", Theor. Comput. Sci. 257, No.1-2, 241-251 (2001).

Encadrement   Encadrant : Mamadou KANTÉ Labo/Organisme : LIMOS Ville : Clermont-Ferrand

Description   Le stage consistera à étudier des problèmes d\\\'étiquetage compact des formules du premier ordre dans des classes de graphes d\\\'expansion bornée. Voir lien pour plus de détails. Accéder au sujet détaillé

Encadrement   Encadrant : Jean-Christophe PESQUET Labo/Organisme : Laboratoire d\'Informatique Gaspard Monge Ville : Champs sur Marne

Description   L’imagerie par résonance magnétique (IRM) est une modalité non invasive massivement utilisée en médecine aujourd\'hui, notamment en neurosciences. Un scanner IRM peut être utilisé comme un microscope dont le grossissement dépend du champ magnétique. Les scanners usuellement employés à des fins cliniques fonctionnent à 1.5 ou 3 Tesla. A ultra-haut champ (UHF) (>= 7 Tesla), ils fournissent cependant une précision nettement accrue de la localisation spatiale des lésions cérébrales et rendent possible la détection de plaques amyloïdes dans la maladie d\'Alzheimer. La pleine exploitation des scanners UHF chez l’homme nécessite néanmoins le développement d\'algorithmes novateurs pour contrôler de façon optimale l\'homogénéité et la sécurité des ondes radiofréquence (RF) utilisées pour obtenir une image. La transmission parallèle (pTX) de ces ondes a été proposée pour s\'attaquer à ces problèmes en augmentant le nombre de degrés de liberté lors de la transmission. Par le biais d’interférences RF et de programmes d’optimisation, il est alors possible d\'obtenir une excitation homogène et efficace sur le plan énergétique. Bien que de nombreux travaux théoriques et expérimentaux aient été réalisés afin de tirer parti de sa puissance, cette technologie demeure sous-exploitée en raison de l\'absence d\'algorithmes optimaux de calcul des impulsions RF et de la complexité des problèmes rencontrés. Dans bon nombre d’applications, le problème est de très grande taille et se pose mathématiquement comme un problème inverse non-convexe sous de nombreuses contraintes quadratiques. Le sujet de stage proposé ici consiste en l’investigation d’algorithmes d’optimisation inspirés des domaines du traitement d’image, notamment l’algorithme Douglas-Rachford (utilisé avec succès dans des problèmes aussi variés que la résolution de Sudoku ou la reconstruction de phase de signaux). Ce stage s\'intéressera en particulier aux possibilités de parallélisation des algorithmes proposés. Remarques: Pour les études théoriques, le stage se déroulera au LIGM (UMR CNRS 8049) qui constitue l\'un des 3 pôles de recherche du LabEx Bezout de l’Université Paris Est. Le LIGM est situé à Marne-la-Vallée (20 mn de Paris par RER A). Le stage se conclura par une implémentation sur un scanner IRM à 7 Tesla équipé d’un prototype de pTX à l’institut NeuroSpin au CEA de Saclay. Le stage sera co-encadré par Nicolas BOULANT, chercheur à NeuroSpin.

Encadrement   Encadrant : Khaled CHAABAN Labo/Organisme : ESTACA, Equipe Systèmes Emabrqués Ville : LAVAL (FRANCE)

Description   L’objectif principal du stage est le développement et mise en place d’un nouvel algorithme d’optimisation évolutionnaire dont le but d’optimiser les performances d’un système embarquée temps réel. Le plan prévu pour ce stage est le suivant : [1] Etude et amélioration de l’algorithme existant : - Plusieurs objectifs d’optimisation - Optimisation de l’espace de recherche : meilleur spécification des contraintes [2] Mettre en oeuvre cette nouvelle méthode sur la plateforme de direction électrique (Figure 1) du laboratoire et en utilisant l’outil de l’analyse et de vérification Symta/s. Connaissances requises : langage C, XML, connaissance en système embarqué temps réel (e.g. ordonnancement temps réel), modélisation du système. Référence : 1. Rafik Henia, Arne Hamann, Marek Jersak, Razvan Racu, Kai Richter and Rolf Ernst, “System Level Performance Analysis - the SymTA/S Approach”, in proceedings of the IEEE conference Computers and Digital Techniques, 2005. 2. Stein, S., Hamann, A., and Ernst, R. 2006. “Real-Time Property Verification in Organic Computing Systems”. In Proceedings of the Second international Symposium on Leveraging Applications of Formal Methods, Verification and Validation (November 15 - 19, 2006). ISOLA. IEEE Computer Society, Washington, DC, 192-197. DOI= http://dx.doi.org/10.1109/ISoLA.2006.65. 3. K. Chaaban, P. Leserf and S. Saudrais. “Steer-By-Wire System Development Using AUTOSAR Methodology”. In proceedings of the 14th Emerging Technologies and Factory Automation (ETFA), Palma de Mallorca, IEEE, September 2009. 4. A. Daghsen, K. Chaaban, S. Saudrais and P. Leserf, “Applying Holistic Distributed Scheduling to AUTOSAR Methodology”, In proceedings of ERTS 2010, 19-21 may 2010, Toulouse. Remarques: Rémunération stagiaire environ 420€ Co-encadrement avec Mr Ahmed Daghsen de la même équipe.

Encadrement   Encadrant : Bertrand JOUVE Labo/Organisme : IXXI/ERIC/ENS Lyon Ville : Lyon

Description   A partir d’API existantes, l’étudiant récupèrera des données de twitter. Il s’agira de disposer de fils de tweets permettant de décrire une certaine dynamique des échanges pour croiser la topologie locale des communautés d’individus et la dynamique des mots-clefs qui émergent sur twitter. L’objectif étant bien sur de rechercher la présence de corrélations entre les deux. Ces données de réseaux seront analysées avec des outils formels de fouille de données et de fouille de graphes. La difficulté provient du fait que l’ensemble du graphe des échanges n’est pas connu. Dans un deuxième temps, il sera possible de mener une analyse linguistique des tweets avec des outils classiques de fouille de textes et de statistiques textuelles pour, à la fois préciser les communautés, à la fois préciser les caractéristiques du lexique utilisé. Remarques: Jean-Philippe Mague (Maître de Conférences en Humanités Numériques, ICAR, Lyon 2-CNRS-ENS Lyon)

Encadrement   Encadrant : Jean-Daniel BOISSONNAT Labo/Organisme : INRIA Sophia Antipolis Equipe Geometrica Ville : Sophia Antipolis

Description   During the last decade, sampling and meshing surfaces in 3-space has been intensively studied, resulting in major theorical advances and reliable and highly efficient codes. Extending those results to higher dimensions is in principle possible and one may hope of approximating higher-dimensional shapes by simplicial complexes (an extension of polyhedra with triangular facets). However, this approach faces several difficulties. The most important one being the computational bottleneck caused by the fact that the size of most data structures grows exponentially with the ambient dimension. To bypass this curse of dimensionality, new types of simplicial complexes have been recently proposed, most notably the witness complex and the tangential Delaunay complex. Thoses simplicial complexes adapt to the intrinsic dimension of the shape one wants to approximate without relying on a subdivision of the ambient space. Their complexity thus depends mostly on the intrinsic dimension of the shape of interest rather than on the dimension of the embedding space, which is usually much bigger. The internship will build on recent results and develop a method to sample and mesh submanifolds of any codimension. The algorithm will be used to mesh the Klein bottle (a non orientable surface (2-manifold) embeddable in R^4), the symmetry set of a 3D shape (the projection in $\R^3$ of a surface embeddable in R^{11}, or the configuration space of closed kinematic chains (such as robots or molecules). The algorithm may also find applications in scientific computing for solving partial differential equations where the domain of interest has the structure of a manifold. This work will be done as part of a european project CG-Learning (http://cglearning.eu/) whose overall goal is to design data structures and algorithms to process and analyse complex shapes in high dimensional spaces. It will also be part of an effort towards extending the CGAL library to higher dimensions. Accéder au sujet détaillé

Encadrement   Encadrant : Damien STEHLE Labo/Organisme : LIP Ville : LYON

Description   Sujet disponible à l'URL : http://perso.ens-lyon.fr/damien.stehle/stageL3_ENSL_12.pdf Accéder au sujet détaillé Remarques: Co-encadrement avec Gilles Villard

Encadrement   Encadrant : Sylvain SCHMITZ Labo/Organisme : LSV, ENS Cachan Ville : Cachan

Description   Propositional Dynamic Logic (PDL) on trees, aka Regular XPath, is a widely used formalism to reason on trees. It has numerous applications, for instance in linguistics, databases, and program verification. Although the PDL model-checking of a single tree can be carried out efficiently in PTime, the model-checking of a regular set of trees and the satisfiability problems suffer from a general ExpTime-hardness complexity. Thankfully, the complexity of model-checking a tree language can vary considerably depending on the considered fragment of PDL and the restrictions put on the tree language. An interesting way of introducing new restrictions on tree languages is to consider the sets of parse trees of a context-free grammar for a sentence. These parse trees have a very specific form, which should be amenable to more efficient processing. The work during the internship consists in investigating appropriate restrictions on the grammars in order to obtain NPTime and PSpace algorithms for the parse tree model-checking problem. Accéder au sujet détaillé

Encadrement   Encadrant : Olivier ROUX Labo/Organisme : IRCCyN Ville : Nantes

Description   Contexte Ce sujet se situe dans le cadre de l'analyse des réseaux de régulation biologiques. Pour être analysés, ces systèmes d'une grande complexité nécessitent d'être abstraits sous la forme d'un modèle mathématique. Les modèles résultants font généralement intervenir un grand nombre de variables (correspondant à des seuils d’activation ou d’inhibition d'un gène, ou représentant des temps de franchissement de ces seuils, etc.) qui sont considérées comme des paramètres car leurs valeurs ne sont pas connues précisément, mais indirectement (relations entre des paramètres, plages de valeur, variations suivant certaines lois de probabilités, ...). L’originalité de notre approche réside dans la prise en compte des aspects temporels dans les modélisations grâce, entre autres, au pi-calcul stochastique. Et plus spécifiquement grâce au framework que nous avons introduit, le process hitting [1], qui fait l’objet d’une implémentation efficace et robuste : pint [2]. Ce logiciel permet par exemple de vérifier en seulement quelques secondes des propriétés d’accessibilité sur des réseaux de régulation comptant plus d’une centaine de gènes. Dans le domaine de la bio-informatique, un pan de travail important consiste à confronter et ajuster les approches de modélisation aux besoins des biologistes. Une autre approche ayant fait ses preuves est celle développée au sein de l’outil BIOCHAM [3] : elle consiste à décrire et analyser les processus biologiques via l’expression des réactions bio-chimiques. L'oursin consiste justement un système biologique particulièrement adapté pour comprendre et analyser les mécanismes biologiques mis en jeu lors des traductions des données génomiques en protéines. De nombreux travaux de recherche se sont focalisés sur ce système. C'est pourquoi une collaboration sur le sujet a vu le jour entre informaticiens et biologistes, d’abord dans le cadre d'un projet PEPS soutenu par le CNRS et désormais dans le cadre du projet ANR «BioTempo». Objectif L'objectif du travail proposé ici est d'étudier la complémentarité entre les différents modèles développés par chacun des partenaires de ces projets. Plus spécifiquement, il s’agit de comprendre les liens entre le process hitting et le formalisme de BIOCHAM. Ce stage vise à établir une traduction formelle du modèle BIOCHAM vers le process hitting, puis à étudier comment le process hitting peut, par exemple, permettre une pré (ou une post) analyse efficace d’un modèle. Ce travail sera appliqué à l'initiation de la traduction chez l'oursin et son influence sur les premières divisions cellulaires, à partir d'un modèle de l'oursin qui sera fourni [4]. Travail à réaliser Le travail consiste en : • une étude bibliographique initiale, permettant de comprendre les enjeux et les spécificités des modèles que sont le process hitting et le formalisme de l’outil BIOCHAM ; • la conception d’une traduction permettant depasser d’un modèle à l’autre. Cette traduction, d’abord discrète, sera ensuite étendue pour prendre en compte les spécificités temporelles de chacun des modèles ; • l’application à l’étude des réseaux de régulation biologiques : étude de cas (traduction du cycle cellulaire chez l’oursin, thérapies géniques). Environnement et conditions de travail L’équipe MeForBio (Méthodes Formelles pour la Bio-Informatique) de l’IRCCyN est composée de deux permanents et deux doctorants. Le sujet de recherche s’intègre dans un projet PEPS dédié à l’analyse de la traduction chez l’oursin, mais également dans un projet ANR dénommé BioTempo, qui concentre notamment les efforts des équipes suivantes : • Équipe «ComBi» du LINA (Nantes) • Équipe «BioInfo» de l'I3S (Sophia-Antipolis) • Équipe «Symbiose Irisa/Inria» (Rennes) • Équipe «Contraintes/Inria» (Rocquencourt) • Équipe «Traduction Cycle cellulaire et développement» de la Station Biologique de Roscoff Ce travail s’intègre de plus dans le contexte de plusieurs collaborations internationales en cours de l’équipe MeForBio, d’une part avec l’équipe d’Alexander Bockmayr (Freie Universität, Berlin), d’autre part avec Andrew Phillips (Microsoft Research, Cambridge). Références [1] Loïc Paulevé, Morgan Magnin, and Olivier Roux. Refining Dynamics of Gene Regulatory Networks in a Stochastic pi-Calculus Framework.Transactions in Computational Systems Biology, 2010. [2] pint: http://processhitting.wordpress.com, 2012 [3] Laurence Calzone, François Fages and Sylvain Soliman. BIOCHAM: An Environment for Modeling Biological Systems and Formalizing Experimental Knowledge. Bioinformatics 22:1805-1807, July 2006. [4] R. Bellé, S. Prigent, A. Siegel and P. Cormier, Model of cap-dependent translation initiation in sea urchin. A step towards the eukaryotic translation regulation network Molecular Reproduction and Development 77(3), 2010, 257-264 Remarques: Co-encadrement par Morgan Magnin, maître de conférences à l'École Centrale de Nantes

Encadrement   Encadrant : Mariette YVINEC Labo/Organisme : INRIA Ville : Sophia Antipolis

Description   Given a set of point P in a metric space, the nearest neighbor searching problem or its approximate version, consists in building a data structure such that for any query point q the nearest neighbor or an approximate nearest neighbor of q in P can be retrieve efficiently, i.e. more quickly than through an extensive visit of all points in $P$. The proposed work consists in a theoretical and experimental study of different methods for nearest neighbor and approximate nearest neighbor searching. The set of tested methods will include at least the famous ANN algorithms for approximate nearest neighbor searching and a method based on a hierarchy of Delaunay graphs which provide exact nearest neighbors. Time permitting the internship student will experiment about coupling these methods with dimension reduction methods such as the Jonhson Lindenstrauss random projection method. Accéder au sujet détaillé

Encadrement   Encadrant : Pierre WEIS Labo/Organisme : INRIA Ville : Rocquencourt ou Pekin

Description   General overview of the domain: Many algorithms use data structures with particular invariants (e.g. a sorted list of values, a list of values with no repetition, etc.) and, to ensure that the invariants are always satisfied, one generally uses abstract or private data types with construction functions. Interestingly, many invariants can be described by algebraic equational theories: sorting corresponds to commutativity, the absence of repetition to idempotence, etc. Moca (moca.inria.fr) is a generator of construction functions for such data types in the OCaml functional programming language. Goal of the project: The goal of the project is to formally prove in the proof assistant Coq that the construction functions generated by Moca are correct. The first task is to study the various possible representations in Coq of the OCaml functions generated by Moca. Indeed, because of Coq\'s restrictions on the definition of functions, especially for termination, the construction functions generated by Moca may not definable in Coq as they can be in OCaml. Then, he will prove the correctness of the construction functions for some particular equational theories on a fixed signature (e.g. the theory of (commutative) monoids and the theory of (commutative) groups). He will then try to develop a framework and tactics in Coq so that these proofs can be done automatically and in a modular way, that is, by combining tactics for each elementary equational theory (associativity, commutativity, etc.). Finally, if time permits, he will extend Moca itself so that, together with the OCaml construction functions, it generates a Coq proof of their correctness. Accéder au sujet détaillé Remarques: Co-supervisor: Frederic Blanqui (http://www-rocq.inria.fr/~blanqui/). The internship can take place either at Beijing (China) or at Rocquencourt (France). Frederic Blanqui is an INRIA researcher in the FORMES team. The FORMES team is an INRIA-CNRS-Tsinghua University team of the LIAMA French-Chinese Consortium. The FORMES team is located at Tsinghua University, Beijing, China. Pierre Weis is an INRIA researcher in the ESTIME team located at INRIA Rocquencourt, France.

Encadrement   Encadrant : Charles-Edmond BICHOT Labo/Organisme : LIRIS (Lyon) Ville : Lyon

Description   Le sujet de ce stage est lié à l'analyse d'image et de vidéo. Pendant ce stage, on s'intéressera à l'approche feature & classier [vdS10] qui donne actuellement les meilleurs résultats en reconnaissance d'objets. Cette approche est basée sur l'étape cruciale d'extraction de caractéristiques des images (feature extraction ) qui est le plus souvent très gourmande en ressources (complexité en temps et en mémoire). Le sujet de ce stage sera d'analyser le descripteur LBP an de proposer un nouveau descripteur permettant de capturer les mêmes informations de texture que celui-ci, mais de manière plus efficiente grâce au calcul parallèle et plus particulièrement le calcul sur GPU. Ce stage sera encadré par Charles-Edmond Bichot, sur le site de l'École Centrale de Lyon, au laboratoire LIRIS. Accéder au sujet détaillé

Encadrement   Encadrant : Charles-Edmond BICHOT Labo/Organisme : LIRIS Ville : Lyon

Description   Le sujet de ce stage sera l'utilisation de métaheuristiques pour l'analyser et la sélection automatique de paramètres de descripteurs d'image. L'objectif de cette étude est d'apporter une connaissance plus fine des éléments caractérisants un objet dans les images. Ce n'est qu'à partir d'une meilleure compréhension de ces caractéristiques que les descripteurs pourront être plus efficients. Accéder au sujet détaillé

Encadrement   Encadrant : Bruno GAUJAL Labo/Organisme : inria Ville : Montbonnot

Description   Dans la théorie des jeux à plusieurs joueurs, la notion d'équilibre de Nash permet de rendre compte de situations dans lesquelles aucun des joueurs ne change son choix unilatéralement sans subir de perte. Ces points fixes du jeu ont cependant des inconvénients: Ils sont souvent difficiles à calculer et peuvent avoir des performances globales très mauvaises. Le but de ce stage est d'étudier comment on peut sélectionner de bons équilibres de Nash en modifiant à la fois la stratégie des joueurs (qui ne sera plus gloutonne) et l'ordre dans lequel les joueurs jouent (aussi appelé le processus de révision). On peut aussi autoriser plusieurs joueurs à agir simultanément. On appliquera ensuite les algorithmes obtenus dans des jeux d'allocations et de routage dans les réseaux sans fils pour mesurer les gains obtenus. Pour plus de renseignements, me contacter directement par mail: bruno.gaujal@inria.fr Remarques: Co-encadrement avec Corinne Touati

Encadrement   Encadrant : Corinne TOUATI Labo/Organisme : Inria Ville : Grenoble - Montbonnot

Description   Dérivés des équations logistiques de Verhulst, les modèles proies-prédateurs jouent un rôle prédominant dans le domaine des dynamiques de populations, tant en raison de la simplicité du modèle, mais aussi de la richesse des phénomènes qui en découlent. Un aspect de ces modèles dynamiques qui a récemment reçu beaucoup d'attention est le cas de proies et de prédateurs dispersés sur un territoire géographique, et qui interagissent à un niveau atomique (deux-à-deux). On a supposé que l'évolution globale des populations pouvaient être modélisée assez précisément par les modèles classiques de Lotka-Volterra, mais ce n'est pas toujours le cas: en fait, en fonction de la distribution spatiale initiale des proies et prédateurs, on peut assister à des phénomènes critiques de type percolation menant à des comportements radicalement différent de ce que l'on observe dans les modèles standards de population. Ainsi, l'objet de ce stage est d'étudier les interactions spatiales entre proies et prédateurs dans un habitat commun au moyen de simulations numériques et d'une analyse, par la théorie des jeux, du modèle d'interaction par paires. References: � [Du99] R. Durrett: Stochastic spatial models, SIAM Review 41 (1999) 677-718. MR2000h:60086 � [NoMay92] M.A. Nowak and R.M. May: Evolutionary games and spatial chaos, Nature 359 (1992), 826-829 � [NoMay93] M.A. Nowak and R.M. May: The spatial dilemmas of evolution, Int. J. Bifur. Chaos Appl. Sci. Engrg. 3 (1993), 35-78. MR 94c:92014 Remarques: Co-encadrement avec Panayotis Mertikopoulos.

Encadrement   Encadrant : Vincent LIMOUZY Labo/Organisme : LIMOS - Université Blaise Pascal Ville : Clermont Ferrand

Description   Le but de ce stage sera de comprendre, analyser et implémenter un algorithme qui calcule la dimension d'un ordre partiel. Accéder au sujet détaillé Remarques: Stage Co-encadré avec A. Mary

Encadrement   Encadrant : Vincent LIMOUZY Labo/Organisme : LIMOS Ville : Clermont Ferrand

Description   Le but de ce projet est de considérer certains problèmes de partitions (découpage) sur les graphes ou d'autres structure, avec la méthode des plans coupants. Accéder au sujet détaillé Remarques: Stage co-encadré par M. Baïou.

Encadrement   Encadrant : Nicolas BROUTIN Labo/Organisme : Inria Paris-Rocquencourt Ville : Le Chesnay

Description   Un arbre rouge/noir est une structure de donnée arborescente qui permet d'implémenter un arbre binaire de recherche. Les algorithmes d'insertion et de mise à jour sont tels que la structure se réorganise au besoin de manière à rester suffisamment équilibrée. Les arbres rouge-noir se comportent bien dans le pire des cas, c'est-à-dire que le temps nécessaire pour répondre à n'importe quelle requête est de l'ordre de log(n) pour un arbre de taille n. Le but de ce stage est d'essayer de quantifier plus précisément les performances des arbres rouge/noir lorsque les clés sont entrées dans la structure dans un ordre aléatoire. Des simulations récentes suggèrent un comportement proche de celui d'arbre totalement équilibré. L'intérêt théorique réside dans les points suivants: - la structure est dynamique, dans le sens où une mise à jour (ajout/retrait) peut conduire à des re-configurations en cascade non-triviales; - il n'y a aucun résultat connu sur le comportement moyen de ce genre de structure dynamique. Objectifs précis: Comme le sujet est assez difficile d'un point de vue théorique, on adoptera une démarche alliant expérimentation et théorie: a. comprendre les approches classiques qui permettent de quantifier les profondeurs des noeuds dans les structures de données arborescentes, et s'en inspirer pour développer des approches dans le cas des structures dynamiques; b. produire des simulations pour diriger l'intuition sur le comportement de l'arbre. En particulier: quelle est la forme de l'arbre après un grand nombre d'insertions, quelle est la structure des re-configurations? c. d'un point de vue théorique, peut-on isoler des événements qui garantissent qu'une re-configuration conduit à des changements à longue distance, ou bien au contraire reste locale? peut-on estimer la probabilité de ces événements? On cherchera en particulier à identifier des paramètres dont l'évolution lors d'insertions successives est plus simple et dont la compréhension théorique pourrait conduire à des preuves de bornes non triviales sur la profondeur d'un noeud aléatoire, la profondeur d'insertion, la hauteur.

Encadrement   Encadrant : Bruno GRENET Labo/Organisme : LIP, ENS Lyon Ville : Lyon

Description   La représentation lacunaire, ou super-creuse, d'un polynôme univarié à coefficients entiers est la donnée, pour chaque monôme non nul du polynôme, du couple (c,e) où c est le coefficient du monôme et e son exposant. La taille d'une telle représentation est alors la somme sur tous les monômes de (log c + log e). Une propriété de cette représentation est la possibilité de représenter des polynômes de très grand degré de manière concise. On s'intéresse au problème de la factorisation des polynômes. Si le polynôme est représenté sous forme dense (c'est-à-dire par la liste complète de ses coefficients), des algorithmes efficaces sont connus depuis les années 1960. L'étude de la factorisation en représentation lacunaire a débuté à la fin des années 1990. On peut aujourd'hui recenser quatre ou cinq algorithmes qui répondent de manière partielle au problème en ne trouvant que les facteurs de petit degré (linéaires par exemple). Ces algorithmes ont une complexité polynomiale mais on ne connaît pas leur complexité exacte. Le but du stage est d'étudier ces algorithmes. Dans un premier temps, il faudra en donner des versions explicites, ce qui n'est pas toujours fait dans la littérature. Ceci permettra ensuite de calculer leurs complexités exactes, en nombre d'opérations arithmétiques et/ou en nombre d'opérations binaires, et également de les implémenter pour les tester et les comparer en pratique. Une compréhension fine des algorithmes proposés pourra également mener à des améliorations. Le ou la stagiaire se concentrera sur un sous-ensemble des algorithmes existants, selon le temps dont il ou elle disposera. Les étudiant(e)s intéressé(e)s sont fortement encouragés à prendre contact avec l'encadrant pour discuter du sujet. Aucun pré-requis spécifique n'est exigé, mais un goût pour l'algorithmique, la complexité et/ou l'algèbre semble être un bon point de départ.

Encadrement   Encadrant : Guillaume FERTIN Labo/Organisme : LINA, UMR CNRS 6241 Ville : Nantes (44000)

Description   A) Objectifs: L'objectif de ce stage est d'étudier le problème appelé ``2-Générateurs minimaux'', qui est défini comme suit: étant donné une suite S={s_1,s_2...s_p} d'entiers strictement positifs, trouver un ensemble X={x_1,x_2...x_q} d'entiers positifs, tels que: * pour tout s_i, 1\leq i\leq p, s_i peut s'écrire s_i=x_j (1<= j<= q) ou s_i=x_j+x_k (1<= j<= k<= q) * q est minimum Ce problème mathématique a des liens avec des problèmes motivés par la biologie. B) Travail demandé Le travail demandé dans ce stage s'articule autour de trois temps: 1) La préparation minutieuse d'une campagne de tests informatiques, laquelle a pour but d'obtenir, par calcul automatique, la liste de tous les 2-générateurs minimaux X pour des suites S d'entiers consécutifs allant de 1 à n. 2) L'implémentation et la réalisation de cette campagne de tests, de façon suffisamment astucieuse et robuste: le but est d'être capable d'obtenir en temps raisonnable ces réponses, en ``poussant'' la valeur de n le plus loin possible. 3) L'analyse des résultats obtenus. Partant des exemples de 2-générateurs minimaux (pour un grand nombre de valeurs de n) obtenus précédemment, il s'agira de les analyser finement, afin de dégager des propriétés générales sur la façon dont ils sont composés. Ces propriétés sont évidemment intéressantes en elles-mêmes ; de plus, elles pourront éventuellement servir à accélérer les calculs et permettre de refaire une campagne de tests visant à obtenir de nouveaux exemples avec des valeurs de n encore plus élevées, lesquelles pourraient mener à découvrir d'autre propriétés. Le cas échéant, si le temps le permet, on pourra étendre cette étude à d'autre types de problèmes sur les générateurs, comme par exemple les 2-générateurs pour des suites S d'entiers consécutifs allant de x+1 à x+n (x>0), ou les 3-générateurs pour des suites S d'entiers consécutifs allant de x+1 à x+n. Remarques: Le stage ne pourra malheureusement pas être gratifié.

Encadrement   Encadrant : Florent DE DINECHIN Labo/Organisme : LIP Ville : Lyon

Description   L'objectif de ce stage est d'optimiser certaines fonctions élémentaires de la bibliothèque mathématique (exponentielle, logarithme, et les fonctions trigonométriques, en simple et double précision) pour un processeur particulier: le Kalray K1, d'architecture VLIW, destiné au marché embarqué haute performance. L'évaluation d'une fonction élémentaire se ramène généralement à une approximation polynomiale sur un petit intervalle. Le défi de ce stage est donc d'utiliser au mieux les opérateurs virgule-flottante spécifiques du processeur Kalray pour l'évaluation polynomiale. Au delà de l'obtention d'une bibliothèque de fonctions élémentaires efficaces, un objectif à long terme est d'automatiser le processus de développement de ce type de code (meta libm). Bibliographie : [1] J._M. Muller. Elementary Functions, Algorithms and Implementation. Birkhauser, 1997. [2] P. Markstein. IA-64 and Elementary Functions : Speed and Precision, Prentice Hall, 2000 [3] The crlibm project: http://lipforge.ens-lyon.fr/projects/crlibm/ Remarques: Co-encadrement avec Nicolas Brunie (Kalray). Possibilité de rémunération. Possibilité de faire une partie du stage à Grenoble chez Kalray.

Encadrement   Encadrant : Herve GRALL Labo/Organisme : Ecole des mines de Nantes Ville : NANTES

Description   Pour développer des architectures à services ("Service-Oriented Architectures"), nous avons conçu un langage appelé Criojo : c'est le langage interne d'une machine abstraite chimique, étendue par un mécanisme d'introspection. Nous aimerions étendre le langage pour permettre la mobilité du code, puisqu'actuellement seules les données sont mobiles. Une manière simple est de développer une machine universelle, capable d'exécuter tout programme écrit en Criojo, une fois représenté sous la forme d'une donnée. *** Objectifs du stage *** L'objectif du stage est de développer en Criojo le programme de cette machine universelle. Ce développement comprendra les étapes suivantes. 1. Représentation des programmes en données 2. Implémentation de l'interpréteur prenant en entrée une représentation d'un programme et une solution chimique et réalisant les réactions chimiques décrites par le programme Accéder au sujet détaillé Remarques: Equipe d'accueil : ASCOLA (INRIA - Mines de Nantes, LINA) Possibilités de logement sur le campus de l'école Gratification

Encadrement   Encadrant : Marie CANDITO Labo/Organisme : Alpage - Paris 7 Ville : Paris

Description Sujet choisi par Thimothee BERNARD   Un nombre enorme de videos est aujourd'hui disponible, en particulier sur Internet, qu'il s'agisse de videos informatives, educatives, de divertissement ou autres. Ce nombre va croissant, et de ce fait l'acces intelligent a leur contenu devient un enjeu majeur. Un scenario de recherche au sein de videos peut par exemple se modeliser comme la recherche de certaines situations ou actions precises (faire du cheval, sortir d'un vehicule, prendre un repas ...). Pour automatiser cette tache par des techniques d'apprentissage supervise, un probleme important est le fait qu'il est tres fastidieux de construire des exemples d'apprentissage o?? les sequences de videos sont couplees a des actions precises. Une solution a ce probleme est de construire automatiquement des exemples d'apprentissage en utilisant, lorsqu'ils existent, les textes associes aux videos. Ces textes sont en particulier disponibles pour un grand nombre de films, sous la forme de scripts de scenario. L'objet du stage est de construire un systeme integre d'analyse de scripts (anglais) de films, en vue de permettre la classification automatique de descriptions de scenes de films en actions, parmi un ensemble predefini d'actions. Il s'agira de de coupler l'utilisation et l'adaptation de modules de traitement existants (reconnaissance d'entites nommees, resolution d'anaphores, tagging, parsing) a des modules specifiques. Deux points (de recherche) attireront notre attention : d'une part l'utilisation du cadre FrameNet pour le reperage des actions, d'autre part les informations de factivite (cadre FactBank) pour savoir si une action s'est effectivement produite. Par exemple pour la description de scene suivante issue d'un script : " The servants move Chang's chair back. Before he goes, however, he turns to Conway and smiles at him. " Il s'agit de reperer les personnages "the servants", Chang, Conway; resoudre les references de "he" et "him"; reperer les actions "move chair", "turn", "smile" et leurs actants; et idealement reperer que la mention de l'action de partir (to go) n'est pas realisee ou pas encore realisee.

Encadrement   Encadrant : Ines KLIMANN Labo/Organisme : LIAFA Ville : Paris

Description Sujet choisi par Quentin BOLLE   Un automate avec une bande d’entrée et une bande de sortie, encore appelé transducteur, peut être vu comme une machine transformant un mot d’entrée en un mot de sortie. En faisant varier l’état d’entrée de l’automate, on obtient un ensemble d’applications sur les mots, et on peut s’intéresser au groupe engendré par ces applications qui est appelé un groupe d’automate. Le stage porte sur la décidabilité de la finitude d'un groupe d'automate. Dans un premier temps le stagiaire se familiarisera avec les résultats orientés informatique théorique obtenus pour le problème de finitude des groupes d'automates (un polycopié de cours sera fourni) et avec le langage de programmation GAP dédié aux groupes. Dans un deuxième temps, il établira une borne empirique sur la taille d'un groupe fini engendré par un automate qui permettra de poser une conjecture pour la résolution de la décidabilité de la finitude de tels groupes. Accéder au sujet détaillé Remarques: stage co-encadré par Matthieu Picantin (MCF LIAFA)

Encadrement   Encadrant : Bertrand JOUVE Labo/Organisme : ERIC/IXXI Ville :

Description Sujet choisi par Hadrien CROUBOIS

Encadrement   Encadrant : Vincent BALAT Labo/Organisme : PPS Ville : Paris

Description Sujet choisi par Raphaelle CRUBILLE   La d�compilation dirig�e par les types est une application de la technique de normalisation par �valuation qui permet de d�compiler un programme en l'ex�cutant, sans jamais regarder le code du programme compil�. Bien que l'algorithme de d�compilation tienne en quelques lignes, la technique pose de nombreux probl�mes lorsque l'on cherche � l'appliquer � des cas r�els : notamment on sait bien traiter le lambda calcul avec types fl�ches et produits mais les types sommes posent beaucoup plus de probl�mes, ainsi que les exceptions et m�me l'utilisation de biblioth�ques externes demande r�flexion. Le projet Ocsigen d�veloppe une technique de programmation d'applications Web client-serveur en OCaml. Le programme est enti�rement �crit en OCaml et les partie � ex�cuter dans un navigateur sont compil�es statiquement vers Javascript. Une autre approche que nous souhaitons explorer consiste � g�n�rer dynamiquement le Javascript, � la demande. Le but du stage sera d'exp�rimenter dans quelle mesure la d�compilation par �valuation peut �tre utilis�e pour cette deuxi�me approche, et �ventuellement de comparer cette technique originale avec des techniques plus classiques de g�n�ration de code. Remarques: Le stage aura lieu � l'IRILL, dans les locaux d'Inria avenue d'Italie � Paris.

Encadrement   Encadrant : Yvan LE BORGNE Labo/Organisme : LaBRI Ville : Talence (voisine de Bordeaux)

Description Sujet choisi par Henri DERYCKE   Le modèle du tas de sable est un modèle de diffusion discret décrivant le mouvement de grains placés sur les sommets d'un graphe (arxiv.org/abs/cond-mat/9909009 ou en version simplifiée http://www.labri.fr/perso/borgne/publis/Lacim.pdf). Lorsqu'un sommet contient au moins autant de grains que son degré, il est qualifié d'instable. Selon la dynamique du modèle, un sommet instable peut s'ébouler, c'est à dire envoyer un grain par chacune de ses arêtes incidentes à ses voisins. Modulo quelques hypothèses techniques, l'itération de l'éboulement des sommets instables d'une configuration se termine avec une configuration dite stable car chaque sommet (sauf peut-être un) contient moins de grains que d'arêtes incidentes. Ce processus de relaxation conduit toujours à la même configuration stable. En effet il s'avère que toutes les suites possibles d'éboulements ne diffèrent que par l'ordre des sommets éboulés. Pour ce sujet, on souhaite étudier certaines relaxations de configurations bien particulières sur des sous-graphes finis de la grille à deux dimensions. La relaxation de ces configurations initiales fortement symétriques conduit à des configurations stables plus complexes mais qui semblent organisées sous forme de "fractales" (voir par exemple http://tuvalu.santafe.edu/~moore/id500.gif). Des articles comme http://arxiv.org/abs/0808.1732 laisse l'espoir de pouvoir préciser ces observations. Par exemple les auteurs y suspectent que les angles formés à l'intersection de zones "texturées" par des motifs périodiques différents sont reliés par une équation impliquant aussi la densité de grains dans chacune de ces zones. Pendant la durée du stage, il est espéré une compréhension du modèle du tas de sable à travers une programmation personnelle de ce modèle permettant ultérieurement d'expérimenter. On souhaite par exemple tester différents ordonnancements des éboulements, certains pouvant mieux structurer le calcul ou expliquer des propriétés du résultat. Ce calcul concret est un fil rouge pour la découverte de multiples aspects du modèle du tas de sable qui, si cela intéresse l'étudiant, conduisent par exemple à des arbres couvrants, un groupe, une chaîne de Markov. En étant optimiste, la vérification expérimentale de la relation à l'intersection de plusieurs zones avec différents motifs périodiques pourrait également conduire à une formulation totalement discrète de cette relation supposée. La version longue du sujet sera disponible prochainement à l'adresse http://www.labri.fr/perso/borgne/stages/mim1-2012.pdf. Remarques: Je suis membre du thème Combinatoire énumérative et algébrique du LaBRI qui se réunit avec une fréquence quasi-hebdomadaire pour un groupe de travail dont la page web est https://cea.labri.fr/pmwiki.php/Groupe/2011-2012. Il est bien sur possible de tenter de satisfaire sa curiosité dans d'autres groupes de travail du LaBRI, cette page en répertorie une grande partie des annonces: http://www.labri.fr/public/actu/accueil.php.

Encadrement   Encadrant : Charles-Edmond BICHOT Labo/Organisme : LIRIS Ville : Lyon

Description Sujet choisi par Xavier DUMONT   L'objectif de ce stage est, en ce basant sur l'état de l'art [Bic11b, Bic11a], d'étudier, proposer et mettre en oeuvre de nouveaux algorithmes parallèles de partitionnement de graphe sur GPU. L'étude de tels algorithmes serait une avancée dans le domaine. Accéder au sujet détaillé

Encadrement   Encadrant : Corinne TOUATI Labo/Organisme : Inria Ville : Grenoble - Montbonnot

Description Sujet choisi par Stephane DURAND   Il existe une classe de jeu particulière, appelée "jeux de potentiels" dans laquelle les équilibres de Nash correspondent aux optimums (locaux) d'une fonction globale au système (la "fonction de potentiel"). Un des grands défis en théorie des jeux est de calculer les équilibres de Nash, voir même l'équilibre de Nash optimal pour la fonction. Il est connu pour être un problème compliqué [1]. Et il l'est encore plus lorsque l'on suppose que chaque joueur agit de façon indépendante (c'est à dire sans pouvoir se synchroniser avec les autres) et qu'il n'a qu'une connaissance partielle du système (typiquement, chaque joueur ignore quels sont les intérêts des autres joueurs). Les algorithmes développés dans ce contexte sont appelés "mécanismes d'apprentissage". Chacun des joueurs tente une action et observe l'utilité qu'elle lui rapporte. Puis le joueur va tenter une autre action et observer l'utilité associée, et ainsi de suite, en se fixant progressivement vers la / les actions dont les utilités associées sont les meilleures. Les mécanismes sont développés de telle sorte que l'on peut démontrer leur convergence vers des équilibres de Nash. L'un des mécanismes les plus étudiés est celui dit "de meilleure réponse" dans lequel chaque joueur joue systématiquement sa meilleure action possible. Il est connu que l'algorithme de meilleure réponse peut converger vers un équilibre de Nash sous-optimal (voir si les joueurs ne sont pas synchronisé, il peut même ne pas converger du tout). Il a également été montré que certaines extensions probabilistes de l'algorithme convergent vers l'équilibre de Nash maximisant la fonction de potentiel [2]. Le but de ce stage est de généraliser ce résultat et de trouver des hypothèses minimales sur l'algorithme pour garantir la convergence du mécanisme ainsi que sa convergence vers les points optimaux. Références: [1] Algorithmic Game Theory, Nisan, Roughgarden, Tardos, Vazirani (chapitre 2) [2] Auto-optimisation des réseaux sans fil : une approche par la théorie des jeux, Pierre Coucheney (chapitre 4) Remarques: Co-encadrement avec Bruno Gaujal

Encadrement   Encadrant : Didier GALMICHE Labo/Organisme : LORIA Ville : Nancy

Description Sujet choisi par Adrien DURIER   La recherche automatisée de preuves en logique intuitionniste propositionnelle (ILP) est un thème de recherche mature. Nous nous intèressons ici aux techniques fond"es sur les calculs à base de séquents. Des travaux récents ont conduit à un calcul LSJ qui possède à la fois la propriété de la sous-formule et celle de simplification. Le sujet propose d'étudier ce système et comment il peut conduire à améliorer la recherche de preuves dans ILP (voir sujet détaillé). Accéder au sujet détaillé Remarques: Co-encadrement avec Dominique Larchey-Wendling

Encadrement   Encadrant : Chantal KELLER Labo/Organisme : LIX Ville : Palaiseau

Description Sujet choisi par Gaetan GILBERT   SMTCoq <http://www.lix.polytechnique.fr/~keller/Recherche/smtcoq.html> est un outil permettant de vérifier en Coq les témoins de preuve produits par les prouveurs SMT, des prouveurs automatiques très efficaces mais non certifiés. Ces témoins de preuves sont très différents d'un prouveur SMT à l'autre, et ne donnent pas le même niveau de détail. Le but du stage est d'intégrer les témoins de preuve de Z3, le prouveur SMT le plus performant à l'heure actuelle, dans SMTCoq. Il faudra dans un premier temps comprendre comment traduire ces témoins dans un certificat suffisamment détaillé pour SMTCoq. Cela pourra ensuite déboucher sur une implémentation. Une application directe sera la certification des appels à Z3 effectués par le système de types appelé Liquid Types <http://goto.ucsd.edu/~rjhala/liquid>. Le sujet plus détaillé est disponible en pdf. Accéder au sujet détaillé Remarques: Le stage est co-encadré par Chantal Keller et Benjamin Werner (directeur de recherche au LIX).

Encadrement   Encadrant : Marc MEZZAROBBA Labo/Organisme : LIP, ENS de Lyon Ville : Lyon

Description Sujet choisi par Thomas GREGOIRE   De nombreuses fonctions usuelles, par exemple les fonctions elementaires exp, ln, cos... mais aussi des fonctions speciales comme la fonction d'erreur erf ou les fonctions de Bessel sont solutions d'equations differentielles lineaires a coefficients polynomiaux. Le DDMF (Dynamic Dictionary of Mathematical Functions, http://ddmf.msr-inria.inria.fr) est un formulaire interactif en ligne qui prend cette caracteristique comme point de depart pour determiner les proprietes des fonctions qu'il decrit. Concretement, chaque fonction presentee dans le DDMF est definie par une structure de donnees constituee d'une equation differentielle et d'un jeu convenable de conditions initiales. Les pages du DDMF dediees a la fonction sont produites automatiquement a partir de cette definition en utilisant des algorithmes de calcul formel. L'objet de ce stage est d'etendre les capacites du DDMF dans le domaine de l'approximation numerique. La candidate ou le candidat ajoutera au programme qui genere les pages le support de nouvelles sections consacrees a un ou plusieurs types d'informations parmi les suivants : - representations graphiques de la fonction consideree ; - approximations polynomiales avec bornes d'erreurs ; - code d'evaluation numerique telechargeable (en langage C par exemple). Il lui faudra pour cela etudier puis adapter et raffiner des algorithmes existants de calcul de solutions approchees d'equations differentielles et/ou de bornes d'erreur sur ces approximations. En particulier, un developpement interessant consisterait a accompagner les approximations de preuves en langage naturel aboutissant a des bornes d'erreur rigoureuses. Sur le plan theorique, la question est d'arriver une methode de calcul de borne d'erreur suffisamment simple pour donner lieu a une preuve redigee comprehensible. (A terme, les preuves obtenues ou leur methode de calcul pourraient servir de canevas a une formalisation dans un assistant de preuve, mais le travail de formalisation depasse largement le cadre du stage.) Suivant les gouts du candidat ou de la candidate, la partie theorique du stage pourra aussi s'orienter vers l'amelioration de la finesse des bornes d'erreurs attachees aux approximations ou encore vers la production automatique de code d'evaluation efficace, pour microprocesseurs ou pour des architectures plus exotiques. L'implementation utilisera les langages Ocaml et Maple, ainsi qu'au besoin C ou C++ suivant la direction prise. Des sujets sur mesure portant sur d'autres sections du DDMF sont aussi envisageables. Les candidats interesses sont invites a nous contacter. Remarques: Encadrants : Marc Mezzarobba, Florent de Dinechin, Nicolas Brisebarre (equipe AriC, LIP, ENS de Lyon)

Encadrement   Encadrant : Philippe SCHNOEBELEN Labo/Organisme : Dept. Computer Science, Univ. Oxford Ville : Oxford, Angleterre

Description Sujet choisi par Benjamin HADJIBEYLI   Les automates à compteurs relationnels (ACR) sont des automates finis manipulant des compteurs entiers et ne disposant que d'un jeu d'instruction assez limité : tests x<y (compteur/compteur), x<c et c<x (compteur/constante), affections x:=y (copie d'un compteur), x:=c (réinitialisation avec une constante), et x:=? (tirage non déterministe d'un entier quelconque). On voit que ces automates ne permettent pas, en tout cas pas directement, d'effectuer des opérations arithmétiques simples comme l'addition x:=y+z, ou même seulement x:=x+1. De fait, les ACR n'ont pas la puissance des machines de Turing et, p.ex., la terminaison ou l'accessibilité d'un état du graphe de contrôle sont décidables pour ces modèles de calcul. [Les ACR sont utilisés p.ex. pour modéliser des protocoles temporisés et dans ce cas les compteurs stockent la valeur courante d'horloges logiques.] L'objectif du stage est de démontrer, par une construction explicite, que les ACR sont capables de calculer faiblement, en un sens à préciser, des fonctions qui croissent très vite, comme la fonction d'Ackermann, et d'en déduire des bornes de complexité très élevées pour ces modèles. Il s'agit d'une question inspirée par l'article [1] (qui traite d'autres familles d'automates à compteurs) et on propose d'essayer d'adapter l'approche de [1] au cadre des ACR. [1] Ph. Schnoebelen. Revisiting Ackermann-hardness for lossy counter machines and reset Petri nets. MFCS 2010. http://tinyurl.com/7vg63f6 Mots-clés : modèles de calcul, algorithmique et complexité, vérification, well-quasi-orderings, fonction d'Ackermann. Remarques: Le stage s'effectuera au sein du Computing Lab. de l'Université d'Oxford où je suis toute cette année en séjour "sabbatique". C'est une occasion pour le stagiaire de nouer des contacts internationaux dans un des meilleurs centres mondiaux de recherche en informatique. Il est possible d'être logé à coût réduit au sein de l'université.

Encadrement   Encadrant : Guillaume HANROT Labo/Organisme : LIP Ville : Lyon

Description Sujet choisi par William LOCHET   L'algorithme BKZ (Block Korkin-Zolotarev), du a Schnorr, est actuellement le meilleur algorithme permettant d'approcher en pratique le probleme du plus court vecteur dans un reseau euclidien de grande dimension. A ce titre, son importance est critique en cryptologie, par exemple pour evaluer la securite des cryptosystemes fondes sur les reseaux a dimension fixee. Plus qu'un algorithme precis, BKZ est une combinaison d'idees largement sous-specifiee, et dont le comportement est tres loin d'etre compris, malgre un premier pas vers une analyse l'an passe. Plusieurs aspects de l'algorithme et de son analyse meritent une etude plus approfondie : * dans le cas ou la taille de bloc est fixee a 2, deux analyses de l'algorithme sont en concurrence ; aucune n'est strictement meilleure que l'autre, et il serait interessant d'essayer de les combiner. * l'analyse realisee l'an passe est une analyse pire cas tres pessimiste. Une analyse en moyenne, ou pire cas realiste, est probablement hors de portee, mais un modele probabiliste peut etre construit et etudie, au moins experimentalement. Il serait interessant de conduire cette etude, et de la confronter a des experiences reelles pour peaufiner le modele probabiliste et regler ses parametres. * enfin, comme precise, plusieurs strategies concurrentes sont possibles pour l'algorithme, plus ou moins parallelisables. L'analyse predit une partie de leur comportement mais il serait la encore utile de la confronter a la realite et de definir des classes de strategies pertinentes (ou valider la strategie "traditionnelle"). Le stage pourra s'orienter dans une des trois directions selon le gout du stagiaire. References. [HPS11] G. Hanrot, X. Pujol, D. Stehle, Analyzing Blockwise Lattice Reduction Using Dynamical Systems, Crypto'2011 [Sc94] C.P. Schnorr, Block reduced lattice bases and successive minima, Combinatorics, Probability and Computing 3 (1994), 507--522. [ScE] C.P. Schnorr, M. Euchner, Lattice basis reduction : improved practical algorithms and solving subset sum problems, Mathematics of Programming 66 (1994), 181--199.

Encadrement   Encadrant : Christophe CRESPELLE Labo/Organisme : LIGM (Marne-la-Vallée) ou LIP (Lyon) Ville : Marne-la-Vallée ou Lyon

Description Sujet choisi par Oreste MANOUSSAKIS   La question de trouver des représentations compactes pour les graphes, c'est à dire prenant peu de place en mémoire, est une question centrale de l'algorithmique de graphes, dans la théorie comme dans la pratique. Malheureusement, les méthodes de codage utilisées pour réduire la taille de la représentation en mémoire ne permettent pas toujours de traiter efficacement les requêtes faites sur les graphes, comme par exemple les requêtes de voisinage d'un sommet, ce qui au final pénalise les algorithmes qui les manipulent. Une façon naturelle de coder un graphe de manière compacte en conservant de bonnes propriétés algorithmiques consiste à trouver un ordre linéaire sur les sommets du graphe de sorte que pour chaque sommet, ses voisins forment un intervalle de cet ordre linéaire. Bien sûr, cela n'est possible que pour certains graphes, appelés bi-convexes. Afin de représenter tous les graphes de cette manière, on peut s'autoriser plusieurs ordres linéaires et choisir un intervalle dans chaque ordre pour chaque sommet, de sorte que les voisins d'un sommet soient exactement l'union des intervalles choisis pour lui dans chacun des ordres linéaires. Le nombre minimum d'ordres nécessaire pour coder un graphe de cette façon est un paramètre appelé la linéarité du graphe. Bien que cette représentation soit naturelle, on en sait peu de choses (si ce n'est qu'il est NP-complet de calculer la linéarité pour les graphes quelconques). En particulier, on ne sait pas quelles sont les classes de graphes qui ont une linéarité faible, ou au contraire une linéarité élevée. Un résultat surprenant est que les classes de graphes connues pour avoir de très bonnes propriétés de codage, comme les graphes de permutation et les graphes d'intervalles, n'ont pas une linéarité bornée : celle-ci peut être de l'ordre de log(n)/loglog(n). Et c'est aussi le cas de la famille des cographes qui est pourtant une des familles les plus fortement structurées qui soit. Cela suscite un grand intérêt pour les questions suivantes : quel est exactement la linéarité de ces familles de graphes dans le pire des cas? Peut-on caractériser les graphes de linéarité bornée? ou même les graphes de linéarité 2? Peut-on calculer la linéarité en temps polynomial sur certaines classes de graphes? Remarques: Le stage est co-encadré par Philippe Gambette (LIGM) et Christophe Crespelle (LIP). Il se déroulera soit à Marne-la-Vallée (au LIGM) soit à Lyon (au LIP), au choix de l'étudiant.

Encadrement   Encadrant : Pierre FILLARD Labo/Organisme : equipe Parietal, INRIA Saclay Ville : Sophia Antipolis

Description Sujet choisi par Gautier MARTI   Contexte : Des cam�ras 3D permettant l'estimation du relief (carte de profondeur) sont arriv�es r�cemment sur le march� (kinect de Microsoft, xtion d'Asus). Leur production en masse (notamment pour l'industrie des jeux vid�os) a fait chuter leurs co�ts (~ 100 euros, contre 10-100 fois plus ant�rieurement), rendant cette technologie tr�s abordable et populaire dans les laboratoires de vision par ordinateur. La carte de profondeur facilite en effet grandement le probl�me de la segmentation d'image (= la d�limitation automatique des diff�rents objets pr�sents dans la sc�ne) puisqu'au lieu de se baser uniquement sur la similarit� des couleurs entre pixels voisins, on peut d�sormais s'appuyer �galement sur leur distance dans l'espace 3D. Ce stage s'effectuera pour des conditions d'utilisation en champ proche, c'est-�-dire que l'utilisateur est tr�s proche de la cam�ra. Ce contexte ne permet pas de voir une partie suffisante du corps de l'op�rateur pour effectuer le suivi du squelette. C'est donc un traitement bas� sur le signal de profondeur qui sera directement r�alis�. Objectif : L'objectif de ce stage est de pouvoir d�tecter de mani�re tr�s robuste la position de la main : compl�tement ouverte oui/non. La principale difficult� vient du signal bruit� du capteur qui d�pend de l'orientation de la main. Il s'agira d'�tablir quelles sont les conditions sous lesquelles la d�tection/identification est r�alisable de fa�on fiable (par exemple : angle de la main, configuration des doigts...). Approche envisag�e : L'approche envisag�e consiste � utiliser des techniques d'apprentissage supervis� pour estimer les caract�ristiques optimales d'un classifieur bas� sur une base d'apprentissage d�j� r�alis�e, compos�e de mains ouvertes et non ouvertes. Cette approche sera r�alis�e en deux �tapes: - une premi�re �tape consiste � produire des descripteurs caract�ristiques de la forme � identifier : densit� de trous, ratio des dimensions de la main, distance entre les extr�mum de courbure... Cette liste est � enrichir dans le stage. - une seconde �tape consiste � utiliser un algorithme d'apprentissage supervis� (les for�ts al�atoires sont conseill�es, mais on pourra �galement tester les algorithmes de boosting ou SVM [Support Vector Machine]) afin d'identifier automatiquement les r�gles permettant de s�parer au mieux les deux classes de la base d'apprentissage. A noter qu'il faudra faire attention � proposer des classifieurs invariants par changement d'�chelle, �tant donn� que la distance de la main au capteur peut �tre variable (donc sa taille). Mat�riel : 1 cam�ra kinect ou �quivalent (Asus xtion) Contraintes : temps r�el (30 images par seconde) Lecture sugg�r�e avant le stage : - http://www.ic.uff.br/iwssip2010/Proceedings/nav/papers/paper_128.pdf - http://research.microsoft.com/pubs/155552/decisionForests_MSR_TR_2011_114.pdf - http://www.microsoft.com/download/en/details.aspx?id=27977 Programmation : - vision par ordinateur (en C++) : OpenCV ( http://sourceforge.net/projects/opencv/ ) - post-processing de la kinect : libfreenect ( https://github.com/OpenKinect/libfreenect ) - statistiques et affichage graphique : R ( http://www.r-project.org/ ) - apprentissage (en python) : scikit-learn ( http://scikit-learn.org/ ) Remarques: Co-encadrement avec Olivier Clatz, equipe Asclepios, INRIA Sophia Antipolis

Encadrement   Encadrant : Emmanuel BEFFARA Labo/Organisme : IML Ville : Marseille

Description Sujet choisi par Antoine MOTTET   Les s�mantiques de jeux ont �t� rendues c�l�bres dans les ann�es 90 par des r�sultats de � full abstraction �. Tr�s flexibles, elles permettent de caract�riser certains traits d�expressivit� des langages de programmation (op�rateurs de contr�le, acc�s � un �tat global, etc.) par des propri�t�s g�n�ralement simples et combinatoires des strat�gies. Au cours du stage, on fera le tour de notions usuelles en s�mantique des jeux (innocence, bon parenth�sage, visibilit�) et de leurs contreparties calculatoires connues. On pourra ensuite aborder la conjecture suivante : les strat�gies respectant la P-visibilit� correspondent � un langage imp�ratif d�ordre sup�rieur, avec variables locales et primitives de contr�le. La difficult� principale sera sans doute de d�crire pr�cis�ment ce langage cible. Remarques: Co-encadrement avec Lionel Vaux

Encadrement   Encadrant : Frederic BLANQUI Labo/Organisme : INRIA Ville : Rocquencourt ou Pekin

Description Sujet choisi par Remi NOLLET   General overview of the domain: Many algorithms use data structures with particular invariants (e.g. a sorted list of values, a list of values with no repetition, etc.) and, to ensure that the invariants are always satisfied, one generally uses abstract or private data types with construction functions. Interestingly, many invariants can be described by algebraic equational theories: sorting corresponds to commutativity, the absence of repetition to idempotence, etc. Moca (moca.inria.fr) is a generator of construction functions for such data types in the OCaml functional programming language. Goal of the project: The goal of the project is to formally prove in the proof assistant Coq that the construction functions generated by Moca are correct. The first task is to study the various possible representations in Coq of the OCaml functions generated by Moca. Indeed, because of Coq\'s restrictions on the definition of functions, especially for termination, the construction functions generated by Moca may not definable in Coq as they can be in OCaml. Then, he will prove the correctness of the construction functions for some particular equational theories on a fixed signature (e.g. the theory of (commutative) monoids and the theory of (commutative) groups). He will then try to develop a framework and tactics in Coq so that these proofs can be done automatically and in a modular way, that is, by combining tactics for each elementary equational theory (associativity, commutativity, etc.). Finally, if time permits, he will extend Moca itself so that, together with the OCaml construction functions, it generates a Coq proof of their correctness. Accéder au sujet détaillé Remarques: Co-supervisor: Pierre Weis (http://bat8.inria.fr/~weis/). The internship can take place either at Beijing (China) or at Rocquencourt (France). Frederic Blanqui is an INRIA researcher in the FORMES team. The FORMES team is an INRIA-CNRS-Tsinghua University team of the LIAMA French-Chinese Consortium. The FORMES team is located at Tsinghua University, Beijing, China. Pierre Weis is an INRIA researcher in the ESTIME team located at INRIA Rocquencourt, France.

Encadrement   Encadrant : Didier GALMICHE Labo/Organisme : LORIA Ville : Nancy

Description Sujet choisi par Louis PARLANT   Le sujet du stage se focalise plus spécifiquement sur la formalisation algorithmique de procédures de transformation de preuves entre les principaux systèmes de preuves proposés récemment pour la logique bi-intuitionniste (BiInt) et leur implantation dans la mesure du possible. (voir sujet détaillé) Accéder au sujet détaillé Remarques: Co-encadrement avec Daniel Méry

Encadrement   Encadrant : Victor CHEPOI Labo/Organisme : LIF Ville : Marseille

Description Sujet choisi par Timothee PECATTE   Voir le lien ci dessous Accéder au sujet détaillé

Encadrement   Encadrant : Jean-Philippe MAGUE Labo/Organisme : ICAR Ville : Lyon

Description Sujet choisi par Luc ROCHER

Encadrement   Encadrant : Matthieu LATAPY Labo/Organisme : LIP6 - CNRS et UPMC Ville : Paris

Description Sujet choisi par Matthieu ROSENFIELD   La propagation des épidémies, des rumeurs, des virus informatiques, ou la diffusion d'une information sont des exemples types de phénomènes de diffusion. De par leur importance, ces phénomènes sont au centre d'une intense activité de recherche. Celle-ci dispose toutefois de très peu de données précises et à grande échelle. Par conséquent, les modèles disponibles reposent sur des intuitions plutôt que des observations, et restent peu validés. Le stage proposé repose sur l'analyse de mesures de phénomènes de diffusions effecturées dans l'équipe, afin d'en tirer des principes pour la modélisation. Plus de détails dans le PDF. Accéder au sujet détaillé

Encadrement   Encadrant : Pierre-Louis CAYREL Labo/Organisme : Laboratoire Hubert Curien Ville : SAINT-ETIENNE

Description Sujet choisi par Quentin SANTOS   Domain : Cryptography and coding theory Presentation : In cryptography, the Fast Syndrome-based hash Functions (FSB) are a family of cryptographic hash functions introduced in 2003 by Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier. Unlike most other cryptographic hash functions in use today, FSB can to a certain extent be proven to be secure. More exactly, it can be proven that breaking FSB is at least as dicult as solving a certain NP-complete problem known as Regular Syndrome Decoding. We call function with these properties provably secure. Though it is not known whether NP-complete problems are solvable in polynomial time, it is often assumed that they are not. Several versions of FSB have been proposed, the latest of which was submitted to the SHA-3 cryptography competition but was rejected in the rst round. Though all versions of FSB claim provable security, some preliminary versions were eventually broken. The design of the latest version of FSB has however taken this attack into account and remains secure to all currently known attacks. As usual, provably security does come at a cost. FSB is slower than traditional hash functions and uses quite a lot of memory, which makes it impractical on memory constrained environments. Furthermore, the compression function used in FSB needs a large output size to guarantee security. Recently, Bernstein et al. introduces a new design for FSB which permits to reach the speed of 2 of the 5 SHA-3 nalists. Purpose : The purpose of the thesis is to understand the recent improvements in the design of hash functions based on the syndrome decoding problem and design/implement an improved codebased stream cipher. The students will have to write an article on his research in a LATEX format and give an English presentation to the team. Goals : The outcome of the thesis is supposed to be a publishable result on code-based secret key cryptosystem. Accéder au sujet détaillé

Encadrement   Encadrant : Matthieu LATAPY Labo/Organisme : LIP6 - CNRS et UPMC Ville : Paris

Description Sujet choisi par Maxime SAVARO   La plupart des très grands graphes rencontrés en pratique ont une structure multi-échelle : ils contiennent des zones denses peu connectées entre elles, et les zones denses ont elles-mêmes cette structure. Il s'agit dans ce stage d'étudier les propriétés de ces structures, sur la bases de programmes les calculant qui sont fournis. Plus de détails dans le pdf. Accéder au sujet détaillé

Encadrement   Encadrant : Guillaume CHARPIAT Labo/Organisme : Stars - INRIA Sophia Antipolis Ville : Sophia Antipolis

Description Sujet choisi par Bertrand SIMON   Contexte : Des cam�ras 3D permettant l'estimation du relief (carte de profondeur) sont arriv�es r�cemment sur le march� (kinect de Microsoft, xtion d'Asus). Leur production en masse (notamment pour l'industrie des jeux vid�os) a fait chuter leurs co�ts (~ 100 euros, contre 10-100 fois plus ant�rieurement), rendant cette technologie tr�s abordable et populaire dans les laboratoires de vision par ordinateur. La carte de profondeur facilite en effet grandement le probl�me de la segmentation d'image (= la d�limitation automatique des diff�rents objets pr�sents dans la sc�ne) puisqu'au lieu de se baser uniquement sur la similarit� des couleurs entre pixels voisins, on peut d�sormais s'appuyer �galement sur leur distance dans l'espace 3D. Par ailleurs, la librairie OpenNI offre la possibilit� d'estimer, en temps r�el, le squelette des personnes pr�sentes dans la sc�ne, c'est-�-dire la position de chacune de leurs articulations dans chacune des images de la vid�o. Par cons�quent, il devient possible d'�tudier pr�cis�ment la dynamique des mouvements, des gestes effectu�s, afin de les d�crire, comparer ou classifier. Objectifs et difficult�s : Il s'agit de reconna�tre automatiquement diff�rents types de gestes, avec la meilleure pr�cision possible. Pour cela, il faut tout d'abord les d�crire, gr�ce aux vitesses angulaires des articulations. Une premi�re difficult� est que les estimations des angles peuvent �tre bruit�es. Ensuite, il faut pouvoir comparer divers gestes. Les difficult�s ici sont qu'il faut savoir quand un geste commence et finit, que la vitesse d'un m�me geste (ou d'une partie du geste uniquement) peut varier, que la carrure des personnes effectuant les gestes peut varier (espacement des �paules, longueur des bras, etc.). Approche : On mod�lisera les descripteurs int�ressants (angles relatifs entre articulations, position absolue/relative au corps, au capteur, extremum de trajectoire ...). Comme la dimension temporelle est particuli�rement importante, on travaillera dans l'espace des phases (position et vitesse) : il s'agira alors de trouver, manuellement ou automatiquement, des descripteurs pertinents des trajectoires suivies, pour quantifier la similarit� de deux gestes ou la distance entre eux. Pour cela, l'algorithme de recalage en temps "dynamic time warping" se r�v�lera utile. Mat�riel : 1 cam�ra kinect ou �quivalent (Asus xtion) Contraintes : temps r�el (30 images par seconde) Suggestions de notions avec lesquelles �tre familier avant le stage : - espace des phases - �quations diff�rentielles (ordinaires/aux d�riv�es partielles) - les diff�rentes fa�ons de repr�senter des angles en 3D (angles d'Euler, coordonn�es sph�riques) - l'algorithme de recalage temporel "dynamic time warping" - automate, cha�ne de Markov (matrice de transition) - covariance Programmation : - langage : C++ - librairie OpenNI ( http://openni.org/ ) pour l'extraction du squelette (position des articulations) - �ventuellement, la librairie OpenCV ( http://sourceforge.net/projects/opencv/ ) Remarques: Encadrant secondaire : Olivier Clatz (�quipe Asclepios)

Encadrement   Encadrant : Monique TEILLAUD Labo/Organisme : INRIA Ville : Sophia Antipolis

Description Sujet choisi par Mathieu SCHMITT   Lloyd's algorithm, or Voronoi relaxation, is used in several applications to compute centroidal Voronoi tessellations. Its convergence has been shown in one dimension. In higher dimensions, one of the problems is due to the fact that the studied domain has a boundary. A package computing 3D periodic Delaunay triangulations has recently been integrated in CGAL, the Computational Geometry Algorithms Library. A demo of Lloyd's algorithm is available. The work will consist in experimentally stuying the convergence of Lloyd's algorithm in the 3D periodic setting, which avoids boundaries. The same experiments will be run with the optimal Delaunay triangulation. In both cases, the distribution of angles will be studied. Also, a possible convergence to some crystalline structures will be examined. Accéder au sujet détaillé

Encadrement   Encadrant : Frederic Cazals Labo/Organisme : INRIA Sophia-Antipolis-Mediterranee Ville : Sophia Antipolis

Description Sujet choisi par Romain TETLEY   Accéder au sujet détaillé

Encadrement   Encadrant : Matthieu LATAPY Labo/Organisme : LIP6 - CNRS et UPMC Ville : Paris

Description Sujet choisi par Weiyang WU   Lorsqu\'on est sur une machine de l\'Internet (une source), il est possible de connaitre le chemin suivi par les informations partant de cette machine vers n\'importe quelle autre machine de l\'Internet (une destination). Cette approche est largement utilisée pour explorer la topologie de l\'Internet (machines et liens entre elles). Nous proposons ici un nouveau point de vue : nous allons voir l\'exécution de traceroute comme une sonde qui, utilisée périodiquement, va nous permettre de construire un radar pour l\'Internet. Accéder au sujet détaillé