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.

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.