M1 2016-2017, useful information

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. 13th, at 14h30, in amphi B.  The organisation of the year, and several other relevant topics, will be discussed.

Slides of the presentations: general presentation, language department, new diploma of ENSL.

A meeting of the whole Département d’Informatique will take place on monday, sept. 19th, at 16h00, at the Maison des Mathématiques et de l’Informatique (next to the round square which is close to the Monod site of ENS).

First semester.

Here is the schedule for the first courses, starting from september 14th. Here is the typical schedule for the semester. [ Here is the schedule for the week 19-23 sept. Here is the schedule for the week 26-30 sept. Here is the schedule for the week 3-7 oct. ]

The schedules of the following weeks will be variations on this one.

Here is the “fiche de choix de modules”, to be printed, signed with your tutor, and given to D. Hirschkoff, before oct, the 4th sept. the 27th, at noon (write an email in advance if you know that you’ll be late, for some reason).

Partiels (midterm exams) and handouts of which I am aware of (beware, this list is not necessarily exaustive — refer to the teachers for the full information): APPD midterm, october 26th, 13h30-15h30. APPD homework: to be determined (assignment available on nov. 7th); TI midterm, nov. 4th, 10h15-12h15. OA midterm: oct. 25th, 10h15-12h15; CAP midterm: oct 24th, 13h30-15h30; EPR midterm: nov. 9th.

Holidays will start on saturday, dec. 17th, and end on january 2nd (courses will resume on tuesday, jan. 3rd).

Here is the schedule for the exams for the first semester.

