Informations M2 (archives 2018-2019)

General Outline

The Master 2 in Computer Science is composed of classes and winter schools from September 10, 2018 to January 25, 2019, followed by an internship from January 28 to June 15, 2019. See details below.

Latest Information

Updated schedule and latest info available on the read-only password-protected pad :

https://pad.inria.fr/p/r.7e3a9396c0b060bfc755a346325a79f2

passwd: m2info18

List of Courses (for full description follow the link CRxx):

  • CR01: Optimal Decision Making and Online Optimization, Panayotis Mertikopoulos and Bruno Gaujal (Grenoble).
  • CR02: Computational Geometry, Monique Teillaud and Olivier Devillers (Nancy).
  • CR03: Hard lattice problems, Damien Stehlé. (Lyon)
  • CR04: Scheduling at scale, Yves Robert. (Lyon)
  • CR05: Advanced Topics in Scalable Data ManagementEddy Caron
  • CR06: Software Engineering & Compilation, Sebastien Mosser and Laure Gonnord (Lyon, Nice).
  • CR07: Complex NetworksMarton Karsai. (Lyon)
  • CR08: Lower bound methods, Pascal Koiran, Omar Fawzi, and Stéphan Thomassé (Lyon)
  • CR09: Approximation Theory and Proof Assistants: Certified Computations, Nicolas Brisebarre and Damien Pous (Lyon)
  • CR10: Cryptanalysis, Elena Kirshanova, Damien Stehlé, and Guillaume Hanrot (Lyon)
  • CR11: Hardware Compilation and Simulation, Christophe Alias and Matthieu Moy (Lyon)
  • CR12: Combinatorial scientific optimization, Bora Ucar, Fanny Dufossé (Lyon, Grenoble)
  • CR13: Topological combinatorics, Frédéric Meunier and Matěj Stehlík (Paris, Grenoble)
  • CR14: Advanced topics in semantics of programming language, Pierre Clairambault and Colin Riba (Lyon)
  • CR15: Logic, Automata and Games for Advanced Verification, Matteo Mio and Denis Kuperberg (Lyon)
  • CR16: Automated Deduction, and opening to Distributed Algorithms, Xavier Urbain and Sébastien Tixeuil (Lyon, Paris)
  • CR17: Machine learning, Aurélien Garivier (Lyon)

Winter Schools:  There are two winter schools taking place during weeks 48 (starting on Monday, Nov. 26) and 49 (starting on Monday, Dec.  3) . During these weeks, the courses stop and are replaced by the schools, which last the whole week. Topics will be announced later on.

Pre-course Meeting: A pre-course meeting will take place on Monday, September 10, 2018 at 9.30am, Amphi B. Attendance to this meeting is mandatory for all students. The general organization of the year and a description of the courses will be provided. Courses start on Monday, September 10, at 1:30pm.

Training Period: A mandatory training period takes place from Monday, January 21 up to mid June. An information session about topics and locations for the training period will be organized in September. Basically, the goal is to research in a laboratory (anywhere on earth), write a report and make an oral presentation in the end.

Schedule: Courses start September 10 at 1:30pm. Autumn holidays are October 27-November 4. Winter holidays are December 22-January 6. Exams will be held on week 3 (starting Monday Jan. 14), for a subset of courses. Again, the detailed weekly schedule will be available on the Inria pad mentioned above. This page will be read-only and updated on a regular basis, check it often.

Rules of the Game: To obtain their degree, CS Master students must complete 60 credits including the internship (30 credits), two winter schools (3 credits each) and four courses (4 credits each) in the above list of CR1 to CR17. To summarize, there are 52 mandatory credits out of 60 and 8 credits that can be picked elsewhere. While a typical choice by many students is 6 CR courses, 2 schools and the internship, the extra courses for the 8 credits can be chosen elsewhere,  e.g. CS courses in the M2 offered by Univ. Lyon 1, or courses from other ENS departments.

Complex Systems: There is an exception for the orientation ‘Complex Systems’. See details at

http://www.ixxi.fr/enseignement/master_systemes_complexes

for course offering. For the validation, the two winter schools are not mandatory for complex systems students, only 4 CR courses and the training period are mandatory, so after mandatory stuff there remains 14 credits instead of 8  to validate, using a selection of courses from the orientation.

