WikiMPRI

Premier cours : Mercredi 19 septembre 2012, de 16h15 à 19h15 (Chevaleret)

Responsable : Michèle Soria

Partie 1

1. Modèles réguliers : Michèle Soria
2. Familles simples d'arbres : Cyril Nicaud
3. Arbres et Graphes fonctionnels : Brigitte Vallée

Partie 2

1. Automates et analyse d'algorithmes : Frédérique Bassino
2. Modèles d'arbres et analyse d'algorithmes: Nicolas Broutin
3. Graphes aléatoires et analyse d'algorithmes : Vlady Ravelomanana

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. Divers types d’applications sont traitées en seconde partie, particulièrement en liaison avec les structures digitales, l’algorithmique probabiliste, la recherche multidimensionnelle, et la recherche de motifs dans les arbres.

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:
   • Tri rapide (Quicksort); Sélection rapide (Quickfind); Variantes avec médiane; Tris (Bubble-sort, etc); 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. 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).
2. Applications avancées.
   • Lois limites en combinatoire analytique: au delà des moyennes et variances, comment caractériser par l'analyse les lois probabilistes qui décrivent le comportement des principales structures discrètes aléatoires et des principaux algorithmes associés? Contenu: théorème des quasi-puissances, méthodes de moments. Applications aux mots et motifs, aux tris, à la factorisation de polynômes, à la recherche multidimensionnelle (arbres quadrants), à l'algorithmique arithmétique (factorisation de Pollard).
   • Analyse dynamique des algorithmes: il s'agit de considérer un algorithme comme un système dynamique, l'opérateur de transfert jouant alors le rôle de super série génératrice. Unification des principaux modèles de source d'information (sans mémoire ou Bernoulli, Markov, fractions continues, etc) et applications à l'algorithmique du texte et aux statistiques de motifs. Structure d'arbre digital (trie) et applications à la gestion de dictionnaires; applications à la compression (de type Lempel–Ziv); algorithmes arithmético-géométriques fondés sur les fractions continues.
   • Algorithmique aléatoirisée: Cf Randomized algorithms de Motwani & Raghavan. Une direction récente est l'algorithmique de la fouille de données: algorithmes de comptage probabiliste, extraction des mots fréquents, extraction des contenus communs à des corpus distincts. Quelques applications à l'optimisation combinatoire ou aux structures de données (skip lists).
   • Algorithmique et modèles probabilistes de la bio-informatique. Statistique des motifs simples et généralisés: facteurs, sous-séquences, motifs approchés, alignements, etc. Ce qui est visé ici est l'articulation entre les analyses combinatoires et probabilistes d'une part, les problèmes issus de la bio-informatique d'autre part.

Contenu des cours

Examens

• Examen Partiel : Mercredi 5 Décembre 2012, de 16hh15 à 19h15
  Sont autorisés uniquement les documents manuscrits et les documents distribués en cours.
• Examen Final: Mercredi 6 Mars 2013, de 16hh15 à 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.

     
     
     ====  Cours liés  ====

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

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