Diviser pour régner
Complexité et récurrences 		D&C logo

Page de Philippe Dumas
Diviser pour régner | Maple | Livres
Publications | Adresse | English version

hline

Introduction
Une idée fondamentale
Complexité et récurrences
Suites 2-rationnelles
Comportement asymptotique
Références

Dans chacun des exemples que nous venons de rencontrer (cf. Une idée fondamentale) une notion naturelle de taille des données intervient. La taille d'une liste est sa longueur; la taille d'un polynôme est son degré; la taille d'un nuage de points est le nombre de ses points. D'autre part une notion de coût d'un algorithme apparaît tout aussi naturellement. Pour un algorithme de tri ce sera le nombre de comparaisons effectuées ou le nombre d'affectations; pour un algorithme de multiplication de matrices ou de polynômes ce sera le nombre de multiplications scalaires effectuées. Ce coût dépend de la donnée mais il est normal de le voir comme une simple fonction de la taille de celle-ci; cette réduction amène à distinguer le coût dans le cas le pire, le coût moyen et parfois le coût dans le cas le meilleur.

Récurrences diviser pour régner. Revenons sur le tri-fusion; la donnée est une liste de taille n et le coût est compté en nombre de comparaisons. Selon la stratégie diviser pour régner le coût pour une donnée de taille n est la somme du coût pour une donnée de taille $\lfloor n/2\rfloor$ et du coût pour une donnée de taille $\lceil n/2\rceil$ augmentée du coût de la fusion. Dans le cas le pire la fusion demande n-1 comparaisons, comme on le voit en considérant les deux listes triées $(1,2,\ldots,k-1,n)$ et $(k,\ldots,n-1)$ avec $k=\lfloor n/2\rfloor$. Le coût Tn du tri-fusion sur une donnée de taille n dans le cas le pire satisfait donc la récurrence

\begin{displaymath} T_n=T_{\lfloor n/2\rfloor}+T_{\lceil n/2\rceil}+n-1\quad\text{pour $n\geq2$},\qquad T_0=T_1=0. \end{displaymath}

On peut montrer [16] que le coût Un du tri-fusion dans le cas moyen satisfait

\begin{displaymath} U_n=U_{\lfloor n/2\rfloor}+U_{\lceil n/2\rceil}+n- \frac{\lf... ...loor n/2\rfloor+1} \quad\text{pour $n\geq2$},\qquad U_0=U_1=0. \end{displaymath}

Cette formule est établie en supposant que les clés à trier sont les entiers de 1 à n et que toutes les permutations des entiers de 1 à n sont équiprobables.

Les récurrences du type précédent en n et n/2 mérite le nom de récurrence diviser pour régner. Cependant avant d'aller plus loin il faut remarquer que les algorithmes diviser pour régner ne conduisent pas nécessairement à des récurrences diviser pour régner. Par exemple le coût moyen Cn du tri rapide sur une liste de taille n satisfait (cf. [25, p.120] ou [33, p. 129])

\begin{displaymath} C_n=(n+1)+\frac{2}{n}\sum_{0\leq k<n}C_k\quad\text{pour $n\gt 1$},\qquad C_0=C_1=0.\end{displaymath}

Nous ne considérons dans la suite que des récurrences diviser pour régner.

Séries génératrices. Pour formaliser les suites diviser pour régner il est plus agréable de considérer la série génératrice ordinaire

\begin{displaymath} f(z)=\sum_{n\geq0}f_nz^n\end{displaymath}

d'une telle suite (fn). De plus il est pratique de faire la convention suivante : une suite (fn) est étendue à tous les réels par la formule

\begin{displaymath} f_x= \begin{cases} f_n&\text{si $x=n$\space entier naturel},\\ 0&\text{sinon}.\end{cases}\end{displaymath}

Les deux opérations sur les suites que sont le décalage et l'homothétie

\begin{displaymath} (f_n)\longmapsto (f_{n-1}),\qquad (f_n)\longmapsto (f_{n/2})\end{displaymath}

se traduisent sur les séries formelles associées en les opérations linéaires

\begin{displaymath} f(z)\longmapsto zf(z),\qquad f(z)\longmapsto f(z^2).\end{displaymath}

On dit qu'une série formelle f(z) est mahlérienne si elle satisfait une équation

\begin{displaymath} c_0(z)f(z)+c_1(z)f(z^2)+\dotsb+c_N(z)f(z^{2^N})=0\end{displaymath}

dans laquelle les ck(z) sont des polynômes non tous nuls. La traduction en termes de suite fournit la définition des suites mahlériennes; une telle suite (fn) satisfait une récurrence de la forme

\begin{displaymath} \sum_{\ell}c_{0,\ell}f_{n-\ell}+\sum_{\ell}c_{1,\ell}f_{(n-\ell)/2}+\dotsb +\sum_{\ell}c_{N,\ell}f_{(n-\ell)/2^{\ell}}=0,\end{displaymath}

