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

[Lire la suite…]

Machine Learning

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

Data Bases and Data Mining

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

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

  • Modelling and checking the [Lire la suite…]

Proofs and Programs

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

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

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

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 [Lire la suite…]

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) [Lire la suite…]

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 [Lire la suite…]

Parallel and Distributed Algorithms and Programs

Course offered in the M1 2017-2018.

See here for exercises.

Performance Evaluation and Networks

See the webpage of the course.