Cyril Banderier (CNRS et LIPN)

En 1963, D.E. Knuth commence à analyser une méthode de hachage dite à essais linaires et s’aperçoit que son efficacité est reliée à une célèbre fonction de la théorie des nombres, la fonction Q de Ramanujan (oui, le jeune génie indien mort prématurément).

Enthousiasmé par un tel pont entre des disciplines jusqu’alors fort distantes, Knuth commence à défricher un champ jusqu’alors peu étudié : l’analyse d’algorithmes, un domaine qu’il crée littéralement, et le volume 1 de “The Art of Computer Programming” paraît 5 ans après.

Cette bible de 4 volumes (voir google search “Don” pour le quatrième) prêche la bonne parole suivante : afin de faire un programme efficace, il est souvent utile de comprendre quelles en sont les structures combinatoires sous- jacentes, et pour en étudier les propriétés “typiques” de celles-ci, rien de tel que de bonnes vieilles mathématiques.

En fait, que ce soit pour des algorithmes de tris, de stockage, de multiplications, de génération aléatoire, de compilation… le comportement (au pire ou en moyenne) s’avère souvent être accessible par des outils mélangeant théorie des nombres et analyse complexe.

Cela remet à l’honneur des travaux qui remontent à Euler, et notamment les “séries génératrices” que ce dernier a introduites en 1753 pour énumérer les triangulations d’un polygone !

Compter (de façon exacte ou de façon asympotique) le nombre de structures combinatoires (e.g. arbres, graphes, permutations, partitions, mots…) vérifiant une propriété donnée est l’essence même de la “combinatoire analytique”, terminologie rendue célèbre par l’école de Philippe Flajolet.

Je donnerai quelques exemples de problèmes triviaux (une fois que l’on connait les méthodes !) ou ouverts.

Pour finir, il est remarquable que, grâce à des progrès en calcul formel et des théorèmes “rouleaux-compresseurs” en asymptotique, de nombreux algorithmes peuvent de nos jours être analysés automatiquement, mettant ainsi informaticiens & mathématiciens au chômage ?

J’espère donc vous faire partager la beauté de ces allers-retours entre mathématique et informatique et vous donner une idée de ce que permet la “combinatoire analytique”.

Public : L’exposé ne nécessite aucune connaissance autre que celles d’un élève de terminale scientifique.
Allez me chercher un élève de terminale !