Projet SADA: présentation détaillée

      retour


Objectifs et contexte :



Ce projet fédérateur, Structures Discrètes Aléatoires et Algorithmes (SADA), propose des objectifs de recherche fondamentale ambitieux. Il s'agit de quantifier les principales propriétés de structures fondamentales qui apparaissent de manière récurrente aux travers d'applications informatiques extrêmement diverses. Les grands chapitres de notre programme de travail sont relatifs aux mots, aux structures arithmétiques, aux arbres, aux graphes, ainsi qu'à la génération aléatoire. Nous visons à développer un corpus cohérent de méthodes permettant de déterminer de manière très précise les ``profils'' des objets aléatoires : bien au delà des propriétés en moyenne, on s'attachera aux analyses en distribution, à la quantification des risques de grandes déviations, ainsi qu'à l'évolution dynamique des structures. Le projet est fondé sur la confrontation de points de vue complémentaires, incluant méthodes combinatoires, probabilistes, analytiques, et dynamiques. Plusieurs de nos approches sont assez fortement mathématisées, tandis que nos objectifs finals sont de nature algorithmique concrète. Trois des équipes composantes sont ainsi issues de laboratoires STIC (Bordeaux, Caen, Polytechnique). Une équipe (Versailles) est située principalement dans un laboratoire de Mathématiques. Une cinquième équipe (Rocquencourt) appartient à l'INRIA et est à vocation mixte. Chaque équipe a été composée de sorte à être de taille relativement petite et formée de permanents particulièrement actifs et reconnus au plan international.

 

On doit largement à Knuth et Rabin dans les décennies 1970--1980 d'avoir révélé l'importance des modèles de l'aléa discret en informatique. À la suite des travaux et synthèses de Knuth, le critère d'efficacité algorithmique s'est déplacé du cas le pire vers le cas probable, démarche qui présente l'intérêt de bien refléter les conditions d'usage des programmes implantant un algorithme donné. Rabin a d'autre part montré les gains parfois spectaculaires que pouvaient entraîner une algorithmique probabiliste qui ``parie'' sur le hasard (``randomisation''). La mise en oeuvre de programmes de recherche autour de ces thèmes s'est considérablement développée dans les années 1990. Elle nécessite un effort particulièrement conséquent d'analyse des propriétés de cet aléa discret.

Nous avons choisi de nous engager sur un petit nombre de thèmes choisis tant pour leur importance en algorithmique que pour la richesse de leurs propriétés et pour la multiplicité des approches méthodologiques qui peuvent leur être appliquées. Ainsi, les mots aléatoires sont à la base de l'algorithmique du texte, mais aussi omniprésents en compression de données symboliques et textuelles et dans la détection de motifs significatifs en fouille de données. On les aborde par le biais de la combinatoire des mots et des méthodes d'analyse combinatoire, par la théorie des systèmes dynamiques, mais aussi par la théorie probabiliste des chaînes de Markov. Les arbres apparaissent comme mode de structuration de données, avec une importance revitalisée par la richesse et la diversité des volumes de données actuels, lesquelles sont fréquemment de nature multidimensionnelle. Les structures arithmétiques aléatoires jouent un rôle essentiel, non seulement en cryptographie, mais aussi en optimisation discrète (via la réduction des réseaux, notamment). Ces structures s'étudient par la théorie des systèmes dynamiques et par des méthodes combinatoires ou analytiques. Les graphes enfin sont centraux en optimisation tout en donnant lieu à des modèles très divers de communication et d'interaction, dont l'intérêt est puissamment motivé par l'essor de l'Internet et des grands réseaux de communication.

Notre thèse est qu'il existe une théorie cohérente de l'aléa discret incarné dans les mots, structures arithmétiques, arbres, et graphes. Celle-ci est encore très largement à construire---nous proposons d'en établir les bases, tout en orientant nos recherches selon les besoins d'une algorithmique de base efficace et bien validée mathématiquement. Par exemple, la structure d'arbre digital est fondamentale en recherche textuelle rapide (Bentley-Sedgewick), elle apparaît dans l'élection de leader en algorithmique distribuée et sert à la construction de protocoles de communication rapides. Dans le même temps, via les arbres suffixes, l'arbre digital joue un rôle essentiel en compression de données textuelles (Lempel-Ziv), et apparaît comme généralisation de l'algorithme d'orientation de vecteurs en géométrie algorithmique. Cette structure donne lieu à un processus combinatoire nouveau et la quantification de ses caractéristiques en probabilité constitue un chapitre central (mais non encore écrit) de la théorie de l'aléa discret.

