En 1963, Knuth se demande quel est le coût d'une certaine méthode de mise en mémoire de l'ordinateur,
et s'aperçoit que ce problème apparemment naïf est relié à une jolie fonction
de Ramanujan. Il est tellement emballé par ce lien inattendu entre mathématique et informatique
qu'il décide de consacrer son temps à un domaine qu'il fonde : l'analyse d'algorithmes en moyenne.
Vers -150 av JC, Hipparque étudie la rhétorique
et se livre à de jolis comptages, dont on n'a que la trace indirecte,
mais qui montre que ses mathématiques étaient non triviales.
En 1751, Euler utilise une série génératrice pour compter le nombre de triangulations d'un polygone.
En 1959, Erdős et Rényi introduisent un modèle de graphe aléatoire
et étudient la probabilité que le graphe soit connexe.
En 2008, Flajolet et Sedgewick publient « Analytic Combinatorics », *la* référence du domaine éponyme.
Dans ce cours, nous verrons ce qui relie ces cinq dates, et comment la
« combinatoire analytique »
telle qu'introduite par Euler, Knuth, Flajolet & Sedgewick
permet d'étudier de nombreux problèmes issus des mathématiques
(théorie des nombres, probabibilités, combinatoire),
de l'informatique (analyse d'algorithmes en moyenne, bioinformatique),
et de la physique (transitions de phase).
Cette « déraisonnable efficacité » repose notamment sur le fait que de nombreuses structures discrètes comme
les arbres, les graphes, les cartes, les chemins (marches aléatoires),
les permutations, les mots, les automates, les grammaires, les partitions, les polyominos, les pavages...
sont autant de structures dont on peut donner une définition récursive,
qui se traduit ainsi naturellement en une récurrence si l'on veut suivre
tel ou tel paramètre de la structure.
La récurrence sur les fn (le nombre d'objets de taille n) se traduit à son tour
en une équation fonctionnelle pour la série génératrice associée F(z)= ∑ fn zn.
Nous verrons une méthode permettant d'aboutir très simplement à ces séries génératrices,
qui ont l'avantage de permettre le recours à des méthodes d'analyse complexe
pour établir le comportement asymptotique de ces récurrences
ainsi que leur comportement typique (lois limites,
via des méthodes de points cols, d'analyse de singularités, de transformée de Mellin).
Nous verrons pourquoi et comment des constantes comme π1/2, ζ(3),
ou la constante d'Euler γ apparaissent de façon ubiquitaire, et ce qu'elles signent.
Aucun prérequis ne sera nécessaire.
Ces prédictions fines d'un comportement typique permettent en retour
d'optimiser finement de nombreux algorithmes.
Nous mentionnerons entre autres l'application à la génération aléatoire.
Nous verrons pour finir comment il est possible d'utiliser le calcul formel
pour automatiser une grande partie de ces approches.
Références :
Livres :
[1] Knuth. The Art of Computer Programming.
[2] Flajolet & Sedgewick. Analytic Combinatorics.
Articles :
[3] Banderier & Flajolet : Basic Analytic Combinatorics of Directed Lattice Paths. Theoretical Computer Science Vol. 281. Issue 1-2, pp. 37-80, 2002.
[4] Banderier & Drmota : Formulae and Asymptotics for Coefficients of Algebraic Functions. Combinatorics, Probability and Computing, Volume 24, January 2015, pp 1-53.