|
|
|
|
|
Algorithms |
|
Project |
 |
|
INRIA |
|
|
|
|
Page de Philippe Dumas
Diviser pour régner |
Maple |
Livres
Publications |
Adresse |
English version
L'adage politique divide ut imperes est devenu une
stratégie fondamentale de l'algorithmique; elle apparait aussi
bien dans la multiplication de polynômes que dans des algorithmes
de tri ou dans la recherche d'enveloppes convexes. Dans chaque cas une
notion naturelle de taille amène à considérer le
coût de l'algorithme employé; on voit ainsi émerger des
suites définies par des
récurrences dites de type diviser
pour régner dans lesquelles le coût pour une donnée
d'une certaine taille dépend du coût pour une donnée de
taille moitié. La qualité des algorithmes concernés
dépend du comportement asymptotique de telles suites et
l'étude de ce comportement s'avère donc être un
problème essentiel dans ce contexte.
|
Table des matières
|
| |
Le nombre de 1 dans l'écriture binaire d'un entier fournit une
suite 2-rationnelle.
|
|
Après une introduction sur la stratégie diviser pour régner et
les récurrences associées,
nous nous concentrons ici sur une classe particulière de suites, les
suites 2-rationnelles, dont la définition est
récente et qui recouvre beaucoup de
récurrences diviser pour régner rencontrées en algorithmique.
Ces suites ont une structure algébrique riche liée à la
numération binaire et aux séries rationnelles de la théorie des
langages formels. En particulier une notion fondamentale est celle de
représentation linéaire; elle généralise le lien classique
entre puissances d'une matrice et récurrence linéaire à
coefficients constants. Une conséquence facile de cette notion est
le comportement de type polynomial des suites complexes 2-rationnelles.
Pour poursuivre l'étude asymptotique de ces suites on peut sur des
exemples simples employer des techniques élémentaires, mais pour
obtenir des résultats profonds il est nécessaire de recourir à
des méthodes sophistiquées qui proviennent de la théorie
analytique des nombres. La formule de Perron appliquée à la
série de Dirichlet associée à la suite permet, dans les bons
cas, de mettre en valeur de subtiles oscillations en échelle
logarithmique.