Nous proposons de développer cette théorie cohérente de l'aléa informatique discret par confrontation et synthèse des approches suivantes : (i) méthodes combinatoires (bijectives ou fondées sur l'algèbre des séries) ; (ii) probabilistes (processus stochastiques) ; (iii) analytiques (singularités, perturbation) ; (iv) dynamiques (opérateurs de transfert notamment). Ces méthodes d'analyse sont souvent étudiées par des communautés scientifiques disjointes. L'un des principes fondateurs de cette proposition est qu'elles s'enrichissent mutuellement et permettent une compréhension en profondeur de l'aléa discret et des phénomènes de complexité algorithmique associés. Par exemple, pour l'arbre digital, les approches probabilistes et dynamiques ``recyclent'' avantageusement les résultats fournis par méthodes analytiques (par exemple de type Fourier-Mellin) et le prétraitement combinatoire des équations fonctionnelles en jeu est largement réutilisable par les trois autres approches. Signalons enfin que plusieurs des chercheurs rassemblés dans cette proposition comptent au plan international parmi la douzaine de leaders mondiaux dans leur domaine. Témoignent de ce fait les livres, publications internationales, place dans les comités de programme, et surtout leur rôle fondateur dans les deux séries de conférences internationales AofA et Algorithms, Trees, Combinatorics and Probabilities, lesquelles touchent une communauté internationale de près de 200 chercheurs. Nos équipes sont les seules, au plan mondial, à aborder un tel programme de recherche de manière pluridisciplinaire, synthétique, et collaborative.


 Description du projet et résultats attendus 

 

Notre programme de recherche aborde quelques unes des ``grandes'' structures de l'informatique : mots et information, structures arithmétiques aléatoires, graphes et cartes, génération aléatoire. Chacun de nos objectifs est partagé par au moins trois de nos cinq équipes de recherche. De nombreux liens croisés renforcent la cohérence méthodologique de notre proposition. Ainsi les méthodes de combinatoire analytique (fonctions génératrices et singularités), les méthodes dynamiques (opérateurs de transfert), les approches probabilistes (vision par processus) sont largement transverses aux objets étudiés, et, dans la plupart des cas, elles peuvent s'appliquer ``en cascade''. Le prétraitement par la combinatoire bijective établit des liens profonds entre des objets en apparence différents (par ex., cartes, arbres, et mots) tandis que les autres méthodes permettent de dégager de vastes classes d'universalité quantifiant la structure asymptotique de grandes classes objets. L'item ``génération aléatoire'' décrit enfin un développement inattendu des méthodes précédentes sur lesquelles il se greffe naturellement.

 

1. Mots et information


 

1.1. Motifs et structures digitales.
Les mots sont la structure centrale de la recherche d'informations textuelle. La quantification des occurrences de motifs dans un texte aléatoire a été l'objet littéralement de centaines de publications. Nous disposons grâce aux progrès très récents de la combinatoire analytique (Flajolet-Sedgewick) et de la notion de source dynamique (Vallée) de méthodes puissantes pour la prédiction d'occurrences dans un texte (mot) obéissant à une variété de modèles de l'aléa.


Objectif 1. Construire une théorie unitaire fondée sur l'analyse des séries génératrices et des opérateurs de transfert permettant de quantifier très précisément les probabilités d'occurrences de motifs, les lois limites associées, les grandes déviations. Quantifier les régimes non asymptotiques (vitesse de convergence). Traiter de la sorte les modèles analytiques les plus larges, comprenant les modèles sans mémoire, les modèles Markoviens, les sources dynamiques à corrélation non bornée.

 

Répondre à cette question permet de disposer de modèles prédictifs sur lesquels on peut séparer les éléments statistiquement significatifs du bruit stochastique inévitable. Les applications, au delà de l'optimisation des algorithmes de recherche de motifs, se situent en détection d'intrusion, fouille de données, et (secondairement pour ce projet) dans l'interprétation de séquences biologiques. Le terme ``motif'' est ici entendu en un sens large, couvrant facteurs, sous-séquences, motifs à trous, motifs imparfaitement spécifiés ou avec erreur. Les travaux déjà effectués par nous (Bourdon, Clément, Fayolle, Flajolet, Nicodème, Vallée) justifient la faisabilité de cette entreprise.

Une motivation essentielle pour la quantification des occurrences de motifs tient à l'importance de cette question dans l'analyse d'algorithmes de recherche rapide d'informations (par exemple, algorithme dit ``ternaire'' de Bentley-Sedgewick), dans la gestion des dictionnaires, et surtout dans le domaine de la compression de données. On pense ici à la compression par antidictionnaire, idée originale due à Crochemore, qui consiste à comprimer un texte en décrivant les motifs les plus courts qu'il évite(!).


