Arbres, chemins: probabilités et algorithmes
|
|
ACI NIM Arbres, chemins: probabilités et algorithmes |
|
|
Publications
Présentation détaillée Membres de l'ACI |
Rencontres
Rapport final Accueil |
| Description du projet |
1. Objectifs et contexte:
L'analyse de l'aléa discret remonte au 19ème siècle, mais son étude s'est trouvée renouvelée grâce aux progrès récents de la théorie des processus stochastiques et de la combinatoire analytique, aux développements de liens nombreux avec d'autres branches des mathématiques et aux poussées issues des besoins de domaines d'application comme la physique statistique ou l'informatique. Dans notre approche, les progrès s'appuient tout d'abord sur un prétraitement fin des structures combinatoires en jeu, où des liens parfois surprenants sont établis entre structures a priori distinctes: arbres et chemins, chemins et cartes, allocations et chemins, arbres et permutations, mots et arbres, etc. L'approche par méthodes analytiques bénéficie de résultats récents qui permettent désormais de tirer dans de nombreux cas les lois de paramètres complexes des structures discrètes, ce notamment par le recours à l'analyse asymptotique fondée sur la théorie des fonctions de variable complexe (analyse de singularités, méthodes de cols, coalescents ou non, théorie perturbative) appliquée aux fonctions génératrices de dénombrement. L'approche stochastique prend le relai car, lorsqu'elle s'applique, elle donne lieu à des résulats ``fonctionnels limites'', lesquels déterminent simultanément les distributions jointes d'un grand nombre de caractéristiques de ``forme'' des objets aléatoires discrets. En ce cas, l'objet aléatoire discret peut même se renormaliser en un objet continu qui est source d'informations précieuses. Dans un cas très simple, penser au mouvement Brownien, comme renormalisation d'une marche de Bernoulli que les combinatoriciens appellent chemin de Dyck et que les informaticiens voient comme trace d'un parcours d'arbre ou histoire d'évolution d'une structure dynamique. D'autres exemples récents de processus qui sont directement relevants à notre problématique sont les processus de coalescence, le ``serpent Brownien", et le continuum random tree.
Contexte national et international.
Les méthodes combinatoires, analytiques, et stochastiques, loin
d'opérer dans l'isolement, s'enrichissent mutuellement.
Les groupes constitutifs de ce projet occupent une
position toute particulière, de par leur combinaison de compétences
(probabilités à Nancy et Versailles, combinatoire à Bordeaux,
analyse à Rocquencourt). Ils ont d'ailleurs joué un rôle moteur
(avec quelques autres) dans l'émergence d'un pôle d'activité
en France sur ces thèmes
(le groupe Aléa
Parmi les principales personnalités abordant des questions voisines
sous l'angle probabiliste, citons Aldous et Pitman qui sont au
département de statistiques de Berkeley, Luc Devroye probabiliste en
poste au département d'informatique de McGill à Montréal,
ainsi que Marc Yor, Jean-François Le Gall, Jean Bertoin,
Wendelin Werner, et leur école en France.
Sur ce registre, une excellente équipe
européenne, avec
laquelle nous collaborons par ailleurs étroitement,
est celle de Technische Universität Wien, autour de M. Drmota.
Des spécialistes de renom sont W. Szpankowski (Purdue) et
R. Sedgewick (Princeton) avec lesquels nous procédons à des publications
communes et des échanges réguliers.
L'équipe de Bordeaux est membre du Réseaux Européen
Ace
État de l'art.
L'analyse d'algorithmes au sens où nous la pratiquons a
été fondée par Knuth (Stanford) il y a une trentaine d'années.
Le principe qui prévaut (mais qui a tardé à être reconnu par
nombre d'informaticiens) est que les cas typiques ---en moyenne ou en
probabilité--- déterminent bien mieux que les scénarios
pessimistes de pire
cas l'efficacité pratique des algorithmes.
Un renouvellement important provient de l'irruption de
l'algorithmique probabiliste où l'ordinateur ``joue aux dés''
(techniques dites de
randomization à la suite de Rabin et Karp), laquelle ne se
conçoit guère sans des évaluations probabilistes précises.
Les gains algorithmiques, même sur des problèmes ``triviaux''
(trier!) sont substantiels et parfois spectaculaires (tout tri en
Unix, par exemple, parie sur la forme probable des données et en tire
avantage: cf. l'algorithme Quicksort).
Dans le même temps, les critères de sélection des algorithmes
d'utilisation courante s'affinent: on vise désormais à
déterminer les fonctions de coûts non seulement en moyenne, mais
en distribution. En d'autres termes on ne se contente plus d'une
caractéristique simpliste (la moyenne), mais on vise à quantifier
la variabilité et le ``risque'' possible (vis à vis de temps de calcul
excessifs) dans l'utilisation des méthodes de calcul.
Cette problématique interne à l'analyse d'algorithmes est concommittante au mouvement perçu parmi plusieurs écoles en probabilités en direction des problèmes discrets: voir par exemple les communications au dernier congrès international des mathématiciens par N. Alon, Y. Peres, O. Zeitouni, H. Kesten, J. Bertoin, P. Biane, G. Lawler, P. Flajolet. Ce mouvement est au départ largement issu de problèmes posés par la physique statistique et par l'optimisation combinatoire des problèmes ``difficiles'' (NP--complets). Nous considérons que l'informatique ``fondamentale'' est à ajouter à la liste de ces sources. L'originalité de ce projet-ci est justement d'en proposer l'application à des problèmes ``faciles''---au sens de l'algorithmique liée à la classe P des problèmes résolubles en temps polynomial, lesquels sont les plus utilisés dans la pratique informatique quotidienne.
Au sein de la classe P, les équipes composantes ont dans un passé récent obtenu quelques résultats remarqués. Nous avons ainsi été les premiers à montrer l'équivalence asymptotique/probabiliste des deux principales stratégies de parcours d'une grande variété d'arbres (Chassaing, Nancy, et Marckert, Versailles). Nous avons mis mis en évidence la loi qui exprime l'évolution des performances des tables de hachage selon le procédé courant des ''essais linéaires'' (Flajolet et al., Rocquencourt). Nous avons découvert des liens profonds entre cartes aléatoires et ``serpent Brownien'', par une combinaison de méthodes bijectives fines et de théorie des processus stochastiques (Bousquet-Mélou & al, Bordeaux et Chassaing, Nancy) et les résultats correspondants nous informent très utilement sur les parcours de graphes planaires tout en fournissant des méthodes de génération aléatoire très rapides pour des objets, fussent-ils de grande taille. Grâce à une utilisation originale de la théorie des martingales, nous avons obtenu les caractérisations les plus fines connues actuellement du comportement évolutif d'une structure de donnée aussi fondamentale en informatique que l'arbre binaire de recherche (Chauvin et al, Versailles). Dans le cas de la recherche multidimensionnelle, nous avons fourni un modèle analytique complet aux problèmes statiques correspondants (Flajolet & Salvy, Rocquencourt) exprimé en termes de fonctions hypergéométriques généralisées.
2. Description du projet :
I. Méthodologie
L'exemple de l'analyse de la plus longue sous-suite croissante dans une permutation aléatoire (e.g., la longueur moyenne est en $2\sqrt{n}$) montre tout le bénéfice qu'on peut tirer d'une approche multidisciplinaire à l'analyse de l'aléa discret. S'y mêlent de la combinatoire algébrique et énumérative (e.g., determinants de fonctions de Bessel par Gessel en 1985), une analyse variationnelle de la forme des tableaux d'Young (Vershik--Kerov 1977), des approches probabilistes (Frieze, Bollobás, et al.), des liens avec la théorie des matrices aléatoires (GUE, lois de Tracy-Widom), le tout culminant avec le résultat, justement célèbre, de Baik, Deift, et Johansson où sont en jeu systèmes intégrables, fonctions d'Airy et déterminants de Fredholm, ainsi que les fonctions de Painlevé; cf. les revues d'Aldous--Diaconis [Bull. Amer. Math. Soc., 1999] et Deift [Notices Amer. Math. Soc., 2000]. Toutes proportions gardées et sur une échelle de temps bien plus courte, cette démarche nous sert de modèle idéal de ce qui peut être fait.
Notre thèse est qu'un grand nombre de ``petits joyaux'', certes beaucoup plus modestes que l'exemple qui précède, gisent inexplorés dans le champ des arbres, chemins, et algorithmes associés. En voici un exemple détaillé, auquel plusieurs d'entre nous ont contribué et pour lequel beaucoup reste à faire.
Prenons l'aire sous l'excursion brownienne. Un probabiliste l'approche typiquement par les formules de Feynman-Kac, ce qui ramène à une équation différentielle linéaire du second ordre, l'équation d'Airy. Ceci fournit un accès naturel à la loi de l'aire, mais ne fournit ni une loi locale limite (au sens des densités), ni un accès facile aux estimations de grandes déviations. Un combinatoricien préfèrera aborder la question par l'angle des excursions discrètes, de Poisson ou de Bernoulli: en ce cas, les problèmes énumératifs conduisent à des équations aux différences, avec des solutions qui s'expriment en termes de fonctions hypergéométriques basiques (q-exponentielles) et dérivées. Un analyste observera, sur ces solutions, que la double inversion qui est à réaliser nécessite le recours à des intégrales de Cauchy apparemment sujettes à un phénomène de ``cols coalescents'' ---ces derniers conduisent à des fonctions d'Airy, lesquelles apparaissent également dans l'étude de la multiconnectivité des cartes planaires aléatoires. Un spécialiste d'analyse d'algorithmes y reconnaîtra enfin l'existence de correspondances bijectives et algorithmiques avec les parcours de graphes aléatoires, la gestion de tables de hachage, ou encore le coût de traversée des arbres dits simples (analogues combinatoires des arbres de Galton--Watson).
L'exemple qui précède montre à tout le moins que le paramètre de l'aire d'excursion est à l'intersection de plusieurs domaines tout en étant central à plusieurs applications algorithmiques. On en donne par exemple une introduction dans la note de Chassaing--Flajolet [Gazette des Mathématiciens, 2003]. De fait, on le retrouve encore dans la gestion dynamique d'équivalences (algorithmes union--find), dans les problèmes de ``parking'' et d'allocation aléatoire, dans une importante classe de processus de coalescence (en un sens curieusement homonyme de la méthode des cols coalescents déjà évoquée). De nombreux problèmes ouverts sont associés à ces correspondances: par exemple, l'analyse des algorithmes optimisés de gestion d'équivalences nécessite la prise en compte de fonctions de coût non standard; l'extension aux structures ``paginées'' (voir ci-dessous) est entièrement à réaliser. Mathématiques et besoins algorithmiques se rejoignent ici autour d'un objectif commun ---comprendre en profondeur et quantifier précisément l'un des ``processus combinatoires'' de base de l'informatique.
II. Algorithmique
Du point de vue algorithmique, notre travail se situe très largement dans la tradition scientifique des travaux de Knuth en informatique, notamment la synthèse de The Art of Computer Programming, qui comporte trois volumes de 600 pages. Knuth y fonde l'analyse d'algorithmes et en déduit une classification des principaux algorithmes de représentation des données (vol. 1), de génération aléatoire et algorithmique du calcul formel (vol. 2), de tri et de recherche de données simples uni-dimensionnelles (vol. 3). Par rapport à ce référentiel qui repose largement sur les connaissances des années 1970--1980, notre contribution possède les originalités suivantes:
Bien au delà des analyses ``en moyenne'', nous visons des analyses en distribution: lois centrales limites, lois locales limites, taux de grandes déviations. Toutes les fois que cela est possible, nous nous attaquerons aux problèmes de type ``fonctionnel limite'' où le comportement simultané d'un grand nombre de paramètres est quantifié. Nous attaquerons aussi l'aspect ``dynamique'', lequel prend en compte finement l'évolution temporelle d'une structure, comme un arbre de recherche auquel s'adjoignent de nouvelles données, un graphe aléatoire qui se modifie, une structure d'union--find qui évolue. L'avantage est d'accéder à des informations très fines ainsi qu'à des fonctions de coût de forme complexe.
La prise en compte dans la conception algorithmique des questions de hiérarchies de mémoire est relativement récente en conception algorithmique. Un accès à une mémoire comme un disque magnétique externe coûte typiquement 10$^4$ fois plus qu'un accès en mémoire centrale. En revanche, un accès externe apporte gratuitement un paquet de données contiguës sous forme de ``pages''. (Des situations analogues se retrouvent dans les mémoires-cache, et l'exploitation extensive de ces propriétés a par exemple conduit à des gains de deux ordres de grandeur dans des mailleurs 3D.) Ces questions de pagination sont peu abordées jusqu'ici sous l'angle de l'analyse d'algorithmes. Nous nous proposons d'étudier les méthodes d'accès direct par hachage, notamment la résolution des collisions par essais linéaires, dans le contexte paginé. Des questions analogues se posent d'ailleurs dans la recherche multidimensionnelle (voir ci-dessous).
L'ouvrage de Knuth traite quasi-exclusivement des méthodes de recherche pour des données simples, c'est-à-dire uni-dimensionnelles; en d'autres termes l'espace sous-jacent est totalement ordonné. Les problèmes de recherche multidimensionnelle (domaines produits) sont l'objet d'une algorithmique foisonnante (arbres k--d, arbres quadrants, arbres digitaux) largement fondée sur des décompositions hiérarchiques et adaptatives des ensembles de données [cf. l'ouvrage de H. Samet, Spatial Data Structures, 1990.]. La classification et l'optimisation de ces structures au niveau ``fondamental'' où nous l'entendons est un domaine qui est encore très largement ouvert. Il en va de même pour la pagination de ces structures. Ce domaine est celui des structures de données ``génériques'' pour la représentation spatiale de nuages de points, et est motivé par divers problèmes de bases de données, systèmes d'informations géographiques, ou gestion de scènes complexes en synthèse d'images.
L'algorithmique probabiliste prend son essort dans la décennie 1980--1990. Ici, il s'agit soit de parier sur la forme probable des données, soit même d'introduire volontairement l'aléa dans le calcul (randomization). L'analyse joue alors un rôle déterminant dans la conception même des algorithmes. Un de nos objectifs est de concevoir des algorithmes de comptage probabiliste permettant l'estimation de cardinalité dans des flots de données soit de grande taille, soit à très haut débit. Les applications se situent en ``fouille de données'' (data mining) et en analyse de trafic dans les routeurs, notamment. De manière peut-être surprenante, la conception utilise des ``observables'' probabilistes, obtenus par hachage des données, et dont la quantification met en jeu plusieurs des thématiques du projet (arbres digitaux, modèles d'urnes, allocations aléatoires, méthodes analytiques, dépoissonisation, transformation de Mellin). Nous espérons par exemple estimer des cardinalités jusqu'au milliard avec une mémoire auxilaire d'un kilo-octets (env. 15 lignes de texte imprimé!) en une passe très rapide, tout en visant une erreur de seulement quelques pourcents, ce avec la garantie d'une très forte probabilité de succès.
La génération aléatoire d'objets structurés complexes a connu tout récemment sous l'impulsion de plusieurs membres du projet des développements importants. Il s'avère possible de détourner les modèles de Boltzmann-Gibbs familiers des probabilistes (et notamment appliqués aux structures combinatoires aléatoires par Vershik et al.) afin de réaliser des tirages en temps linéaire ou quasi-linéaire. Ce domaine bénéficie lui aussi de la synthèse entre approches combinatoires bijectives, analytiques, et probabilistes.
III. Mathématiques
La partie mathématique de notre programme de recherche se décline en quatre grands chapitres, que nous présentons ci-dessous. Ceux-ci sont largement motivés par la section algorithmique qui précède. Loin de nous limiter à des développements d'outils, nous avons comme ambition, à l'occasion de ce projet, d'élaborer des mathématiques à la fois consistantes et originales.
III.a. Combinatoire énumérative et équations fonctionnelles. Par opposition au dénombrement asymptotique, le but de la combinatoire énumérative est de dénombrer exactement les objets discrets auxquels on s'intéresse. La première étape d'un tel travail consiste à comprendre la structure fine des objets considérés, soit en parvenant directement à les décrire de façon récursive, soit en établissant un codage non trivial par d'autres objets, à la structure plus limpide. Dans un deuxième temps, cette structure élucidée doit se traduire (idéalement) en une formule donnant le nombre d'objets de taille n, mais le plus souvent en une récurrence reliant ces nombres. Très souvent enfin, cette récurrence est codée par une équation fonctionnelle satisfaite par la série de dénombrement (ou série génératrice) des objets.
L'utilisation de ces séries présente de nombreux intérêts, bien au delà du simple codage : elle permet d'utiliser le vocabulaire des fonctions spéciales pour classifier les problèmes de dénombrement (séries algébriques, D-finies...) à tel point que, dans certains cas, une information sur la nature de la série suggère aussitôt une idée sur la structure des objets qu'elle compte. De plus, ces séries, vues comme fonctions d'une ou plusieurs variables complexes, donnent le bon point de vue pour accéder ensuite à des informations de nature asymptotique, par le biais de l'analyse de singularités. Ce point est détaillé dans le paragraphe suivant.
On peut donc considérer les équations fonctionnelles satisfaites par les séries de dénombrement comme le reflet de la structure des objets étudiés. On constate d'ailleurs souvent que des objets a priori fort éloignés obéissent à des équations voisines. Il devient alors naturel d'étudier, plutôt que des classes d'objets, des classes d'équations. Nous souhaitons nous concentrer sur une famille d'équations récemment apparues dans des problèmes de comptage variés (détaillés ci-dessous), que l'on appelle ``équations à deux variables catalytiques''. Elles régissent des séries de dénombrement selon plusieurs paramètres, et donc font intervenir plusieurs variables, dont deux -- dites catalytiques -- font l'objet de substitutions par des constantes dans l'équation fonctionnelle. Signalons que le cas d'une variable catalytique a fait l'objet de travaux récents de membres de ce projet [Banderier et al.] et qu'il est maintenant établi que leurs solutions sont en fait toujours algébriques.
Nous nous proposons, plus précisément, de développer les points suivants :
Marches dans un quart de plan : les marches (ou chemins) en dimension 1, contraintes à rester positives, sont connues, selon les auteurs, sous le nom de chemins de Dyck, ou excursions browniennes discrètes. Elles ont fait, et font encore, l'objet de nombreux travaux. Elles représentent l'évolution d'une pile ou d'une file d'attente. Les chemins 2D contraints à rester dans le quart de plan positif constituent leur analogue 2-dimensionnel. Ils décrivent l'évolution simultanée de deux piles, ou de files d'attente à deux serveurs. L'énumération des trajectoires de ces marches mène directement à des équations linéaires à deux variables catalytiques. L'étude de quelques exemples révèle que les solutions de ces équations sont beaucoup plus riches que dans le cas d'une variable catalytique : on trouve des solutions algébriques, holonomes transcendantes, et non holonomes [Bousquet-Mélou 02] (on appelle fonction holonome, ou encore fonction $\partial$--finie, une solution d'équation différentielle à coefficients fractions rationnelles). Notre premier objectif est la classification de ces équations selon la nature de leur solution. Dans l'idéal, cette classification pourrait être ensuite ``algorithmisée''. Ces mêmes marches peuvent aussi être considérées comme les trajectoires d'une chaîne de Markov ; le calcul de la loi de la chaîne équivaut alors à la solution d'une telle équation. Le cas limite (calcul de la distribution stationnaire) a récemment fait l'objet d'un livre [Fayolle et al.], basé sur de l'analyse complexe sophistiquée, et montre que les fonctions elliptiques jouent un rôle capital dans ce problème. Il semblerait, au moins sur certains exemples, que notre nouvelle approche permette des solutions plus élémentaires et effectives. Enfin, nous envisageons de raffiner l'énumération en prenant en compte d'autres paramètres (position du point d'arrivée, passages en l'origine...) et de dégager des lois limites.
D'autres objets combinatoires simples obéissent également à des équations linéaires à deux variables catalytiques, et notamment certaines classes de permutations : par exemples celles dont la plus longue sous-suite croissante est bornée, déjà évoquées plus haut, ou d'autres liées à des procédures de tri. Ces objets fournissent autant d'exemples nous permettant de tester et d'affuter nos techniques, et d'améliorer notre compréhension de ces équations.
Les objets simples qui nous intéressent fournissent également des specimens d'équations polynomiales à deux variables catalytiques. Par exemple, une codage récent des cartes planaires (graphes plongés) les transforme en un ``serpent Brownien'' positif discret. L'énumération des trajectoires de ce serpent est régie par une telle équation. À une (très remarquable) exception près, ce type d'équation n'a jamais été attaquée de front. L'exception concerne une équation de cartes résolue après 10 ans d'efforts, et autant de papiers, par Tutte, qui parvient à une solution différentiellement algébrique. Pour d'autres exemples, on sait par un autre biais que la solution est tout simplement algébrique. L'étude et la classification de ces équations polynomiales est une généralisation naturelle -- et nécessaire -- de nos travaux sur les équations linéaires.
Enfin, il convient d'envisager des q-analogues de ces équations. Ces extensions permettent de prendre en compte des paramètres similaires à l'aire sous l'excursion brownienne déjà mentionnée. Ce cas, uni-dimensionnel, et quelques unes de ses variantes, sont régis par des q-analogues d'équations algébriques {[Bousquet-Mélou 96]}, et mènent à des q-analogues d'exponentielles, de fonctions de Bessel, ou plus généralement de séries hypergéometriques. Le cas des marches 2-dimensionnelles reste à traiter. Enfin, dans le cas du serpent Brownien, un q-analogue permettrait de prendre en compte les hauteurs cumulées de la position du serpent, et d'accéder ainsi aux moments de ce processus.
III.b. Combinatoire analytique. On entend par combinatoire analytique tout un ensemble de méthodes qui partent d'une description exacte (sans perte d'information) d'un modèle combinatoire par séries génératrices (voir ci-dessus) et en extraient les informations asymptotiques pertinentes ---dénombrements, lois limites, ou grandes déviations. Le principe de base consiste à traiter ces séries génératrices de dénombrement comme transformations analytiques du plan, puis à exploiter la nature des singularités et leurs déformations (dans le cas multivarié). Cette démarche s'applique à la plupart des modèles ``exactement résolubles'', mais aussi à nombre de fonctions qui ne sont qu'implicitement accessibles via des équations fonctionnelles. Dans le cas des arbres, chemins, cartes, graphes, ou permutations, une grande variété de telles équations (généralement non-linéaires) se manifeste: purement différentielles, aux différences, ou encore mixtes aux dérivées et aux différences partielles, notamment. Comme on l'a vu au paragraphe III.a., la structure de ces équations fonctionnelles reflète directement la structure combinatoire du problème d'origine. Les méthodes d'analyse de singularité et de perturbation singulière donnent des estimations asymptotiques très précises (vitesse de convergence au régime asymptotique, corrections d'ordre supérieur à 1, etc). Dans le cadre de notre démarche, celles-ci fournissent plus que les méthodes stochastiques en termes de précision des estimées, mais moins en terme de richesse ou de finesse de description. Par exemple, un problème aussi simple à formuler que celui de la largeur d'un arbre aléatoire [Chassaing-Marckert] résiste à de telles approches, tandis que l'analyse fournit des lois locales limites pour la hauteur des arbres de Galton-Watson qui semblent bien peu accessibles aux méthodes stochastiques [Flajolet--Odlyzko]. Globalement, les deux approches, analytique et stochastique, se complètent donc, et les méthodes analytiques dont il est question ici peuvent fournir des convergences de moments (d'où un accès non constructif aux lois limites), ainsi que des estimations fini-dimensionnelles susceptibles de servir de tremplin aux critères de convergence de processus et à la caractérisation des taux de grandes déviations.
Les axes que nous proposons de développer ici sont les suivants:
L'analyse en les singularités des équations fonctionnelles de la partie III.a. liées aux chemins et aux cartes. Par exemple, un certain nombre de problèmes conduisent à des q-analogues qui sont des q-exponentielles, q--Bessel, etc [Bousquet-Mélou]; à la limite $q\to1$, ces équations livrent des solutions de problèmes énumératifs dont certains, curieusement, sont des fonctions algébriques, d'autres des fonctions holonomes. On aimerait classifier, au plan singulier notamment, les méthodes de résolution issues de la partie III.a. et disposer d'outils permettant d'en déduire les lois de probabilité associées. Un cas typique est la double inversion (déjà évoquée) liée à l'aire sous les excursions discrètes, laquelle est gravide d'informations probabilistes sur l'excursion Brownienne.
Le développement de méthodes systématiques d'analyse des coefficients de fonctions algébriques ou holonomes. De telles fonctions spéciales se rencontrent en liaison avec les modèles combinatoires d'arbres, cartes et chemins (cas algébrique) et dans de nombreux cas d'arbres multi-dimen\-sionnels (cas holonome ou $\partial$-fini). De même, une classification en termes analytiques des principaux schémas algorithmiques dits ``diviser-pour-régner'' fait encore défaut: de tels schémas sont eux-aussi étroitement liés aux modèles d'arbres aléatoires. Les problèmes à surmonter concernent la gestion des opérateurs intégro-différentiels associés, des produits de Hadamard (produits terme-à-terme de séries), et des relations de ``connection'' (reliant les conditions initiales aux constantes des développements singuliers).
En liaison avec ce qui précède, le développement de méthodes de traitement de l'asymptotique des coefficients de fonctions génératrices qui soient dotées d'un certain degré d'universalité. On pense ici en particulier aux lois qui mettent en jeu la fonction d'Airy, lesquelles se rencontrent dans le noyau des cartes, la connexité des graphes aléatoires, certains modèles d'urnes, l'aire des excursions, la longueur de cheminement des arbres, les tables de hachage, etc. Ces questions sont d'un abord difficile, mais celles qui sont visées mettent en jeu d'une façon ou d'une autre une confluence de singularités et/ou la coalescence de points critiques (cols). Un important travail de développement technique et de classification est à effectuer. Une direction de recherche voisine est l'exploration des cas limites à l'analyse de singularité classique liés à l'existence de frontières naturelles.
La quête de lois stables dans les structures aléatoires discrètes. Ceci sort du cadre Gaussien qui est le plus fréquent et est associé à une perturbation agréable de régime singulier (déplacement lisse de la singularité ou changement analytique des exposants singuliers, notamment). Au delà du cas des noyau de cartes planaires, certaines de nos études préliminaires suggèrent la présence de telles lois (et de lois dérivées nouvelles) dans divers modèles d'urnes -- par exemple, certains de ceux-ci mettent curieusement en jeu des fonctions elliptiques (sous la forme de Weierstrass).
III.c. Arbres aléatoires
Cet intitulé signifie que les structures de données arborescentes, évidemment omniprésentes en algorithmique, sont vues mathématiquement comme des éléments (appelés arbres) d'un espace de probabilité correctement muni de tribu, filtration et mesure de probabilité. Les quantités qui intéressent les informaticiens (fonctions de coût, risques) deviennent des variables aléatoires, mieux des processus aléatoires, dont on ne va pas seulement étudier le comportement moyen mais aussi le comportement trajectoriel ou les grandes déviations. Les processus de branchement, des plus simples (Galton-Watson) aux plus élaborés (processus spatiaux, versions continues comme les branchements-diffusions) jouent ainsi un rôle fondamental dans cette approche. Cette démarche conduit, on le voit bien sur l'exemple des arbres binaires de recherche, à des raisonnements "dynamiques" sur l'évolution de la suite d'arbres, plutôt qu'à des raisonnements du type ``diviser pour régner'' et sont très complémentaires. Ces derniers, grâce à des méthodes analytiques (voir III.b.) fournissent des résultats très précis sur l'asymptotique des coefficients de fonctions génératrices, tandis que le travail sur le processus discret associé à l'arbre produira, par exemple par des méthodes de martingales, des résultats sur le profil de l'arbre, difficilement accessibles autrement.
Les axes que nous nous proposons de développer sont les suivants, ils rejoignent l'objectif général d'élaboration d'une théorie de ``processus combinatoires'' par complémentarité des méthodes favorites des membres de l'équipe, analytiques, combinatoires et probabilistes.
L'étude de ``schémas de Pólya'' qui sont dans notre terminologie une hyper généralisation des urnes de Pólya. Nous aurons en base d'approche deux cas particuliers déjà élaborés que sont d'une part les arbres m-aires de recherche, pour lesquels restent quelques points non élucidés : profil, lois limites fines, sens physique de la transition de phase ; d'autre part les urnes de Pólya-Eggenberger à deux couleurs équilibrées, qui font intervenir des fonctions elliptiques. Avec le point de vue des marches aléatoires multidimensionnelles non homogènes, nous souhaitons mettre en évidence non seulement un comportement asymptotique moyen mais des lois limites trajectorielles, qui ne seront pas toujours gaussiennes (lois stables entre autres), et qu'il s'agira de classifier. Des transitions de phase apparaîtront, que nous souhaitons prédire. Tout ceci sera possible par combinaison de caractérisations de type analytique (fonctions elliptiques), algébrique (décomposition d'opérateurs de transition) et probabiliste (changements de probabilité, plongements).
L'application de raisonnements dynamiques à d'autres structures de données que les arbres de recherche est un travail de longue haleine, les objectifs immédiats sont les structures multidimensionnelles qui sont encore largement en friche, en particulier les arbres quadrants dont l'évolution présente des caractéristiques géométriques et probabilistes encourageantes. Les diagrammes de décision binaires ou les listes probabilistes devraient être également accessibles, en tant que processus, à des méthodes de martingales ou de polynôme de niveaux .
Les relations entre les processus de branchement continus ou discrets, les arbres binaires de recherche et les diverses martingales attachées ne sont pas complétement élucidées. Elles peuvent être vues au travers de deux prismes :
la combinatoire stochastique telle qu'elle apparaît dans le cours de Pitman à Saint-Flour,
les méthodes (dites conceptuelles ou de Lyons Pemantle Peres) utilisant les changement de probabilités.
Dans les arbres de union--find étudiés récemment à Nancy, il existe une bijection (de Devroye) avec la hauteur `` à gauche'' des arbres binaires de recherche. Du coup, les méthodes décrites plus haut (raisonnement dynamique, martingale additive, martingale dérivée, profil ou grandes déviations) pourraient enrichir l'étude des arbres de union--find.
La représentation des formules booléennes par les arbres et/ou : les travaux récents sur la complexité des fonctions booléennes, en relation avec leur probabilité d'apparition, font apparaître plusieurs lois de probabilité possibles sur ces fonctions, lois qu'on ne sait pas encore comparer ; on se propose aussi de prendre en compte la commutativité et l'associativité des opérateurs booléens dans la représentation des fonctions booléennes par un arbre aléatoire.
III.d. Modèles probabilistes continus.
L'étude de la convergence des chemins aléatoires (renormalisés) vers des processus stochastiques liés au mouvement Brownien a une longue histoire. Ce type de convergence "fonctionnelle" reste très éclairante en combinatoire [Bousquet-Mélou--Schaeffer 02], et en analyse d'algorithmes [Chassaing, Marckert & Yor, 03]. Une idée naturelle est d'étendre cette démarche à d'autres objets aléatoires discrets, comme les arbres, les cartes planaires, et les marches branchantes. Ainsi apparaissent, en passant à la limite, des modèles probabilistes continus (des ``processus combinatoires") comme le continuum random tree, le serpent Brownien et les processus de coalescence. Par comparaison avec le mouvement Brownien, ces objets limites sont moins explorés, leurs propriétés moins bien connues. Parfois, comme dans le cas des cartes planaires, l'objet limite n'est pas complètement défini. Il y a là un champ d'exploration où les diverses compétences de notre groupe peuvent s'employer:
Le continuum random tree, introduit par Aldous en 1990, est un espace topologique aléatoire, muni d'une distance aléatoire, qui apparaît comme objet limite, quand n tend vers l'infini, d'une suite d'arbres aléatoires de taille n tirés au hasard dans une vaste famille d'arbres: les arbres dits simples. Pour observer cette convergence, comme dans le cas des chemins, il faut appliquer une renormalisation (ici un arbre aléatoire de taille n aura des arêtes de longueur $1/\sqrt n$). L'avantage conceptuel du résultat d'Aldous est d'offrir une explication (et une démonstration) globale pour l'ensemble des asymptotiques des statistiques fondamentales des arbres simples (hauteur, cheminement total ...) souvent obtenus en premier lieu par des méthodes de combinatoire analytique. Les résultats de combinatoire analytique ont donc une fois de plus servi d'éclaireurs. La combinaison des deux approches permet maintenant d'obtenir, simultanément, des résultats nouveaux sur l'excursion Brownienne, et la loi limite de l'indice de Wiener des arbres simples [Janson, 2003]. C'est ce genre de coopération féconde que notre offre entend favoriser.
Partant des travaux d'Aldous, des membres de notre groupe ont pu augmenter la complexité d'un cran et aborder l'étude des marches branchantes: une marche branchante encode non seulement la généalogie d'une population de taille n, à un seul ancêtre, (comme le fait déjà un arbre simple), mais aussi la position des individus de cette population dans l'espace. Typiquement, on suppose que chaque individu fait un pas au hasard à partir de la position de son père. Cela induit une distribution aléatoire de masse dans l'espace. Comme cela a été démontré récemment par des membres de ce projet, les deux structures aléatoires (marches branchantes et distributions aléatoires de masse) satisfont à des théorèmes fonctionnels, les objets limites étant le serpent Brownien (introduit par Le Gall), et l'ISE [Aldous, 1993]. Les motivations pour étudier le serpent Brownien sont nombreuses (cf. Slade, Notices of the AMS, 2002, vol. 49, n. 9). Entre autres :
il apparaît comme objet limite des lattices trees (arbres dessinés dans $\mathbb Z^d$, qui sont une modélisation des polymères branchants) pour $d\ge 8$;
la distribution aléatoire de masse induite par le serpent Brownien (ISE) semble être un bon modèle pour la distribution de la masse d'un grand cluster en percolation critique;
en géométrie quantique, les cartes planaires aléatoires fournissent un modèle de géométrie aléatoire. Or une correspondance bijective a été récemment établie par Gilles Schaeffer entre marches branchantes et cartes planaires, avec pour conséquence la convergence de certaines statistiques des cartes planaires (rayon, profil) vers les statistiques correspondantes du serpent Brownien.
Cependant les lois des statistiques de bases du serpent Brownien sont encore mal connues: c'est un autre champ d'investigation où la coopération entre méthodes stochastiques et analytiques a commencé, et s'annonce prometteuse (voir III.a.). Un autre de nos objectifs est l'élaboration d'un modèle de "continuum random planar map", défini à partir du serpent Brownien, avec des applications attendues à l'analyse des algorithmes (génération rapide de cartes planaires) et à la géométrie quantique.
L'étude des liens entre structures combinatoires (tables de hachage, arbres aléatoires, graphes aléatoires) apparaissant en algorithmique, et d'autre part les phénomènes de coalescence-fragmentation, liés ou non au mouvement Brownien soulève des problèmes nouveaux. Par exemple, dans l'étude de la gestion d'équivalences (algorithmes union--find), une masse de données est fragmentée en sous-ensembles qui se scindent et s'agglomèrent au hasard. On doit alors mener à bien l'étude fine de l'évolution dans le temps (la dynamique) des volumes des fragments. Cet aspect dynamique et la complexité de l'espace d'états (la suite des masses des fragments au temps t peut être vue, après renormalisation, comme une mesure de probabilités sur $\mathbb N$) sont sources de difficultés, simplement pour exprimer la loi du processus limite, et a fortiori pour mener des calculs exacts sur l'objet limite, ou pour établir la convergence d'un modèle discret combinatoire vers l'objet limite continu. Les modèles dont l'étude paraît la plus urgente sont issus de la fragmentation d'arbres (coalescent additif à la Aldous & Pitman) et plus encore du graphe aléatoire à la Erdös-Renyi (coalescent multiplicatif) : le cas additif a été traité par des membres du projet, mais leur méthode ne s'étend pas directement à des cas plus généraux, ni même au cas multiplicatif. L'étude des processus de coalescence-fragmentation connaissent des avancées théoriques significatives ces derniers temps sous l'impulsion d'Aldous, Pitman, Bertoin, Norris, et bien d'autres. Ces avancées n'ont pas encore été transposées à l'analyse d'algorithmes, hormis dans des travaux récents [Chassaing-Louchard] sur le hachage. Il semble que ce soit juste le bon moment et la bonne configuration de compétences pour passer à cette nouvelle phase.
IV. Fonctionnement.
Notre demande correspond à un soutien de fonctionnement aux équipes composantes. Sont prévus les missions de présentation des résultats du Projet ACPA aux conférences nationales ou internationales, les réunions de groupes de travail (Arbres et Algorithmes sous la direction de Versailles, séminaire Algorithmes de Rocquencourt), ainsi que les échanges de doctorants et l'invitation de spécialistes étrangers que nous prévoyons de partager largement. Pour rester focalisé, le Projet a été élaboré par un noyau de relativement petite taille, mais il s'insère dans le cadre de groupes plus larges, notamment le groupe national ALÉA (70 membres) et nous nous proposons de réserver environ 20% de notre financement à l'animation de cette communauté. Nous espérons de la sorte à la fois aider la communauté et profiter d'un effet d'amplification de notre effort de recherche sur les thèmes proposés.
Les membres du Projet ACPA ont aussi une politique volontariste dans le domaine de la formation interdisciplinaire Math-Info: ceci est matérialisé par le montage complet d'un DEA Math-Info à Versailles, un rôle moteur dans la filière ``Analyse d'algorithmes'' du DEA parisien ``Algorithmique'', dans la filière Math-Info du DEA de Bordeaux, et dans le DEA de Mathématiques appliquées de Nancy. C'est pour ces raisons que nous effectuons des demandes d'allocation de thèse. Plus généralement, notre sentiment est d'opérer dans un domaine jeune, en croissance sensible, dans un environnement pluridisciplinaire motivant, et il nous semble important que ceci soit reflété par l'attribution d'allocations de thèse et de bourses postdoctorales.
Résultats attendus :
Les résultats attendus ont été évoqués dans la description du projet, où sont apparus en détail les développements mathématiques envisagés. D'un point de vue plus ``macroscopique'', nous souhaitons par la réalisation de ce vaste programme
Organiser, structurer, et unifier les méthodes de quantification des principaux paramètres ou fonctions de coût algorithmique des arbres et chemins: dénombrements exacts, classes d'équations fonctionnelles et fonctions spéciales associées, lois limites locales, grandes déviations, théorèmes fonctionnels limites.
Développer un ensemble cohérent de méthodes pour attaquer l'analyse des problèmes de pagination en algorithmique des arbres, chemins, et stuctures associées. Développer les modèles d'urnes correspondants.
Réaliser l'analyse et l'optimisation des structures arborescentes adaptées au traitement de données multidimensionnelles (arbres quadrants, arbres digitaux, par exemple) par la combinaison de méthodes de martingales et de techniques d'équations différentielles dans le champ complexe.