Informations M1 2020/2021

Many informations about the M1 Informatique Fondamentale for the year 2019-2020, including the schedule, are available on the following web page:

https://pad.inria.fr/p/r.14d360dc2550cb7952e0234cf77b86fe
The password is M1IF2021

A few useful documents:

M1 2019-2020

Many informations about the M1 Informatique Fondamentale for the year 2019-2020, including the schedule, are available on the following web page:

https://pad.inria.fr/p/r.20943fdd887f77240ab855e959460964
The password is FI1M1920

Here are some useful files:

    • slides of the welcome meeting, on sept. 6th

(here for the presentation about the Centre de Langues)

Documents to help preparing the internship contract.

M1 2018-2019

This page gathers useful informations for students following the first year of Master in Computer Science at École Normale Supérieure de Lyon.

The rules for the Master are here. See here for a description of the year.

Internship.

Slides of the meeting of sept. 25th, 2018. Slides of the meeting of jan. 14th, 2019.

The internship defenses will take place on sept. 4th (the whole day) and 5th (in the morning), 2019, at ENS de Lyon. Stay tuned for the schedule of these presentations.

ENSL Diploma.

You can find here the “Livret du diplôme” for the academical year 2018-2019.

PhDs and PhD grants.

A meeting was organised on november 16th, at 16h15, in amphi B, about PhDs and PhD grants.

Class representants.

Théophile Dubuc and Antonin Dudermel are your class representants this year.

Second semester.

Courses offered: CGDI (David Coeurjolly), DBDM (Emmanuel Coquery et Marc Plantevit), ML (Marc Sebban), SV (Colin Riba), CS (Omar Fawzi), DS (Eddy Caron), CC (Omar Fawzi), PP (Philippe Audebaud), CA (Guillaume Hanrot et Stéphan Thomassé).

Schedule: note that the Integrated Project course will resume its activities on friday, january 25th, at 13.30
Here is the typical schedule. Local changes might apply.
Weekly schedules are available on a shared document — you should have received a link. If not, please write to Suzanne Zeitounian to get the access.

Holidays: 18/02-22/02, 15/04-22/04 — Final exams: between 23/04 and 30/04, schedule to be defined.

Here is the fiche de choix de modules (choice of courses), to be left in D. Hirschkoff’s “mailbox” before feb. 12th at noon.

First semester.

Courses offered: CAP (Laure Gonnord), IT (Omar Fawzi, TDs), PEN (Éric Thierry, TDs), OA (Nicolas Bousquet), APPD (Anne Benoit), Integrated Project (Eddy Caron).

Here is the typical weekly schedule for the first semester.

Weekly schedules: 14-18 jan.7-11 jan. 17-21 dec.10-14 dec. 3-7 dec.19-23 nov 5-9 nov22-26 oct15-19 oct8-12 oct1-5 oct 24-28 sept 17-21 sept. 10-15 sept.

Holidays: 29/10-3/11, and 22/12-5/1 — Final exams: january 21-25, here is the schedule.

Here is the fiche de choix de modules (choice of courses), to be left in D. Hirschkoff’s “mailbox” before sept. 26th at noon.

Midterm exams APPD nov. 5th, PEN nov. 5th, CAP nov. 8th, IT nov 8th, OA nov 20th.

Research schools.

Two research schools are organised, in the weeks 12-16 nov. and 26-30 nov. During those weeks, no course and no TD in M1 (language courses go on, and you are supposed to attend). See the appropriate web page.

Back to school.

The welcome reception of the Computer Science Department will be on sept. 17th, at 16.00, at the IFÉ (Institut Français de l’Éducation).

A mandatory meeting took place on sept. 10th, at 9h00, in Amphi A. See here the slides of the presentation, and here for slides of the centre de langues.

Students who were at ENSL in L3 in 2017-2018 did their administrative registration on friday, sept. 7th.

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.

Machine Learning

Machine Learning

Course offered in the second semester of the M1.

This course gives a general introduction to Machine Learning, from algorithms to theoretical aspects in
Statistical Learning Theory.

Topics covered:
• General introduction to Machine Learning: learning settings, curse of dimensionality, overfitting/underfitting, etc.
• Overview of Supervised Learning Theory: True risk versus empirical risk, loss functions, regularization,
bias/variance trade-off, complexity measures, generalization bounds.
• Linear/Logistic/Polynomial Regression: batch/stochastic gradient descent, closed-form solution.
• Sparsity in Convex Optimization.
• Support Vector Machines: large margin, primal problem, dual problem, kernelization, etc.
• Neural Networks, Deep Learning.
• Theory of boosting: Ensemble methods, Adaboost, theoretical guarantees.
• Non-parametric Methods (K-Nearest-Neighbors)
• Domain Adaptation
• Metric Learning
• Optimal Transport