1.2. Compression et arbre digital.
En compression de données (textuelles), la plupart des méthodes connues reposent sur des structures d'arbre digital particulières, notamment l'arbre des suffixes. L'arbre digital (ou ``trie'') est fondé sur les préfixes distinctifs minimaux d'un ensemble de mots ; l'arbre des suffixes est analogue, mais construit sur les suffixes d'une longue séquence. Les importantes méthodes de compression de Lempel et Ziv (gzip, etc) reposent sur de tels arbres, lesquels servent à la fois de structure de données et de structure ``conceptuelle'' sous-jacente. Des progrès considérables ont été obtenus dans la clarification des méthodes analytiques adaptées aux modèles de base : équations fonctionnelles, transformation de Mellin, perturbation analytique et théorème des quasi-puissances. L'état actuel butte sur l'extension à une riche classe de modèles de sources plus aptes à rendre compte de données réelles. Nous énonçons :

Objectif 2. Viser à déterminer en moyenne, variance, distribution, et grandes déviations, les paramètres principaux des arbres digitaux et arbres suffixes sous les modèles unificateurs de sources dynamiques.


Le challenge tient ici à la nécessité d'analyses en distribution, tandis que la décennie écoulée s'est essentiellement limitée à des analyses en moyenne, les analyses distributionnelles constituant déjà des prouesses techniques sous le modèle le plus simple (Bernoulli ou sans-mémoire). Nous attendons beaucoup de certains progrès récents dans le domaine des structures arithmétiques aléatoires (voir ci-dessous) où des résultats profonds ont été obtenus (Baladi-Vallée). Les travaux antérieurs relatifs aux arbres digitaux (Clément-Flajolet-Vallée) suggèrent qu'un traitement général est possible. Ces questions sont significatives. D'une part, l'efficacité d'un algorithme de compression se jauge à son écart à l'entropie, appelé ``redondance''. Tous les algorithmes usuels atteignent l'entropie au premier ordre asymptotique, de sorte qu'ici des analyses très fines sont essentielles pour quantifier la redondance des principaux schémas de compression. Szpankowski, collaborateur de SADA, a tout récemment observé que cette redondance pouvait être mise à profit pour superposer sans coût additionnel une correction d'erreurs. Les résultats d'analyse sont aussi directement transposables à l'optimisation de l'allocation mémoire. Dans un autre ordre d'idées, les études de profil limite, de niveaux de saturation, de superposition d'arbres s'appliquent très directement à la comparaison de séquences.


1.3. Communication et arbres digitaux.
Les arbres digitaux, bien qu'issus des mots, se sont avérés de manière surprenante être à la base de protocoles de communication rapide. Le contexte est celui de réseaux de communication---il s'agit d'accéder à un canal de communication---ou du cadre de l'analyse du trafic qui passe par un lien d'un réseau de type ADSL. Dans les deux cas l'état du système est représenté par une structure abstraite en arbre (digital !) qui évolue au cours du temps avec l'arrivée et le départ des requêtes de communication : c'est le protocole en arbre CTM qui ``bat'' largement Ethernet en stabilité, niveau de saturation, et délais d'attente. Dans le cas de l'analyse de trafic, la suppression d'une partie des noeuds représente la fin de connections TCP sur plusieurs blocs d'adresses Internet. En dehors de certaines propriétés de stabilité, peu de travaux ont été réalisés pour analyser les performances des algorithmes utilisant ces structures d'arbres dynamiques.


Objectif 3. Déterminer les propriétés asymptotiques du régime d'équilibre des protocoles en arbre sur des quantités telles que la taille de l'arbre, sa profondeur, ou encore sur les fonctions de coûts propres au système considéré comme le délai pour les réseaux ou le temps moyen de détection d'un incident sur le trafic.


Plusieurs approches seront considérées : 1) Étude du système à la limite de la saturation ; il s'agit de déterminer le profil limite de l'arbre considéré dans cette situation (lien avec les travaux de Marckert, Mokkadem, Schaeffer sur les arbres limites). 2) Étude de la stabilisation de l'algorithme quand les mécanismes d'adjonction de noeuds est général (les cas étudiés ne concernent que des adjonctions de type poissonnien). L'approche envisagée pour attaquer ce problème difficile repose sur une représentation probabiliste des équations d'évolution du système, laquelle se relie aux approches précédentes.


1.4.Mots et codages de chemins sur réseaux.
L'énumération des chemins à sommets de coordonnées entières, partant d'un point donné, formés de pas choisis dans un ensemble fini prescrit à l'avance, et évitant une zone donnée de l'espace, est un problème très classique en combinatoire. De nombreuses questions s'y ramènent, par exemple des modèles de files d'attente et de partage de ressources d'allocation mémoire. Ainsi, l'état d'une mémoire partagée par d processeurs se représente-t-il par un point dans l'espace d-dimensionnel et l'histoire d'une évolution se réduit à un chemin aux plus proches voisins dans un hyperoctant. De telles histoires sont donc codées par des mots obéissant à diverses contraintes, lesquels permettent d'exprimer les histoires d'évolution comportementale d'un ou plusieurs processus informatiques. L'approche par ce canal, ouvre la voie à de nombreuses applications, mais elle reste très imparfaitement maîtrisée.