Note that ‘Complex Systems’ is an orientation, not a separate M2. The only diploma delivered by ENS Lyon is M2 Informatique Fondamentale, and computer science must remain at the heart of the curriculum. In particular, the training period must be oriented towards research in core computer science (possibly applied to other disciplines).

Formal Validation: To meet the quality requirements of our program, all course choices must be approved by the academic tutor and the head of the Master 2 program. Administrative registration to chosen courses is mandatory and takes place in late September, after a trial period.

Please refer to the rules of the Master here

Contact: Yves Robert

Information M2 – 2017/2018

List of courses (for full description follow the link CRxx):

  • CR01: Optimal Decision Making and Online Optimization, Panayotis Mertikopoulos and Bruno Gaujal.
  • CR02: Computational Geometry, Monique Teillaud and Olivier Devillers.
  • CR03: Hard lattice problems, Damien Stehlé.
  • CR04: Automata, coinduction, and relation algebra, Damien Pous.
  • CR05: Monadic Second Order Logic, Automata, Expressivity and DecidabilityMatteo Mio and Denis Kuperberg.
  • CR06: Implicit Computational Complexity, Patrick Baillot and Olivier Laurent.
  • CR07: Models of concurrency, categories, and games, Pierre Clairambault and Glynn Winskel.
  • CR08: Scheduling at scale, Yves Robert.
  • CR09: Advanced Topics in Scalable Data ManagementEddy Caron and Marcos Dias de Assuncao
  • CR10: Software Engineering & Compilation, Sebastien Mosser and Laure Gonnord 
  • CR11: Mathematical Methods for Image SynthesisNicolas Bonneel and Julie Digne.
  • CR12: Modeling and performance evaluation of computer and communications system, Philippe Nain.
  • CR13: Computational TopologyFrancis Lazarus and Arnaud de Mesmay.
  • CR14: Network Information TheoryJean-Marie Gorce and Samir M. Perlaza. Sorry, this course will not open this year but later in 2018-2019.
  • CR15: Complex NetworksEric Fleury and Marton Karsai.
  • CR16: Lower bound methods, Pascal Koiran, Omar Fawzi, and Stéphan Thomassé.
  • CR17: Graph Decompositions: From Tree-Width to Perfect GraphsNicolas Trotignon and Stéphan Thomassé.

Winter schools:  Information will be provided later on. The three schools will take place on week 49 (starting Monday Dec. 4), on week 3 (starting Monday Jan. 15)  and on week 4 (starting Monday Jan. 22).

Pre-course meeting: A (mandatory) pre-course meeting will take place on Monday, September 11 at 9.30am, Amphi B. The general organization of the year and a description of the courses will be provided.

Schedule: Courses start September 11 at 1:30pm. Autumn holidays are October 28-November 5. Winter holidays are December 23-January 7. Exams will be held on week 2 (starting Monday Jan. 8), for a subset of courses. The detailed schedule is available here:

https://pad.inria.fr/p/r.542fa856c4fe21df30b444eb43913405

This page is read-only and password protected (password is ‘m2info17’). The page is updated on a regular basis, check it often.

On Thursday October 12 at 12:15pm, right after the CR15 course, there is a meeting about the training period (or internship). Come ofr information and prepare your questions!

Validation: To obtain their degree, CS Master students must complete 60 credits including the internship (30 credits), three winter schools (2 credits each) and four courses (4 credits each) in the above list. A typical choice is 6 courses, 3 schools and the internship; the extra courses can be chosen either in the CS courses or in the other departments. To meet the quality requirements of our program, the course choices must be approved by the academic tutor and the head of the Master 2 program. Administrative registration is mandatory. Please refer to the rules of the Master here

Contact: Yves Robert

Master 2 – 2016/2017

List of courses (for full description follow the link CRxx):

CR-01 : Usages du hasard en sciences (du hasard qui fait du bruit)

Programme de l’UE

A) Partie Informatique: Possibilités inattendues offertes par le hasard en algorithmique (N. Schabanel)

