(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

P2 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 ; sauts à la ligne autorisés ;

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

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

• 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 -> ..)

if then else, uniquement avec des tests entre entiers ;
opérateurs à prendre en compte : > >= < <= = <> (vous pouvez ajouter not && ||, mais ça n’est pas imposé).
NB : il n’y a pas vraiment de type bool en fouine, au sens où un calcul renvoie soit un entier, soit une fonction, et les booléens n’apparaissent que dans la construction if then else.
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.

• Qu’est-ce qu’un programme ?

Un programme est une expression. Cette expression peut contenir des let .. in. Par conséquent, un programme est de la forme let .. = ... in ... ... let .. = ... in BLA.

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

Il vous est en outre demandé d’autoriser les quatre facilités de saisie suivantes, pour les let.. in qui sont « en surface » (i.e., pas à l’intérieur d’un autre let.. in) :

-1- un ;; peut être utilisé à la place d’un « in » pour une construction let.. in ;
-2- au sein d’un enchaînement de let.. in se terminant par un ;;, il faut omettre le in (pour les let.. in qui sont « en surface ») ;

Ainsi, on peut écrire (et c’est « l’écriture canonique ») :

let a = 3 in
let b = 5 in
let c = 7 in
a*b*c

et, de manière équivalente

let a = 3
let b = 5
let c = 7;;
a*b*c

ou aussi

let a = 3;;
let b = 5
let c =7;;
a*b*c

Mais pas

let a = 3
let b = 5
let c = 7
a*b*c

ni des choses comme

let a = 3
let f x =
   let y = x*x
   let z = x*x*x in
y*y*z

(en effet, ci-dessus, « let y = ..  » et « let z = .. » ne sont pas en surface).

-3- vous devez aussi autoriser une séquence de let.. in sans le BLA final. Une telle entrée sera traduite en la même séquence de let.. in, suivie par « in 0 » ;
-4- vous devez autoriser l’utilisation du caractère « souligné » tout seul, dans des expressions de la forme let _ = ... in (et cela n’est pas réservé aux let.. in de surface). 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 : Il serait très maladroit d’avoir plusieurs constructions dans votre interprète pour les diverses écritures possibles d’un let.. in.

• Un programme peut renvoyer un entier, ou une fonction (les conditions booléennes ne peuvent exister que dans les if then else).

Priorités etc. Là aussi, 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

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

Affichage.

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.

Exécution des programmes.

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.

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.
À noter qu’un calcul ne renvoie pas un booléen (tout du moins dans la version « de base » de fouine) : on ne manipule des booléens qu’au sein des tests dans des if then else.
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.

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, du coup certainsprogrammes exploseront lors de l’exécution.

Réfléchissez à la gestion de ces erreurs (appelées dynamiques), et proposez une solution plus ou moins 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.

P2 L3IF — débutants Linux

Dans un terminal

  • la touche « tab » permettent 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 _build

      ocaml -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 !

OLD – M1, convention de stage

Voici enfin les documents attendus pour préparer votre convention de stage! Lisez attentivement les informations qui suivent, on rajoute quelques points de suivi pour éviter les problèmes qui sont assez courants…

La procédure générale à suivre: Procédure.