Objectif 4. Déterminer une classification structurelle des chemins contraints sur réseaux, notamment en petite dimension, conduisant à des équations fonctionnelles ``exactement résolubles'' et à des modèles analytiques explicites.


Cet objectif vise à raffine considérablement la classification, commune en informatique théorique, des mécanismes fondamentaux de génération et de reconnaissance. Des résultats substantiels mais encore parcellaires ont été obtenus (Bousquet-Mélou). On aimerait classer chaque problème dans une hiérarchie bien établie de séries formelles : séries rationnelles, algébriques, ou différentiellement finies. Dès lors, les méthodes de combinatoire analytique (analyse de singularités et théorie perturbative) prennent le relais et fournissent des informations asymptotiques précises ainsi que les régimes non-stationnaires. Les applications principales se situent dans l'analyse de partage de ressources et dans les phénomènes d'attente avec couplage de service en temps discret.


2. Structures arithmétiques aléatoires



La théorie des systèmes dynamiques prend désormais sa place dans l'analyse des algorithmes. Le groupe de Caen a eu ici un rôle de précurseur et de leader. Il a élaboré un nouveau concept, celui d'analyse dynamique des algorithmes où l'on considère un algorithme et l'ensemble de ses données comme un système dynamique. Les données sont alors les particules du système qui sont soumises au ``champ" créé par les opérations que leur fait subir l'algorithme. À un système dynamique, on associe classiquement, depuis Ruelle, un opérateur appelé opérateur de transfert qui permet de décrire l'évolution du système. L'idée originale du groupe caennais consiste à détourner l'opérateur de transfert de son usage habituel et à le considérer comme un opérateur ``super-générateur", en ce sens qu'il engendre lui-même les séries génératrices associées à l'algorithme. Les opérations sur les algorithmes continuent à bien se traduire en opérations sur ces opérateurs générateurs, et la valeur propre dominante de l'opérateur de transfert concentre les propriétés essentielles du système. C'est pourquoi elle va jouer un rôle essentiel, le même rôle que la singularité dominante dans le cadre classique des séries génératrices, et va ainsi permettre d'appréhender le comportement asymptotique probable de l'algorithme, même quand celui-ci est corrélé.

L'approche dynamique a été appliquée avec succès à la théorie de l'information et aux arbres digitaux (voir section précédente). Il sera ici question de deux autres catégories de problèmes : les algorithmes arithmétiques et la réduction des réseaux (au sens mathématique du terme).


2.1.Les algorithmes Euclidiens.
Ces algorithmes que tout le monde connaît représentent un véritable challenge pour les méthodes d'analyse d'algorithmes. En effet, ils opèrent par transformation successive d'états d'une manière qui garde en un sens la mémoire du passé. Ils se distinguent donc a priori des structures arborescentes qui sont très ``libres'' (décomposables, modulaires). Dans le même temps, il apparaît nécessaire de pouvoir analyser de tels comportements ``transformationnels'' que manifestent par exemple toutes les structures d'arbre de recherche équilibrés. L'importance pratique des algorithmes Euclidiens est rehaussée par le fait qu'on estime à près de 50% le temps de calcul qui y est passé dans les systèmes arithmétiques fondés sur de l'arithmétique rationnelle ou modulaire (en calcul formel et cryptographie notamment).

La conjecture de Brent-Knuth portant sur l'algorithme binaire a été résolue plus de 20 ans après sa première formulation grâce aux méthodes dynamiques (Vallée). Le domaine reste techniquement difficile. Nous proposons :


Objectif 5. Développer des méthodes systématiques pour aborder la complexité tant arithmétique que booléenne (``en bits'') des principaux algorithmes euclidiens, notamment par le calcul des constantes de structure, des variances, et de lois limites. Élargir le champ des méthodes dynamiques à une classe significative d'algorithmes ``transformationnels''.


On ne sait par exemple comprendre encore que partiellement les algorithmes ``Plus-Moins'' et ``LSB'', ce malgré leur évidente efficacité pratique. Par ailleurs, l'amélioration des seuils de validité des méthodes rapides conjuguée à l'augmentation de longueur des clefs dans les systèmes cryptographiques à clefs publiques justifie l'investigation des méthodes récursives rapides (à base de FFT). L'intérêt méthodologique de ces recherches est grand : il s'agit de faire sauter le verrou lié aux limitations des structures de données ``libres'' ou ``décomposables''.


2.2. La réduction des réseaux.
L'algorithme LLL est une découverte spectaculaire des années 1980 qui résout de manière approchée le problème de la réduction des réseaux (au sens de maillages réguliers de l'espace). Les conséquences de cet algorithme central sont innombrables en cryptographie (par ex., attaque des systèmes de "sac à dos''), en calcul formel, géométrie algorithmique, et optimisation combinatoire (par ex., programmation linéaire en nombres entiers). Les analyses existantes décrivent le cas le pire, très différent du comportement observable de l'algorithme en situation réelle. Ce dernier est loin d'être compris, d'où de grandes difficultés de ``réglages'' (dimensionnement de paramètres) qui sont pourtant cruciales dans nombre des applications déjà citées.


Objectif 6. Déterminer l'impact des méthodes dynamiques sur l'algorithmique de la réduction des réseaux (LLL), en partant des petites dimensions. Développer des modèles exacts ou approchés qui ``expliquent'' les performances atteignables sous diverses conditions d'utilisation.

Le fait que cet objectif idéal ait une base réaliste tient au fait que la réduction en dimension 2, brique de base de LLL, est déjà reconnue comme susceptible d'une analyse dynamique (Clément, Flajolet, Vallée). À noter que dans ce cas, se révèlent même des connexions inattendues avec la conjecture de Riemann(!) en mathématiques. L'examen de la dimension 3 constitue un premier verrou. Peut-être faudra-t-il développer des modèles approchés partiellement heuristiques et validés par simulation?



3. Arbres et processus stochastiques


La structure d'arbre est certainement la plus importante de l'informatique. Elle représente des données symboliques (arbres de terme en logique et vérification, calcul formel, compilation et interprétation), sert de fondement aux méthodes d'accès rapide à l'information (arbres de recherche ou arbre digital supra), et fournit la structure abstraite sous-jacente à de nombreuses stratégies de type ``diviser-pour-régner'', y compris dans un contexte distribué.


3.1. Méthodologie d'analyse des structures arborescentes.
Nous visons d'abord un effort conséquent destiné à dégager des méthodes applicables à de larges classes de problèmes.


Objectif 7. Organiser un faisceau de méthodes (appliquées jusqu'ici de manière ad hoc à des cas assez disparates) visant à quantifier les paramètres principaux de grandes classes de modèles d'arbres et à dégager des phénomènes d'universalité correspondants. Viser une convergence des points de vue stochastique, analytique, et dynamique.


Le projet dispose sur ce plan de grandes compétences et des résultats marquants ont été obtenus sur certains problèmes particuliers : comparaison des stratégies d'exploration en largeur et en profondeur (Marckert), description fine des arbres de recherche unidimensionnels (Chauvin, Rouault), par ex. Une première piste unificatrice transverse est apparue tout récemment : celle des processus de fragmentation. Un tel processus rend compte de la taille des fragments d'une particule soumise à certaines règles de dislocation. Par exemple, on part d'une particule de masse 1. L'étude des phénomènes de fragmentations/coagulations a connu ces dernières années de profondes avancées dues à Bertoin, Pitman, Yor. Un domaine peu étudié est celui du processus historique associé aux fragmentations (on appelle processus historique, l'arbre généalogique représentant la filiation des fragments en fonction du temps). Certains arbres associés aux fragmentations apparaissent en informatique comme des objets naturels ; par exemple l'arbre binaire de recherche est le processus historique associé à une fragmentation binaire, le quadtree est celui d'une fragmentation quaternaire, l'arbre digital est l'arbre associé à une fragmentation K-aire où K est la longueur de l'alphabet. Nous avons pour but d'étudier systématiquement les processus historiques associés aux fragmentations homogènes. On attend de ces travaux de mieux comprendre les phénomènes de fragmentation/coagulation ainsi que d'avoir une approche générique pour l'analyse des arbres d'utilisation courante en informatique, sujet de nombreuses publications ces dernières années, et dont le comportement (très comparable entre les différents cas) doit être susceptible d'une explication unitaire.

Une deuxième piste pour une approche unificatrice de ces questions se situe dans les modèles d'urnes : des particules de divers types (« couleurs ») évoluent stochastiquement selon des règles déterminées. Ces modèles d'urnes possèdent, on le sait, une grande valeur descriptive : ils prennent en compte des modèles de croissance d'arbre, de gestion de tables de hachage (paginées ou non), d'occupation mémoire pour les arbres équilibrés (« B-trees »), par ex. Mais pour leur traitement effectif, on manque encore cruellement d'approches générales. De premiers résultats très récents fondés sur des approches analytiques (Pouyanne, Flajolet) indiquent heureusement la possibilité de dégager de nouvelles classes de modèles exactement résolubles, sur lesquels les méthodes de combinatoire analytique doivent fournir des résultats très précis. On espère ainsi comprendre la nature de phénomènes de seuil encore mystérieux entourant les arbres m-aires de recherche par exemple.


Les progrès des méthodes d'analyse évoquées ci-dessus ont un impact direct en algorithmique distribuée. Un contexte typique est celui de réseaux de capteurs ou de stations mobiles de type ``ad-hoc'' disposant de ressources énergétiques limitées. Il s'agit de déterminer de façon distribuée une des stations qui jouera le rôle de ``leader'' pour rassembler les données collectées par l'ensemble de stations ou organiser la communication. Les algorithmes envisagés sont de type arborescent : à chaque étape, une partie des stations est éliminée dans le processus de sélection, selon un tirage au sort réparti. Il s'agit de déterminer les constantes critiques qui déterminent le nombre d'étapes d'élection ou la consommation totale en énergie, par ex. Ces algorithmes font plus généralement partie d'une classe homogène d'algorithmes de type diviser pour régner (ceux qui sont fondés sur des tirages individuels, de type Bernoulli). Les méthodes probabilistes d'analyse d'arbres (processus de fragmentation notamment) et les méthodes dynamiques des sections précédentes devraient permettre d'élucider le rôle de la fonctionnelle d'entropie dans ces questions, et, partant de là, de caractériser simplement le comportement probable d'une large classe d'algorithmes.


3.2. Arbres quadrants et structures multi-dimensionnelles.
Les systèmes informatiques traitent désormais des données multiformes, composées de plusieurs ``attributs", parfois hétérogènes, et il s'avère essentiel d'accéder rapidement à de tels ensembles de données de très grande taille. La dernière édition du volume 3 de The Art of Computer Programming [Knuth, 1998] ne consacre encore que 20 pages sur 600 à ces questions pourtant très importantes ; Knuth écrit (tout en citant certains de nos travaux, Flajolet et al.) : ``The mathematical analysis of random quadtrees is quite difficult''. Les phénomènes liés à la pagination et à la recherche dans des espaces de dimension intermédiaires, par ex., entre 2 et 12, sont encore très mal compris (au delà, d'autres algorithmes de réduction de dimension doivent être appliqués).


Objectif 8. Quantifier le phénomène de la ``dimension de séparation'' et les seuils associés dans les arbres à branchement non binaires, quadtrees. Dégager de la sorte des principes d'optimisation de la pagination et de l'allocation mémoire pour ces structures fondamentales.


L'approche à cette question doit bénéficier d'une multiplicité d'angles d'attaque. Les méthodes de martingale appliquées avec un succès marqué aux arbres binaires de recherche classiques (Chauvin, Rouault) pourraient permettre une étude en trajectoire, à partir du lien non encore totalement établi entre le modèle des permutations et le modèle ``local uniforme'' dans lequel les probabilités conditionnelles sont fournies par le volume. Des méthodes de combinatoire analytique seront requises pour l'étude en distribution. La jonction avec les modèles d'urnes devrait permettre de compléter le tableau.
 


4. Graphes et cartes aléatoires


L'algorithmique des graphes est foisonnante et traite de problèmes suscités aussi bien par la modélisation des réseaux que par les questions de dessins de graphes (design de circuit, etc) ou de géométrie algorithmique (manipulation de maillage). Nous nous concentrons sur le modèle particulièrement riche des cartes, dont l'étude implique de plus des techniques voisines de celles développées par ailleurs dans ce projet.

Une carte est la description combinatoire du dessin d'un graphe dans une surface. À l'instar de la liste d'adjacence des sommets pour les graphes, la carte combinatoire est l'abstraction naturelle des structures de données représentant les maillages en géométrie algorithmique. Ainsi, les questions de compression de maillages ont récemment suscité un intérêt particulier pour le contenu informationnel de familles de cartes contraintes.

Le point de vue combinatoire a permis de rapprocher ces aspects algorithmiques de questionnements issues de la physique, notamment autour de l'étude de la géométrie intrinsèque des cartes aléatoires. Ce travail fédérateur se poursuit et nous voulons nous concentrer ici sur une série de questions fondamentales qui relèvent directement de l'approche SADA : ces questions vont d'aspects méthodologiques comme l'approfondissement de la relation entre arbres aléatoires et cartes aléatoires, à des questions plus applicatives liée au dessin de graphe et à la génération aléatoire (pour ce dernier point on se réfèrera plus spécialement à la section suivante).


4.1. Comprendre les cartes à l'aide des arbres.
L'importance des arbres couvrants en algorithmique
des graphes n'est pas à démontrer. La notion d'arbre couvrant canonique a pris dans le contexte des cartes une place encore plus centrale à la suite d'une série de travaux au départ centrés sur l'énumération bijective et dont les développements se sont révélés pertinents dans des directions inattendues, allant de la physique mathématique à l'algorithmique de la compression.

Un premier intérêt majeur des codages par arbres canoniques issus de l'approche bijective est de lier de façon fine la ``forme'' des cartes à des paramètres de leur arbre-code. Cet aspect nouveau autorise l'adaptation à l'étude des cartes de tout l'outillage extrêmement riche développé pour l'analyse d'arbres aléatoires.


Objectif 9. Établir la frontière entre les propriétés de cartes réductibles à des propriétés d'arbres et celles qui ne le sont pas. En particulier comprendre jusqu'où l'approche en terme d'arbres-codes peut rendre compte de la complexité structurelle des cartes.


Ainsi les arbres canoniques de type ``arbres bien étiquetés'' ont permis de faire sauter un premier verrou à la compréhension asymptotique fine de la forme des cartes : étude du diamètre des quadrangulations (Chassaing et Schaeffer), convergence des quadrangulations normalisées vers un objet limite (Marckert et Mokkadem), convergence des cartes biparties normalisées munies de lois assez générales (Marckert et Miermont). Dans l'idée d'obtenir des résultats d'universalité à la manière de ceux recherchés pour les arbres, une approche naturelle est de montrer pour des classes très générales de cartes la convergence vers une unique limite continue aléatoire : la carte brownienne (Marckert et Mokkadem) est l'ébauche d'une telle limite. Il reste à élucider le problème de la convergence des métriques discrètes, et d'autres part les propriétés topologiques de la limite.

Une direction complémentaire de recherche est d'attaquer directement le problème de la métrique d'un point de vue discret. La première étape de ce programme techniquement très difficile peut se reformuler complètement dans le langage des arbres plongés. Un plongement d'arbre est une application des sommets de l'arbre sur une ligne qui donne longueur unité à toutes les arêtes. La mesure de répartition des sommets sur la ligne par le plongement (qui peut être déterministe ou aléatoire) est liée pour de grands arbres aléatoires à une certaine distribution de probabilités aléatoire apparue il y a quelques années comme un objet "universel" en probabilités, "the Integrated SuperBrownian Excursion". Il s'agit d'un objet assez compliqué qui implique deux niveaux d'aléa.

Il est cependant possible de calculer certaines de ses propriétés par une approche discrète, via les arbres plongés. Par exemple, nous avons pu récemment calculer la loi de sa fonction de répartition en un point (Bousquet-Mélou). Nous envisageons de nous attaquer au calcul de la loi jointe de tous ses moments, par le biais des arbres binaires, de certaines séries génératrices et de l'analyse de leurs singularités. On rejoint ici les questions d'analyses de paramètre d'arbres de la section précédente, et il semble possible d'appliquer ces techniques à des questions ouvertes sur les longueurs de cheminement droite/gauche dans les modèles standards d'arbres aléatoires.


4.2. Arbres, orientations et contenu informationnel des cartes.
Un second type de codage par arbre canonique développé par des membres du projet fait intervenir de façon centrale la notion d'orientation minimale. L'utilisation de ces arbres conduit notamment à des algorithmes de codages optimaux relativement au contenu informationnel des cartes codées (Poulalhon, Fusy, Schaeffer). Du point de vue de la compression de maillage, ces résultats montrent par exemple que pour les triangulations, contrairement à ce que suggérait l'analyse des heuristiques existantes, un algorithme linéaire à base de parcours peut garantir un taux de compression optimal (c'est-à-dire égal à l'entropie de la classe des triangulations). Les travaux de la thèse d'Éric Fusy illustrent le fait que ces orientations sont en fait omniprésentes dans les techniques de codage par arbres canoniques. Ceci pose la question :


Objectif 10. Unifier les techniques d'orientations et d'arbres canoniques qui sous-tendent les résultats d'énumération bijective de cartes et leur applications à l'algorithmique du codage et du tirage aléatoire, et à l'étude des paramètres des grandes cartes.


Dans cette direction, un premier lien très général entre ces orientations et les arbres couvrants quelconques des cartes a été explicité par Olivier Bernardi. Le fil conducteur qui a conduit aux résultats mentionnés ci-dessus est que l'explication combinatoire de propriétés énumératives remarquables, au delà de son intérêt esthétique indéniable, permet de mettre à jour des propriétés structurelles exploitables algorithmiquement. Dans cette optique la nouvelle approche bijective proposée récemment par Olivier Bernardi, qui suggère un lien à creuser avec les modèles de chemins dans le quart de plan, est très prometteuse.


4.3.Paramètres d'arbres et dessin de graphes.
De nombreux algorithmes de dessins planaires reposent sur l'utilisation de certains ordres canoniques pour calculer les coordonnées attribuées aux sommets du graphe. Le choix d'un ordre plutôt qu'un autre a une grande influence sur la qualité du dessin et notamment sur la taille de la grille qu'il est nécessaire d'utiliser. Pour l'instant, les heuristiques utilisées dans la littérature reposent sur des analyses rigoureuses des pires cas. Nous avons montré récemment dans le cas des triangulations planaires que le choix d'un certain ordre "minimal" donne des dessins presque sûrement de meilleure qualité. Il sera intéressant d'explorer plus généralement comment de telles analyses en moyenne permettent de développer de meilleures heuristiques de dessin. Nous proposons :


Objectif 11. Étendre le champ d'application des analyses en distribution d'algorithme de dessin de graphes, notamment en direction des dessins de types diagrammes de contacts ou de visibilité.


Les résultats déjà obtenus par des membres du projet portent sur les dessins rectilinéaires de triangulations et reposent sur l'analyse asymptotique de paramètres combinatoires d'arbres couvrants associés aux orientations minimales. Les techniques utilisées combinent donc l'analyse de singularité avec la combinatoire des orientations de graphes. Dans un premier temps, en se concentrant sur la condition de minimalité, il devrait être possible d'étendre naturellement nos analyses à la grande familles des algorithmes basés plus ou moins explicitement sur des orientations ou des ordres canoniques. L'étape suivante, plus délicate, sera d'essayer de lever cette condition de minimalité. Une voie prometteuse dans cette direction est d'obtenir une description bijective de l'ensemble des orientations possibles à la manière de ce qui peut être fait pour les orientations associées aux arbres de Schnyder des triangulations.


5. Génération aléatoire


La génération de structures aléatoires discrètes sert en premier lieu au développement de simulations, ce afin de déterminer empiriquement le comportement de paramètres non clairement réductibles à l'analyse. Elle sert aussi à engendrer des tests destinés soit à la validation logique (correction) des programmes, soit à la validation de leur complexité. Dans de tels contextes, il est nécessaire de tirer aléatoirement des structures discrètes (arbres, mots, graphes, cartes, permutations) obéissant à des contraintes souvent complexes. Une première approche méthodologique de portée générale a été proposée---la méthode récursive, fondée sur des spécifications dans le style de la combinatoire analytique et déjà implantée dans le système Maple. Trois des participants à ce projet (Duchon, Flajolet, Schaeffer) ont, dans une publication de 2004, entièrement renouvelé le sujet en montrant les gains de complexité très importants (tant théoriques que pratiques !) qu'on pouvait attendre de l'introduction inopinée des modèles de Boltzmann. (Un modèle de Boltzmann affecte à toute structure un poids proportionnel à l'exponentielle de sa taille. Des classes larges de modèles étiquetés deviennent ainsi susceptibles d'une génération en temps linéaire, ce qui est évidemment optimal).

Il est proposé d'étendre cette approche à l'univers des structures non-étiquetées, dont ressortissent les mots, les arbres de termes, des classes larges de langages formels, les cartes, etc.


Objectif 12. Développer une algorithmique complète universelle pour les structures non-étiquetées décomposables. Valider cette algorithmique par des algorithmes dédiés aux principaux modèles discrets, opérant en temps linéaire, avec de très faibles constantes de temps. Développer une algorithmique correspondante discrète (plutôt que ``flottante'') ; contrôler les problèmes d'approximation numérique et les défauts d'uniformité induits.


L'intérêt des approches génériques de génération pour les structures décomposables est marqué par des travaux très récents de génomique (Denise, Ponty, Termier) et de test statistique (``random testing'') en génie logiciel (Denise, Gaudel, Gouraud).

Quelques premières expériences illustrant la viabilité de notre approche ont été conduites : par exemple, un stage de DEA (Pivoteau, Rocquencourt) montre déjà la possibilité d'obtenir en quelques secondes des partitions d'entiers contraintes à avoir des sommants distincts, ce même pour des tailles avoisinant le million. Des investigations préliminaires d'un doctorant (Fusy, LIX et Rocquencourt) suggèrent qu'il sera vraisemblablement possible de tirer des graphes planaires aléatoires de taille voisine du million, ce en quelques minutes de temps calcul (tout en assurant une distribution parfaitement uniforme) : un tel résultat est jusqu'à présent très largement hors de portée de tous les algorithmes connus.

La conduite de ce programme passe par le développement d'une algorithmique traitant génériquement les constructions de multi-ensemble, ensemble sans répétition, cycles, substitution, et pointage. L'algorithmique de base repose sur des réels en (petite) multiprécision. Des gains supplémentaires importants devraient être obtenus par la construction de générateurs purement discrets, mais ceci passe par des analyses de sensibilité numérique et le développement de nouveaux algorithmes, tâches qui s'avèrent particulièrement délicates.

Des directions étayant ce programme de recherche seront poursuivies, soit à titre de comparaison d'efficacité algorithmique, soit afin d'en élargir le spectre. Citons ici : la génération multicritère (selon la taille et divers paramètres annexes) ; la génération Lagrangienne (fondée sur l'inversion de Lagrange multivariée) a priori bien adaptée aux cartes ; les méthodes bijectives (cartes, arbres, chemins) ; les méthodes de chaînes de Markov ; la génération des structures définies par inclusion-exclusion. Notons que cet item du programme de recherche se relie totalement aux modèles et méthodes développés dans les autres sections de cette proposition. Il regroupe d'ailleurs des participants issus de quatre des cinq équipes constitutives du Projet SADA.


retour