Depuis une trentaine d’années, les informaticiens ont révélé que l’on pouvait faire des usages assez étonnants du hasard, d’autant plus étonnants que ces résultats sont violemment contre-intuitifs. Nous verrons dans ce cours comment utiliser du hasard pour compter exactement avec une mémoire toute petite (randomized counters), comment corriger un programme buggé sans modifier son code (autocorrection de code), comment tester si quelqu’un sait quelque
chose, sans rien apprendre ni savoir de son secret (zero-knowledge), étudier les étranges propriétés des graphes expandeurs et leurs étonnantes applications.

Le plus surprenant est que ces méthodes sont très simples, tant  prouver et qu’  mettre en oeuvre, et sont le plus souvent bien plus efficaces que leurs alternatives déterministes: à la fois plus rapides et plus économiques en ressources. Ces techniques ont donc toutes les chances d’être favorisées par la sélection naturelle et pourraient donc bien se retrouver dans la nature, donc autant s’y préparer ! Le hasard est ainsi loin d’être seulement un bruit dont on chercherait à se débarrasser mais est au contraire appeler à jouer des rôles moteur insoupçonnés. Nous verrons également comment la notion de hasard peut être reliée à la notion de problèmes difficiles.

B) Partie physique :  Bruit et/ou information  (P. Borgnat et P. Flandrin)

Classiquement le bruit est vu comme une nuisance dont il faut s’affranchir dans des méthodes d’analyse de données, que ce soit en traitement du signal et des images, en statistiques ou dans des opérations d’acquisition de données. Cependant, au-delà de dire parfois que l’information peut être portée par du bruit, certaines méthodes proposent d’utiliser le bruit comme aide à l’analyse et à la décision. Plusieurs de ces approches ont une origine dans le monde des sciences physiques. On propose de couvrir trois familles d’approches en ce sens :

  1. Accès à des données avec de l’aléatoire dans les mesures : Echantillonnage ou quantification aléatoires ou irréguliers ; idée d’échantillonnage compressif (compressed sensing) ; estimation par projections aléatoires (scketch, filtres de Bloom,…)
  2. Méthodes de brassage aléatoire des données : bootstrap ; données substituts (surrogates),…
  3. Analyse assistée par le bruit : résonance stochastique ; moyennes robustes par l’ajout de bruit ; liens avec les algorithmes ou les simulations assistés par le bruit (gradients stochastiques, méthodes de Monte-Carlo, recuit simulé).

C) Partie biologie: le hasard au coeur de la cellule (O. Gandrillon) (à confirmer)

Mots clés.

 

Prérequis.

 

Modalités de l’examen.

 

Intervenants

  • Nicolas Schabanel, DR CNRS (responsable)
  • Pierre Borgnat, CR CNRS
  • Patrick Flandrin, DR CNRS
  • Olivier Gandrillon, Univ. Lyon 1

CR-02 : Concurrence et complexité implicite

Programme de l’UE

On étudiera les systèmes concurrents et le calcul fonctionnel par le biais de deux formalismes: les calculs de processus d’une part, et le lambda-calcul d’autre part. Des problèmes comparables se posent pour
l’analyse des systèmes dans les deux cadres: peut-on statiquement garantir que l’exécution d’un programme va terminer ? Peut-on apporter des bornes de complexité en temps sur cette terminaison?

Dans le cas des calculs concurrents, on développera les concepts permettant de raisonner sur la dynamique des systèmes, sur l’équivalence de processus, et sur leur terminaison. Dans celui du lambda-calcul on présentera des systèmes de types dérivés de la logique linéaire et permettant de garantir statiquement des bornes de complexité sur les programmes. On illustrera ainsi comment des techniques communes (typage) peuvent être exploitées à la fois dans le cadre concurrent et dans le cadre fonctionnel.  Enfin si le temps le permet on verra comment les méthodes développées pour la complexité dans le cadre du calcul fonctionnel inspirent des approches similaires dans le cadre concurrent.

Prérequis. 

  • notions élémentaires de lambda-calcul simplement typé,
  • définitions de base de classes de complexité en temps déterministe (les notions des cours d’algorithmique de L3 sont suffisantes). Les définitions nécessaires seront cependant rappelées.

Calendrier prévisionnel : 08/10, 09/10, 16/10, 22/10, 23/10, 6/11, 12/11, 13/11, 19/11, 26/11, 27/11, 4/12

Modalités d’examen. Un devoir à la maison en cours de trimestre, et un examen écrit à la fin du cours.

