Sujet de ma thèse
Titre de la thèse :
Distribution de valuations sur les arbres.
Sujet
On peut représenter une expression arithmétique
par un arbre étiqueté, de telle manière
qu'aux nœuds internes se trouvent des opérateurs,
et qu'aux feuilles, ou nœuds externes, se trouvent des nombres.
La valuation de l'arbre est le résultat de
l'expression arithmétique correspondante. Si on parcourt
l'arbre dans l'ordre infixe, on l'écriture polonaise
infixe de l'expression arithmétique.
La taille n d'un arbre étant le nombre de ses
nœuds internes, soit En l'ensemble des
arbres de taille
n correctement étiquetés par des jeux de nombres
et d'opérateurs bien fixés, e.g.
{+,-} et {0,1}. Dans l'espace En, je
considère la valuation des arbres comme une variable
aléatoire Xn. J'étudie
la loi P(Xn=k) et je cherche la distribution-limite
de Xn pour n tendant vers l'infini.
Cas déjà traités
Opérateurs {+,-} : loi-limite gaussienne, car jeu de pile
ou face généralisé ;
Opérateurs {-} : loi-limite gaussienne, via
le théorème des quasi-puissances de Hwang.
Notons l'intervention
des nombres de Narayana, dénombrant e.g. le nombre
d'arbres généraux selon leur taille et leur nombre
de feuilles.
Perspectives
L'énergie de repliement d'une molécule d'ARN
peut s'exprimer grosso modo par un arbre d'expression
arithmétique avec opérateurs {+,×}. Il s'agit
donc d'étudier ce jeu d'opérateurs, pour pouvoir
prévoir la forme des molécules d'ARN.
En parallélisme, l'étude des jeux d'opérateurs
{max,+}, {min,+}, ou de fonctions
min-max-plus plus générales,
peut se montrer utile. Stéphane Gaubert, de l'INRIA
Rocquencourt, m'aide à définir plus
précisément les applications possibles.
On peut aussi regarder des arbres d'expressions rationnelles,
issues de la théorie des langages.
Deux directions s'offrent à nous :
- Selon Cyril Nicaud,
qui sera scientifique du contingent au LIX l'an prochain,
la valuation peut servir à discriminer certains algorithmes
associés à ces expressions rationnelles.
- Les
travaux d'Allemands tels que Henning Fernau
interprètent
la valuation d'une expression rationnelle décrivant une
fractale, comme la dimension de Hausdorff de cette fractale.
Étudier la distribution de la valuation pourrait aider
à la génération aléatoire de fractales
ayant une dimension Hausdorff donnée, ou tout du moins
appartenant à un certain intervalle.