L’Ansatz cellulaire deux exposés au Séminaire Algo INRIA, Rocquencourt, 2 Mars 2009 résumé: Le mot Ansatz, venant de l'allemand et signifiant début, naissance ou racine, est un terme souvent utilisé par les physiciens comme une supposition qui marche (par exemple: Ansatz de Bethe, Ansatz matriciel). Dans ces deux exposés, je propose d'introduire une méthodologie permettant de construire "automatiquement" des bijections à partir de relations algébriques. Jusqu'à présent, l'unique exemple était la classique correspondance RSK (Robinson-Schensted-Knuth) entre les permutations et les paires de tableaux de Young de même forme. Cette bijection peut se définir sous diverses formes équivalentes (insertion de Schensted, version géométrique par ombres et lumières," jeu de taquin" de M.P.Schützenberger, etc.). S. Fomin en a donné une version "cellulaire" avec des règles locales sur une grille carrée pour ses "diagrammes de croissance". L'idée est de définir deux opérateurs U et D sur les diagrammes de Ferrers vérifiant la relation de commutation UD=DU+Id. En "planarisant" les calculs dans l'algèbre engendrée par U et D par des réécritures sur une grille, et en "propageant" l'interprétation combinatoire de la relation de commutation attachée à chaque cellule de la grille, on peut retrouver la construction de Fomin et ainsi la correspondance RSK. Après avoir rappelé cet exemple basique, j'en construirai un nouveau: une bijection entre les permutations et les tableaux appelés "alternatifs". Ici la relation de commutation de départ est la relation DE=ED+E+D. Cette relation est à la base de la résolution (c'est le "matrix Ansatz" de B.Derrida et ses coauteurs) du modèle appelé PASEP en physique des systèmes dynamiques (ou "partially asymmetric exclusion process"). Les tableaux alternatifs ont été introduit par l'orateur, comme une variante symétrisée plus agréable des "tableaux à permutations" introduits par A.Postnikov, E.Steingrimsson et L.Williams à partir de considérations de géométrie algébrique.  Je montrerai comment construire une bijection entre les permutations et ces tableaux alternatifs, avec la même philosophie "cellulaire" que pour RSK,  à partir d'une représentation combinatoire des opérateurs D et E.  Cette représentation est basée sur des recherches entreprises en informatique par J. Françon, P. Flajolet et J.Vuillemin il y a une trentaine d'années: la notion d'  "histoires de structures de données" pour le calcul de coûts intégrés. Ici nous aurons besoin de la structure "dictionnaire"' et de la bijection FV