Intervenants:

  • Patrick Baillot, CR CNRS (responsable)
  • Damien Pous, CR CNRS

CR-03 : Preuve et arithmétique virgule flottante

Programme de l’UE

L’arithmétique virgule flottante, grâce à son efficacité (grande « dynamique » et opérateurs très rapides) s’est imposée en calcul scientifique. Aucun des problèmes numériques de très grande taille qui se posent quotidiennement aux ingénieurs (mécanique des fluides, calculs de structures, etc.) ne serait résoluble en temps raisonnable autrement qu’en arithmétique virgule flottante. Pourtant son caractère approché peut parfois poser problème (des erreurs d’arrondis peuvent s’accumuler). Egalement, une programmation erronée ou naïve peut rendre le comportement des programmes imprévisibles. Enfin, les utilisateurs ignorent trop souvent que depuis quelques années le comportement des opérations virgule flottante est complètement spécifié (norme IEEE 754), et qu’on peut élaborer des preuves qui utilisent ces spécifications. Ce dernier point est très important lorsque l’arithmétique virgule flottante est utilisée dans un contexte où une erreur pourrait avoir des conséquences graves (transport aérien, contrôle de processus physico/chimiques dangereux, etc.)

L’objet de ce cours est d’abord de présenter aux étudiants des propriétés « fines » de l’arithmétique virgule flottante: grâce aux spécifications de la norme IEEE 754, on peut construire et prouver des algorithmes qui permettent de faire des calculs « exacts » (ou très précis) avec cette arithmétique « approchée » (calculs exacts de sommes, de produits scalaires, mise au point d’algorithmes de division, de calcul des fonctions « transcendantes »). On se focalisera ensuite sur la possibilité d’élaborer des preuves formelles des algorithmes virgule flottante, en illustrant ce point par la formalisation dans l’assistant de preuve Coq de l’arithmétique virgule flottante.

Modalités d’examen. L’évaluation se fera par une analyse d’articles présentée par un rapport écrit et une soutenance orale, lors de laquelle des questions portant sur le cours pourront être posées.

Prérequis: un minimum de notions de logique et d’algorithmique. Les débutants complets en Coq sont les bienvenus, le cours s’adaptera à eux.

Bibliographie pour le cours

Calendrier prévisionnel

11/09, 18/09, 19/09, 25/09, 2/10, 3/10, 9/10, 16/10, 17/10, 24/10, 6/11, 7/11 [de 8h à 10h].

Intervenants

  • Jean-Michel Muller, DR CNRS (responsable)
  • Damien Pous, CR CNRS
  • Laurent Théry, CR INRIA

CR-04 : Décompositions arborescentes et algorithmes FPT

Programme de l’UE

Une grande majorité des problèmes en algorithmique des graphes sont NP-difficiles, comme par exemple le problème du voyageur de commerce. En revanche, la plupart de ces problèmes deviennent polynomiaux lorsque les graphes considérés sont acycliques, e.g. des arbres. Une manière de contourner la difficulté est de structurer le graphe en le décomposant de façon arborescente. L’objectif de ce cours est de présenter ces techniques, dont notamment la désormais incontournable notion de tree-width, ou largeur arborescente, introduite par Robertson et Seymour. Une introduction aux algorithmes FPT (fixed parameter tractable), qui découlent de cette théorie, sera aussi proposée.

  1. Introduction des notions de largeur arborescente (tree-width) et de ses nombreux dérivés, dont la path-width et la branch-width. Résultats de base, jusqu’au Grid-Minor Theorem.
  2. Programmation dynamique sur les graphes de largeur arborescente bornée.  Ce résultat est le point de départ du chapitre suivant.
  3. Introduction à la complexité paramétrée.
  4. Notion de Noyau et d’algorithme de compression.
  5. Le théoreme des mineurs de graphes. Avec son corollaire principal: Pour toute classe de graphe close par mineur, il existe un algorithme polynomial qui décide si un graphe appartient à cette classe ou pas. Nous présenterons ce résultat, certainement le plus difficile et le plus profond de la théorie des graphes. Une application directe est par exemple qu’il est polynomial de décider si un graphe se plonge sur une surface donnée. La largeur arborescente et le routage (linkage) sont les clés de ce résultat.
  6. Graph Searching. La notion de largeur arborescente est interprétable en termes de nombre minimum d’agents requis pour rechercher un fugitif dans un réseau. Les stratégies gagnantes des deux camps suggèrent une dualité.
  7. Certificat dual de la tree-width. Introduction de la notion de bramble et autres certificats des mesures de largeur arborescente.
  8. Introduction de la notion de clique-width de Courcelle. Une mesure de complexité qui capture plus de graphes que la tree-width, et stable par complémentation. Equivalence avec la notion de rank-width de Seymour et Oum.

