ACI NIM Arbres, chemins: probabilités et algorithmes

le 5 MAI 2008, Institut Elie Cartan, Nancy

Résumé. On trouvera le détail du projet financé par cette ACI à cette adresse:

http://www.iecn.u-nancy.fr/~chassain/ACPA/detail.html

En résumé, l'objectif de cette ACI était de créer les conditions de dialogue, d'échange, d'émulation et de collaboration entre 3 communautés (probabilités avec Nancy et Versailles, combinatoire avec Bordeaux et informatique avec Rocquencourt) qui étudient les grandes structures discrètes avec des outils (processus stochastiques, combinatoire analytique, e.g.) et des motivations (physique statistique, informatique, e.g.) parfois différentes, favorisant ainsi des avancées majeures dans nos domaines respectifs. L'objectif a été atteint à travers l'organisation de rencontres nationales et internationales, financées en partie par l'ACI. La participation des membres de l'ACI à ces rencontres a également été financée en partie par l'ACI. À ce sujet, on pourra consulter les comptes détaillés antenne par antenne. Le bilan purement comptable de cette ACI est la publication de 79 articles dans des revues internationales ou des proceedings de conférences internationales à comité de lecture. On trouvera la liste des 79 publications à cette adresse :

http://www.iecn.u-nancy.fr/~chassain/ACPA/publications.html

Bilan scientifique. Ce bilan renonce à rendre pleinement justice à la créativité foisonnante des membres du projet. Mentionnons quelques exemples:

Côté algorithmique, 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, avec applications en ``fouille de données'' (data mining) et en analyse de trafic dans les routeurs, ont été conçus, analysés et optimisés, essentiellement à Rocquencourt, autour de Philippe Flajolet, avec une contribution mineure mais utile de Nancy. L'utilisation de méthodes à la Boltzman, fournissant des algorithmes de tirage aléatoires de grandes structures combinatoires en temps linéaire ou quasi-linéaire, a été généralisée en collaboration entre Rocquencourt et Bordeaux. Ce travail a été salué par l' Outstanding Simulation Publication Award 2007.

La partie combinatoire énumérative et équations fonctionnelles de ce projet se proposait de développer l'étude de paramètres des marches dans le quart de plan et des cartes planaires, ce qui a été mené à bien dans une série d'articles en particulier dûs à Mireille Bousquet-Mélou et à ses coauteurs. Ces travaux ont été reconnus par une conférence invitée à l'ICM 2006.

La partie combinatoire analytique s'est signalée par de nombreuses contributions à l'étude des arbres et de leurs paramètres, sujet où Rocquencourt est leader mondial. On remarque en particulier de très belles contributions à l'étude des schémas d'urnes, d'abord pour analyser les arbres m-aires de recherche, puis dans un cadre général de processus de Pölya, contributions faisant apparaître l'efficacité d'une approche combinant des méthodes issues de la géométrie, de l'algèbre linéaire et des probabilités. Dans l'étude des arbres aléatoires pour l'algorithmique, le plus célèbre d'entre eux, l'arbre binaire de recherche associé à Quicksort, a encore été à l'honneur, puisque les résultats obtenus sur le profil de cet arbre sont les plus performants obtenus à ce jour. Notons aussi, en collaboration entre Rocquencourt et Versailles, les premiers travaux sur les fonctions booléennes mêlant les points de vue "combinatoire analytique" et probabiliste. Dans tous ces sujets les échanges avec l'approche plus probabiliste (martingales, processus stochastiques) utilisée à Versailles a été clairement bénéfique.

Enfin un des sujets phare a été l'étude des grandes cartes aléatoires, où chacun des 4 sites contribué de manière importante, et où il est difficile de séparer nettement la contribution de la combinatoire énumérative, de la combinatoire analytique, ou des probabilités. Les travaux du groupe sur les cartes aléatoires ont eu un grand retentissement hors du groupe, et se poursuivent en collaboration avec des membres de l'équipe de probabilité d'Orsay.

Rencontres. L'ACI a permis, entre autres, d'organiser les (ou de participer aux) rencontres ci-dessous:

Conférences internationales.

• 3rd and 4th Colloquia on Mathematics and Computer Science (Algorithms, Trees, Combinatorics and Probabilities) Septembre 2004 et 2006, Vienna et Nancy
• AofA'04 Berkeley, AofA'05 Barcelone, AofA'06 Alden Biesen et AofA'07 Juan les Pins

Rencontres nationales.

• Journées ALEA 2004, 2005, 2006 (CIRM)

Rencontres au sein de l'ACI.

• Journées Arbres et Chemins, Bordeaux, 2004 & 2005
• Journées Arbres Nancy 2004 et Nancy 2006
• Journées Arbres à Versailles (2004, 2005, 2006)

L'essentiel du budget de l'ACI a été affecté à l'organisation de ces rencontres et conférences, qui ont été cruciales pour le développement de nos travaux.

Philippe Chassaing
Coordinateur de l'ACI NIM ACPA