Master 2 – 2016/2017

Yves Robert

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

Conventions de stage (M2)

Yves Robert

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: Procedure.

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

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

Une fois la demande approuvée, vous devez récupérer 4 conventions au secrétariat pour amorcer le processus de signatures. C’est votre responsabilité de vous assurer que toutes les signatures sont faites avant le début de votre stage. Pour les étudiants en Erasmus, les conventions vous seront transmises par courrier.

Pour le suivi des signatures, on vous demande de nous envoyer un mail (1) lorsque les conventions ont été transmises à l’organisme d’accueil (par vos soins), accompagnées d’un courrier explicatif (modèle: Courrier accompt conv, ou en anglais: Courrier-accompt-conv-en), et (2) lorsque votre encadrant de stage vous a confirmé avoir obtenu les signatures de son côté et avoir renvoyé les conventions à l’UCBL (par son soin).

Tous les mails doivent être adressés au responsable des stages (Laurent Lefèvre pour le M2) et au secrétariat (Amel Zagrarni) avec comme objet: « [StageM2] 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!

Evaluation of M2 courses

Yves Robert

For your information, here are the modalities of evaluation for all M2 courses.

CR01: The students are given research articles twice. Each time, they give an oral presentation based on these articles. The first one counts as continuous evaluation (CE), the second one as final evaluation (FE). The final note is given by (CE+2FE)/3.

CR02: There is homework for continuous evaluation (CE). The students are given research articles, they produce a written report and give an oral presentation based on these articles (FE). The final note is given by (CE+2FE)/3.

CR03: There is homework for continuous evaluation (CE). The students are given research articles, they produce a written report and give an oral presentation based on these articles (FE). The final note is given by (CE+2FE)/3.

CR04: There is homework for continuous evaluation (CE). The students choose research articles, they produce a written report and give an oral presentation based on these articles (FE). The final note is given by (CE+FE)/2.

CR05: 3 homeworks for continuous evaluation (CE); written report and give an oral presentation based on a research article for final evaluation (FE). The final note is given by (CE+2FE)/3.

CR06: Two mini-projects counting each for 1/4 of the final grade. One final exam counting for the last half.

CR07: Two homeworks for continuous evaluation (CE1,CE2). The students are given research articles, they produce a written report and give an oral presentation based on these articles (FE). The final note is given by ((CE1+CE2)/2+2FE)/3.

CR08: Grades will be based on a final exam and on the presentation of a research article, each contributing to one half of the grade.

CR09: The students are given research articles, they produce a written report (WR/20) (between 8 and 20 pages). We will do a cross review. One report of another given student report (1 or 2 pages maximum) will be done (RR/20). And student gives an oral presentation based on these articles (OP/5). Questions should be done by students (Q/5). The final note is given by (3WR+3OP+2*(RR+Q))/7

CR10: The students are asked to write a static analyser for a mini language (AS). The students are given research articles, they give an oral presentation based on these articles (FE). The final note is given by (AS+FE)/2.

CR11: There will be a programming project (6pts, due after the mid-term break), a modeling project (7pts, due after the end-of-term break) and a written exam (7pts).

CR12: The final grade for the CR12 course is computed as follows: small exercices to be handed each week, during the first half of the course, count for 1/4 of the grade; a mid term exam counts for 1/4 of the grade; a final exam counts for 1/2 of the grade.

CR13: There is homework for continuous evaluation (CE). The students have also a final evaluation (FE) based on a written exam at the end of the course. The final note is given by max(FE,(CE+2FE)/3).

CR14: There is homework (based on the content of lectures as well as the study of research papers) for continuous evaluation (CE). There is a written exam (2h) for final examination (FE). The final note is given by (CE+2FE)/3.

CR15: The evaluation of the CR15 Complex Networks course will depend on whether the student is involved in the M2 Complex System program or not. If yes then the student’s participation will be mandatory to the TD, which is evaluated through projects during the semester and the final mark will count as 1/3 to the final overall mark. In addition every student has to pass a written exam by the end of the semester for the lecture, which will count with 2/3 weight in the final evaluation. If the student is not involved in the Complex System program only the written exam is mandatory, which result will determine 100% the final mark. On the other hand even these students have the option to participate to the TDs, complete the projects and get a TD mark. In this case the student will have the advantage to gain the better mark gained with or without the TD results.