Prérequis. Le cours s’adaptera au public.

Calendrier prévisionnel. 14/09, 17/09, 21/09, 24/09, 28/09, 01/10, 05/10, 12/10, 15/10, 26/10, 5/11, 9/11

Modalités d’examen. Examen écrit et oral.

Bibliographie

  • Une petite Introduction aux mineurs de graphes, de László Lovász.
  • Le Graph Theory, de Reinhard Diestel, est à conseiller. Le chapitre 12, traite de la ‘tree-width’.
  • Le Parameterized Complexity Theory, de Jorg Flum et Martin Grohe, est une bonne réference pour les algorithmes FPT.

Pour les plus courageux, la série des Graph Minors de I à XXIII, de Neil Robertson et Paul Seymour, est intéressante à parcourir, pour se rendre compte de la difficulté du résultat.

Lien sur la page du cours

Intervenant

  • Stéphan Thomassé, Pr ENS Lyon

CR-05 : Modèles de Blum-Shub-Smale et de Valiant

Programme de l’UE

Prouver des bornes inférieures sur la complexité algorithmique de problèmes spécifiques est souvent très difficile.  Par exemple, la question « P=NP ? » est de cette forme: il s’agit d’obtenir une borne inférieure superpolynomiale sur la complexité en temps du problème SAT (ou de manière équivalente sur la complexité de n’importe quel problème NP-complet).  Etant donnée la difficulté de ce problème et d’autres problèmes de ce type, on a proposé des modèles de calculs algébriques, variantes des modèles booléens « standards »; et on espère que les questions analogues soient plus abordables dans ces nouveaux modèles.

Les deux principales versions algébriques du problème « P=NP ? » sont dûes à Valiant et à Blum-Shub-Smale, et sont toujours ouvertes. Par exemple, le contenu algorithmique du problème « P=NP ? » dans le modèle de Blum-Shub-Smale sur le corps des nombres réels est le suivant: étant donné un polynôme dedegré 4 en n variables, peut-on décider s’il admet une racine réelle en un nombre d’opérations arithmétiques et de comparaisons polynomial en n ? Les meilleurs algorithmes connus à ce jour effectuent un nombre d’opérations exponentiel en n.

Dans le modèle de Valiant on ne s’intéresse pas à des problèmes de décision mais à l’évaluation de polynômes. Le contenu algorithmique de la question VP=VNP peut être formulé ainsi: est-il possible d’évaluer le permanent d’une matrice en un nombre d’opérations arithmétiques polynomial en la taille de cette matrice ?

On présentera ces deux modèles de calcul et des approches proposées pour aborder les versions correspondantes du problème P=NP:

  • conjecture tau de Shub et Smale: n! (ou un multiple) ne peut pas se calculer en un nombre d’opérations arithmétiques polynomial en log n
  • La version de cette conjecture sur le nombre de racines entières des polynômes donnés par circuits (qui est supposé polynomial en la taille du circuit).
  • La non généralisation aux racines réelles (polynômes de Chebyshev, exemple de Borodin-Cook).
  • Une version réelle pour les sommes de produits de polynômes creux.

On présentera également des résultats sur la réduction de profondeur pour les circuits arithmétiques, certains anciens (Muller-Preparata, Valiant-Skyum-Berkowitz-Rackoff), d’autres plus récents (Agrawal-Vinay).  Ces résultats sont non seulement intéressants du point de vue du calcul parallèle, mais aussi comme on le verra pour les bornes inférieures.

Prerequis: Il s’agit d’un cours de complexité donc un certain goût pour ce sujet et les connaissances acquises à l’occasion d’un premier cours (par exemple, le cours de complexité algorithmique de M1) ne peuvent pas faire de mal. Mais il n’y aura pas de besoin de connaissances specialisées dans le domaine car le cours porte sur des modèles de calcul alternatifs à la traditionnelle machine de Turing. Si nécessaire, quelques rappels de complexite booléenne seront faits.