Attention: avant de rentrer votre demande de convention sous Elipse, on vous demande de remplir le formulaire ci-joint, qui reprend les informations demandées dans Elipse: FormulaireConventionUCBL. Ce formulaire devra être retourné au responsable des stages et au secrétariat de département pour vérification avant de commencer toute saisie sous Elipse (étape 1.4)

  • Pour un stage en France, ce document devra être daté, signé et cacheté par l’organisme d’accueil (OA). Il est en effet nécessaire que le secrétariat de l’OA valide les informations: s’il y a une erreur sur l’adresse de l’OA, la convention ne sera pas signée par l’UCBL en bout de chaîne et tout sera à recommencer. Assurez-vous d’avoir les bonnes informations, que votre encadrant de stage n’a pas forcément: il faut que votre encadrant de stage s’en assure auprès de son secrétariat.
  • Pour un stage à l’étranger, envoyez (sauf cas particulier/avis contraire du responsable des stages de M1) un exemplaire de convention vierge à l’organisme d’accueil (2015-CONVENTION_STAGE_FR_EN-v1.2 et la notice explicative 2015-Notice_Convention_Stage_FR_EN-v1.1), afin de vous assurer qu’ils acceptent ce modèle. Il y a souvent des refus de signature pour raisons juridiques. Si problème, alerter immédiatement le responsable des stages, en donnant les raisons précises du refus de la convention.Dans le cas contraire, faites suivre un mail de l’encadrant (ou de quelqu’un de l’administration à l’organisme d’accueil) au secrétariat du DI et au responsable des stages indiquant explicitement l’accord pour signer la convention de stage Elipse, et précisant les coordonnées à mentionner pour l’organisme d’accueil.
    Lorsque des modifications sont demandées sur le modèle de convention, il faut d’abord les faire valider via le responsable des stages et le responsable d’année. Si tel est le cas, un avenant à la convention sera préparé, tenant compte des modifications demandées. Il faut alors saisir le stage sous Elipse, afin d’avoir les données du stage dans le système d’information (le circuit de validation reste le même sous Elipse).

Voici en complément la copie d’écran pour l’étape « Sésame »: Sesame Lyon 1, et le guide Elipse: Guide Lyon 1.

Une précision : le module à sélectionner sous Elipse est « ENS – Stage de recherche de 12 semaines » (même si le stage peut faire 11 semaines).

Une fois la demande approuvée, fin du premier acte.

Deuxième acte : signatures de la convention. Le circuit est le suivant  (vous devez vous charger de la première étape; on décrit les étapes suivantes pour que vous puissiez expliquer si nécessaire) :

  • il faut apporter un timbre au secrétariat du DI pour un courrier, entre 50 et 100 grammes, pour le pays concerné, pour ce que l’on appelle ci-dessous l’enveloppe magique;
  • le secrétariat du DI édite 4 exemplaires de la convention, et se charge de récupérer deux signatures : la vôtre et celle de votre tuteur pédagogique à l’ENS Lyon;
  • le secrétariat du DI envoie les 4 exemplaires à l’organisme d’accueil, ainsi que l’enveloppe magique, qui est affranchie avec le timbre susmentionné;
  • sur place (à l’organisme d’accueil), les 4 exemplaires sont signés par le tuteur du stage et par la personne qui représente l’organisme d’accueil, et les 4 exemplaires, ainsi que l’enveloppe magique, sont envoyés à l’UCBL.
  • La dernière signature est enfin ajoutée côté UCBL. 2 exemplaires sont ensuite envoyés à l’organisme d’accueil dans l’enveloppe magique (l’un d’entre eux est pour vous; c’est le troisième voyage de l’enveloppe magique, et cette fois c’est elle le medium — elle est décidément vraiment magique, cette enveloppe), 1 autre est envoyé au secrétariat du DI.

Tous les mails doivent être adressés au responsable des stages (Frédéric Vivien pour le M1) et au secrétariat (Amel Zagrarni) avec comme objet: « [StageM1] vos NOM et Prénom ». N’hésitez pas à discuter avec votre tuteur pédagogique si vous avez besoin d’aide, ou à contacter le responsable des stages.

N’attendez pas pour lancer la procédure, ça peut être long! Dès que le responsable des stages a validé votre stage, envoyez le formulaire à votre organisme d’accueil pour récupérer toutes les informations. Bon courage!

Gestion et Fouille de Données

Gestion et Fouille de Données

Ce cours est offert au second semestre du M1.

Descriptif du cours :

  • Bases de données
    – Modèle relationnel, calcul relationnel, SQL
    – Algèbre, équivalence algèbre/calcul, indexation et optimisation
    – Dépendances fonctionnelles, axiomatisation, relations d’Armstrong
    – Dépendances d’inclusion, data exchange, chase, réécriture de requête
  • Fouille de données
    – Introduction à la fouille de données (motifs ensemblistes et algorithmes/explorations classiques)
    – Fouille de motifs sous-contraintes:  étude et exploitation des   propriétés des contraintes
    – Langage de motifs plus sophistiqués (concepts formels, séquences, graphes, graphes dynamiques, …)
    – (Bi-|Co-)Clustering
    – Ouverture vers les problématiques actuelles.

