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 9 Février 2016

Suites équilibrées de faible complexité et algorithmes de fractions continues multidimensionnelles

par Sébastien Labbé (Université de Liège, Belgique)

Étant donné un vecteur de densité, i.e., un vecteur de d nombres réels positifs dont la somme est 1, peut-on construire un mot infini sur un alphabet à d lettres dont le vecteur des fréquences des lettres soit bien défini et égal au vecteur de densité choisi? Comment construire de tels mots le plus simplement possible? Cette question a des applications en géométrie digitale, mais aussi pour la planification de tâches Just in time.

En dimension deux, la question est complètement résolue par les mots sturmiens. Toutefois, la généralisation de leur construction en dimension supérieure n'est pas canonique et les généralisations les mieux connues (orbites d'échanges d'intervalles, mots de billard) ne préservent pas toutes les bonnes propriétés des mots sturmiens. Nous expliquerons en quoi les algorithmes de fractions continues multidimensionnelles permettent de répondre à cette question.

Dans la deuxième partie et si le temps le permet, nous présenterons quelques résultats d’expérimentation menant à la création d’un algorithme de fractions continues multidimensionnelles appelé Arnoux-Rauzy-Poincaré qui est une sorte de fusion entre deux algorithmes (celui de Poincaré et celui des substitutions d'Arnoux-Rauzy). Nous présenterons quelques résultats sur cet algorithme, concernant notamment la complexité en facteurs des suites produites.

Nous terminerons avec une question ouverte sur la notion de bon algorithme de fractions continues multidimensionnelles.

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