CR16: The students will be proposed research articles about which they need to produce a report (with some numerical applications of the content of the article) and an oral presentation. The report and presentation are used for the note.

CR17: Two homeworks (counting each for DM/2) and one final exam (DS). The final grade is (DM+2DS)/3.

CR18: The students are given 3 homework assignments for continuous evaluation (CE). At the end of the semester, students are asked to study and orally present research articles (FE). The final note is given by (CE+2FE)/3.

CR19: There is homework for continuous evaluation (CE). The students are given research articles, they produce a written report and have an exam based on these articles (FE). The final note is given by (CE+2FE)/3.

ER01: Randomized Algorithms (7-11 décembre)

Matthieu Rosenfeld

Date : 7-11 décembre 2015

Intervenants: Joel Ouaknine, Ben Worrell et Stefan Kiefel (Oxford).
Contact local: Pascal Koiran

(Un résumé du contenu se trouve sur la version anglaise de cette page.)

Voici l’emploi du temps :

 

Monday: 9:30 – 11:30 am and 1:30 – 3:30 pm
Tuesday: 9 – 11:30 am, 1:30-3:30 pm and 4-6 pm.
Wednesday: 9-11:30 am and 1:30-3:30 pm.
Thursday: 9 am – 12:30 pm
Friday: 9 am – 12:30 pm and afternoon exam: 2 pm – 4 pm

Registering at Lyon1

Yves Robert
Here are some useful informations for your registration at Lyon1.
  • What do you need to pay?
    • Sécurité sociale : 215 € (you are not all concerned)
    • Médecine préventive universitaire : 5,10 €
    • Master : 256 €
  •  Those of you who were at ENS Lyon last year can do everything online after Saturday Sept. 12 (we first need to confirm to Lyon1 who is indeed accepted to the M2): http://inscriptionweb.univ-lyon1.fr/
  • For those of you who enter ENS Lyon this year, you will need to go there. First, you need to fill this document:
Also, you can find the list of documents required here: docs-Lyon1.
You can get some help to fill the registration documents thursday between 11h30 and 13h00 (see the “circulaire de rentrée”), and then some of you (5 at most) can directly go to register at Lyon1 at 13h. You will need a way to pay, and someone with basic knowledge of french because no-one speaks english there. Please let me know asap if you want to go thursday, and I will then send you directions.
We will arrange another time to register for those who could not make it on thursday afternoon.

Emplois du temps M2 2015-2016

Yves Robert

The pre-course meeting for the M2 is planned Friday September 11 at 9am in Amphi B.

Courses start September 14. Here is the typical timetable for all weeks: EdT-M2-type

Note that the schedule will slightly change from one week to another. Timetables will be posted (and sent by email to students registered to the M2) whenever they are available.

Here is the form to fill for your choices of courses: modules-M2IF

  • Week 38 (starting Sept 14): EdT-M2-S38 (new version of Sept 11)
  • Week 39 (starting Sept 21): EdT-M2-S39
  • Week 40 (starting Sept 28): EdT-M2-S40-v3 (a few changes of rooms / updates of courses)
  • Week 41 (starting Oct 5): EdT-M2-S41-v2 (exchange CR01-CR02)
  • Week 42 (starting Oct 12): EdT-M2-S42
  • Week 43 (starting Oct 19): EdT-M2-S43-v2 (update of room)
  • Holidays
  • Week 45 (starting Nov 2): EdT-M2-S45
  • Week 46 (starting Nov 9): EdT-M2-S46-v2
  • Week 47  (starting Nov 16): EDT-M2-S47
  • Week 48 (starting Nov 23): EDT-M2-S48
  • Week 49 (starting Nov 30): EDT-M2-S49
  • Week 50 (starting Dec 7): Research school, no courses
  • Week 51 (starting Dec 14): EDT-M2-S51

Exams will be held on January 4-8, 2016 (EDT-M2-EXAMS), followed by two weeks of research schools.

Gestion et Fouille de Données

Daniel Hirschkoff

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

Daniel Hirschkoff

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

Daniel Hirschkoff

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

Daniel Hirschkoff

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é

Daniel Hirschkoff

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

Daniel Hirschkoff

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

Daniel Hirschkoff

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.