Cours MPRI(2) P. Flajolet
MPRI2, Année 2004-2005
Filière Analyse d'algorithmes
(Adresse de cette page: http://algo.inria.fr/flajolet/mpri04.html.)
Il s'agit du cours d'Analyse d'algorithmes dans le cadre du
Master Parisien de
Recherche en Informatique,
2eme année, composante
Algorithmique
Les enseignants
sont, dans l'ordre d'apparition à l'écran:
Correspondant en gros aux mois de OCT04, NOV04, DEC04, JAN05, resp.
Notez que je ne maintiens cette page sur la Toile que pour la partie
du cours que je présente. Cependant, les notes de l'Amphi0
discutent brièvement le plan d'ensemble du cours (environ 16
séances d'environ 3 heures chacune).
Séances par Philippe Flajolet:
- Séance du 30 SEP 2004: Voir texte Amphi0
ci-dessous;
en complement voir: le Chapitre 1 de
Introduction, et/ou les pages 1--11 de Analytic
Combinatorics, cf pointeur ci-dessous.
Mots clefs: complexité et analyse d'algorithmes; analyse en
moyenne; relation avec les dénombrements
combinatoires; asymptotique de base. L'exemple des
triangulations; définition d'une fonction
analytique; notion informelle de singularité
universalité et problèmes d'arbres:
les modèles en racine-carrée et les modèles logarithmiques.
mots, motifs et bioinformatique;
textes, arbres et dictionnaires digitaux, information.
- Séance du 7 OCT 2004: Le début de
Analytic Combinatorics, Chapitre I, pages 15--44 (en version
"light"); cf pointeur ci-dessous.
Mots
clefs: classe combinatoire; isomorphisme combinatoire; fonction
génératrice ordinaire (=OGF); le minidictionnaire avec
Union disjointe, Produit Cartésien et Séquence. Le recouvrement de
l'intervalle par des allumettes 1,2. Les compositions d'entier.
Remarques sur les généralisations. Langages réguliers et
ambiguïté. Un problème de codage (Alice et Bob); l'histoire des lapins
de Fibonacci (1202); analyse asymptotique de coefficients de fonctions
rationnelles simples. L'automate qui traduit les mots contenant
abb; traduction générale. La monnaie en pièces de
1,2,5 centimes (l'ordre ne compte pas = dénumérants ou
partitions d'entiers).
- Séance du 14 OCT
2004: Le début de Analytic Combinatorics,
Chapitre I, pages 45--69 (en version "light"); cf pointeur ci-dessous.
Mots clefs: La notation officielle [z^n] des
coefficients. L'énoncé officiel de l'analyse des poles
de fractions rationnelles (preuve). Retour sur Alice et Bob qui
doivent eviter 00000 et 11111 (codage et borne inf.). Les arbres plans
enracinés: équation fondamentale. Le theoreme de
Lagrange (non démontré). Application aux arbres binaires
(Catalan), arbres généraux, arbres ternaires et
t-aires. La correspondance de rotation
(arbres géneraux <--> binaires).
Bref commentaire sur les langages context-free
("algébriques") et les fonctions algébriques. Le
dictionnaire complet avec ENSemble, MultiENSemble, CYCle:
énoncé et
preuve (exp-log) des cas MENS et ENS. Commentaire: les partitions
d'entier; les arbres non
plans et l'équation fonctionnelle de Cayley.
- Séance du 21 OCT 2004:
Analytic Combinatorics,
Chapitre II, pages 77--109 (en version "light"): initiation aux
structures étiquetées.
Mots clefs:
Le Professeur Sinus ne voit de ses élèves que des têtes rondes
indistinguables; c'est l'univers non étiqueté;
Le Professeur Cosinus distingue les noms de ses élèves: c'est l'univers
étiqueté. Nombre de partitions et compositions, soit
d'entiers soit d'ensembles dont les éléments sont
distingués par des étiquettes. Notion de classe
étiquetée et fonction génératrice exponentielle (EGF).
Premiers exemples de classes étiquetées: les
permutations (ou graphes linéaires), les urnes (graphes
complets ou disconnectés ou graphes linéaires triés),
les cercles (ou cycles). Définir un produit qui convient
aux structures étiquetées: pour deux objets, on répartit
les étiquettes en préservant la structure d'ordre; la
formule binomiale. Pour deux classes (ou plus), le
produit de séries exponentielles. Dérivés: SEQuence à
k composantes et SEQuences tout court. Exemple:
les mots sur deux lettres, aussi où chaque lettre
apparait au moins une fois. Généralisation:
surjections, partitions d'ensembles et nombres de
Stirling (des partitions). Le grand dictionnaire avec
en plus ENSemble et CYCle qui correspondent à exp(.)
et log1/(1-.). Nombres de Bell et nombre de
surjections. Cycles dans les permutations: le nombre
de cycles vaut en moyenne H(n), le nombre harmonique
[calcul sans séries doubles]. Application au nombre de
maxima via la bijection fondamentale de Foata. Les
arbres étiquetés non plans et la formule de Cayley.
Indications très sommaires sur les graphes fonctionnels.
- Séance du 28 OCT 2004: Analytic Combinatorics,
Chapitre III, pages 123--151 (en version "light"): initiation aux
fonctions génératrices bivariées et aux analyses de paramètres
de structures.
Mots clefs: Qu'est-ce qu'une série
génératrice bivariée (BGF)
relative à une classe combinatoire et à un paramètre? Les
versions ordinaire et exponentielle. Exemple de calcul
direct, les mots sur (a,b) et le paramètre nombre de
a. Le théorème "C'est pareil!": Avec de menus
ajustements, les traductions symboliques restent
valables pour le paramètres dits hérités (par cas
sur les unions disjointes, par addition sur les
produits et constructions dérivées). Calcul des
moyennes et des variances. Exemples pour
voir comment ça marche: "marquer"le nombre de
sommants dans une composition d'entiers, de sommants
égaux à 1 ou à 19, etc. Le nombre de cycles dans les
permutations; le nombre de singletons. La formule
nombre moyen de cycles égale H(n) [nombre
harmonique] et l'interprétation du terme
1/m.
Exercice: On observe
deux records consécutifs dans une permutation
réputée tirée au hasard; est-ce normal? Les
inégalités de Markov-Chebyshev. Preuve rapide. Le
nombre moyen de cases remplies à k éléments
dans une allocation aléatoire où l'on jette
n boules dans m cases, avec un
rapport constant m/n=lambda [preuve par
séries génératrices surtout dans le cas des cases
vides]. L'approximation
de Poisson pour la proportion en moyenne de cases remplies à
k éléments. Un exemple d'algorithme probabiliste: le
comptage par "collisions": on a un flux de données
de plusieurs milliards d'éléments (paquets avec
entête expéditeur-destinataire); on doit déterminer
ou estimer le nombre d'eléments différents;
on ne peut pas se permettre un calcul exact, trop couteux.
on garde alors un tableau
de bits qui est le squelette d'une table de hachage
(information vide/occupé); on infère la cardinalité
en inversant la formule qui donne le nombre de
cases vides à n connu.
Informations complémentaires
- Séance du 4 NOV 2004: Communiqué de Michèle Soria.
Contenu du cours:
1- Rappels sur les fonctions analytiques : définitions équivalentes,
propriétés de clôture, fonctions méromorphes, théorème des résidus,
formule de Cauchy des coefficients.
2- Singularités : rayon de convergence, lemme de Pringsheim, ordre de
grandeur exponentiel des coefficients.
Asymptotique des coefficients : fonctions rationnelles et méromorphes
3- Analyse de Singularités
L'échelle des fonctions log-algebriques et l'échelle associée de leurs coeff;
les théorèmes de transferts (j'ai préféré énoncer les
résultats et reporter les demonstrations à la fois prochaine, car ca prend
du temps, meme pour les esquisser).
Exemples simples sur les arbres.
Application : coût moyen de l'algo de dérivation formelle des expressions
formées sur les opérateurs + et exp et la variable x; généralisation aux
dérivation d'ordre supérieur.
- Pas de séance le 11 NOV 2004: pour des raisons
évidentes...
- Séance du 18 NOV 2004: Communiqué de Michèle Soria.
Contenu du cours:
1- Analyse de Singularités : reprise
Estimation du coefficient de z^n dans (1-z)^{-a}, par inversion de Cauchy avec
contour de Hankel. Lemmes de transfert : conditions d'analycité.
Exemples : dérangements, arbres de Cayley, graphes fonctionnels, nombre moyen
de cycles et de points cycliques dans les graphes fonctionnels.
Compléments : singularités multiples, dérivation et intégration.
2- Application aux familles simples d'arbres
Théorème d'inversion analytique des fonctions implicites. Exemple : familles
simples d'arbres, arbres de Cayley
Paramètres sur les famille d'arbres. Série bivariée vs série cumulative.
Calcul de la probabilité limite et de la moyenne pour le degré à la racine.
Calcul de la moyenne pour les paramètres additifs (ex nb de noeuds de degré d,
Longueur de cheminement, coût de la dérivation formelle).
Forme d'un arbre aléatoire.
- Séance du 25 NOV 2004: Cours de Michèle Soria.
Contenu du cours: 1- Le modèle des arbres croissants : tournois, permutations et arbres binaires
de recherches. Statistiques : longueur moyenne de branche gauche et
longueur moyenne de cheminement externe.
Lien entre les ABR et quicksort ; SGB, moyenne et variance du nombre de
comparaisons pour quicksort. Mediane de 3 : moyenne.
2- Graphes fonctionnels et factorisation d'entiers : longueur moyenne
de rho dans les graphes fonctionnels ; algorithme de Floyd pour la detection
de cycle ; algorithme de rho-pollard et analyse de complexité.
3- Distribution limites discrètes, équivalence entre la convergence des
distributions et celle des sgp. Exemples : degré à la racine des Cayley
et des arbres généraux, collisions de hachage primaire.
Distribution limites continues, théorème de continuité des fonctions
caractéristiques. Exemples : nombre de composants dans les compositions
d'entiers et nombre de cycles dans les permutations.
Généralisations aux schémas alg-log et exp-log donnant lieu a des
distribution limites gaussiennes. Exemples : nombre de blocs dans les
sujections et nombre de cycles dans les Graphes fonctionnels.
- Séance du 2 DEC 2004: Exposé de synthèse-Séminaire
de Gilles Schaeffer, LIX.
Un tutorial sur la génération
aléatoire. Combinatoire bijective, méthodes
symboliques et analytiques servent à simuler
efficacement nombre de modèles discrets...
- Séance du 9 DEC 2004: Premier cours de Jean-Marc
Steyaert.
Mots, motifs et bioinformatique I.
1. Comment montrer simplement, en utilisant les OGF et la technologie symbolique
qu'un mot de longueur >=k.2^k contient tous les mots de longueur k
avec probabilité tendant vers 1.
Essentiellement ça revient à constater (pour k=3)
qu'il y a beaucoup plus de mots qui e'vitent 000 et 111 que tous les autres motifs
(par calcul des po^les), puis a` estimer ce nombre de mots a` multiplier la
proba induite par 2^k et a` faire tendre vers 0 pour trouver
le seuil...
2.
Du comptage exact (méthode Guibas-Odlyzko) pour avoir avec le polynôme
d'autocorrélation, une formule jolie pour les mots qui évitent un motif;
ensuite de l'asymptotique mais, comme on est en 1/z, faut regarder
depuis l'infini... [Note de PF: on peut faire aussi bien
en~0.]
- Séance du 16 DEC 2004: Deuxième cours de Jean-Marc
Steyaert.
Mots, motifs et bioinformatique II.
Combinatoire analytique des expressions régulie`res:
-- les automates déterministes ou la non-ambiguïté effective
-- les séries g.o. associées, ou comment compter sur un automate
(on peut aussi probabiliser les transitions, mais c'est seulement suggéré)
-- la résolution effective dans un cas particulier : S*aba$*,
calcul de l'espérance et de la variance dans le cas equidistribué
-- on fait apparaître la loi binomiale d'où la distribution gaussienne
-- esquisse de la situation générale avec développement local.
2005
- Séance du 6 JAN 2005: Troisième cours de Jean-Marc
Steyaert.
Mots, motifs et bioinformatique III.
Distribution du nombre d'apparitions d'un motif avec auto-corrélation
(analyse Régnier-Szpankowski) dans le cas Bernoulli (Markov évoqué
mais pas traité).
-- on reprend le schéma Guibas-Odlyzko, mais en s.g.o. standard
cette fois;
-- on étudie les 3 régimes selon le nombre d'occurrences:
O(1), limite centrale, grandes déviations et comparaison des régimes.
- Séance du 13 JAN 2005: Exposé de synthèse-Séminaire
de Bruno Salvy.
Aperçus sur le calcul formel, la combinatoire
analytique et l'analyse d'algorithmes.
On peut se servir du calcul formel pour déterminer des séries
génératrices de dénombrement, effectuer des calculs
asymptotiques précis, et même aider voire
automatiser certaines tâches de calcul en analyse
d'algorithmes.
Voir par exemple la page web de Bruno Salvy et du Projet
ALGORITHMES de l'INRIA, les Studies in
Automatic Combinatorics, la bibliothèque
Combstruct de Maple.
- Séance du 20 JAN 2005: Pas de cours le
20 JAN 2005. (Cette décision a été prise en raison
des nombreux préavis de grève pour cette journée.)
- Séance du 27 JAN 2005: Cours-Conférence de
Brigitte Vallée.
Documents utiles
- Amphi0:
Texte en PDF
- Analytic Combinatorics: Il
s'agit d'un futur livre de Flajolet et Sedgewick.
Le manuscrit sur le web est de 500 pages mais seulement au plus un
quart sera utile au cours. Il se télécharge
en
http://algo.inria.fr/flajolet/Publications/books.html.
- Introduction à l'analyse des
algorithmes ou sa version anglaise An Introduction
to the Analysis of Algorithms. Par Flajolet et
Sedgewick. Se trouve dans toutes :-) les
bonnes librairies ou blibliothèques.
- Le cours 1998-1999 contient
une présentation informelle d'un
cours de DEA
sur des sujets voisins en HTML.
- Generatingfunctionology by Herbert WILF constitue une bonne introduction
à plusieurs thèmes du cours. Il est disponible gratuitement (chargeable).
Email: Philippe dot Flajolet AT inria dot fr