M1 2017-2018

This page gathers useful informations for students following the first year of Master in Computer Science at École Normale Supérieure de Lyon. See here for a description of the M1 year. Here for the rules of the game.

Back to school.

A (mandatory) meeting is organised on sept. 8th, at 9h00, in amphi B. The organisation of the year, and several other relevant topics, will be discussed. There will also be two courses on that day (Integrated Project and Optimisation&Approximation), the second one will finish at 15h30 — see below, “First semester”.

See here about the administrative procedure to register at ENSL. Students who were at ENSL in L3 will register on monday, sept. 11th. There will also be some exercise sessions on that day.

Slides of the presentations (to be provided): general presentation, language department.

A meeting of the whole Département d’Informatique will take place on sept. 18th, at 16.00 at Bâtiment Buisson.

First semester.

Here is the typical schedule for the first semester. Nota: local modifications can occur along the semester.

Here is the schedule for the first courses (sept. 8th-15th). Here is the schedule for the week 18-22 sept., Here is the schedule for the week 25-29 sept., Here is the schedule for the week 2-6 oct., Here is the schedule for the week 9-15 oct., Here is the schedule for the week 16-22 oct. Here is the schedule for the week 23-29 oct. Here is the schedule for the week 6-10 nov. Here is the schedule for the week 13-17 nov. Here is the schedule for the week 20-24 nov. Here is the schedule for the week 27 nov.-1 dec.
The week 4-9 dec. will be devoted to a Research School: see here for informations (including the schedule).
Here is the schedule for the week 11-15 dec. Here is the schedule for the week 18-22 dec.

Here is the “fiche de choix de modules”, to be left in D. Hirschkoff’s mailbox on sept. 26th at noon at the latest.

Holidays: from oct. 28th to nov. 5th, and from dec. 23th to jan. 7th.

CAE sessions (english certification) will be on january 13th, march 24th and june 23rd.

Final exams will take place during the week starting on jan. 8th, 2018. See here for the schedule.

Research schools.

Three research schools will be organised, during the weeks dec. 4th, jan. 15th and jan 22nd. More information here.
Here is the “fiche de choix d’écoles de recherche”, to be left in D. Hirschkoff’s mailbox before november 27th at noon.

Second semester.

Holidays: there will be two weeks of holidays during the second semester, in winter (february 19-26) and in spring (april 16-23).

Here is the “fiche de choix de modules”, to be left in D. Hirschkoff’s mailbox on feb. 13th at noon at the latest.

Here is the schedule for the week 29 jan – 2 feb. Here is the schedule for the week 5-9 feb. Here is the schedule for the week 12-16 feb. Here is the schedule for the week 26 feb.-2 march. Here is the schedule for the week 5-9 march. Here is the schedule for the week 12-16 march. Here is the schedule for the week 19-23 march. Here is the schedule for the week 26-30 march. Here is the schedule for the week 3-6 april. Here is the schedule for the week 9-13 april.

Midterm exams (of which I am aware of, the reference is what the teachers say): CS march 13th, 15.45-17.45. SV march 14th, 13.30-15.30, CC march 13th, 10.15, DS march 12th, 13.30-15.30.

Monday, april 2nd is a holiday (Easter). As a consequence, the CA course that cannot take place will be on wednesday, march 28th, between 18.00 and 20.00. Stay tuned for the DS course that should be on april 2nd.

Final exams will take place in the week 23-27 april. The schedule is available here.

Internship.

See the slides of the meeting of oct. 20th, 2017. Stay tuned for some advice about the preparation of the internship contract (remember that the first step from this point of view is to ask whether the hosting institution is willing to sign the contract given by UCBL). Stay tuned also for some advice about the preparation of the internship report and of the defense.

The person in charge of M1 internships is Frédéric Vivien.

Here are the slides of the presentation given on february 12th, 2018.

Some useful files, provided by the bureau des stages: Template internship agreement, aide à la saisie sous Elipse, guide Elipse