Modalités d’examen : exposé sur un article (petit rapport + présentation orale) et examen écrit « classique » à la fin.

Intervenant

  • Pascal Koiran, Pr. ENS Lyon

CR-06 : Approximations : du symbolique au numérique, et applications.

Programme de l’UE

Nous passons en revue une partie de la théorie de l’approximation du point de vue du calcul effectif. Comment calculer des approximants polynomiaux ou rationnels, développer efficacement en série de Taylor ou sur des bases de polynômes orthogonaux, calculer des approximants de Padé, puis comment utiliser ces développements pour obtenir des approximations à précision donnée (algorithmes de Remez, modèles de Taylor et de Chebyshev). La puissance de ces techniques sera illustrée en développant trois applications, attachées à des domaines scientifiques différents : preuves d’irrationalité en théorie des nombres, évaluation efficace de fonctions numériques, problème des « Near-Earth Objects ».

Prérequis :

Calendrier prévisionnel : 19/09, 24/09, 26/09, 01/10, 08/10, 10/10, 15/10, 22/10, 24/10, 5/11, 7/11, 12/11.

Modalités d’examen : Examen écrit, et un travail à la maison noté.

Intervenants

  • Nicolas Brisebarre, CR CNRS (responsable)
  • Bruno Salvy, DR INRIA

CR-07 : Ordonnancement

Programme de l’UE

L’ordonnancement est une branche de la recherche opérationnelle qui vise à allouer des ressources à un ensemble de tâches, et de planifier leur exécution dans le but d’optimiser une certaine fonction objective (temps d’exécution, rendement, etc). Dans ce cours, nous étudierons les problèmes d’ordonnancement présents dans les systèmes informatiques, et en particulier dans les plates-formes de calcul parallèles.

Nous commencerons par présenter des problèmes et techniques classiques en ordonnancement, puis nous introduirons progressivement des modélisations qui permettent de prendre en compte les spécificités des plates-formes de calcul actuelles tout en permettant de résoudre les problèmes d’ordonnancement. Nous présenterons enfin des objectifs propres à ces plates-formes, ainsi que les techniques employées pour résoudre les problèmes qu’ils soulèvent.

Plan du cours

  1. Approches classiques de l’ordonnancement
    • introduction et problèmes classiques (list scheduling, Smith ratio, etc.)
    • modélisation des applications (graphes de tâches, flow-shop, tâches malléables, etc.)
    • rappel de NP-complétude, algorithmes d’approximation
    • ordonnancement à la volée et non-clairvoyant
  2. Vers une modélisation plus réaliste des plates-formes de calcul introduction des coûts de communications
    • ordonnancement de tâches divisibles
    • ordonnancement en régime permanent
    • prise en compte de interférences calculs/communications
  3. Nouveaux objectifs et nouvelles techniques en ordonnancement
    • tolérance aux pannes, robustesse
    • réduction de la consommation d’énergie
    • ordonnancement multi-organisation
    • apports de la théorie des jeux
    • approche stochastique
    • ordonnancement multi-critère

Toutes les techniques exposées seront abondamment illustrées par des études de cas.

Modalités d’examen. L’évaluation consistera à une analyse et présentation d’articles. Certains cours seront d’ailleurs l’occasion pour les étudiants de pratiquer la lecture et l’analyse d’articles.

Pré-requis: il est souhaitable (mais pas indispensable) d’avoir suivi le cours d’Algorithmique Parallèle de M1. Des étudiants motivés peuvent s’en passer en lisant quelques chapitres importants du livre correspondant.

Intervenants

  • Loris Marchal, CR CNRS
  • Frédéric Vivien, DR INRIA

CR-08 : Compilation avancée

Programme de l’UE

Un compilateur n’est autre qu’un traducteur d’un langage (par exemple C ou Caml) vers un autre (par exemple un langage assembleur). Bien entendu, les langages de programmation sont dotés de propriétés sympathiques (par exemple grâce aux grammaires LALR) qui font que les traductions des compilateurs sont, heureusement, nettement plus convaincantes que celles d’un traducteur de langage naturel comme Babel Fish! On ne s’intéressera pas dans ce cours à ces problèmes de traduction, aujourd’hui bien maîtrisés.

