JOURNEE ALGORITHMIQUE, COMBINATOIRE & PHYSIQUE (ALCOPHYS) (Premiere annonce) Le JEUDI 14 DECEMBRE 2000 de 11h00 a 17h30 A l'I.H.P. (Salle 5, Institut Henri Poincare', Paris V) >>>> http://algo.inria.fr/Alcophys <<<< Ces journees de synthese ALCOPHYS sont organisees par l'Action de Recherche Cooperative (INRIA). Elles ont ouvertes a tous les chercheurs interesse's par ces questions. Huit exposes de 30 minutes chacun seront presentes. ====================================================================== 10h45 ACCUEIL (R. Cori) 11h00 a 12h00 Philippe Flajolet et Robert Cori P. FLAJOLET (INRIA-Rocquencourt) COMBINATOIRE ANALYTIQUE, ANALYSE d'ALGORITHMES et ALCOPHYS. L'objectif est ici la quantification de l'alea discret par methodes analytiques. Les applications principales se situent en combinatoire et en analyse d'algorithmes. Il est prevu d'examiner ainsi sous l'angle analytique le comportement de divers objets combinatoires tels: les cartes aleatoires (d'apres Banderier Soria & Schaeffer), les graphes aleatoires (approche par cols coalescents d'apres Flajolet-Salvy-Schaeffer), les arbres digitaux et systemes dynamiques (Vallee et al.), les mots et sous-sequences dans les mots, les diagrammes de cordes, etc. ------------------------------- R. CORI (Labri, Bordeaux et LIX, Palaiseau) ALGORITHMIQUE et COMBINATOIRE DANS LE MODELE DU TAS DE SABLE Apre`s une rapide introduction sur le mode`le et les raisons de son succe`s dans le contexte des phe'nome`nes critiques auto-organise's on fera le point sur quelques re'sultats obtenus re'cemment. Il s'agit d'une part de la de'finition d'un ide'al de polyno^mes et l'utilisation d'une re'duction a` l'aide d'une base de Gro"bner pour le calcul de l'identite' du groupe (travail commun RC, Dominique Rossin, Bruno Salvy). Un autre re'sultat est une bijection entre les configurations re'currentes de hauteur k et les arbres recouvrants d'activite' k; ceci explique que le polynome ge'ne'rateur des configurations re'currentes suivant leur hauteur soit une spe'cialisation du polyno^me de Tutte du graphe sous-jacent (re'sultat d'Yvan Le Borgne). ======================================================================= ***************************************************** * 12h15 a 13h45 * * REPAS, BISTROTS, CIGARETTES, etc... * ***************************************************** ========================================================================== 13h45 a 14h45 Mireille Bousquet-Melou/Philippe Duchon et William Orrick Mireille BOUSQUET-MELOU (Labri, Bordeaux) et Philipe DUCHON (Labri, Bordeaux) COMBINATOIRE ENUMERATIVE A BORDEAUX Nous donnerons une prM-isentation gM-inM-irale des activitM-is bordelaises dans le domaine d'AlCoPhys, et plus spM-icialement de la combinatoire et physique. Nos rM-isultats portent notamment sur l'M-inumM-iration d'objets discrets reliM-is M-` la physique statistique (chemins sur une grille, chemins auto-M-ivitants, animaux), et sur les caractM-iristiques statistiques des objets de grande taille (lois limites pour la distribution de certains paramM-htres). Cet expose' general resumera les activites en combinatoire enumerative du groupe bordelais. ------------------------------- William ORRICK (Melbourne et Bordeaux) ON THE SUSCEPTIBILITY OF THE ISING MODEL The Ising model has long been the premiere vehicle for the mathematical understanding of phase transitions in physical systems, and many quantities have been computated exactly for the two-dimensional version. Nevertheless, the susceptibility has resisted solution. A long-ignored set of partial difference equations has recently been put to use in computing very long series expansions for the susceptibility. Analyses of these series have overturned some long-held beliefs concerning the behavior of the model at its critical point, and revealed the source of the difficulty in finding an exact expression. ======================================================================= 15h00 a 16h00 Brigitte Vallee et Jean-Paul Allouche B. VALLEE (Greyc, Caen) SYSTEMES DYNAMIQUES ET ANALYSE D'ALGORITHMES. On montrera l'application des systemes dynamiques et de l'analyse fonctionnelle (notamment, operateurs de transfert) a divers domaines de l'analyse d'algorithmes. Les progres recents concernent des domaines a priori non relies, tels: les algorithmes arithmetiques (e.g, complexite en bit du pgcd d'Euclide, algorithmes du symbole de Jacobi), la theorie de l'information, (sources dynamiques et entropie, complexite'), ainsi que les modeles et algorithmes de traitement de donnees textuelles (structures de donnees, arbres digitaux). ------------------------------- Jean-Paul Allouche (CNRS, LRI) ÉQUATION DISCRÈTE de SCHRÖDINGER À UNE DIMENSION ET PALINDROMES Inspirés en particulier par la découverte des quasi-cristaux binaires les physiciens s'intéressent à l'équation de Schrödinger discrète à une dimension. On peut se représenter par exemple une chaîne de ressorts identiques, séparés par des masses de deux types. Il se trouve que des propriétés combinatoires de la suite des potentiels (ou de la suite des masses entre les ressorts) donnent des indications pour l'étude du spectre de l'opérateur de Schrödinger (ou pour les vibrations propres du système masses-ressorts). En particulier un résultat de Hof, Knill et Simon dit essentiellement que le spectre de l'opérateur de Schrödinger est singulier continu si cette suite est uniformément récurrente et contient des palindromes arbitrairement longs. Nous présentons un récent travail en commun avec M. Baake, J. Cassaigne et D. Damanik, motivé par ce qui précède, et consacré à l'étude de la complexité palindromique des suites infinies sur un alphabet fini. ========================================================================== 16h15-17h15 Claire Kenyon et Dominique Poulalhon COMBINATOIRE ET ANALYSE PROBABILISTE D'ALGORITHMES. Claire KENYON (LRI, Orsay) Je resumerai tout d'abord les problemes sur lesquels les chercheurs d'Orsay ont travaille: composante geante de graphes aleatoires, graphes d'intervalles aleatoires, 2 sat et min 2 sat, piles de sable, animaux diriges, modele de Bak-Sneppen, dynamique de Glauber pour le modele d'Ising, spin glass. Puis je parlerai d'analyse probabiliste d'algorithmes de bin-packing et bin-covering. ------------------------------- Dominique POULALHON (LIX, Palaiseau) Bisuites de parking ou Configurations rM-icurrentes dans les graphes bipartis complet. Les suites de parking se sont rM-ivM-ilM-ies M-jtre au centre de diffM-irents problM-hmes combinatoires. Nous introduisons ici des couples de suites d'entiers dont la dM-ifinition est voisine de celle des suites de parking, que nous nous proposons d'appeler {\em bisuites de parking}. Nous en donnons une interprM-itation imagM-ie, tirM-ie de la constitution d'une liste de candidats pour un scrutin. Les suites de parking peuvent d'autre part M-jtre considM-irM-ies comme les configurations rM-icurrentes dans un automate du tas de sable sur le graphe complet; nous montrons que les suites de parking biparties correspondent aux configurations rM-icurrentes sur le graphe biparti complet auquel on a ajoutM-i un puits reliM-i M-` tous les sommets. Ceci nous permet d'en donner une formule d'M-inumM-iration. =========================================================================== 17h15-17h30 DISCUSSIONS ET FIN DE LA JOURNEE (POT?) ****************************************** CONTACT: Philippe.Flajolet@inria.fr LIEU: Salle 5, Institut Henri Poincaré; 11, rue Pierre et Marie Curie, 75231 Paris Cedex 05 (http://www.ihp.jussieu.fr/), RER Luxembourg. SITE INTERNET: http://algo.inria.fr/Alcophys (pour details et mises a jour) NOTER EGALEMENT: Journee du 18/12/2000 a l'X (cf http://algo.inria.fr/Alcophys).