
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”.
[Lire la suite…]
List of courses (for full description follow the link CRxx):
 CR01: Optimal Decision Making and Online Optimization, Panayotis Mertikopoulos and Bruno Gaujal.
 CR02: Computational Geometry, Monique Teillaud and Olivier Devillers.
 CR03: Hard lattice problems, Damien Stehlé.
 CR04: Automata, coinduction, and relation algebra, Damien Pous.
 CR05: Monadic Second Order Logic, Automata, Expressivity and Decidability, Matteo Mio and Denis Kuperberg.
 CR06: Implicit Computational Complexity, Patrick Baillot and Olivier Laurent.
 CR07: Models of concurrency, categories, and games, Pierre Clairambault and Glynn Winskel.
 CR08: Scheduling at scale, Yves Robert.
 CR09: Advanced Topics in Scalable Data Management, Eddy Caron and Marcos Dias de Assuncao
 CR10: Software Engineering & Compilation, Sebastien Mosser and Lire la suite…]
Machine Learning
Course offered in the second semester of the M1.
See here for a description of the course (teaching personnel: Marc Sebban and Amaury Habrard, UJM).
Gestion et Fouille de Données
Ce cours est offert au second semestre du M1.
Descriptif du cours :
 Bases de données – langages relationnels (Algèbre, Calcul, Datalog, Thm d’équivalence) – théorie des dépendances (dépendances fonctionnelles) pour la conception.
 Fouille de données – méthodes de découverte de motifs (itemsets, séquences, graphes, dépendances) – approches de classification automatique
 Ouvertures – représentation condensée des motifs fréquents – dualisation sur des ordres partiels – liens avec le big data
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 – Selfstabilization
 Advanced Algorithms – kclustering in distributed systems – Clock synchronization in distributed systems
 Practical Sessions – Introduction to Erlang
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:
Proofs’n’Programs
This course is offered in the second semester of the M1. See the french version of this page of a description of the contents of the course.
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, ..
[Lire la suite…]
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 [Lire la suite…]
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 Pseudorandom number generators Pseudorandom functions Message Authentication Codes Stream ciphers and block ciphers Security against chosen plaintext/ciphertext attacks Hash functions
 Asymmetric cryptography Discrete logarithm, decision DiffieHellman Factoring, RSA problem Key exchange Digital signatures Publickey encryption The random oracle methodology
 Other topics possibly covered: Zeroknowledge proofs Secret sharing Yao’s garbling circuits
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, ToomCook 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, floatingpoint arithmetic, finite fields arithmetic.
II. Linear algebra over [Lire la suite…]
Information Theory
Course offered in the first semester of M1 20172018.
See the course website, and the webpage for the TDs.
Course objectives:
One can summarize the most important objectives of the course as follows.
 Measuring information content using Kolmogorov complexity [2 hours]
 Measuring information content using information processing tasks (a) Source compression (Shannon theorem, Huffman coding and LempelZiv 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) [Lire la suite…]
Optimisation and Approximation
Course offered in M1 20172018, 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:
 Linear Programming. – Notions on polytopes. – Simplex algorithm. – Duality and complementary slackness. – Sensitivity analysis. – Integer polytopes (flows, transportation, totally unimodular matrices). – Integrality gap, ErdosPosa property. – VCdimension.
 Approximation via linear relaxation. – PrimalDual algorithms. – Branch and bound.
 Matroids and greedy algorithms
 Non linear [Lire la suite…]
Course offered in the M1 20172018.
See here for exercises.
See the webpage of the course.