Teaching methods: Lectures and Lab sessions.
Form(s) of Assessment: written exam (50%) and project (50%)

References:
– Statistical Learning Theory, V. Vapnik, Wiley, 1998
– Machine Learning, Tom Mitchell, MacGraw Hill, 1997
– Pattern Recognition and Machine Learning, M. Bishop, 2013
– Convex Optimization, Stephen Boyd & Lieven Vandenberghe, Cambridge University Press, 2012.
– On-line Machine Learning courses: https://www.coursera.org/

Expected prior knowledge: basic mathematics and statistics – convex optimization

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.

M1 2015-2016, 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.

Courses will start on september the 14th. See here for a schedule of that week. A (mandatory) meeting is organised on september 10th, at 15.30, in Amphi I (slides of the presentation, slides about english & other languages). The organisation of the year, and several other relevant topics, will be discussed. The venue will be announced later. There is no dress code. A meeting of the whole Département d’Informatique will take place on monday, sept. the 14th, at 16.00, in atrium Mérieux (not far from the fountain on the round square next to the Monod site of ENS).

First semester.

Here is the typical week for the first semester, which will serve as a reference starting on sept. the 14th. Be aware that along the semester, local changes to the schedule may apply: refer to the emails you receive (typically, on thursday or friday for the following week). Here is the schedule for the first week, 14-18 sept. Here is the “fiche de choix de modules”, to be printed, signed with your tutor, and given to D. Hirschkoff.

Midterm exams (beware, this is list is not necessarily exhaustive, and is only there to help you — please refer to the actual course to learn about exams/homeworks/etc.): Information Theory as well as Parallel and Distributed Algorithms and Systems, nov. 9th, Compilers and Program analysis on nov.17th, Performance Evaluation and Networks on nov. 13th nov. 18th, Optimisation&Approximation nov. 20th.

The exams for the first semester will take place in the week jan.25-29. Here is the schedule.

Research schools.

M1 students should validate at least two research schools. See this webpage for a list of the research schools proposed in this academical year. Here is the fiche de choix d’écoles de recherche.

Second semester.

The second semester will last between february 1st and april 26th. The exams will take place between april 27th and may 4th.

The schedule for the first weeks is available here. The plan is to organise, after a couple of weeks, some overlap between courses, in order to have thursday afternoon free, and to gain more flexibility in the handling of the schedule.

Here is the fiche de choix de modules, to be given to D. Hirschkoff for february 16th, at noon.

Partiels (be aware that this list may be non-exhaustive, it contains the information I am aware of): computer algebra march 14th / computational complexity march 22nd / cryptography and security march 18th / april 6th: CGDI project due.

Exams : here is the schedule.

Internship.

Here are the slides of the meeting about internship that took place on oct. the 6th, 2015 (nota: we are not sure yet about the date for the defense: it could be end of august or beginning of september).

Important dates:

  • march 15th: deadline to apply to ENS fundings for travel (see the slides)
  • march 31st: Internship contract data entered in Elipse
  • april 15th: internship contract sent abroad
  •  may 16th 9th: leaving for the internship

The procedure for the preparation of the internship contract (convention de stage) is described here.

Deadlines and advices for the evaluation of the internship: see here.

Modes of interaction, all along the year.

For administrative matters, please contact Amel Zagrarni (secrétariat du Département d’Informatique). To discuss scientific/academical matters, as well as your training period, your future, etc., you can contact your tutor (the list of tutors is here), or Daniel Hirschkoff. Your délégués (representants of the students) are Victor Hublitz, Raphaël Monat and Étienne Moutot. Remember that you are supposed to read your email @ens-lyon.fr — in case of a technical problem, get in touch as soon as possible with the Direction des Systèmes Informatiques).

