JOURNÉE ALGORITHMIQUE,
COMBINATOIRE & PHYSIQUE
Dernière modification le 12 décembre 2000.
Le JEUDI 14 DÉCEMBRE 2000
À l'I.H.P, Salle 5
(Institut Henri Poincaré Paris V)
http://algo.inria.fr/Alcophys
Les journées de synthèse ALCOPHYS sont
organisées par l'Action de Recherche Coopérative ALCOPHYS
(INRIA). Elles sont ouvertes à tous les chercheurs de la communauté
intéressés par ces questions.
Huit exposés de 30 minutes chacun seront présentés.
=========================================================================
10h45 ACCUEIL (Robert Cori)
=========================================================================
11h00 à 12h00 Philippe Flajolet et Robert Cori
Philippe FLAJOLET (INRIA-Rocquencourt)
COMBINATOIRE ANALYTIQUE, ANALYSE D'ALGORITHMES ET ALCOPHYS
L'objectif est ici la quantification de l'aléa discret
par méthodes analytiques. Les applications principales se situent
en combinatoire et en analyse d'algorithmes. Il est prévu d'examiner
ainsi sous l'angle analytique le comportement de divers objets combinatoires
tels : les cartes aléatoires (d'après Banderier, Soria et
Schaeffer), les graphes aléatoires (approche par cols coalescents
d'après Flajolet, Salvy et Schaeffer), les arbres digitaux et systèmes
dynamiques (Vallée et al.), les mots et sous-séquences dans
les mots, les diagrammes de cordes, etc.
-------------------------------
Robert CORI (LaBRI, Bordeaux et Lix, Palaiseau)
ALGORITHMIQUE ET COMBINATOIRE DANS LE MODELE DU TAS DE SABLE
Après une rapide introduction sur le modèle et
les raisons de son succès dans le contexte des phénomènes
critiques auto-organisés on fera le point sur quelques résultats
obtenus récemment. Il s'agit d'une part de la définition
d'un idéal de polynômes et l'utilisation d'une réduction
à l'aide d'une base de Gröbner pour le calcul de l'identité
du groupe (travail commun RC, Dominique Rossin, Bruno Salvy). Un autre
résultat est une bijection entre les configurations récurrentes
de hauteur k et les arbres recouvrants d'activité k; ceci explique
que le polynôme générateur des configurations
récurrentes suivant leur hauteur soit une spécialisation
du polynôme de Tutte du graphe sous-jacent (résultat
d'Yvan Le Borgne).
=========================================================================
12h15 à 13h45 REPAS, BISTROTS, CIGARETTES, etc...
=========================================================================
13h45 à 14h45 Mireille Bousquet-Mélou/Philippe
Duchon et William Orrick
Mireille BOUSQUET-MÉLOU et Philippe DUCHON (LaBRI, Bordeaux)
LA COMBINATOIRE ÉNUMÉRATIVE À BORDEAUX
Nous donnerons une présentation générale des
activités bordelaises dans le domaine d'AlCoPhys, et plus
spécialement de la combinatoire et physique. Nos
résultats portent notamment sur l'énumération
d'objets discrets reliés à la physique statistique
(chemins sur une grille, chemins auto-évitants, animaux), et
sur les caractéristiques statistiques des objets de grande
taille (lois limites pour la distribution de certains
paramètres).
Cet exposé général résumera les
activités en combinatoire énumérative du groupe
bordelais.
-------------------------------
William ORRICK (Melbourne et LaBRI, 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 à 16h00 Brigitte Vallée et Jean-Paul Allouche
Brigitte VALLÉE (Greyc, Caen)
SYSTÈMES DYNAMIQUES ET ANALYSE D'ALGORITHMES
On montrera l'application des systèmes dynamiques et de
l'analyse fonctionnelle (notamment, opérateurs de transfert) à
divers domaines de l'analyse d'algorithmes. Les progrès récents
concernent des domaines divers et à priori non reliés, tels
: les algorithmes arithmétiques (e.g, complexité en bit du
pgcd d'Euclide, algorithmes du symbole de Jacobi), la théorie de
l'information et les modèles de données textuelles (sources
dynamiques et entropie, complexité, structures de données,
arbres digitaux).
-------------------------------
Jean-Paul Allouche (CNRS, LRI, Orsay)
É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
Claire KENYON (LRI, Orsay)
COMBINATOIRE ET ANALYSE PROBABILISTE D'ALGORITHMES
Je résumerai tout d'abord les problèmes sur lesquels
les chercheurs d'Orsay ont travaillé : composante géante
de graphes aléatoires, graphes d'intervalles aléatoires,
2 sat et min 2 sat, piles de sable, animaux dirigés, modèle
de Bak-Sneppen, dynamique de Glauber pour le modèle 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 RÉCURRENTES
DANS LES GRAPHES BIPARTIS COMPLET
Les suites de parking se sont révélées être
au centre de différents problèmes combinatoires. Nous introduisons
ici des couples de suites d'entiers dont la définition est voisine
de celle des suites de parking, que nous nous proposons d'appeler bisuites
de parking. Nous en donnons une interprétation imagée,
tirée de la constitution d'une liste de candidats pour un scrutin.
Les suites de parking peuvent d'autre part être considérées
comme les configurations récurrentes dans un automate du tas de
sable sur le graphe complet; nous montrons que les suites de parking biparties
correspondent aux configurations récurrentes sur le graphe biparti
complet auquel on a ajouté un puits relié à tous les
sommets. Ceci nous permet d'en donner une formule d'énumération.
=========================================================================
17h15 à 17h30 DISCUSSIONS ET FIN DE LA JOURNÉE (POT?)
******************************************
CONTACT: Philippe.Flajolet@inria.fr
LIEU: Salle 5
Institut Henri Poincaré
11, rue Pierre et Marie Curie
75231 Paris Cedex 05
Téléphone : 01 44 27 67 89
Télécopie : 01 43 25 40 67
http://www.ihp.jussieu.fr/
RER Luxembourg
SITE INTERNET: http://algo.inria.fr/Alcophys (pour détails et
mises à jour)
NOTER EGALEMENT: La journée thématique du 18 décembre
à Palaiseau
(accès à partir de http://algo.inria.fr/Alcophys).