Informations M2 – 2020/2021

General Outline

The Master 2 in Computer Science is composed of research courses (CR)  from September 7, 2020 to January 29, 2021, followed by an internship from February 1 to June 25, 2021. An extended set of 19 courses will open. Each course corresponds to 32 hours (typically 4 hours per week during 8 weeks). Here is a tentative calendar:
– Monday, September 7, 2020: pre-course meeting at 9:30am. Attendance to this meeting is mandatory for all students.
– Wave 1 : weeks starting on 07/09, 14/09, 21/09, 28/09, 05/10, 12/10, 19/10, 02/11 and 09/11, with a vacation week starting on 26/10 (Toussaint). 9 courses will take place during wave 1.
– Wave 2 : weeks starting on 16/11, 23/11, 30/11, 07/12, 14/12, 04/01, 11/01, 18/01 et 25/01, with two vacation weeks starting on 21/12 et 28/12 (Christmas). 10 courses will take place during wave 2.
– Full-time internship from 01/02 to 25/06, 2021.

Latest Information

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

https://pad.inria.fr/p/r.fe63ced1eb81edb1b8ee6bc300de5990

passwd: m2info20

List of Courses (for full description follow the link CRxx — some links to be updated soon):

  • CR01: Virtualization technologies: design and implementation, Alain Tchana (ENS Lyon)
  • CR02: Selected topics in Information Theory, Jean-Marie Gorce (INSA Lyon) and Samir Perlaza (INRIA)
  • CR03: Graph-based knowledge representation (for complex systems and graph databases), Angela Bonifati and Russ Harmer (Lyon 1, ENS Lyon)
  • CR04: Hidden Markov models for time series classification and filtering, Stéphane Derrode (Centrale Lyon)
  • CR05: Data aware algorithms, Loris Marchal (ENS Lyon)
  • CR06: Modern algorithms for symbolic summation and integration, Bruno Salvy, Gilles Villard and Alin Bostan (ENS Lyon, Inria Saclay)
  • CR07: Parameterized and exact algorithms, Édouard Bonnet and Rémi Watrigant (ENS Lyon)
  • CR08: Quantum information and computation, Guillaume Aubrun, Andre Chailloux and Omar Fawzi (ENS Lyon) (Lyon 1, Inria Paris, ENS Lyon)
  • CR09: Numerical methods for computer graphics, Julie Digne and Nicolas Bonneel (Lyon 1)
  • CR10: Advanced Topics in Cryptography, Alain Passelègue (ENS Lyon)
  • CR11: Molecular programming, Nicolas Schabanel (ENS Lyon)
  • CR12Numerical Mechanics: from Lagrangian mechanics to simulation tools for computer graphics, Florence Bertails-Descoubes, Mélina Skouras, Mickaël Ly (Inria Grenoble) — this course takes place on Thursday for the whole day
  • CR13: Approximation Theory and Proof Assistants: Certified Computations, Nicolas Brisebarre and Damien Pous (ENS Lyon)
  • CR14Hardware Compilation and Simulation, Christophe Alias and Mathieu Moy (ENS Lyon)
  • CR15: Concentration of measure in probability and large-scale machine learning, Guillaume Aubrun, Aurélien Garivier and Rémi Gribonval (ENS Lyon) — this course is joint with the Master of Advanced Mathematics
  • CR16: The structure of graphs of high chromatic number, Marthe Bonamy,  Stephan Thomassé (Bordeaux, ENS Lyon)
  • CR17: Logical Foundations of Programming Languages, Olivier Laurent and Colin Riba (ENS Lyon),
  • CR18: Mathematical aspects of automata theory, Denis Kuperberg and Matteo Mio (ENS Lyon)
  • CR19Floating-point arithmetic and beyond, Sylvie Boldo, Claude-Pierre Jeannerod,  Guillaume Melquiond and Jean-Michel Muller  (LRI Orsay, ENS Lyon)

Pre-course Meeting: A pre-course meeting will take place on Monday, September 7, 2020 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 7, at 1:30pm.

Training Period: A mandatory full-time training period takes place from Monday, January 25 up to Friday, June 25. 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. Training periods will be defended on June 28 and 29, 2021.

Schedule: Courses start on September 7 at 1:30pm. Autumn holidays are October 24-November 1. Winter holidays are December 26-January 3. Exams will be held at the end of each wave (for those courses with a final). Again, the detailed weekly schedule will be available on the Inria pad mentioned above. This pad will be 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) and four courses (5 credits each) in the above list of CR1 to CR19. To summarize, there are 50 mandatory credits out of 60 and 10 remaining credits that can be picked elsewhere. While a typical choice by many students is 6 CR courses and the internship, the extra courses for the 10 remaining credits can be chosen in other masters,  e.g.:
– CS courses in the M2 offered by Univ. Lyon 1 https://fst-informatique.univ-lyon1.fr/formation/masters/
– courses from other ENS departments, often Mathematics (http://mathematiques.ens-lyon.fr/master-2-234092.kjsp) or Complex Systems (http://www.ixxi.fr/enseignement/master_systemes_complexes)

The 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.

Course validation: At the end of each course, there is an evaluation based upon a research presentation, or a written exam, or both. Many professors also give exercises during the span of the course. The research presentation consists of reviewing and synthesizing a research paper, and usually involves writing  a short report in addition to the oral presentation. Research presentations are time-consuming, hence it is expected that students have a balanced set of courses per each wave. Indeed, the main motivation for the waves is to help students organize their schedules and avoid having 6 research presentations to defend on the same week; instead, having 3 presentations in the first wave and 3 in the second wave is much more likely to succeed!

Please refer to the rules of the Master here and to the grading algorithm for each course here.

Contact: Zoe Michal-Sihalath (admin) or Yves Robert (head of M2)

(English) Binômes Projet 2 L3IF 2019

Débutants

AL-ASMAR Alice / CONOT Tristan
BAUER Esaie / MEKKI Anes
SIDI ALI CHERIF Mohamed / VARIN Zoe
GENEAU DE LAMARLIERE Paul

Intermédiaires

BAUMERT Sébastien
BERTHE Gaetan / DESRENTES Oregane
CHADDA Amel / PETIT-JEAN Coline
HERVOUIN Mathieu / DUBOIS Loic
MARCILLE Pierre-Marie / MICHEL Mathias
MARETTE Thibault / BERTRAND Jules
MARTIN Firmin / ROCTON Mathis
SORCI Emile / VESSERON Nina

Avancés

ROUSSEAU Guillaume / ALLORANT Baptiste
SAUVAGE Justine / MARTHE Alexandre
CORRADI Quentin / LO IACONO Marine
BATHIE Gabriel / BOILLOT Jerome
ROGET Mathieu / PASQUALE Valentin
GAZULL Yann-Situ / TRON Eliot

Projet L3IF — spécification de fouine

fouine — Syntaxe du langage

Cœur du langage fouine.
• expressions arithmétiques : constantes entières (y compris négatives), somme, soustraction, multiplication ;

• parenthèses ouvrantes et fermantes, construction begin.. end. Les sauts à la ligne sont possibles.

• construction let .. in
Deux exemples : let a = 3 in 2*a + a*a   et     let f x = x*x in f (f 3).

• identificateurs de variables : ils commencent par une lettre minuscule ; après, n’importe quoi en termes de chiffres et de lettres (majuscules ou minuscules) ; let oO0Oo = 0 marche, par exemple ;

• fonctions : on peut déclarer une fonction avec let f x z = .. ou avec let f = fun x -> fun z -> .. (ou un mélange des deux approches) ; on autorisera aussi fun a b c -> ...
On peut appliquer les fonctions comme dans f s t.
On peut utiliser une fonction directement sans la nommer (« fonctions anonymes ») let x = (fun x -> x) a in ...

la fonction fonction prInt. On ajoute une construction spéciale au langage, pour pouvoir faire de l’affichage et ainsi voir ce que font les programmes. Cette construction s’appelle prInt, c’est une fonction qui affiche son argument entier, va à la ligne, et renvoie pour valeur ce même argument.
Voici un petit exemple :

# 2 + prInt (1+2);;
3
- : int = 5

En Caml (mais pas en fouine), on peut définir prInt comme suit :

# let prInt x = print_int x;print_newline(); x;;
val prInt : int -> int =

On se restreindra à des usages simples de prInt ; en particulier, on ne passera pas la fonction prInt à une fonction.

NB : fouine n’est pas IMP, le petit langage vu en théorie de la programmation (pour ceux qui ont suivi ce cours) : il ne fait pas sens de séparer les expressions arithmétiques et les commandes, car « tout est expression » en fouine.

Analyse syntaxique, priorités etc. Le comportement de Caml sert de référence. La principale difficulté est le traitement des applications lorsqu’une fonction est appliquée successivement à plusieurs arguments.

Vous n’avez en particulier pas le droit d’imposer à l’utilisateur d’ajouter davantage de parenthèses que ce qui est demandé en Caml.

Voici quelques exemples illustratifs :

# let add x y = x+y;;
val add : int -> int -> int =
# 3 + add 2 3;;
- : int = 8
# let k = 3 + (fun x -> x + 1) 5;;
val k : int = 9
# let k = 3 + fun x -> x + 1 5;;
Characters 12-28:
let k = 3 + fun x -> x + 1 5;;
^^^^^^^^^^^^^^^^
Error: This expression should not be a function, the expected type is int

Syntaxe, au-delà du cœur.

if then else, uniquement avec des tests entre entiers ;
opérateurs à prendre en compte : > >= < <= = <> pour comparer des entiers,  not && || entre booléens
NB2 : en fouine, tout est expression, et 27 est une expression au même titre que (fun x -> 1+2*x) 9.
NB3 : if then else, mais pas de if then tout court.

• La construction let.. in : formes dérivées

–  ne pas nommer : vous devez autoriser l’utilisation du caractère « souligné » tout seul, dans des expressions de la forme let _ = ... in

Cette utilisation sert à ne pas nommer une expression que l’on évalue (on l’utilise généralement lorsqu’on fait des effets de bord — affichage à l’écran, écriture dans un fichier, mise à jour de référence ..).

NB : dans le type des expressions de votre interprète, il faut avoir une seule construction pour let.. in.

  – let.. in « en surface » : un programme est de la forme let x1 = e1 in let x2 = e2 in … let xn = en in e. Les déclarations des xi sont dites « en surface ». Un let.. in qui se trouve dans l’un des ei n’est pas en surface.

L’écriture ci-dessus suppose que e n’est pas à son tour un let.. in (sinon on aurait pu « développer » davantage). Dans ce cas, tout let.. in que contient e n’est pas non plus en surface.

On a droit à une écriture alternative pour les let.. in en surface, définie ainsi : si l’utilisateur saisit une expression de la forme
let x = e1 in e2
il a le droit de l’écrire
let x = e1;;
e2
et **dans ce cas**, le remplacement peut également être fait, récursivement, dans e2.

• construction let rec (en deux mots), pour définir des fonctions récursives (pas de message d’erreur si la fonction n’est pas récursive). On ne s’intéressera qu’à des définitions récursives de fonctions. Les diverses écritures pour les fonctions seront acceptées (let rec f = fun x ->, et aussi let rec f x y z = .., ou encore let rec f = fun x y z -> ..)

Aspects impératifs.

Création de références (ref), affectation (:=), lecture (!), séquence (;), unit ( () ).

Interdit d’implémenter une référence à l’aide d’une référence de Caml.

Exceptions.

Il y a une seule exception, qui est notée E, et prend un entier en argument (c’est “acquis”, au sens où les programmes fouine ne contiendront pas de déclaration exception E of int).
Constructions raise et  try .. with.
Exemples :
if t >= 12 then raise (E 17) else [5;3]
let n = try f z with E x -> x+1

On autorisera aussi l’écriture with | E x ->   (avec le « | » facultatif).
Les exceptions ne seront pas traitées comme des valeurs (pas de fonction renvoyant une exception, par exemple).

Interdit d’implémenter les exceptions à l’aide des exceptions de Caml.

 

Exécution des programmes fouine.

• Dans la version « de base », un programme fouine peut renvoyer un entier, une fonction ou un booléen.

En l’absence d’utilisation de prInt, un programme ne fait rien de visible (tout comme en Caml, à partir du moment où l’on n’utilise pas l’interprète mais le compilateur).

• Plutôt que de décrire formellement la sémantique opérationnelle de fouine, on adopte l’approche “lancez le programme avec Caml, cela vous donnera le comportement attendu”. Vous pouvez interagir avec les encadrants si vous avez des doutes sur un point précis.

Pour lancer le programme avec Caml, vous devrez insérer la définition let prInt x = print_int x; print_newline(); x au début.

Typiquement, de petits programmes comme let a = prInt 5 in a + prInt 7 ou let f x y = x*y in f (prInt 3) (2+prInt 2) vous permettront de vérifier que vous implémentez les choses comme il faut.

Affichage d’un programme fouine

Vous devez programmer une fonction qui affiche un programme fouine. Afficher le programme saisi en entrée ne donne pas nécessairement le même programme, car il se peut que des transformations élémentaires soient appliquées au passage (par exemple, let f x =.. remplacé par let f = fun x -> ..). Il faudra toutefois que le programme affiché soit accepté par Caml, en supposant que l’on ait défini la fonction prInt comme ci-dessus.

Les erreurs que ne connaı̂t pas Caml.
En Caml, un programme est typé, ce qui permet d’éviter d’exécuter des programmes absurdes comme 3 + (fun x -> x+1). Pas de typage en fouine, par conséquent certains programmes exploseront lors de l’exécution.

Réfléchissez à la gestion de ces erreurs (appelées dynamiques), et proposez une solution satisfaisante. Cela peut aller de messages d’erreur un peu explicatifs dans certains cas (quand une addition fait intervenir une fonction, par exemple) à des choses plus sophistiquées, où l’on indique d’où vient l’erreur
dans le code source.

Projet L3IF — débutants Linux

Dans un terminal

  • la touche « tab » permet de compléter la commande courante, les flèches haut et bas se promènent dans l’historique des commandes qui ont été saisies
  • tapez make pour compiler; pour « éteindre et rallumer », tapez make clean puis make
  • apprenez à vous promener dans vos répertoires à coups de cd (cd .. vous fait remonter d’un cran)
  • une fois que vos fichiers Caml sont dans un endroit déterminé, et que vous avez mis en place git pour les modifier, vous pouvez les éditer avec ce que vous voulez : vim, emacs, un environnement de développement sophistiqué, ..

Compiler et exécuter du code Caml.

  • on compile en tapant make. Il se débrouille pour comprendre quels fichiers il doit recompiler, et dans quel ordre. Il se sert d’ailleurs d’un sous-répertoire appelé _build, que vous n’avez pas à aller regarder, a priori.
  • quand on tape ./main.native < tests/t1.txt,on appelle le programme main.native, qui est dans le répertoire courant (c’est le « ./ »), en lui faisant manger le contenu du fichier t1.txt qui est dans le sous-répertoire tests
  • On ne « voit » ce que fait un programme Caml qu’à partir du moment où celui-ci interagit avec le monde extérieur. Typiquement, ce sont les fonctions d’affichage qui déclenchent quelque chose de visible. On trouve volontiers quelque chose comme
    let _ = f x y,
    invocation qui signifie « on lance le calcul de f avec x et y, et on ne donne pas de nom au résultat (le « _ », c’est « pas de nom »). L’idée ici c’est que le calcul de f aura des effets sur l’univers (modification de certaines références, affichage, ..).
  • Pour faire des open dans l’interprête Caml, il faut les précéder de la commande #load.
    • On lance Caml avec une option pour lui dire de regarder dans le répertoire _buildocaml -I _build (il y a un « _ » avant le build !)
    • On fait les incantations#load "cell.cmo";;

      open Cell;;

      et il connaît alors ce qui est défini dans le fichier cell.ml (à condition que vous ayez compilé cell auparavant).

  • Deux mots sur la question 3 du niveau Débutants du rendu 1.Pour récupérer dans un fichier les instructions du petit langage qui sert à modifier les cases du tableur, et les traduire en des valeurs Caml, on s’appuie sur ce que contiennent les fichiers lexer.mll et parser.mly.

    Il y a trois entités : la chaîne de caractères qui correspond au mot que l’on veut reconnaître (p.ex., « MULT », avec les guillemets, car c’est une chaîne de caractères) ; le mot du langage (on dit lexème, ou token) (p.ex., MULT sans guillements) ; et la valeur Caml à laquelle on aboutit (p.ex., M, qui est un constructeur du type oper, défini dans le fichier cell.ml).

    Dans lexer.mll, on associe le lexème MULT à la chaîne de caractères « MULT ». Puis, dans parser.mly, on dit que le mot MULT est associé à M, ligne 47, après avoir déclaré vers le début du fichier que MULT est un lexème. On notera en passant que parser.mly contient des règles de grammaire, dans l’esprit de ce que vous avez vu en FDI.

Consulter la réservation des salles

Voici un petit tutoriel sur la réservation des salles à l’ENS de Lyon.

Allez sur http://planningsalles.ens-lyon.fr/

Vous devrez peut-être vous identifier, puis vous verrez quelque chose comme ceci :

Tapez ensuite le nom des salles dont vous voulez faire apparaître la réservation (par exemple, « Salle B1 », « Amphi B » — cf. plus bas), vous verrez quelque chose comme ceci :

Quelques commentaires :

  • Les salles « par défaut » en informatique sont l’amphi B et les salles (de TD) B1 et B2.
  • Les salles E001, 125 et 171 contiennent des ordinateurs sous Linux (pour les TPs).
  • Le planning des salles de maths (amphi A, salles A1 et A2) et des amphis du Département des Sciences de la Matière (amphis C à H) sont consultables également via l’interface décrite ci-dessus.
  • Un point important : lorsqu’on change la liste des salles dont on affiche le planning (soit en ajoutant une salle, soit en en supprimant une), le système nous ramène par défaut à la semaine en cours (tel est le comportement en octobre 2017, tout du moins). Cela est volontiers source de confusion, si vous êtes en train de regarder le planning pour un mois plus tard ; essayez de garder la chose à l’esprit !

Analyse de programmes et vérification de systèmes

Programme de l’UE :

  1. Structures ordonnées
    Ordres et topologies. Points fixes. Approximations et correspondances de Galois. Domaines de Scott
  2. Sémantiques dénotationnelles
    Domaines d’interprétation. Sémantique directe et par continuations.

    Correction et complétude de la Sémantique Axiomatique.
  3. Analyse de programmes
    3.1. Analyses dynamique et statique. Systèmes de types.

    3.2. Interprétation abstraite : principes, élargissement/rétrécissement,
    analyses avant et arrière, analyse polyédrale.
  4. Vérification
    4.1. Logiques modales. Structures de Kripke. Model checking.

    4.2. Systèmes réactifs. Logiques temporelles LTL et CTL.

Intervenants

CB-03 : Arithmétique des ordinateurs

Programme de l’UE

L’arithmétique des ordinateurs s’intéresse à la fois à la conception d’opérateurs arithmétiques, et à leur utilisation fine pour réaliser des fonctions plus complexes.

Ce cours présente un panorama des représentations utilisées en machine pour manipuler les nombres entiers, les réels et les polynômes, ainsi que l’algorithmique associée à chaque représentation pour réaliser les opérations de base (addition, multiplication, division, racine carrée… ) et calculer des fonctions « élémentaires » (logarithme, exponentielle, fonctions trigonométriques, etc.).

On s’intéressera d’abord à la manipulation de nombres en « précision fixée » (entiers, virgule flottante, norme IEEE 754) ainsi qu’à diverses techniques permettant d’augmenter ou de garantir la précision des calculs: on montrera ainsi qu’une arithmétique « approchée » comme la virgule flottante permet de faire des calculs exacts.

On étudiera ensuite la complexité et l’algorithmique des opérations de base sur les polynômes (multiplication, division, évaluation, interpolation), en arithmétique exacte.

Enfin, nous aborderons la question du calcul sur les polynômes en arithmétique approchée. Cela permettra d’une part de présenter les notions fondamentales de conditionnement d’un problème et de stabilité d’un algorithme et, d’autre part, de comprendre pourquoi l’évaluation polynomiale est de plus en plus souvent au coeur des implantations (logicielles ou matérielles) d’opérateurs arithmétiques de base comme la division ou la racine carrée.

Intervenants

  • Jean Michel Muller, DR CNRS (http://perso.ens-lyon.fr/jean-michel.muller/)
  • Claude Pierre Jeannerod, CR INRIA (http://perso.ens-lyon.fr/claude-pierre.jeannerod/)

Quelques ouvrages de référence

  • Ercegovac et Lang, Digital Arithmetic, The Morgan Kaufmann Series in Computer Architecture and Design, 2004
  • D.E. Knuth, The Art of Computer Programming, Volume 2, Addison Wesley 1997
  • Muller, Arithmétique des Ordinateurs, Masson, 1989 (texte intégral accessible à http://prunel.ccsd.cnrs.fr/ensl-00086707)
  • J. von zur Gathen et J. Gerhard, Modern Computer Algebra, Cambridge 2003.
  • Muller, Elementary functions, algorithms and implementation, 2ème édition, Birkhauser, 2006
  • P. Burgisser, M. Clausen, et M.A. Shokrollahi, Algebraic Complexity Theory, Springer 1997.
  • Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Seconde édition, Août 2002
  • Muller, Brisebarre, de Dinechin, Jeannerod, Lefèvre, Melquiond, Revol, Stehlé et Torrès, Handbook of Floating-Point Arithmetic, Birkhauser, 2010

Réseaux

Programme de l’UE :

Le but de ce cours est de présenter certains fondements des réseaux, dans son fonctionnement mais aussi des points de vues algorithmique et
d’évaluation de performances. Le module s’articule autour d’une présentation de l’architecture de l’Internet et des protocoles réseaux,
et des outils/méthodologie d’évaluation de performances. Les notions abordées lors de ce cours sont les suivantes :

  • Notions, principes et les architectures réseaux.
  • Algorithmes d’accès à un médium de communication
  • Méthode statistique pour l’évaluation des performances
  • Evaluation des performances des réseaux sans fil
  • Principe de l’IP et de l’Internet
  • Notions avancés de routage
  • Algorithmes des protocoles de transport (TCP, partage, performance)

Modalité d’évaluation

  • Examen écrit
  • TP ou Mini-projet

Fiche d’évaluation

Intervenants