[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 dès cette année.

Research schools.

You have to follow and validate at least 2 of the research schools that are offered, in Lyon and Sophia Antipolis. See here for the dedicated webpage.

The fiche de choix d’écoles de recherche, to be given for november 15th, at noon, is available here.

Important notice for the Research Schools organised in Sophia-Antipolis: please make sure to register to the school (follow the links to the dedicated webpage). You may ask for help in order to find an accomodation there.

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 weekly schedule, as of january 5th. The planned week for the exams is may 15-19, some exams may take place in the preceding week. Here is the “fiche de choix de modules”. The deadline is march 7th, at noon.

Projet intégré: sessions on feb. 13th, feb. 27th, mar. 6th, mar. 13th. Demo on april 7th, final meeting on april 10th.

Midterm exams: CS on march 30th, 8.00-10.00.

Schedule of the last weeks of teaching : 24-28 april, 2-5 may, 9-12 may.

Schedule of the final exams: here.

Internship.

Slides of the meeting which took place on october 10th.Stay tuned for a page describing the procedure to prepare the internship contract (convention de stage).

The presentations of the internships will take place on september 5th and 6th, in Lyon.

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.
  • Spend a year doing (research) internships, in France and/or abroad.

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 R. Cerda and T. Sterin.

OLD – M1 research internship, evaluation

[ this translation of the french version of this page is based on work by Raphaël Monat: merci beaucoup! ]

Get quickly in touch with D. Hirschkoff (or your tutor) if you have difficulties during your intenship.

A general remark: you should not suppose that people reading your report/attending your presentation are specialists of the field you worked on during your internship. This should not prevent you from providing technical details, but the latter should be explained. Do not focus on the technical material only. Experience shows that M1 students tend to give too much emphasis on the technique, as if they were talking to their internship supervisor.

1 Report

Format:

20 pages at most. If needed, you include an online appendix, containing proofs, numerical results, an article you wrote with your supervisor, some code…

It is highly recommended that your supervisor proofreads your report (this means that you need to finish writing your draft early, to have time for proofreading and corrections).

Concerning the content:

  • Introduce the domain

You need to explain the question you have studied, and the context/reasons of your study.
– Where does the problem you studied come from?
– Why is this question interesting/relevant?
– What was the state-of-the-art at the beginning of your internship?
– Be aware that you need to present relevent related work.

  • Present your work

– If you have 10 results, you will not have the space to present everything (or it will be compressed and really difficult to understand). You need to select what you will present.
– If you don’t have any result, you can write about what you tried and why it failed, and how the difficulties were handled, together with your supervisor, along the internship.

  • Comment on your approach

It is also interesting to know how your research went:

– What did not work?

– Your interactions with your supervisor

– Your collaborations with other members of the lab

– The initiatives you have taken
This shouldn’t be a signficant part of your report/presentation, but it will help in assessing the quality of your work.

  • Experimental results (if applicable)

If you have developped non-trivial programs or used some tools, mention them!

– Size of the code
– Tools/languages used
– Expected use of the tool(s)
– Implementation choices

2 Presentation

  • Format: 20 minutes of presentation, 5 minutes of questions.

Rehearse your presentations at least twice! You will be interrupted if you exceed the given presentation time.

Your presentation will be a disaster if you’re interrupted during part 2 / 5 of your presentation. Conversely, if you finish your presentation in 8 minutes, it will also be a disaster.

Put pressure on yourself! Preparing a nice and crystal-clear presentation is a really difficult exercise, needing a lot of preparation.

– You should avoid mentionning too many technical details, you will loose your audience this way. But you need to strike a balance and still mention technical points.

– (Similar to the report) You need to present the question you worked on, and your contributions. Non specialists (i.e, other researchers from the LIP, or other students) should be able to follow your presentation.

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.

3 Technical points

Have a backup of your presentation on a USB stick, in case of technical problems between your computer and the projector.
– You need to have a machine to project your slides. You can share a computer for all presentations of a given session. It is highly recommended to test your projection skills before the presentation day.
– If you are using Beamer, `pdfpc’ is an interesting tool to project your slides
– Use git to version your documents/work. This should prevent ay loss of your work.

Computer algebra

Contents of the course

  • Gcd and extended Gcd : Euclidean algorithm, Extended Euclidean Algorithm (complexity analysis, properties), quasi-linear gcd (Knuth-Schonhage).
  • Algorithms for polynomials : evaluation, interpolation. Product tree. Quasi-linear algorithms for multiple point evaluation and interpolation.
  • Algorithms for linear algebra : Gauss pivoting (over a field), applications (image, kernel, determinant, linear system solving) ; multimodular methods and Hensel lifting over Z and K[X].
  • Elimination theory and resultant. Applications to the computation of theintersection of two plane algebraic curves.
  • Polynomial factoring over Z/pZ : Berlekamp algorithm, Cantor-Zassenhaus algorithm, Hensel lifting over Z/p^k Z.
  • Application to Error-Correcting Codes : Reed-Solomon codes. Decoding algorithms, list decoding algorithms.
  • (… to be completed)

See the french version of this page for informations about the organisation of this course.

Cryptography and Security

Course contents:

Cryptography aims at securing communications against malicious parties.  This field enjoys numerous links with theoretical computer science (complexity theory, security proofs) but has also a very rich practical counterpart: Cryptographic protocols are part of every-day life (electronic commerce, payment cards, electronic voting, etc).
This course is an introduction to the different facets of modern cryptography. The following topics will be addressed:

  • Symmetric encryption
  • Asymmetric encryption
  • Cryptographic hashing
  • Authentication
  • Pseudo-random number generators
  • Zero-knowledge proofs
  • Public-key infrastructure
  • Cryptanalysis
  • Provable security
  • Secret sharing

We will also describe several practical applications, such as PGP, TLS/SSL and electronic voting.

Evaluation sheet.

Teaching staff

Program analysis and systems verification

Contents of the course

  • Ordered structures and Topologies. Scott domains. Denotational and Axiomatic semantics. Abstract interpretation.
  • Principles of model-checking. kripke structures and Büchi automata. Temporal logics (LTL, CTL, …).

Practical matters related to the organisation of the course will be presented at the first course.

People in charge:

Parallel algorithms and parallel programming

Program

Parallelism is now ubiquitous in computers because all modern computers contain multicore processors. This lecture series focuses on the design of efficient parallel algorithms and on their actual implementation. The lectures will deal with the theoretical models used to design and analyze parallel algorithms. A number of classical algorithmic problems will be studied in details: complexity study, algorithm design and analysis, approximation algorithms, etc. The lectures will be supplemented with six exercise sessions, and six laboratory sessions. The aim of the lab sessions is to introduce students to parallel programming through message passing (MPI).

Overview

  • The theoretical model of sorting networks
  • The theoretical model of PRAMS
  • Algorithms on processor rings and processor grids: vector-matrix product, matrix-matrix product, 2D stencils, etc.
  • Taks graph scheduling, with and without communications, with and without resource constraints: complexity, approximation algorithms, and heuristics
  • Dependence analysis and automatic parallelization
  • Introduction to algorithms for GPUs

Students will be graded through a final examination and a continuous assessment. The continuous assessment will comprise both a mid-term examination and a programming homework.

Teachers

Performance evaluation

Description :

This course presents basic tools for qualitative and quantitative performance evaluation of communication and computing systems. It is a
theoritical course but some real systems will be analyzed such as communication networks. This course will also present an introduction to
statistics and some discussions about the experimental method.

Plan of the course :

  1. Short refresher about probability prerequisites
  2. Simulation schemes and random generation
  3. Discrete time Markov chains
  4. Continuous time Markov chains and queuing theory
  5. Markovian decision process
  6. Petri nets
  7. Statistics

Prerequisites :

A classical but strong background in probability is necessary (like some knowledge about finite state Markov chains or convergence of random  variables).

People in charge of the course:

  • Eric Thierry (a web page dedicated to the course will be made available from E. Thierry’s page).
  • Julien Herrmann

Distributed Systems

Program

This lecture focuses on algorithmic for distributed systems. We will introduce distributed algorithms to solve communication problem, resource allocation, synchronization, … Thus leader election problems, waves algorithm, termination, routing, fault tolerance, self-stabilization, etc. are some examples that we will see  during the lecture. Different kind of distributed system programming and implementation will be studied through ERLANG, CORBA or the DIET middleware.

Speakers

Language

English upon request.