FICHE MODULE SI5 / M2 IFI

TITRE : Algorithms for telecommunications : Advanced tools.

Durée/Period : 8 semaines / 8 weeks

RESPONSABLE  : Frédéric Havet
QUALITE/CV : CR1 CNRS, projet Mascotte

AUTRES INTERVENANTS ACADEMIQUES (Nom /Etablissement) :

• Stéphane Pérennes, CR1 CNRS

AUTRES INTERVENANTS EN ENTREPRISE (Nom / Entreprise) :

• Jerome Galtier, Orange Labs

RESUME  : In this course, we will present some powerful theoretical tools in graph theory and combinatorial optimisation : probabilistic method, discharging method, tree decomposition and convex programming. We will in particular illustrate how such tools may be applied to solve some problems arising from telecommunications like channel assignment, routing in networks, ...

OBJECTIFS (2 lignes) : Give engineers and researchers a strong theoretical background to understand the difficulty of present optimisation problems. This would help to either develop some theoretical results or design efficient algorithms for such problems.

CONTENU 

1. Probabilistic method (Introduction) [C/TD]
2. Probabilistic method (Applications) [C/TD]
3. Discharging method [C/TD]
4. Tree decomposition and dynamic programming   [C/TD]
5. Tree decomposition and dynamic programming (ctd) [C/TD]
6. Convex programming [C/TD]
7. Convex programming (ctd) [C/TD]
8. Evaluation: viva

PREREQUIS : Algorithms for telecommunications I, Linear Programming

BIBLIOGRAPHIE :

• Probabilistic method (Alon and Spencer), lecture notes of F. Havet (in french) see his webpage,
• Geometric Algorithms and Combinatorial Optimization (Martin Grotschel, Laszló Lovász, and Alexander Schrijver)

SUPPORT de COURS : Lectures notes

MODE D’EVALUATION :

Quelque soit la langue du cours, c'est l'étudiant qui choisi la langue dans laquelle il sera évaluer. La rédaction du sujet est dans la langue du cours (un cours en français aura un sujet en français, un cours en anglais aura un sujet en anglais).

Mettre une croix dans le mode d'évaluation choisi