Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Doctoral studies

Thesis of

Christian Costermans

Thursday 5 June 2008

Calcul symbolique non commutatif : analyse des constantes d'arbre de fouille

L'étude de certaines variables aléatoires, comme l'arité de la racine d'un arbre hyperquaternaire de points, ou des paramètres additifs sur ces mêmes arbres, ou encore le nombre de maxima au sein d'un ensemble de n points indépendants, et uniformément distribués dans [0,1]d font apparaître des suites particulières, les sommes harmoniques multiples (SHM), extensions des nombres harmoniques classiques à des multi-indices s.
Nos travaux visant à appliquer des méthodes symboliques pour l'étude de ces variables aléatoires, nous troquons l'utilisation des multi-indices contre un codage par des mots, et nous appuyons alors sur des résultats importants dans le domaine de la combinatoire des mots, comme l'existence d'une base pour les algèbres de mélange, que nous appliquons à des fonctions spéciales, les polylogarithmes - qui vérifient une relation de mélange pour le produit classique shuffle - et à nos suites spéciales de SHM – qui vérifient une relation de mélange pour un autre produit, le stuffle -. Dans les cas convergents, les deux objets convergent (respectivement lorsque z tend vers 1 et lorsque N tend vers l'infini) vers la même limite, nommé polyzêta.
Pour les cas divergents, l'utilisation de séries génératrices non commutatives nous permet d'établir, par des techniques `à la Hopf' un théorème `à l'Abel', faisant apparaître comme limite commune la série génératrice des polyzêtas convergents. Ce théorème nous permet de donner une forme explicite aux constantes d'Euler généralisées associées à des SHM divergentes, autrement dit les constantes intervenant dans le développement asymptotique de ces sommes dans l'échelle de Bertrand, et ainsi d'obtenir un algorithme très efficace pour calculer ce développement. Cet algorithme est comparé à deux autres approches : la première fondée sur le développement singulier de la série génératrice des SHM (qui est en fait une fonction polylogarithmique) au voisinage de z=1 ; la seconde construite sur l'isomorphisme entre l'algèbre des SHM et l'algèbre de mélange pour le produit stuffle, qui permet de ramener des problèmes sur ces sommes à des problèmes sur les mots.
Finalement, nous proposons des applications des sommes harmoniques dans le domaine des structures de données multidimensionnelles, pour lesquelles notre approche donne naissance à des calculs exacts, qui peuvent par la suite être aisément évalués asymptotiquement.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster