Algorithmique, Combinatoire et Physique Statistique

Alcophys

Action de Recherche Coopérative INRIA

Le texte de la proposition est disponible en [HTML | DVI | PS]. Les équipes composantes sont : Le Labri (Bordeaux) ; le LIX (Palaiseau) ; le LRI (Orsay) ; le Projet ALGO (Rocquencourt).

RÉUNIONS ALCOPHYS en Décembre 2000

• La réunion de synthèse ALCOPHYS aura lieu le Jeudi 14 décembre 2000, de 10h45 à 17h30. Voici les Annonce et Programme. La réunion se tiendra à l'Institut Henri Poincaré.. Organisateurs: R. Cori & P. Flajolet.
• Une journée thématique ALCOPHYS du Lundi 18 décembre 2000 constituée de séminaires (par Jean Vannimenus et Dominic Welsh) et de la thèse de D. Rossin. Cliquer ici pour le Annonce et Programme en PS. La réunion aura lieu a l'École Polytechnique (Palaiseau). Organisateur: R. Cori.

Adresses des participants

• Henri Orland: une méthode de Monte Carlo de croissance pour les polymères, protéines et petits agrégats.
• Alexandre Zvonkine : Des cactus et des tresses d'un point de vue combinatoire et algébrique.
• Vincent Pasquier: Théories conformes et modèles integrables. Plusieurs résultats des théories conformes peuvent être obtenus par des methodes combinatoires élémentaires.

En particulier, Olivier Martin a présenté une interprétation physique de problèmes d'optimisation combinatoire comme le voyageur de commerce. Cette interprétation se prête à l'application de la méthode ``cavité'' pour évaluer des paramètres sur les solutions optimales. L'intérêt de la méthode est qu'elle permet d'utiliser l'intuition physique pour suggérer des approximations. Les transparents de cette présentation sont disponibles ici.

Robert Cori a donné un exposé sur le modèle des tas de sable en utilisant des transparents proches de ceux-ci. Un tas de sable est un graphe dont chaque noeud comporte un certain nombre de grains de sable. Les grains se réorganisent en suivant la règle que chaque noeud (à l'exception d'un puits) peut donner à chacun de ses voisins un grain s'il en a assez pour les servir tous. Toute configuration initiale mène à une seule configuration finale. En autorisant la présence d'un nombre négatif de grains de sable aux noeuds du graphe, on trouve une structure de groupe additif sur l'ensemble des configurations. Ce groupe est naturellement à quotienter par les relations qui correspondent aux distributions de grains aux voisins. Le quotient est un groupe commutatif fini dont la cardinalité est le nombre d'arbres couvrants du graphe. Par ailleurs, on peut trouver dans chaque classe d'équivalence un représentant particulier qui correspond à une configuration dite récurrente (c'est-à-dire observable au bout d'un long temps). Les questions qui se posent en physique sont le nombre d'operations nécessaires pour amener le tas à une configuration stable, ou le nombre de noeuds affectés lors d'une telle ``avalanche''. On trouvera aussi des liens avec le polynôme de Tutte en cliquant ici.

Le second exposé, par Rémi Monasson, était consacré à l'utilisation de méthodes issues de la physique statistique des systèmes désordonnés au problème de la K-satisfiabilité aléatoire. Une analogie entre les booléens et les spins, puis entre la véracité et l'énergie permet de mener des calculs très surprenants par la méthode des répliques dont les résultats sont confirmés par l'expérimentation. Le résumé détaillé d'une version antérieure de cet exposé présentée au séminaire Algo se trouve ici.

• Participations à l'École internationale "Statistical Physics and Theoretical Computer Science" a l'ICTP de Trieste, Aout-September 1999. Des notes introductives au cours principal de P. Flajolet sont disponibles sous le titre: "Random Systems in Combinatorics". Rémi Monasson était membre du comité d'organisation et plusieurs Alcophysiciens (O. Dubois, O. Martin, R. Monasson) ont présenté des communications au Workshop NP-hardness and Phase Transitions suivant l'école.
• Plusieurs exposés du Séminaire ALGORITHMES de l'INRIA pour 1999-2000 sont relatifs a la problématique Alcophys (notamment dans ses relations a la combinatoire analytique). Par exemple: Enumeration of geometric configurations on a convex polygon, by Marc Noy; Counting structures on square grids and Tutte polynomials, by Marc Noy; Some Sharp Concentration Results about Random Planar Triangulations, by Jason Zhicheng Gao; Queues, Stacks, and Transcendentality at the Transition to Chaos, by Cristopher Moore; Colorings, Potts Models, Height Representations, and Entropic Forces, by Cristopher Moore; Coalescence: emergence of the map-Airy law, by Cyril Banderier; Enumeration of planar rooted triangulations, by Jason Zhicheng Gao; Planar Maps and Composition Scehmas, by Gilles Schaeffer.
• Rémi Monasson (ENS) a présenté au Séminaire d'Algorithmique LIX-LRI (21 janvier 1999) un exposé sur "Transition de phase et complexité typique: le modèle de la 2+p-satisfaisabilité aléatoire". Résumé: "Le problème de la K-satisfiabilité (SAT) est d'importance primordiale en théorie de la complexité. Récemment, des travaux numériques et théorique ont mis en évidence l'existence de seuils pour le problème de décision associé à une formule booléenne aléatoire. Nous montrerons comment ce problème, proche des graphes aléatoires orientés, peut être étudié avec les méthodes de physique statistique des sytèmes désordonnés. Une attention particulière sera portée au paramètre d'ordre émergeant lors de cette étude et sur l'information qu'il renferme sur la structure des solutions satisfaisant les formules booléennes considérées. Après avoir introduit le modèle mixte de la 2+p-satisfaisailité, nous soulignerons l'importance fondamentale de la notion d'ordre de la transition de phase, en particulier si l'on s'attache à comprendre pourquoi SAT devient difficile à résoudre autour du seuil SAT/UNSAT."
• Brigitte Vallée a présenté "Systèmes dynamiques et analyse d'algorithmes" au séminaire de Physique théorique de l'IHES le 21 juin 2000. Resumé: " C'est une idée tout à fait naturelle de considérer un algorithme et l'ensemble de ses données comme un système dynamique. Le temps (discret) se confond alors avec le nombre d'itérations de l'algorithme. Les principaux outils classiques des systèmes dynamiques, tel l'opérateur de Ruelle, permettent alors de décrire l'évolution du système au cours du temps et de réaliser l'analyse de divers algorithmes en théorie des nombres et en théorie de l'information."
• Divers membres de l'actions ont travaillé sur le modèle des tas de sables. Voir par exemple: Dominique Gouyou-Beauchamps, Tas de sable et partitions d'entiers (Séminaire d'Algorithmique LIX-LRI, le 6 Mai 1999); Cori (Robert), Rossin (Dominique), and Salvy (Bruno). - Polynomial Ideals for Sandpiles and their Gröbner Bases (rapport de recherche accessible depuis la page de Bruno Salvy, juin 2000).
• Le Séminaire du LPTMS à Orsay explore de nombreuses questions reliées a Alcophys. Par exemple: E. Marinari : Spin Glasses and Other Complex Problems; M. Saraceno : Quantum Computers and Quantum Maps; Paul Zinn-Justin, pzinn@physics.rutgers.edu : Quelques solutions exactes de modèles statistiques sur réseaux aléatoires.
• La page web d'Olivier Martin contient un interessant chapitre intitulé Combinatorial optimization algorithms.
• La page web de Brigitte Vallé présente un ensemble cohérent de travaux sur le thème Systèmes dynamiques et analyse d'algorithmes.
• La page web de Mireille Bousquet-Mélou propose des reprints électroniques de divers problèmes de combinatoire énumerative, incluant animaux, polygones convexes, cartes, partitions, etc.
• La page web de Philippe Flajolet contient des reprints électroniques de travaux en combinatoire analytique et analyse d'algorithmes dont: coalescence, cartes planaires, allocations aléatoires, tables de hachage, arbres digitaux, etc.
• Ludovic Meunier (X) rejoint le Projet ALGO de l'INRIA après un DEA de physique du solide (Orsay) et un stage sur la satisfaisabilité de formules booléennes aléatoires (R. Monasson, ENS).
• La page web de Jerôme Houdayer au LPTMS contient divers articles ainsi que sa thèse sur le thème optimisation combinatoire et systèmes désordonnés.
• Plusieurs membres d'Alcophys participent au programme scientifique et au comité de programme du Colloque: Analysis of Algorithms, AofA'2000
  Krynica Morska, near Gdansk, Poland. July 3-7, 2000 Voir la description et les pointeurs sous: http://algo.inria.fr/AofA/Research/06-00.html. Ce colloque explore plus particulièrement les propriétés des structures combinatoires aléatoires et leurs implications en analyse d'algorithmes.
• Plusieurs membres d'Alcophys participent au programme scientifique et au comité de programme du Colloque: Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities
  University of Versailles-St Quentin (FRANCE) September 18-20, 2000. Voir la page web: http://www.prism.uvsq.fr/complex/confs/mathinfo2000/et le programme scientifique.