Preuves et programmes

Preuves et programmes

Ce cours est offert au second semestre du M1.

Contenu du cours :

Raisonner et programmer sont les deux côtés d’une même pièce.

L’épine dorsale de cette relation est la découverte d’une correspondance très forte entre des énoncés simples (calcul propositionnel) et des termes d’un modèle de calcul (λ-calcul). C’est la correspondance de Curry-Howard (1980).

En 2006, suite aux travaux de Voevodsky sur l’univalence (basée sur la théorie de l’homotopie), une nouvelle révolution est en marche. qui permet désormais de *faire des mathématiques en programmant*.

C’est un sujet qu’aucun format de cours ne saurait prétendre couvrir sur un seul semestre. Mais tous les chemins commencent par un premier pas, et nous nous assurerons de maîtriser d’abord les notions les plus fondamentales. Le programme envisagé est le suivant :

  • La correspondance de Curry-Howard, cuite dans son jus.
  • Théories de types et avènement des assistants à la preuve.
  • Les éléments d’une refondation des mathématiques : état de l’Art.

Références bibliographiques :

Outre la page de WikiPedia pour les impatients (https://fr.wikipedia.org/wiki/Correspondance_de_Curry-Howard) :

  • Intuitionistic Type Theory. P. Martin-Löf. 1980.
  • Proofs and Types. J.-Y. Girard, Y. Lafont, P. Taylor. 1987.
  • Lambda-calcul : types and modèles. J.-L. Krivine. 1990.
  • Homotopy Type Theory. Collectif. http://homotopytypetheory.org/book/.

Plus en suivant ce lien : https://perso.ens-lyon.fr/philippe.audebaud/PnP/

Géométrie computationnelle et images digitales

Image processing, digital and computational geometry

Course offered in the second semester of M1.

Objectives of the course:

The objective of this course is to introduce fundamental notions of image processing, digital geometry and computational geometry.  The first lectures will be dedicated to image processing (filtering, smoothing, morphological mathematics, ..) and shape representation. Then, we will focus on theoretical and algorithmic issues involved in the analysis of digital shapes. During this analysis of  digital geometry processing tools, we will have to present and integrate some tools from various fields: discrete mathematics, combinatorics, arithmetics, computational geometry, ..

Course contents:

  • Image/Shape representation
  • Image processing (filtering, segmentation)
  • Digital Geometry for shape analysis
  • Computational geometry and data structures
  • Requirements: basic notions of algorithmics

References:

  • Géométrie discrète et images numériques, D. Coeurjolly, A. Montanvert and J.-M. Chassery, Ouvrage collectif, Traité IC2, Hermès, 416 pages, 2007
  • Digital Geometry: Geometric Methods for Digital Picture Analysis, Reihnard Klette, Azriel Rosenfeld, Morgan Kaufmann, 2004
  • Computational Geometry: Algorithms and Applications, Mark de Berg, TU Eindhoven (the Netherlands) Otfried Cheong, KAIST (Korea),Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands), Springer-Verlag

Complexité algorithmique

Computational Complexity

Course offered in the second semester of M1.

Overview of the course:

Computational complexity aims to classify computational problems depending on the resources they need. One
studies various modes of computation such as deterministic, randomized, nondeterministic or quantum and compares
resources such as time or space needed to solve algorithmic problems. The objective of this course is to give a
broad understanding of the notions used to classify computational problems. About half of the course is dedicated
to studying basic complexity classes defined using Turing machines. We introduce (or study deeper) notions that are
central in complexity theory: nondeterministic computation (e.g., the class NP), reductions between computational
problems (e.g., NP-completeness) and the technique of diagonalization (e.g., hierarchy theorems). We also study
randomized computation and computation using boolean circuits as well as their relation to basic complexity classes.
We conclude the course by studying the complexity of communication, i.e., trying to evaluate communication
bottlenecks to perform a given computational task between different parties.
Teaching in 2014: Omar Fawzi (lectures) and S ́ebastien Maulat (exercise classes)