Next year

  • Préparation à l’agrégation { this information is not relevant if you don’t speak french } : il y a 12 ECTS à valider par le biais de modules de professionalisation.Cette page, qui sera régulièrement mise à jour, décrit l’ensemble des cours qui sont proposés (ainsi que les modalités d’inscription). À noter que cela peut être une bonne idée de valider ces modules l’année qui précède la préparation à l’agrégation, mais on ne peut pas les valider plus d’un an en avance (si vous souhaitez préparer l’agrégation après le M2, c’est en M2 que vous pourrez suivre et valider ces modules).
    Les gens qui ont manifesté un intérêt potentiel/hypothétique pour la préparation à l’agrégation l’an prochain sont: Carette Titouan, Combette Guillaume, Faron Maxime, Iannetta Paul, Lajou Dimitri, Lebeau Fabrice, Lucas Christophe, Mauras Simon, Ohlmann Pierre, Perrotin Elise, Seif Johanna
  • M2: you might be interested in applying for the M2 at ENS Lyon, but maybe also somewhere else, depending on your scientific interests. It is up to you to find out about the corresponding application procedure, and about the dates. Usually applications can be made around may-june. (You may well apply to several Masters, be accepted in several places, take your decision during the summer, and inform everybody of your choice — including places where you don’t go)
    Important notice: alas, it might be the case that you will not validate your M1, or that you validate it but will not be accepted to our local M2. It is up to you to judge whether you run the risk of ending up in this situation or not. It is also up to you to be prepared for all possibilities, and, if applicable, to apply to a different Master, at M1 level. Do it in advance, september is usually too late.

Data Bases and Data Mining

Databases and Data Mining

Course offered in the second semester of the M1.

This course gives a general introduction of data management through relational databases and data mining from algorithms to theoretical aspects.

Topics covered:

Databases:

  • Relational model, relational calculus, SQL
  • Relational algebra, equivalence between relational calculus and algebra, indexation and optimisation
  • Functional dependencies, axiomatisation, Armstrong’s relations
  • Inclusion dependencies, data exchange, chase, query rewriting
  • Openness to current issues

Data Mining:

  • Introduction to data mining (itemset/rule mining, enumeration algorithms)
  • constraint-based pattern mining: study of constraint properties and pruning
  • Assessment of results (statistical significance, relevancy w.r.t. background knowledge, user prior)
  • Advanced pattern mining: formal concept analysis, sequences, graphs, dynamics graphs, attributed graphs
  • Clustering: general aims, distances, similarities, algorithms (kmeans, EM, density-based clustering, spectral clustering, hierarchical clustering), graph clustering
  • Anomaly detection
  • Current issues and challenges

Teaching methods: Lectures and Lab sessions (TP).
Form(s) of Assessment: written exam (50%) and project(s) (50%)

References:

  • M. Levene, G. Loizou. A Guided Tour of Relational Databases and Beyond. Springer, 1999.
  • I S. Abiteboul, R. Hull et V. Vianu. Fondements des bases de données. Addison-Wesley, 1995.
  • I R. Ramakrishnam et J. Gehrke. Database Management Systems. 2003 (third edition).

    Material available on pages.cs.wisc.edu/~dbbook/)

  • On line course: https://cs.stanford.edu/people/widom/DB-mooc.html
  • Charu C. Aggarwal, Data Mining, Springer, 2015.
  • Mohammed J. Zaki, Wagner Meira, Jr. Data Mining and Analysis Fundamental Concepts and Algorithms. Cambridge University Press, 2014.

Expected prior knowledge:

Link:

https://perso.liris.cnrs.fr/ecoquery/dokuwiki/doku.php?id=enseignement:dbdm:start

Distributed Systems

Distributed Systems

Course offered in the second semester of M1.

Course contents:

Abstract: In this class, through many examples and training we will discover the main distributed algorithms. From the modelization to the implementation. Wave Algorithms, Transversal Algorithms, Leader Election, Mutual Exclusion are introduced.

In a second part of the class we will focus on an advanced distributed systems approach (this advanced part change over the years). We built distributed system using Erlang during the practical sessions. A distributed middleware will be introduced too.

Prerequisites:

Basic knowledge in algorithmics.

Teaching material:

Slides will be published in a private room due to the fact than updates are usual.

Proofs and Programs

Proofs and Programs

Contents of the course.

“Reasoning and programming are the two sides of the same coin”.

The core of this relation relies on the discovery of a very deep correspondence between Gentzen presentation for proofs of elementary statements from propositional calculus and typing Church’s λ-terms, named Curry-Howard correspondence (1980). Since then, the correspondence has been widely extended, which led toward powerful proof assistants and finer understanding of mathematical proofs; and correctness of programs as well.

Yet, until recently, equality was not properly understood, leaving on one side major mathematical techniques (congruences, quotients, …). In 2006 [Vladimir Voevodsky](Vladimir Voevodsky) envisioned a connection between equality proofs and homotopy. Since then, the relation between proofs and programs has regained a huge amount of attention. Recently (2015), a first contribution to providing a computational interpretation to the extended Type Theory HoTT has been proposed. We get closer to be able to do maths by programming!