Aujourd’hui, on demande bien plus à un compilateur, on veut qu’il génère du code non seulement correct (traduction) mais aussi efficace pour l’architecture cible (compilateur optimisant). Écrire « from scratch » un compilateur pour un processeur spécifique prend plusieurs années pour une équipe d’ingénieurs et, avec la pression du marché (« time-to-market ») et l’évolution rapide des processeurs, cette approche n’est pas viable. On préfère produire des compilateurs dits reciblables, optimisants, pour une gamme de processeurs.

La difficulté et l’intérêt (du point de vue du chercheur) résident dans la mise au point d’optimisations. On souhaite que le code soit rapide, qu’il génère le moins de trafic mémoire possible, qu’il consomme peu, qu’il soit compact, etc. En pratique, une optimisation est une recette de cuisine pour transformer, améliorer le code, enrichir l’information que l’on a de celui-ci. Les recettes de cuisine sont bien entendu plus ou moins sophistiquées et coûteuses, et la difficulté pour l’ingénieur-cuisinier est de les faire cohabiter et de les utiliser à bon escient. Ainsi, la compilation est avant tout un problème d’ingénierie (certes d’experts) où la difficulté réside dans le choix des représentations intermédiaires du code et des informations qui lui sont associées: la représentation intermédiaire permet ou non d’exprimer trivialement certaines propriétés, ce qui influence considérablement l’implémentabilité de tel ou tel outil d’analyse.

On verra entre autres que les outils « mathématiques » nécessaires aux optimisations en compilation sont relativement divers (théorie des graphes, propriétés de treillis, programmation linéaire, ordonnancement) selon les représentations intermédiaires (graphe de flot de contrôle, forme SSA, forme psi-SSA, boucles imbriquées), les niveaux d’abstraction du code (code source ou code assembleur), et les fonctionnalités architecturales (instructions avec prédicats, registres). Le but de ce cours sera donc de décrire un certain nombre de phases d’analyses et de transformations relativement classiques et d’en profiter pour donner un aperçu des outils utilisés par le chercheur en optimisation de programmes.

Contenu du cours (indicatif)

Les thèmes suivants seront traités:

  • Représentations (CFG, psi-SSA, dominance, loop-forest, etc.)
  • Analyse (dependances, durée de vie, alias, flot de données, interprétation abstraite — treillis, points fixes, étiquetage de graphe)
  • Transformations (fusion de boucles, pavage, data-layout, source-à-source, unimodulaire — ILP, graphes, polyèdres, réseaux)
  • Allocation de registres (assignation vs allocation, vidage en mémoire, coalescing — graphes, optimisation combinatoire, LP)
  • Ordonnancement (ordonnancement, pipeline logiciel — ILP, approximabilité, retiming)

Calendrier prévisionnel

12/09, 17/09, 19/09 [de 16h à 18h]

Intervenants

  • Alain Darte, DR CNRS
  • NN

CR-09 : Grilles et Nuage de Calcul

Programme de l’UE

Ce cours vise à offrir une présentation la plus large possible de ce qui fait en recherche autours des grilles (dans différentes déclinaisons grilles de calcul, grille de recherche, grille de production, etc.). Nous aborderons des sujets tels que les architectures de grille, la gestion de données (Hadoop, etc.), les intergiciels, la notions de services (SOA, PaaS, SaaS, …), le Cloud computing, etc. ainsi que les différents modèles de programmation, tels que les worflows, les composants logiciels, les squelettes algorithmiques ou encore les modèles chimiques. Ce cours de seconde année de master sera fortement orienté recherche par l’étude d’articles du domaine par les étudiants.

Intervenants

  • Eddy Caron
  • Christian Perez

CR-10 : Théorie des jeux et applications dans les systèmes répartis.

Programme de l’UE

La théorie des jeux est aujourd’hui un outil indispensable pour comprendre l’évolution de domaines aussi divers que l’apprentissage, la tarification, l’optimisation distribuée ou l’algorithmique des réseaux de communications.