Course objectives:

One can summarize the most important objectives of the course as follows.

  1. Understand the formal definitions for the basic complexity classes like L, NL, P, NP, coNP, PSPACE.
    Be familiar with nondeterministic computation and the polynomial hierarchy. Know about the inclusions and separations between these classes.
  2. Understand the notion of reduction between computational problems, and the notion of complete problem, e.g., SAT is NP-complete, PATH is NL-complete, TQBF is PSPACE-complete.
  3. Understand complexity classes defined using boolean circuits, and the notion of uniformity in computation. Know the relation to basic complexity classes.
  4. Understand complexity classes using randomized computations. Know the relation to basic complexity classes.
  5. Get a flavour for the power of interactive proofs.
  6. Be familiar with an important tool in theoretical computer science: communication complexity. Be able to reduce various problems to a communication complexity problem.

Cryptographie et sécurité

Cryptography and Security

Course offered in the second semester of M1.

Course contents:

This course is an introduction to the different facets of modern cryptography.

The following topics will be addressed:

  • Symmetric cryptography
    Pseudo-random number generators
    Pseudo-random functions
    Message Authentication Codes
    Stream ciphers and block ciphers
    Security against chosen plaintext/ciphertext attacks
    Hash functions
  • Asymmetric cryptography
    Discrete logarithm, decision Diffie-Hellman
    Factoring, RSA problem
    Key exchange
    Digital signatures
    Public-key encryption
    The random oracle methodology
  • Other topics possibly covered:
    Zero-knowledge proofs
    Secret sharing
    Yao’s garbling circuits

Calcul formel

Computer Algebra

Course offered in the second semester of M1.

contents:

This class shall survey some of the central topics of computer algebra: arithmetics, effective linear algebra, polynomial system solving.

The following topics will be studied:

  1. Arithmetic(s) — mostly polynomial.
    – Representation of polynomials, linear operations (addition, evaluation).
    – Multiplication : schoolbook method, Karatsuba method, Toom-Cook method Fast Fourier Transform.
    – Division : schoolbook method, Newton method, recursive division
    – GCD : Euclidean algorithm, extended GCD, application to CRT; introduction to fast GCD.
    – Fast multiple point evaluation, fast interpolation, fast CRT.
    – Introduction to multiple precision integer arithmetic, floating-point arithmetic, finite fields arithmetic.
  2. Linear algebra over a field
    – Matrix/vector product, naive matrix/matrix product
    – Row echelon form & applications : kernel, image, rank, determinant, linear system solving, etc.
    – Fast matrix/matrix product : Strassen ; fast inversion/determinant.
    – Structured matrices: circulant, Hankel, Toeplitz, Cauchy, and related algorithms.

Algorithmique et Programmation Parallèles et Distribuées

Algorithmique et Programmation Parallèle et Distribuée

Cours du M1 2015-2016, premier semestre.

Programme de l’UE :

Le parallélisme est devenu incontournable en informatique, le moindre
processeur étant multi-cœurs. Cette UE a pour objet la conception
d’algorithmes parallèles et distribués efficaces, et aborde leur mise
en œuvre pratique sous forme de TPs.
Les séances de cours auront pour objet les modèles théoriques utilisés
pour la conception et l’analyse des algorithmes et l’étude de
problèmes algorithmiques particuliers (complexité, définition et
analyse d’algorithmes, algorithmes d’approximations, etc.).
Les quatorze séances de cours seront accompagnées de sept séances de
TDs et de sept séances de TPs. Les TPs auront pour but l’initiation
la programmation parallèle et distribuée par passage de messages
(MPI). Un petit projet de programmation est organisé sous forme de
devoir à la maison.

