Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 4 Décembre 2007

Densité et complexité des arbres balancés

par Nicolas Gast (Laboratoire d'Informatique de Grenoble)

Les mots de Sturm sont des mots infinis qui admettent plusieurs définitions équivalentes: ce sont les mots de complexité minimale, ce sont les mots équilibrés apériodiques et ce sont les mots mécaniques. De plus ces mots ont d'étonnantes propriétés d'optimalité qui peuvent être appliquées aux réseaux.

Une manière naturelle de les généraliser aux arbres est d'étendre la notion de complexité. Ce faisant, on perd les bonnes propriétés des deux autres définitions équivalentes. Une autre manière de généraliser aux arbres binaires infinis est de considérer les arbres non-ordonnés où l'on obtient des résultat intéressants.

À travers cet exposé, nous nous intéresserons à la notion d'arbre où les fils ne sont pas ordonnés infini et tenterons de répondre à diverses questions: qu'est-ce qu'un arbre régulier? Comment définir la densité? Comment définir et caractériser les arbres balancés et mécaniques?

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr