Premier cours : Mercredi 11 septembre 2019, de 16h15 à 19h15 (Bat. Sophie Germain, 1013)

Responsable : Vlady Ravelomanana

Partie 1

1. Introduction : Vlady Ravelomanana
2. Modèle rationnel : Frédérique Bassino
3. Familles simples d'arbres et analyse de singularités : Olivier Bodini
4. Structures étiquetés: permutation, graphes fonctionnels et hachage : Vlady Ravelomanana

Partie 2

1. Graphes aléatoires et combinatoire analytique : Elie de Panafieu
2. Algorithmes de comptage probabiliste et estimation de cardinalité : Nicolas Broutin

voir plan détaillé ci-dessous.

La première partie de ce cours vise à mettre en place les bases de l'étude des modèles combinatoires quantitatifs de l'analyse d'algorithmes. Ceci met en jeu la théorie générale de la combinatoire analytique, où interviennent des méthodes de combinatoire énumérative (par fonctions génératrices) conjuguées à des méthodes d’analyse asymptotique. Cette approche permet l’évaluation des principaux algorithmes et structures de données de l’informatique. Le cours est étayé de nombreux exemples. La seconde partie est dédiée à l'étude de divers types d’applications (différentes selon les années), particulièrement en liaison avec les structures arborescentes, l’algorithmique probabiliste, la recherche multidimensionnelle, et les graphes aléatoires.

1. Socle
   • Généralités sur les modèles probabilistes discrets: moyennes, variances, lois de probabilité discrètes. Liens entre dénombrements, analyse asymptotique, et analyse d'algorithmes. Inégalités de Chebyshev. Exemple élémentaire: sélection des k premiers, tables d'inversion, nombre de Stirling, comparaison de deux stratégies de sélection.
   • Dénombrements exacts par séries génératrices ordinaires et exponentielles. Modèles de base pour les mots et langages, familles d'arbres, permutations, graphes contraints, allocations (modèles d'urnes). Pour les modèles rationnels: liens entre automates, séries rationnelles, systèmes linéaires, et matrices de transfert. Pour les modèles algébriques et leurs variantes: inversion de Lagrange, théorème de Cayley (arbres étiquetés), applications aux fonctions finies (mappings).
   • Notions sur les fonctions génératrices à plusieurs variables: calculs explicites de moments et de lois de probabilité.
   • Dénombrements asymptotiques. Utilisation des propriétés analytiques des séries génératrices: pôles des fractions rationnelles, bornes sur les rayons de convergence (bornes de col), les singularités et leur influence sur les coefficients de séries (bases de l'analyse de singularité).
   Le traitement est élémentaire en ce qui concerne la manipulation algébrique de séries génératrices. Il reste pragmatique sur les aspects liés à l'analyse complexe (détection des singularités positives grâce au théorème de Pringsheim). Il est demandé peu de connaissances préalables à l'étudiant mais l'acceptation d'une théorie par nature assez mathématisée. Les applications traitables à ce niveau sont par exemple:
   • Mots et motifs: polynômes d'autocorrelation, linéarité en moyenne de la recherche naïve de motifs.
   • Arbres de Catalan, objets bijectivement reliés (chemins de Dyck, triangulations), et leurs principales caractéristiques probabilistes.
   • Arbres de Cayley et application aux générateurs aléatoires ainsi qu'à la factorisation entière (méthode rho de Pollard).
   • Tri rapide (Quicksort); Sélection rapide (Quickfind); Variantes avec médiane; Caractéristiques principales des arbres binaires de recherche (longueur de cheminement, pagination).
   • Hachage avec chainage séparé et allocations aléatoires: paradoxe des anniversaires, collectionneur de coupons, loi de Poisson des remplissage, linéarité en moyenne.
2. Applications avancées.
   • Problèmes difficiles en optimisation et combinatoire analytique : apports de la Combinatoire Analytique dans les problèmes difficiles d'optimisation, les graphes aléatoires et les transitions de phase dans les formules du type SAT.
   • Algorithmique aléatoirisée. Une direction récente est l'algorithmique de la fouille de données: algorithmes de comptage probabiliste et estimation de cardinalité, extraction des mots fréquents, extraction des contenus communs à des corpus distincts.

• 11/09 : introduction
• 18/09, 25/09 et 02/10 : modèles rationnels
• 09/10, 16/10 et 23/10 : familles simples d'arbres
• 30/10, 06/11 et 13/11 : structures étiquetées
• 20/11 : séance d'exercices
• 27/11 : examen partiel
• 08/01, 15/01 et 22/01 : transformée de Mellin et applications (algorithmes et structures aléatoires)
• 29/01, 05/02 et 12/02 : graphes aléatoires
• 19/02 : séance d'exercices
• 26/02 : examen

• Examen Partiel : Mercredi 27 Novembre 2019, de 16h15 à 19h15
  Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.
• Examen Final : Mercredi 26 Février 2020, de 16h15 à 19h15
  Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.
• Note finale = (EFinal+EPartiel)/2.

Le cours aura lieu en français, mais les documents servant de support sont, pour la plupart, en anglais.

Des supports de cours existent, sous forme de résumés détaillés, de notes de cours rédigées et d'annales: vous pouvez par exemple accéder à la page du cours de 2005. Ce cours s'appuie par ailleurs très fortement sur l'ouvrage cité dans la bibliographie.

Des exercices sont proposés chaque semaine (et corrigés au début du cours suivant). Deux séances d'exercices précèdent les examens.

Ce cours est très lié au cours 2.10, qui couvre des thématiques très proches (mais on peut aussi suivre un seul de ces deux cours).

Dans des domaines de l'algorithmique voisins, il est recommandé de suivre des cours comme 2.11.1, 2.11.2, 2.17.1, 2.22, ou 2.29-1

Ce cours relativement mathématisé doit bien convenir à des étudiants ayant une formation mixte en mathématiques et informatique de bon niveau, comme il s'en rencontre à l'École polytechnique et dans les Écoles normales supérieures, ainsi que dans les parcours Math-Info des cursus universitaires. Il peut aussi servir de passerelle vers l'informatique, pour des étudiants dont la formation jusqu'à Bac+4 était principalement mathématique. Pour ceux qui ont suivi des filières plus informatiques, il propose un socle méthodologique solide mais demande un certain investissement.

Pour la première partie, le niveau de traitement est intermédiaire entre le livre de R. Sedgewick et Ph. Flajolet (Introduction à l'analyse des algorithmes) et les Chapitres I– V de Analytic Combinatorics (800p.) de Ph. Flajolet et R. Sedgewick disponible en ligne. Pour la seconde partie, les articles de références seront donnés par les enseignants.

• Année 2011-2012
• Année 2012-2013