These

Informations

• Publié par: Luzev
• Nombre de lectures: 30
• Langue: Catalan

Extrait

Numérod’ordre:4180
Thèseprésentéepourl’obtentiondu
Doctoratdel’UniversitédesSciencesetTechnologiesdeLille
spécialitéInformatique
Calculsymboliquenoncommutatif:
analysedesconstantesd’arbredefouille
ChristianCOSTERMANS
UniversitédesSciencesetTechnologiesdeLille
Présentéeetsoutenuepubliquementle05juin2008,
Devantlejurycomposéde
Rapporteurs:
Jacky CRESSON, Professeur, UniversitédePau
Gérard DUCHAMP, Professeur, UniversitéParis13
JorisVanDerHOEVEN, ChargédeRechercheCNRS,HDR, UniversitéParis11
Directeur:
HOANG NGOC MINH, Professeur, UniversitéLille2
Examinateurs:
Brigitte VALLÉE, DirectricederechercheCNRS, UniversitédeCaen
Marie-ClaudeVIANO, ProfesseurÉmérite, UniversitéLille1
Sophie TISON, Professeur, UniversitéLille1iiTabledesmatières
Introduction 1
1 Arbreshyperquaternairesdepoints 5
1.1 Récurrencefondamentalepourlesparamètresadditifs . . . . . . . . . . . 7
1.1.1 Probabilitésd’éclatement . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2 Moyennedesparamètresadditifs . . . . . . . . . . . . . . . . . . . 10
1.1.3 Aritédelaracine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Sériesgénératricesettransformation d’Euler . . . . . . . . . . . . . . . . . 13
1.2.1 Analysedesingularités . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Récurrencefondamentale,formeintégrale . . . . . . . . . . . . . . 15
1.2.3 Transformation d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.4 Analyseenmoyennedesparamètresadditifs . . . . . . . . . . . . . 18
1.3 Étudedeladistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.1 Dunombredefeuilles . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.2 D’autresparamètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Quelquesélémentsd’algèbrenoncommutative 23
2.1 Combinatoiredesmots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 MotsdeLyndonetthéorèmedeRadford . . . . . . . . . . . . . . . . . . . 26
2.3 AlgèbresdeLie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Formescrochetéesetbasesduales . . . . . . . . . . . . . . . . . . . 28
2.4 AlgèbresdeHopf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Fonctionspolylogarithmes 33
3.1 Codagedespolylogarithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Relationdemélange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Propriétésdelasériegénératrice . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Desfonctionssymétriquesauxsommesharmoniques 39
4.1 Algèbredessommesharmoniques . . . . . . . . . . . . . . . . . . . . . . . 40
4.1.1 Fonctionssymétriques . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.1.2 Fonctionsquasi-symétriques . . . . . . . . . . . . . . . . . . . . . . 40
iiiiv TABLEDESMATIÈRES
4.1.3 Sommesharmoniquesmultiples . . . . . . . . . . . . . . . . . . . . 42
4.1.4 SériesgénératricessurY . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Analyseasymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Parlasériegénératrice . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.2 Parlaformuled’Euler-MacLaurin . . . . . . . . . . . . . . . . . . . 52
4.2.3 Constantesassociéesàdespolyzêtasdivergents . . . . . . . . . . . 56
4.2.4 Applicationpourl’améliorationdesalgorithmes . . . . . . . . . . . 59
4.2.5 Efficacitéscomparées . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Applications 63
5.1 Auxarbreshyperquaternaires . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.1 Autourdelaracine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.2 Retoursurlesparamètresadditifs . . . . . . . . . . . . . . . . . . . 69
5.2 Auxmaximapourdesdonnéesmultidimensionnelles . . . . . . . . . . . . 74
5.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2.2 ÉquivalentasymptotiquedeVar(K ) . . . . . . . . . . . . . . . . 76n,d
5.2.3 Déterminationdudéveloppementcomplet . . . . . . . . . . . . . . 78
Conclusion 81
A Valeursdesconstantesκ 83d
B ExpressionexactedeVar(K ) 85n,d
C DéveloppementasymptotiquedeVar(K ) 89n,d
Index 100Introduction
"Lesgensquianalysentlesalgorithmesressententunejoiedouble.Ilsex-
périmententd’abordlabeautéd’élégantesstructuresmathématiquesquien-
tourent d’élégantesprocéduresinformatiques. Puisilsreçoiventunerécom-
penseenretourlorsqueleursthéoriesrendentpossiblesderésoudred’autres
problèmesplusrapidementetpluséconomiquement."
Ces lignes, qui constituent un avant-propos du livre "An introduction to the analysis
of algorithms" ([24]), sont dûes à un certain D.E. Knuth, et apparaissent très appro-
priés vis-à-vis de la méthode générale qui nous a guidés au cours de ce mémoire, à
savoir l’application de méthodes symboliques pour l’étude de constantes apparaissant
dans des problèmes de fouille de données aléatoires. En effet, Knuth fut à l’origine de
la popularisation des notations dites “en O," mais regrettait déjà en 1976 [37] la faible
utilisation des notations en Ω et en Θ. Pourtant, dans certains cas, les calculs de com-
plexité moyenne peuvent prendre une forme exacte. Un exemple classique et fonda-
mentaldesuiteparticulièrepermettantdecaractériserunecertainecomplexitéestcelui
des nombres harmoniques d’ordrer ≥ 1,H (N) (ou nombres harmoniques généralisésr
sir≥ 2),
NX 1
H (N) = .r rk
k=1
Ainsi, l’algorithme de tri rapide Quicksort, sur N éléments générés aléatoirement né-
cessite, en moyenne [24], 2(N +1)(H (N +1)−1) comparaisons. De plus, la variance1
2de ce nombre de comparaisons est donné explicitement par 7N − 4(N + 1)H (N)−2
2(N +1)H (N)+13N [38].Autreexemple,dansunarbrebinairederecherchealéatoire,1
le coût moyen d’une recherche infructeuse est 2H (N +1)−2 et la variance de ce coût1
est2H (N +1)−4H (N +1)+2.1 2
Par ailleurs, Euler a utilisé sa formule sommatoire (également découverte par la
12 TABLEDESMATIÈRES
suite,etdemanièreindépendante,parMac-Laurin)pourobtenirlesdéveloppements N k−1X X1 B 1 1j
= logN +γ− +O ,
j kn j N N
n=1 j=1 N k−1X X1 B j 1 1j−r+1
= ζ(r)− +O ,
r j kn j r−1 N N
n=1 j=r−1
où les B sont les nombres de Bernoulli et γ (respectivement ζ(r),r ≥ 2) la constantei
d’Euler-Mac Laurin associée au nombre harmonique divergent H (N) (respectivement1
au nombre harmonique convergent H (N),r ≥ 2) [28]. Ces résultats nous permettentr
d’obtenirdeséquivalents(enréalitédesdéveloppementsaussiprécisquesouhaité)des
βαmoyennesetvariancesprécédentesdansl’échelle,ditedeBertrand,des{N ln (N),α∈
Z,β∈Z},échellequicaractériseunecomplexité“linéaire”,“quasi-linéaire”,“quadrati-
que”,etc.
Récemment, et pour des données multidimensionnelles, l’application de stratégies
diviser pour régner à des algorithmes et des structures de données hiérar-du type
chiquessurlesarbresontconduitplusieursauteursàl’étudedessommesharmoniques
multiples,associéesàunmulti-indice(s ,...,s )[25,40]1 rX 1
H (N) =s ,...,s1 r s1 srn ...n1 rN≥n >...>n >01 r
dont la fonction génératrice ordinaire, P , est une fonction polylogarithme, à uns ,...,s1 r
1
facteur près :
1−z X Li (z)s ,...,sN 1 rP (z) = H (N)z =s ,...,s s ,...,s1 r 1 r 1−z
N≥1
avec
nX 1z
Li (z) = .s ,...,s1 r s1 srn ...n1 rn >...>n >01 r
L’objet du chapitre 1 est de préciser en détail un contexte particulier dans lequel
apparaissentcesobjets,celuidesarbreshyperquaternairesaléatoires,construitsàpartir
dde suites de points dansR . Cette structure, définie par une décomposition récursive
de l’espace, et les paramètres additifs qui lui sont liés (nombre de feuilles, de noeuds
à 1 enfant, longueur de cheminement) ont déjà fait l’objet de nombreuses publications
[44, 22, 40, 8], et les techniques utilisées (tout du moins pour des arbres en dimension
d ≥ 3) font appel à des techniques d’analyse complexe, plus précisément d’analyse de
singularités,dontnousrappelonslesgrandeslignesensection1.2.1page14.
Tandis que le chapitre 2 constitue un survol de la combinatoire des mots - qui va
constituer l’ossature de notre approche symbolique des quantités rencontrées au cha-
pitre précédent-, etnous permetde présenterlesproduits de mélangeetlesstructuresTABLEDESMATIÈRES 3
algébriques associées, i.e. les algèbres de mélange, qui interviennent dans les relations