Plan indicatif des cours :

  • Modèle théorique des réseaux de tri
  • Modèle théorique des PRAMs
  • Algorithmique sur anneau et grille de processeurs: produit matrice-vecteur,
    produit matrice-matrice, stencil 2D, etc.
  • Algorithmique distribuée: modèles, élection, consensus, détection de
    terminaison
  • Ordonnancement de graphes de tâches avec et sans communications,
    avec ou sans contraintes de ressources: complexité, algorithmes
    d’approximations et heuristiques
  • Analyse de dépendance et parallélisation automatique
  • Exemple d’algorithme pour GPU

La note de contrôle continu est établie à partir d’un partiel organisé
en milieu de semestre, du devoir à la maison de programmation, et d’un
examen final.

OLD – Stage de recherche M1, évaluation

Préambule: contactez D. Hirschkoff (ou votre tuteur) si vous avez des problèmes durant le stage, ou pour toute question.

Re-préambule : vous ne pouvez pas supposer qu’un(e) spécialiste du domaine où vous avez travaillé en stage relira votre rapport ou assistera à votre soutenance. Il faut donc que vous adaptiez votre rendu en conséquence. Cela ne signifie pas jeter toute la technique à la poubelle, mais il faut être capable de choisir les points techniques que vous souhaitez traiter, et de les amener. En règle générale, les étudiants de M1 ont plutôt tendance à vouloir mettre trop de technique, comme s’ils s’adressaient à leur encadrant de stage.

Rapport

Vous devez envoyer votre rapport à Daniel Hirschkoff au plus tard le 28 août 2018 à midi (heure de Lyon), par mail. 20 pages maximum, vous pouvez au besoin pointer vers une « annexe » en ligne (l’annexe peut être un fichier contenant des preuves, un fichier contenant tous vos résultats numériques, un article écrit avec vos encadrants, du code que vous avez produit..). Vous pouvez écrire en anglais, mais ne le faites que si votre niveau d’anglais rend cela possible. Il est souhaitable que votre encadrant valide votre rapport en le relisant (ce qui signifie l’écrire suffisamment en avance pour qu’il y ait le temps d’une relecture et de corrections).

Au sujet du contenu:

  • décanter / situer

sachez expliquer et motiver la question que vous avez étudiée: d’où vient-elle, pourquoi on se pose cette question, quel était l’état de la science au début de votre stage, quels sont les travaux existants pertinents.

  • présenter

si vous avez 10 résultats, ne les présentez pas tous de façon détaillée, faites un « travail éditorial » de sélection; si vous en n’avez aucun, racontez ce qui aurait pu marcher, quelles pistes ont été tentées.

  • commenter la démarche

vous êtes encouragés à raconter dans votre rapport comment se sont passées les choses: les pistes qui n’ont pas marché, des interactions/collaborations avec votre encadrant et d’autres chercheurs dans le cadre du stage, des initiatives que vous avez prises.

  • ne mettez pas les aspects expérimentaux sous le tapis: si vous avez codé quelque chose de non ridicule, ou utilisé des outils, parlez-en (taille du  code, outils/langages utilisés, utilisations futures escomptées, choix d’implémentation, etc.).

Présentation

Informations préliminaires: les soutenances auront lieu les 5 et 6 septembre 2018, à l’ENS Lyon, dans les salles B1 et B2. 20 minutes de soutenance, suivies de 5 minutes de questions. Le planning est disponible ici.

Faites au moins deux répétitions! On vous coupera la parole brutalement au bout du temps imparti, et c’est une catastrophe si à ce moment-là vous n’avez pas encore abordé la partie 3 de votre expose qui en comporte 5. C’est aussi catastrophique si vous terminez au bout de 8 minutes. Mettez-vous la pression, faire une présentation propre/claire n’est pas un exercice qui s’improvise, et c’est très différent d’une discussion scientifique à bâtons rompus. Pour ce qui est du contenu de la présentation, mêmes remarques que pour le rapport. Cela ne sert a rien de noyer l’auditoire sous des tonnes de détails techniques. Tâchez de faire comprendre la question que vous avez traitée, et votre contribution, de façon compréhensible pour un auditoire non spécialiste, tout en évitant de trop glisser sous le tapis les choses plus techniques.

