Séance du 27 OCT 2005:
Analytic Combinatorics, Chapitre III, (en version
"ultralight").
Mots clefs:
Paramètres, probabilités, et fonctions géne'ratrices bivariées (BGF).
- Section 1: Suites à deux indices, dénombrements liés à un
paramètre sur une classe combinatoire. Notion de BGF (bivariate
generating function) de type ordinaire ou exponentiel. La suite
illustrera: A) Comment on calcule avec; B) Ce qu'on en tire (par ex.,
moyennes, variances); C) Comment on les obtient, ces BGF. Exemple 1:
calcul de la BGF des coefficients binomiaux, on trouve 1/(1-z-zu).
Exemple 2: idem pour le nombre de cycles dans les permutations
(nombres de Stirling des cycles), on trouve (1-z)^{-u}.
- Section 2: Parametres et lois. Rappels sur fonction generatrice
de probabilités (Probability Generating Function, PGF) et le calcul des
moyennes et variance. Proposition reliant la PGF d'un paramètre
sur les objets de taille n, sa
moyenne, sa variance a une BGF. Le procédé: dériver, instancier en u=1,
extraire un coeff. Brève notions de concentration de
distribution, alias convergence en probabilité, mais simple mention
des noms de Markov et Chebyshev. Application aux Exemples 1 et 2 ci-dessus.
- Section 3: La méthode symbolique pour les BGF. Ce qu'est un
paramètre hérité ou additif. Le cas particulier des marques. On joue
d'abord à quelques exercices de programmation pour marquer: les
"b"dans les mots binaires, les cycles dans les permutations, les
sommants dans les compositions d'entiers (idem avec les sommants égaux
à 3), les feuilles dans un arbre général. Puis on énonce les deux théorèmes du dictionnaire pour l'univers non-étiqueté et l'univers étiqueté.
- Section 4: Applications: On revient sur tous les exemples
précédents et on déduit les BGF correspondantes. Par exemple, le
nombre moyen de cycles d'une permutation vaut Harmonic(n) soit environ
log(n). En général on calcule les moyennes et on énonce les variances
en passant. Fin du cours: très BRÈVES indications sur tout ce qu'on
peut marquer pour faire le lien avec la suite: (a) les occurrences de
motifs dans les mots (plus généralement: les paramètres des langages
réguliers); les polynômes sur un corps fini et les propriétés de la
factorisation.
FIN du cours de P. Flajolet
- Séance du 3 NOV 2005:
Cours de remplacement par Philippe Flajolet.
Voici
un résumé télégraphique de ce cours.
-
Asymptotique des coefficients des fonctions génératrices.
Il s'agit d'un aperçu.
(1) Rayon de convergence, taux exponentiel, facteurs subexponentiels.
(2) Le cas des fractions rationnelles.
(3) L'analyse de singularité (selon l'axe réel:
sans preuve ni conditions analytiques détaillées).
(4) La loi de Gauss et le Théorème Central Limite.
(5) La loi de Gauss en combinatoire (Quasi-puissances, sans preuve).
- Séance du 10 NOV 2005:
PAS DE COURS le 10 NOVEMBRE 2005.
(Cf Message de Brigitte Vallée daté du 7 NOV 2005).
- Séance du 17 NOV 2005: Cours de remplacement par
Philippe Flajolet. Bases de la théorie des fonctions analytiques pour
l'asymptotique en combinatoire. NOTES DE COURS par PF
-
(1) Fonctions analytiques; fonctions différentiables. Le Théorème
d'équivalence fondamentale.
- (2) Intégrales, fonctions
méromorphes, résidus. La propriété d'intégrale nulle le long d'un
chemin fermé. Le théorème des résidus pour les fonctions
méromorphes. La formule des coefficients de Cauchy.
- (3)
Croissance exponentielle des coefficients et singularités des
fonctions. Théorème: il existe toujours une singularité sur le bord du
disque. Donc on sait déterminer le rayon de convergence, d'où le taux
de croissance exponentiel des coefficients, a la simple vue de la
fonction elle-même. Variante de Pringheim pour les fonctiosn à
coefficients positifs.
- (4) Analyse de singularité: D'abord les
coeffs de (1-z)^{-a} par contour de Hankel. Puis transfert
des O() et o() de la fonction aux coefficients.
- Séance du 24 NOV 2005: Cours par Brigitte Vallée.
Analyse d'algorithmes sur les polynômes: pgcd et factorisation.
- Où il apparaît que les méthodes symboliques
en combinatoire servent à obtenir des fonctions géneratrices exprimant
les principaux paramètres de complexité. Puis que l'analyse de
singularité et le théorème des quasi-puissances permettent d'obtenir
des renseignenent très précis, comme: le nombre de tours de
l'algorithme d'Euclide appliqué à une paire de polynômes P,Q de degré
n ou le nombre de facteur d'un polynôme à coefficient sur un
corps fini (les entiers modulo p).
- Séance du 1 DEC 2005: Examen en 3 heures dans la salle habituelle
surveillé par Brigitte Vallée.
You can write your solutions to the problems in English.
Les contenus des cours qui suivent sont donnés à titre indicatif.
Séance du 8 DEC 2005: Cours par
Brigitte Vallée. Analyse d'algorithmes sur
les entiers I: le PGCD et l'algorithme d'Euclide.
Il sera question de systèmes dynamiques (transformations de
l'intervalle, opérateurs de transfert) et de séries génératrices de
Dirichlet (une nouvelle sorte de fonction génératrice). Des méthodes
nouvelles se conjuguent aux méthodes combinatoires traditionnelles
(description de paramètres par séries génératrices, singularités). Ce
domaine appartient a l' algorithmique en théorie des nombres
["computationla number theory"] possède des intersections avec la
cryptographie et le calcul formel (algorithmique des algorithmes
fondamentaux).
Séance du 15 DEC 2005: Cours par
Brigitte Vallée. Analyse d'algorithmes sur
les entiers II: le PGCD et l'algorithme d'Euclide. .
Notions d'analyse en distribution. (Utilisation du Théorème des quasi-puissances.)
Séance du 5 JAN 2006: Cours par Jean-Marc Steyaert.
Apparition de motifs dans les mots aléatoires. Polynôme d'autocorrelations; série génératrice rationnelle.
Indications sur la loi limite du nombre d'occurrences d'un motif: elle est Gaussienne.
Liens avec la bioinformatique. Liens avec les algorithmes de compression du type
Lempel-Ziv (gzip)?
Séance du 12 JAN 2006: Cours par Jean-Marc
Steyaert. Dénombrement des familles simples d'arbres. Fonctions
génératrices de dénombrement (rappel). La singularité est de type
racine carrée. Par analyse de singularité on a une formule
"universelle": C.A^n.n^{-3/2} (comme pour les arbres/nombres
de Catalan). Ces arbres servent dans diverses branches de
l'informatique, par ex., le calcul formel, le calcul symbolique au
sens large (déduction automatique), etc. La dérivation usuelle des
expressions a une complexité moyenne en O(n^{3/2}).
Séance du 19 JAN 2006: Séminaire sur la
Génération Aléatoire de Structures Combinatoires par Gilles
Schaeffer, École polytechnique.
- Cette séance ainsi que la suivante (le 26
JAN) est un "séminaire": c'est-à-dire qu'il s'agit d'une conférence
d'ouverture par rapport aux sujets traités en cours, en direction
d'autres domaines---un moyen agréable de changer un peu l'éclairage et
de réviser, en quelque sorte! :-) Ici, Gilles Schaeffer montrera des
liens entre combinatoire analytique et combinatoire tout court.
L'objectif global est de parvenir à des algorithmes efficaces
permettant de générer des objets de grande taille de manière uniforme
(c'est là la difficulté!). Tout d'abord des bijections dont certaines
ont déjà été vues en octobre 2005 dans le cours d'analyse
d'algorithmes (par exemple entre arbres et chemins de Dyck) peuvent
être exploitées. Ensuite, tout ce qui donne lieu à des équations de
séries génératrices par la méthode symbolique peut se traduire en
algorithme de génération aléatoire: c'est ce qu'on appelle la méthode
récursive. Celle-ci est implantée en Maple et permet habituellement
d'engendrer des structures de taille égale à quelques milliers. Une
méthode plus récente [Duchon, Flajolet, Louchard, Schaeffer] étendue
tout récemment par une doctorante issue du MPRI2 (Carine Pivoteau)
permet enfin l'accès à des structures encore bien plus grandes. Il
s'agit de la méthode de Boltzmann, laquelle repose une nouvelle fois
sur les fonctions génératrices, la méthode sybolique, et même un peu
l'analyse telle que présentee dans les cours précédents.