Schedule: report due on august 28th, at noon; presentations on september 5th and 6th.
Here is the current version of the schedule for the presentations — make sure to look at it a few days before the presentations, because changes may occur.

Next year.

Most of the M1 students proceed along one of the following paths after validating the M1:

  • Study in M2, either at ENS Lyon or somewhere else (in France, abroad).
  • Follow a year of preparation for the agrégation de mathématiques.

[this is intentionally in french] Si vous envisagez de préparer l’agrégation de mathématiques l’an prochain, il est conseillé de valider un module de dès cette année. Voir ceci et ceci pour cela.

  • Spend a year doing (research) internships, in France and/or abroad.
  • Double diplomas (here, and also here for EPFL).

This is something you should keep in mind along the year of M1, and prepare ahead of time.

Means of communication.

The class representants are L. Assouline, S. Fernandez, U. Léchine and P. Oechsel.

Distributed Systems

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

Semantics and Verification

Sémantique et Vérification

The goal of Formal Verification is to check algorithmically that some programs or systems are correct with respect to their requirements.
In this course, we will see how such programs, systems and requirements can be modeled, and what computations can be performed on these models.
We will give the mathematical tools to understand how algorithms can automatically check for bugs, and give us useful feedback information.

Content of the course:

  • Introduction and basic principles of model-checking
  • Modelling the systems

    -Concurrent systems
    -Labelled transition systems
    -Software and Hardware systems

  • Linear-Time properties

    – Definition, Examples and Topological characterizations
    – omega-Regular Properties and Büchi automata
    – Linear Temporal Logic

  • Bisimulation and Modal Logic

    – Bisimulation and Trace Equivalence
    – Hennessy-Milner Logic
    – Bisimulation and Logical Equivalence

Image processing, digital and computational geometry

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

Computational Complexity

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.

Cryptography and Security

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

Computer Algebra

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 :

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

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

Information Theory

Information Theory

Course offered in the first semester of M1 2017-2018.

See the course website, and the webpage for the TDs.

Course objectives:

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

  1. Measuring information content using Kolmogorov complexity [2 hours]
  2. Measuring information content using information processing tasks
    (a) Source compression (Shannon theorem, Huffman coding and Lempel-Ziv compression) [6 hours]
    (b) Channel coding (Channel model, Shannon theorem) [4 hours]
    (c) Application in combinatorics: Counting perfect matching [2 hours]
    (d) Application in cryptography: Shannon theorem on perfect security (optional: privacy amplification) [2 hours]
  3. Error correcting codes
    (a) Linear codes (definition, decoding, bounds on the distance) [2 hours]
    (b) Reed-Solomon codes properties and decoding [6 hours]
    (c) Achieving channel capacity with almost linear-time encoding and decoding (for the binary erasure channel) [4 hours]
    (d) Application to hashing [2 hours]
  4. Opening: Analogue signals and digital conversion, Nyquist sampling theorem, and going beyond it with Compressed Sensing [2 hours]

Pre-requisites

Familiarity with basic probability and linear algebra. The necessary background for finite fields will be introduced.

References

  1. Cover and Thomas, Elements of Information Theory
  2. Guruswami, Rudra and Sudan, Essential Coding Theory

Optimisation and Approximation

Optimisation and Approximation

Course offered in M1 2017-2018, first semester. The webpage of the course.

Objective:

The goal of this course is to present optimization techniques with a main focus on linear relaxation. Applications to approximation algorithms will be highlighted.

Tentative plan:

  1. Linear Programming.
    – Notions on polytopes.
    – Simplex algorithm.
    – Duality and complementary slackness.
    – Sensitivity analysis.
    – Integer polytopes (flows, transportation, totally unimodular
    matrices).
    – Integrality gap, Erdos-Posa property.
    – VC-dimension.
  2. Approximation via linear relaxation.
    – Primal-Dual algorithms.
    – Branch and bound.
  3. Matroids and greedy algorithms
  4. Non linear optimization (if time permits).
    – Semidefinite programming (approximation of MAX-CUT and MAX 2-SAT).
    – Convex optimization.