Year: 2015

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

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

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

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/