Plan général:

  • En introduction, nous allons introduire les concepts principaux de la théorie des jeux (définition, matrice de gain, équilibre de Nash, de Wardrop, notions d’équité, mesure d’efficacité).
  • Dans un deuxième temps, nous allons étudier plus précisément certains types de jeux: jeux à somme nulle, jeux de potentiel, jeux super-additifs.
  • Une troisième partie présentera les mécanismes d’enchères et les coalitions qui donnent lieu à des notions d’équilibres légèrement différentes.
  • Une quatrième partie sera consacrée à quelques applications dans le domaine des réseaux de communication (on montrera en particulier que TCP est équitable au sens de l’équité proportionnelle), et des méthodes de résolution de routage optimal.

Le deuxième volet du cours sera consacré aux algorithmes de calcul des équilibres dans les contextes présentés précédemment.

  • On présentera la dynamique de meilleure réponse, de réplication,… et on montrera leurs propriétés de convergence vers les équilibres de Nash.
  • Nous étudierons ensuite des versions algorithmiques distribuées de ces dynamiques en mettant en évidence les difficultés qui apparaissent alors.
  • Une dernière partie sera consacrée à étudier les liens avec les dynamiques d’apprentissages (recuit simulé, méthode de Monte Carlo et plus généralement, les méthodes d’approximations stochastiques)

Dates des cours :

Liens sur des transparents.

Intervenants

  • Bruno Gaujal, DR INRIA
  • Corinne Touati, CR INRIA

CR-11 – Réseaux avancés : architectures et protocoles

Programme du cours

  • Architecture de l’internet du futur (réseaux/équipements) : evals de perfs, simulation, modélisation
  • Introduction à la simulation à événements discrets (2 x 2h)
  • Cas pratique d’un routeur (2 x 2h)

Nouveaux protocoles réseaux : services/middleware, QoS, réseaux verts

  • Réseaux autonomes et programmables (2h)
  • Réseaux fiables (2h)
  • Réseaux verts (2 x 2h)
  • Communication entre processus (par message (socket), par mémoire partagée (RPC)) (3h)
  • Liens entre middleware (MPI), réseaux rapides et infrastructures (3h)

Planning prévisionnel :

20/09, 27/09, 4/10, 11/10, 18/10, 25/10

Intervenants

  • Thomas Begin, MCF UCBL
  • Laurent Lefèvre, CR INRIA

CR-12 : Grands graphes de terrain

Programme de l’UE

Dans de nombreux contextes des grands graphes jouent un rôle essentiel ; citons par exemple la topologie de l’Internet, les graphes du Web ou les échanges Pair-à-Pair, mais aussi les réseaux sociaux, réseaux de contact, biologiques ou linguistiques. La disponibilité de données massives, de capacités de traitement adéquates, et l’observation de diverses propriétés en commun ont récemment donné naissance à un vaste effort de recherche sur ces objets. Son originalité réside dans le fait qu’on part de graphes issus d’observations, et non définis formellement. C’est en ce sens que ce sont des « graphes de terrain« .

Ce cours abordera les différentes problématiques soulevées par ce domaine que l’on peut regrouper en quatre familles complémentaires :

  • Mesure et Métrologie Mener des mesures fiables, de qualité et à grande échelle est une problématique de recherche en soi, qu’il ne faut pas ignorer. savoir ce que l’on mesure, comment et pourquoi est l’un des points de départ crucial de l’analyse des grands graphes de terrain.
  • Analyse : On abordera les outils et les formalismes pour décrire les grands graphes de terrain afin d’en extraire les principales propriétés.
  • Modélisation. Une fois les principales propriétés d’un graphe identifiées, les capturer dans un
    modèle formel est crucial notamment pour les expliquer, obtenir des résultats formels, et mener
    des simulations.
  • Algorithmique. La taille des graphes considérés interdit l’utilisation d’algorithmes quadratiques ou plus ; de nombreux problèmes pour lesquels des solutions habituellement satisfaisantes sont connues doivent donc être retravaillés. Par ailleurs, la présence de propriétés caractéristiques des graphes de terrain ouvre la voie au développement d’algorithmes efficaces dans ces cas.

Intervenants

  • Alain Barrat, CR CNRS, Centre de Physique Théorique, Marseille, France
  • Eric Fleury, Professeur ENS Lyon
  • Christophe Crespelle, Maître de conférences, Université de Lyon 1

Support de cours