References.

  • Lectures on C.-H. isomorphim, by M. H. Sørensen and P. Urzyczyn.
  • Homotopy Type Theory, collaborative book (http://homotopytypetheory.org/)

Prerequisites.

  • Logic (mainly Proof Theory, as opposed to Model Theory)
  • Basics in Lambda-calculus

Webpage of the course: https://perso.ens-lyon.fr/philippe.audebaud/PnP/

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.

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 objectives:

This course will cover the basic questions of information theory as
well as applications of information theory in computer science. It
will cover the following topics:

  • Shannon theory:

    • – Data compression
    • – Channel coding
    • – Applications of entropies in computer science
    • Error correcting codes:

      • – Linear codes
      • – Reed-Solomon codes
      • – Capacity achieving codes with efficient encoding and decoding

    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

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

Optimisation and Approximation

Optimisation and Approximation

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

Contents of the course.

  1. Linear Programming.
    • 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. Non linear optimization.
    • Semidefinite programming.
    • Convex optimization.

References.

  • Understanding and Using Linear Programming, Matousek and Gartner (2006).
  • Linear Programming, Chvatal (1983).

  • Applied Mathematical Programming, Bradley, Hax, and Magnanti (1977).
  • The Design of Approximation Algorithms David P. Williamson and David B. Shmoys (2010).

Prerequisites for the course.
Students should know the basics from Calculus and Linear Algebra.

The webpage of the course.

Compilation and Program Analysis

Compilation and Program Analysis

Contents of the course.

This course covers basic topics in compilation and program analysis: the differents steps of machine language production, as well as program analysis for optimisation and verification:

  • lexical and syntactic analysis;
  • typing, semantics;
  • code optimisation and code generation;
  • imperative languages, functional langages;
  • abstract interpretation.

Prerequisites : familiarity with formal languages (regular expressions, grammars), and induction reasoning, as well as basic notions of computer architecture and in Python programming.

The course has 1 course session (2hours) and 1 lab session (2 hours) per week during the first semester of M1. Students will develop their own compiler as well as a basic abstract interpretation tool.

Page for 2018-19 : http://laure.gonnord.org/pro/teaching/compilM1.html

Parallel and Distributed Algorithms and Programs (PDAP/APPD)

Contents of the course.

Parallelism is everywhere in computer science, since nowadays, each processor
has multiple cores. In this course, we will teach how to design efficient
parallel and distributed algorithms, and how to implement
them through lab sessions. Classes discuss theoretical models
used for the design and analysis and study of algorithms (complexity,
algorithm definition and analysis, approximation algorithms, …).
There will also be tutorials and lab sessions to understand the concepts
seen in class, and in particular there will be an initiation to
parallel and distributed programs through MPI (Message Passing Interface).
The evaluation is done through on-table exams and a programming homework.

The covered topics include sorting networks, PRAMs, algorithms on processor
rings or grids, distributed algorithms, and task graph scheduling.

References.

– Parallel Algorithms. H. Casanova, A. Legrand, Y. Robert. Chapman and
Hall/CRC Press, 2008.

– Introduction to Distributed Algorithms. Gerard Tel. Second Edition,
Cambridge University Press, 2000.

– Distributed Algorithms: An Intuitive Approach. Wan Fokkink. MIT
Press, 2013.

– Scheduling and Automatic Parallelization. A. Darte, Y. Robert, F.
Vivien. Birkhäuser, 2000.

Prerequisites.

Basic knowledge in algorithm design and NP-completeness, and programming skills.

Performance Evaluation and Networks

Performance Evaluation and Networks

Course focused on the performance evaluation in communication networks. “Performance evaluation” is a label that covers many topics, including the design of mathematical models (very often with probabilistic assumptions), the analysis of such models (mathematically or using simulation), the design of experimental protocols (measuring tools, data collection, validation of theoretical models), the analysis of data (statistics on the real experiments or in silico experiments).
This course will address these different items in the framework of communication networks. Some illustrations will be also picked from related systems like transport networks, logistics or automatic control.

References :

  • Performance Evaluation of Computer and Communication Systems. J.-Y. Le
    Boudec. EPFL Press, 2011.
  • Markov Chains, Gibbs Fields, Monte Carlo Simulation and Queues. P.
    Brémaud. Springer-Verlag, 1999.

Prerequisites : Requires basic knowledge in probability. Some knowledge about networks may be useful but not essential.

Current webpage : http://perso.ens-lyon.fr/eric.thierry/Perf2018/