Points organisationnels : ayez vos transparents au format pdf sur une clef usb, pour le cas où il y aurait les sempiternels problèmes techniques pour la projection.  Ayez de quoi projeter vos transparents (nous fournissons le vidéoprojecteur, pas la machine). Une bonne solution consiste à vous mettre d’accord entre étudiants qui présentent à la même session, afin de partager un ordinateur, que l’on connecte pendant la pause qui précède la session).

Vous pouvez sauf cas particulier assister à la présentation de vos camarades, à partir du moment où ceux-ci sont d’accord.

Vous pouvez présenter en français ou en anglais, mais ne soyez pas prétentieux, n’optez pour l’anglais que si votre niveau le permet.

PROG – Théorie de la Programmation (1er semestre, 6 ECTS)

Cours : Daniel Hirschkoff

TD : Adrien Durier & Alexis Ghyselen & Julien Braine

Il existe de nombreux langages de programmation, et ce foisonnement est sans cesse alimenté par l’apparition de nouveaux langages. Ce cours propose une introduction à un certain nombre de méthodes ouvrant la voie à l’analyse rigoureuse des langages de programmation et des programmes. Ces méthodes fournissent un cadre dans lequel représenter les programmes, et prouver des propriétés sur leur comportement à l’exécution. Ce faisant, il est possible d’analyser des transformations de programmes, d’établir des comparaisons entre langages de programmation, et, plus généralement, de prendre du recul par rapport à la richesse du paysage des langages de programmation.

Les sujets suivants sont traités dans le cours:

  • définitions inductives, sémantique opérationnelle des programmes (pour un mini-langage impératif et un mini-langage fonctionnel)
  • garanties sur l’exécution des programmes: sémantique axiomatique (logique de Floyd-Hoare), typage
  • propriétés abstraites sur l’exécution des programmes, notions de réécriture: terminaison, confluence, unification

Bibliographie

  • G. Winskel, The semantics of programming languages, MIT Press.
  • J. Reynolds, Theories of Programming Languages, CUP.
  • F. Baader et T. Nipkow, Term Rewriting and All That, Cambridge University Press
  • une page web liée au cours sera disponible à partir de la page http://perso.ens-lyon.fr/daniel.hirschkoff

Le cours est organisé selon le schéma hebdomadaire suivant: 2h de cours; 2h de travaux pratiques sur machine ou de travaux dirigés. En travaux pratique, une initiation à l’assistant de preuves Coq sera
proposée.

Prérequis: une expérience de la programmation, quel que soit le langage, est souhaitée.

PROJ2 – Projet Programmation (2ème semestre, 6 ECTS)

Cours : Daniel Hirschkoff

TP : Etienne Moutot & Valentin Lorentz

Prérequis : Connaissances de base en algorithmique, et connaissance (même peu avancée) du langage OCaml, langage qui est imposé pour ce cours.

Objectif

L’objectif de ce module est multiple :

  • apprendre ou consolider des pratiques de programmation ayant trait à la structuration du code et à la modularité ;
  • apprendre des notions en lien avec l’exécution des programmes (interprétation, transformation de programmes) ;
  • mieux comprendre la programmation fonctionnelle en OCaml ;
  • travailler en binôme à un projet logiciel, en organisant le travail sur plusieurs semaines.

Organisation

Le module comprend une série de cours magistraux, accompagnée de séances sur machine. Les étudiants sont répartis en binômes, suivant leur expérience de la programmation et leur connaissance de Caml. 3 ou 4 rendus sont proposés au long du semestre, dont la difficulté est adaptée au niveau d’expérience du binôme. L’évaluation se fait à la fois sur la qualité du logiciel obtenu, et sur l’organisation du travail au long du semestre.

Une page www sera mise à disposition afin de rassembler des ressources utiles pour le cours.

Calcul formel

