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 ; à noter que fun a b c -> .. est également possible) .
On peut appliquer les fonctions comme dans f s t.
On peut utiliser une fonction directement sans la nommer (fun x -> x) a.

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

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 : tant qu’on y est, précisons que la grammaire de fouine se démarque de la grammaire du petit langage impératif (Imp) que d’aucuns ont pu voir dans le cours Théorie de la programmation au premier semestre. Il n’y a pas une grammaire pour les expressions arithmétiques d’un côté, et une grammaire pour les « commandes » de l’autre, tout simplement parce qu’il n’y a pas vraiment de notion de commande. 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 » :

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

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.

Systèmes distribués

Distributed Systems

Course offered in the second semester of M1.

Course contents:

  • Introduction
    – Distributed System Modelization
    – Communication Protocol
  • Classic Algorithms
    – Wave Algorithms
    – Transversal Algorithms
    – Leader Election
    – Mutual Exclusion
  • Fault Tolerance
    – Fault Tolerance introduction
    – Self-stabilization
  • Advanced Algorithms
    – k-clustering in distributed systems
    – Clock synchronization in distributed systems
  • Practical Sessions
    – Introduction to Erlang

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.