Algorithmique et Combinatoire

  Maurice Margenstern (UPVM, LITA, Metz) ,  
  Titre : Automates cellulaires dans le plan hyperbolique : dix ans après. (pdf de la présentation)
  Résumé :
Dans cet exposé, on présente les recherches menées depuis 1998 sur l'implantation d'automates cellulaires dans le plan  hyperbolique. Ces recherches sont fondées sur une approche combinatoire de la géométrie hyperbolique. Elles ont obtenu des résultats intéressants et, de plus, elles ont eu des retombées certaines sur l'étude des pavages de ce plan, ce qui sera aussi abordé. Comme ces recherches avaient également pour but de construire des automates cellulaires universels avec le plus petit nombre d'états possibles, cette question sera également abordée.
 

 Julien Bernat (UHP, IECN)
  Titre :   Langages substitutifs et paires équilibrées irréductibles (pdf de la présentation)
  Résumé :
Sous des hypothèses algébriques, certains systèmes dynamiques symboliques engendrés par des substitutions admettent une représentation géométrique. On peut alors établir des liens entre des propriétés de nature combinatoire, topologique ou ergodique, et formuler de nombreuses questions encore non résolues.
Dans cet exposé, nous nous intéressons principalement à l'étude de propriétés combinatoires. Après avoir rappelé les notions utiles à l?étude de systèmes substitutifs, nous montrerons comment l'étude d'un algorithme en combinatoire des mots permet d'obtenir des informations utiles pour tenter de répondre aux questions ouvertes précédemment introduites.
 

 Eric Domenjoud (CNRS, LORIA, Equipe ADAGIo)
  Titre : Dénombrement de motifs dans les plans discrets naïfs (pdf de la présentation)
  Résumé :
Nous nous intéressons au dénombrement de motifs rectangulaires de taille m x n dans les plans discrets naïfs. Le plan discret naïf de vecteur normal (a,b,c) et de décalage mu est défini dans Z^3 par la double inégalité 0 <= a*x+b*y+c*z + mu < max(|a|,|b|,|c|). Le seul résultat de dénombrement connu dans ce domaine jusqu'à récemment est une formule close établie en 1988 pour le nombre de segments de droites discrètes de longueur donnée. En utilisant un codage adapté, nous établissons une formule close pour le nombre de motifs de dimension 2 x n dans les plans discrets. Nous donnons également des pistes pour le cas général, c'est à dire la détermination du nombre de motifs de taille m x n.
 

 Philippe Chassaing (UHP, IECN)
  Titre :   Factorisation des mots aléatoires et riffle-shuffle (pdf de la présentation)
  Résumé :
On reliera le comportement asymptotique de la factorisation de Lyndon des mots aléatoires au riffle shuffle et à la distribution de Poisson-Dirichlet, généralisant ainsi des travaux de Arratia, Barbour, Tavare, Hansen, Diaconis, Pitman.
 

  Valérie Berthé (CNRS, LIAFA, Paris) ,  
  Titre :  Plans discrets et pavages (pdf de la présentation)
  Résumé :
Les plans arithmétiques discrets sont obtenus en sélectionnant des points à coordonnées entières situés à une  certaine distance (épaisseur)  d'un plan  euclidien donné. Ce sont  des modèles de quasicristaux simples mais aux propriétés combinatoires, arithmétiques et dynamiques  intéressantes. Ces primitives de la géométrie discrète entretiennent  de plus des liens étroits avec les  pavages.
Le but de cet exposé est de montrer comment ces deux  points du vue sur les plans discrets (quasicristaux et pavages)  permettent  de  décrire de nombreuses de leurs  propriétés ainsi que  d'établir des algorithmes d'engendrement ou de reconnaissance, même   dans le   cas  d'une  épaisseur quelconque.

 Régine Marchand (UHP, IECN)
  Titre : Théorèmes de forme asymptotique pour processus de croissance aléatoire (pdf de la présentation) (fichier avi démo. 42 Mo)
  Résumé :
Nous allons voir, sur trois exemples, comment la recherche d'un théorème de forme asymptotique pour un modèle de croissance aléatoire est étroitement liée à la recherche d'une fonctionnelle ayant de bonnes propriétés de sous-additivité ainsi qu'à l'application d'un théorème ergodique sous-additif adapté.