Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 08 novembre 2011 à 14h30 en B311, Patrick Dehornoy nous parlera de : Sur la distance de rotation entre deux arbres binaires

Résumé : Le problème est de construire des arbres binaires éloignés vis-à-vis de la distance de rotation, ce qui équivaut à construire des expressions parenthésées éloignées vis-à-vis de l'associativité, ou encore des triangulations de polygone éloignées vis-a-vis de l'échange de diagonales. On présentera la magnifique solution de Sleator-Tarjan-Thurston basée sur la géométrie hyperbolique, qui est optimale mais valable seulement pour une taille assez grande (non effective), ainsi qu'une méthode combinatoire basée sur une notion de séparatrice dans les associaèdres, qui est (pour le moment) non optimale, mais valable pour toute taille.

 [Slides.pdf]


Dernière modification : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr