Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

Analyse d'algorithmes (48h, 6 ECTS)

Premier cours : Jeudi 17 septembre 2009, de 16h15 à 19h15 (Chevaleret 1C18)

Responsables : Philippe Flajolet et Michèle Soria

Plan du cours et intervenants prévus pour 2009-2010

Partie 1

1. Langages réguliers et fonctions génératrices: Ph. Flajolet
2. Arbres et Graphes fonctionnels : M. Soria et B. Vallée

1. Recherche digitale et analyse d'algorithmes : B. Vallée et Ph. Flajolet
2. Modèles d'arbres et analyse d'algorithmes: N. Broutin et JM. Steyaert

voir plan détaillé ci-dessous.

Objectifs

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.

Contenu

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.

Planning Prévisionnel

• 17/09/09 Introduction : Combinatoire et Analyse d'algorithmes
• 24/09/09 Classes combinatoires, méthode symbolique ; Langages reguliers, asymptotique des fractions rationnelles
• 01/10/09 Paramètres, fonctions génératrices multivariées et langages
• 08/10/09 Classes d'arbres : dénombrement et paramètres - propriétés universelles
• 15/10/09 Analyse de Singularités et applications
• 22/10/09 Constructions combinatoires sur les classes étiquetées,
• 29/10/09 Pas de cours
• 05/11/09 Paramètres de permutations et de graphes fonctionnels
• 12/11/09 Combinatoire Analytique : synthèse et exercices
• 19/11/09 Partiel
• 26/11/09 Algorithmes sur les mots : tries
• 3/12/09 Analyse de Quicksort et Quickselect : tries
• 10/12/09 Analyse de tries
• 17/12/09 Thématiques de la combinatoire analytique
• 7/01/10 Analyse de structures de données géométriques : BST
• 14/01/10 Analyse de structures de données géométriques : k-d, quad trees
• 21/01/10 Analyse d'algorithmes de réécriture et compactification
• 28/01/10 Analyse d'algorithmes d'unification
• 11/02/10 Examen

Langue du cours

Supports de cours

Nouveau décembre 2009 : support de cours sur les tries

Annales

• Enoncé du partiel de novembre 2005 : mpri-partiel05.pdf

• Corrigé du partiel de novembre 2005 : mpri-partiel05cor.pdf

• Devoir sur la dérivation formelle, extrait du partiel de novembre 2006 : partiel06DerivForm.pdf

• Enoncé du partiel de novembre 2008 : partiel2008.pdf

Cours liés

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

Pré-requis

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.

Bibliographie

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.

Les années précédentes

• Année 2008-2009
• Année 2007-2008
• Année 2006-2007

Équipe pédagogique