Programme de l’UE :

  • Pgcd et pgcd étendu : algorithmes d’Euclide et d’Euclide étendu (coût algébrique, coût arithmétique, propriétés, …), algorithme quasi-linéaire de Knuth et Schonhage.
  • Algorithmes sur les polynômes : évaluation, interpolation. Arbre des produits. Algorithmes quasi-linéaires pour l’évaluation multi-points et l’interpolation.
  • Algorithmique de l’algèbre lineaire : pivot de Gauss (sur un corps), applications (calcul d’image, de noyau, de déterminant, systèmes linéaires), méthodes multimodulaires et relèvement de Hensel sur Z ou K[X].
  • Résultant, élimination ; application au calcul de l’intersection de deux courbes algébriques planes.
  • Factorisation des polynômes sur Z/pZ : algorithme de Berlekamp, de Cantor-Zassenhaus, relèvement de Hensel d’une factorisation.
  • Application aux codes correcteurs d’erreurs : codes de Reed-Solomon. Algorithmes de décodage, de décodage en liste.

Nota: programme incomplet — à titre d’indication, voici le programme du cours de l’an dernier:

  1. Évaluation en un point : schéma de Horner, interprétation en termes de division euclidienne, optimalité dans le modèle de complexité non scalaire (pgms straight-line).
  2. Multiplication : racines (primitives) n-ièmes, transformée de Fourier discrète (DFT) et sa version rapide (FFT), DFT inverse, multiplication de polynômes par FFT, algorithme de Schonhage et Strassen, fonctionM(n).
  3. Division euclidienne : calcul rapide du reste à partir du quotient, polynômes réciproques, itération de Newton pour l’inversion modulo x^n en O(M(n)), équivalence de complexité entre division et multiplication.
  4. Évaluation multipoint et interpolation : algorithme de Lagrange, algorithme quadratique, arbre des sous-produits et algorithmes quasi-linéaires (somme de fractions, evaluation, interpolation), cas d’une progression géometrique (algorithme de Aho, Steiglitz, Ullman).
  5. Pgcd et pgcd étendu : algorithmes d’Euclide et d’Euclide étendu (analyse de coût, propriétés, …), algorithme quasi-linéaire de Knuth et Schonhage.
  6. Évaluation polynômiale en arithmétique flottante : standard IEEE 754, notations pour l’analyse des erreurs d’arrondi, stabilité (directe, inverse), conditionnement, error-free transforms et algorithmes TwoSum et TwoProd,technique de compensation appliquée au schéma de Horner.
  7. Algorithmique de l’algèbre lineaire : pivot de Gauss (sur un corps, sur Z ou K[X]), applications (calcul d’image, de noyau, de déterminant, systèmes linéaires) méthodes multimodulaires
  8. Résultant, élimination ; application au calcul de l’intersection de deux courbes algébriques planes ; sous-résultants et applications à l’analyse des variantes de l’algorithme d’Euclide étendu sur Z[X]
  9. Rappels sur les corps finis ; factorisation des polynômes sur les corps finis : algorithme de Berlekamp, de Cantor-Zassenhaus
  10. Relèvement de Hensel d’une factorisation ; bornes sur les facteurs d’un polynôme à coefficients entiers. Algorithme de Berlekamp-Zassenhaus pour la factorisation des polynômes à coefficients rationnels.

Intervenants

Cours: Guillaume Hanrot et Jean-Michel Muller

TDs: Silviu Filip

Optimisation et programmation linéaire

Programme de l’UE :

  1. Les bases. Programme linéaire.
    Algorithme du Simplexe. Lemme de Farkas. Dualité. Ecarts complémentaires. Analyse de sensitivité.
  2. Programmation en nombres entiers.
    Polyèdres et Polytopes. Relaxation fractionnaire. Matrices totalement unimodulaires et TDI. Arrondis déterministes et aléatoires. Générations de coupes.
  3. Modélisation et applications classiques.
    Flots et réseaux de transport. Stratégies mixtes (jeux matriciels). Codes correcteurs. Compressed sensing.
  4. Extensions possibles.
    Ellipsoide. Oracles de coupe (Grotschel Lovasz Schrijver). Programmation semi-définie (Capacité Shannon, Fonction Theta, coupe minimum de Goemans et Williamson). Minimisation des fonctions sous-modulaires.

Intervenants

Cours: Stephan Thomassé

TDs: Guillaume Aupy