Teaching
L3 RI
Je donne le cours d'Algorithmique avancée (ALGO2) aux L3 Informatique, parcours Recherche et Innovation. Ce cours est suivi également par des L3 Maths. Les TD sont assurés par Lilian Besson pour les L3 info et Bastien Thomas pour les L3 maths.
| Cours | Contenu | Détails |
|---|---|---|
| 1 | Analyse des algorithmes | Théorème central complexité ; complexité moyenne ; analyse amortie |
| 2 | NP-complétude | Réduction polynomiale ; NP-dureté / NP-complétude ; Théorème de Cook ; |
| 3 | Algo approximation | Pb décision vs Pb optimisation ; 2-approx pour Vertex-Cover ; ln(n)-approx pour Set-Cover ; inapproximabilité voyageur de commerce |
| 4 | Algo approximation / probabilistes | Schéma d'approximation entièrement polynomial pour KnapSack; Tri rapide randomisé ; Classes ZPP ; Algorithme de Krager pour MinCut ; Classe RP |
| 5 | Algo probabilistes | Méthode probabiliste illustrée sur MaxCut : algo probabiliste et dérandomisation |
| 6 | Algo probabilistes | Comptage d'interprétation pour les formules DNF : schéma d'approximation entièrement polynomial ; lemme local de Lovasz : applications |
| 7 | Géométrie algorithmique | Enveloppe convexe : marche de Jarvis, algorithme de Graham ; Points les plus proches : diviser pour régner |
| 8 | Algorithmique du texte | Plus courte surséquence commune : algorithme d'approximation ; Repliement ARN | 9 | Compression des données ; codes | Code de Shannon-Fanon ; Code de Huffman | 10 | Algorithmique des chaînes de Markov | Simulation ; Couplage depuis le passé : algorithme de Propp et Wilson |
Prépa Agreg
J'interviens dans l'option D (option informatique) de la prépa Agreg.J'étais responsable de cette option en 2014-2015 et 2015-2016.
Les années précédentes je donnais le cours de Langages Formels. Les transparents.