dans laquelle les sommes ne comportent qu'un nombre fini de termes et les $c_{k,\ell}$ sont non tous nuls. On parle de série mahlérienne en l'honneur de Kurt Mahler. En effet celui-ci a étudié la suite (bn) du nombre de partitions binaires du point de vue asymptotique [29]; précisons qu'une partition de l'entier n est binaire si tous ses sommants sont des puissances de 2 par exemple

27=1+1+1+2+2+4+8+8

est une partition binaire de 27. La suite (bn) satisfait la récurrence

\begin{displaymath} b_n=b_{n-1}+b_{n/2},\qquad b_0=1,\end{displaymath}

ou encore

\begin{displaymath} b_{2k}=b_{2k-1}+b_k,\qquad b_{2k+1}=b_{2k},\qquad b_0=1.\end{displaymath}

De façon équivalente sa série génératrice

\begin{displaymath} b(z)=\prod_{k\geq0}\frac{1}{1-z^{2^k}}\qquad\text{satisfait}\qquad (1-z)b(z)=b(z^2).\end{displaymath}

Il a aussi étudié [30] des problèmes de transcendance liés à des séries comme

\begin{displaymath} f(z)=\sum_{k\geq0}z^{2^k}\qquad\text{qui satisfait}\qquad f(z)=z+f(z^2).\end{displaymath}

On pourrait généraliser la définition en considérant des équations en f(z) et f(zB) où B est un entier au moins égal à 2 mais les résultats qualitatifs sont du même type que pour B=2 et le cas B=2 est de loin le plus courant dans les applications.


On a ainsi défini une classe de séries qui satisfait les propriétés de clôture suivantes :

-
les séries rationnelles sont mahlériennes;
-
si une série satisfait une équation avec second membre

\begin{displaymath} c_0(z)f(z)+c_1(z)f(z^2)+\dotsb+c_N(z)f(z^{2^N})=b(z)\end{displaymath}

dans laquelle b(z) est mahlérienne, elle est elle même mahlérienne;
-
la somme de deux séries mahlérienne est mahlérienne;
-
le produit de Cauchy de deux séries mahlériennes est mahlérienne;
-
la dérivée d'une série mahlérienne est mahlérienne.
Précisons aussi qu'une série mahlérienne a un rayon de convergence strictement positif et définit donc une fonction analytique.

Une série f(z) est du type diviser pour régner si elle satisfait une équation avec second membre

\begin{displaymath} c_0(z)f(z)+c_1(z)f(z^2)+\dotsb+c_N(z)f(z^{2^N})=b(z)\end{displaymath}

dans laquelle b(z) est une série formelle et les ck(z) sont des polynômes non tous nuls. Une suite est du type diviser pour régner si sa série génératrice est du type diviser pour régner.

Domaines d'application. On rencontre les séries diviser pour régner dans différents domaines. L'exemple des partitions binaires a montré qu'elles interviennent en combinatoire. Dans la même orbite on peut signaler des exemples de combinatoire des mots : la corrélation de deux mots u et v est un mot sur l'alphabet $\{0,1\}$ obtenu en faisant glisser le second mot par rapport au premier et en notant la coïncidence dans la partie commune; en particulier l'autocorrélation d'un mot indique ses répétitions. Cette notion intervient dans l'étude du nombre d'occurrence d'un motif dans un texte ou au contraire dans l'étude des mots à motifs interdits [23]. On peut montrer que la série génératrice du nombre de mots d'autocorrélation donnée est mahlérienne [22].

Ces séries interviennent aussi dans les problèmes liés à l'écriture binaire des entiers. Un exemple classique est la suite (Sn) qui donne le nombre de 1 dans les écritures binaires de entiers entre 1 et n [11].

Bien sûr la stratégie diviser pour régner fournit une pléiade d'exemples. Par exemple la multiplication de deux polynômes de degré n, telle que nous l'avons signalée plus haut, utilise trois multiplications de polynômes de degrés moitié et en gros 3n additions de coefficients. Comme le coût est croissant avec n, une suite qui majore le coût de la multiplication de deux polynômes de degré n est la suite (Pn) défine par [26, p. 278]

\begin{displaymath} P_n=3P_{\lfloor n/2\rfloor}+cn,\qquad P_0=1,\end{displaymath}

où c est une constante qui traduit le coût de l'addition de deux nombres. La série génératrice P(z) satisfait

\begin{displaymath} P(z)=3(1+z)P(z^2)+\frac{cz}{(1-z)^2}.\end{displaymath}

Une telle équation peut se résoudre par itération.

hline

Page précédente : Une idée fondamentale
Page suivante : Suites 2-rationnelles