Dans cet article, on va illustrer le fonctionnement de l’algorithmique sur un exemple suffisamment typique pour montrer comment ça marche, et suffisamment simple pour ne pas nécessiter de connaissances préalables sur la théorie des graphes ou la structure interne des ordinateurs. Il s’agit du calcul du temps minimal qu’il faut pour parcourir un arbre équilibré.

L’algorithmique est l’étude des algorithmes, en particulier du point de vue de la comparaison de leurs performances.

Position du problème

Une activité fréquente en informatique est la recherche d’une donnée dans une base de données. Par exemple, le succès du moteur de recherche Google montre l’importance qu’il y a à pouvoir retrouver une donnée, autant que la difficulté que représente cette tâche lorsque la base de données est immense...

Un exemple de méthode de recherche est l’algorithme de recherche par dichotomie : Supposons que je veuille chercher un mot dans le dictionnaire, en ayant une connaissance parfaite de l’ordre alphabetique. Je peux très bien ouvrir le dictionnaire pile au milieu de celui-ci, puis, si le mot cherché est avant la lettre que je vois, l’ouvrir au premier quart, sinon aux trois quarts, etc. Ce procédé me permettra à coup sûr de trouver le mot que je cherche mais le permet-il rapidement ? Il va de soi que si on cherche un mot comme « abeille » ou « zygomatique » la méthode par dichotomie n’est pas la plus adaptée... Cela est dû à ce que les lettres extrêmes ont beaucoup moins de pages que les lettres du milieu en français, et que l’arbre de recherche n’est pas équilibré.

Définitions

1. Un arbre est dit binaire si, de chaque nœud, partent au plus deux branches (ou arêtes). C’est le cas de l’arbre obtenu par dichotomie.
2. La profondeur d’un arbre est le nombre maximal d’arêtes qui séparent une feuille (nœud terminal) de sa racine (premier nœud).
3. Un arbre équilibré est un arbre binaire tel que les deux sous-arbres partant de chaque nœud autre qu’une feuille ont des profondeurs différant au maximum de 1.

Un exemple d’arbre très déséquilibré est la liste, où chaque nœud a un seul fils, et qui revient à chercher un mot dans le dictionnaire en commençant par « abacule », puis en passant à « abaque » etc...

Pour chercher le temps maximal mis à parcourir un arbre équilibré, lequel est mesuré par sa profondeur, on va inverser le problème et chercher dans un premier temps le nombre minimal de nœuds d’un arbre équilibré de profondeur $n$ pour toute valeur de $n \in \mathbb{N}$. En notant $u_n$ la suite obtenue, on cherche essentiellement une valeur asymptotique de $u_n$, pour $n$ tendant vers l’infini.

Expression récurrente de la suite

Voici les premiers arbres équilibrés minimaux, numérotés par leurs profondeurs à partir de la profondeur nulle (un seul sommet) :

Par simple comptage des nœuds, on voit que $u_0=1$, $u_1=2$, $u_2=4$, $u_3=7$ et $u_4=12$.

Mais on voit aussi que l’arbre équilibré minimal de profondeur $n+2$ contient, à sa gauche, l’arbre équilibré minimal de profondeur $n+1$ et, à sa droite, celui de profondeur $n$. L’exemple $n=2$ est illustré en couleur, à ceci près que pour des raisons de place disponible on a retourné l’arbre $n=2$, représenté en bleu. Et comme en plus des sous-arbres rouge et bleu, il y a aussi le sommet de l’arbre, on a pour tout $n$,

$$ \fbox{u_{n+2}=1+u_{n+1}+u_n}$$

L’essentiel du problème d’algorithmique étudié ici consiste alors à trouver une expression analytique de $u_n$ fonction de $n$, à partir de laquelle on aura l’expression asymptotique voulue.

Pour commencer, on peut calculer les premiers termes de $u_n$ avec un tableur et représenter graphiquement la suite. Pour le calcul des termes, on a ceci :

La représentation graphique donnée par SciLab en coordonnées logarithmiques suggère que la suite $u_n$ est asymptotiquement géométrique, de raison supérieure à 1 :

Expression analytique

Pour trouver $u_n$ en fonction de $n$, on utilise sa fonction génératrice

$$ g(z)=\sum_{n=0}^\infty u_n \, z^n$$

définie sur $\mathbb{C}$ ou plus précisément sur le disque de centre 0 et de rayon $R$, rayon de convergence de la série, qu’il reste à déterminer.

L’utilisation de la relation de récurrence dans la définition de $g(z)$ donne alors une relation algébrique vérifiée par $g$, laquelle permet à son tour de déterminer $g$

sous réserve que les séries convergent absolument ;

en sommant la relation de récurrence multipliée membre à membre par $z^n$, ce qu’on peut faire si $| z | < R$, on obtient

$$\sum_{n=0}^\infty u_{n+2} \, z^n =\sum_{n=0}^\infty z^n+\sum_{n=0}^\infty u_{n+1} \, z^n+\sum_{n=0}^\infty u_n \, z^n$$

ce qu’on peut aussi écrire par changement d’indice

$$\sum_{n=2}^\infty u_n \, z^{n-2} =\sum_{n=0}^\infty z^n+\sum_{n=1}^\infty u_n \, z^{n-1}+\sum_{n=0}^\infty u_n \, z^n$$

ou

$$\frac{\sum_{n=2}^\infty u_n \, z^n}{z^2} =\sum_{n=0}^\infty z^n+\frac{\sum_{n=1}^\infty u_n \, z^n}{z}+\sum_{n=0}^\infty u_n \, z^n$$

$$\frac{\sum_{n=0}^\infty u_n \, z^n-1-2z}{z^2} =\sum_{n=0}^\infty z^n+\frac{\sum_{n=0}^\infty u_n \, z^n -1}{z}+\sum_{n=0}^\infty u_n \, z^n$$

$$\frac{g(z)-1-2z}{z^2} =\frac{1}{1-z}+\frac{g(z) -1}{z}+g(z)$$

puis en multipliant les deux membres par $z^2(1-z)$

$$(g(z)-1-2z)(1-z)=z^2+z(1-z)(g(z)-1)+z^2(1-z)g(z) $$

puis en faisant tout passer à gauche et en développant

$$-(z^3-2z+1)g(z)+1=0 $$

soit encore

$$(z^3-2z+1)g(z)=1$$

d’où l’expression désirée pour $g(z)$ :

$$g(z)=\frac{1}{z^3-2z+1}$$

Ensuite on factorise le dénominateur pour trouver la série de Taylor de $g$ qui donnera par identification des coefficients, la valeur voulue de $u_n$.

On peut factoriser à partir d’une racine évidente, en l’occurence 1.

On trouve que $z^3-2z+1=(1-z-z^2)(1-z)$, et le premier facteur se factorise lui-même par le calcul de son discriminant $\Delta=1+4=5$. On trouve que les deux racines de ce trinôme sont

$\frac{-1-\sqrt{5}}{2}=-\Phi$ et $\frac{-1+\sqrt{5}}{2}=\Phi^{-1}$

où $\Phi$ est le nombre d’or. Finalement le dénominateur s’écrit

$$z^3-2z+1=(\Phi+z)(\Phi^{-1}-z)(1-z)$$

et

$$g(z)=\frac{1}{(\Phi+z)(\Phi^{-1}-z)(1-z)}$$

D’une part, on en déduit (enfin !) le rayon de convergence de $g$, qui est le minimum des modules des trois racines du dénominateur, en l’occurence $R=\frac{\sqrt{5}-1}{2}$. Par ailleurs, on peut trouver la série de Taylor de $g$ par une décomposition en éléments simples, c’est-à-dire en cherchant $a$, $b$ et $c$ tels que

$$\frac{1}{(\Phi+z)(\Phi^{-1}-z)(1-z)}=\frac{a}{\Phi+z}+\frac{b}{\Phi^{-1}-z}+\frac{c}{1-z} $$

Par mise au même dénominateur du second membre, on a

$$g(z)=\frac{a(\Phi^{-1}-z)(1-z)+b(\Phi+z)(1-z)+c(\Phi+z)(\Phi^{-1}-z)}{z^3-2z+1} $$

soit, par développement

$$g(z)=\frac{(a-b-c)z^2-(\Phi a + \Phi^{-1}b +c)z+\Phi^{-1}a+\Phi b+c}{z^3-2z+1}$$

En égalant le numérateur à 1, on déduit que $a$, $b$ et $c$ sont solution du système

$$\left\{ \begin{array}{rcl} a-b-c &=& 0 \\ \Phi a + \Phi^{-1}b +c &=& 0 \\ \Phi^{-1}a+\Phi b+c &=& 1\end{array} \right. $$

dont la solution est $a=\frac{\Phi^{-2}}{\sqrt{5}}$, $b=\frac{\Phi^2}{\sqrt{5}}$ et $c=-1$

D’où

$$g(z)=\frac{\frac{\Phi^{-2}}{\sqrt{5}}}{\Phi+z}+\frac{\frac{\Phi^2}{\sqrt{5}}}{\Phi^{-1}-z}-\frac{1}{1-z}=\frac{\Phi^{-3}}{\sqrt{5}}\times\frac{1}{1+z\Phi^{-1}}+\frac{\Phi^3}{\sqrt{5}}\times\frac{1}{1-z\Phi}-\frac{1}{1-z}$$

et finalement

$$\sum_{n=0}^\infty u_n \, z^n=g(z)=\frac{\Phi^{-3}}{\sqrt{5}} \sum_{n=0}^\infty (-\frac{1}{\Phi})^n~; z^n+ \frac{\Phi^3}{\sqrt{5}} \sum_{n=0}^\infty \Phi^n ~; z^n -\sum_{n=0}^\infty z^n$$

d’où par identification des coefficients

$$ \fbox{u_n=\frac{\Phi^3}{\sqrt{5}} \Phi^n + \frac{\Phi^{-3}}{\sqrt{5}}(-\frac{1}{\Phi})^n-1}$$

expression dont il est d’ailleurs difficile de deviner que c’est un entier !

À la lumière de ce résultat et dans cet exemple précis, une méthode plus rapide existe.

L’apparition du nombre d’or dans cet exemple fait remarquer que la relation de récurrence qui définit $u_n$ ressemble à celle de la suite de Fibonacci, et incite à démontrer par récurrence que $u_n=F_{n+2}-1$, où $F_n$ est la suite de Fibonacci. En effet

• $u_0=1=2-1=F_2-1$ ;
• $u_1=2=3-1=F_3-1$ ;
• Si $u_n=F_{n+2}-1$ et $u_{n+1}=F_{n+3}-1$ alors $u_{n+2}=u_n+u_{n+1}+1=F_{n+2}-1+F_{n+3}-1+1=F_{n+4}-1$.

Or une expression exacte des nombres de Fibonacci est bien connue : La formule de Binet

$$F_n=\frac{\Phi^{n+1}-(-\Phi)^{-n-1}}{\sqrt{5}}$$

On en tire alors $u_n=\frac{\Phi^{n+3}-(-\Phi)^{-n-3}}{\sqrt{5}}-1$

qui est bien l’expression trouvée ci-dessus. En fait la formule de Binet n’est rien d’autre que l’écriture des puissances de la matrice $\left(\begin{array}{lc}0&1\\1&1\end{array} \right)$ obtenue par diagonalisation de celle-ci, comme on peut le voir en consultant le tutoriel en français du logiciel Euler Math Toolbox

Ordre de grandeur

On déduit enfin de l’expression analytique ci-dessus que, lorsque $n$ tend vers l’infini, $u_n$ est équivalente à $\frac{\Phi^3}{\sqrt{5}} \Phi^n$, le second terme tendant vers 0 en tant que suite géométrique de raison inférieure à 1 en module, et le troisième terme, constant, étant négligeable devant le premier.

Il ne reste plus pour conclure l’exemple, qu’à inverser l’approximation ci-dessus :

$$u_n \asymp \frac{\Phi^3}{\sqrt{5}} \Phi^n$$

$$\mbox{ln }u_n \asymp \mbox{ln }\frac{\Phi^3}{\sqrt{5}} +\mbox{ln }\Phi^n$$

$$\mbox{ln }u_n \asymp 3\, \mbox{ln }\Phi-\frac{1}{2}\mbox{ln }5 +n \mbox{ln }\Phi$$

Or $\lim_{n \rightarrow \infty} u_n = +\infty$, donc les deux premiers termes du second membre sont négligeables devant le reste qui tend vers l’infini :

$$\mbox{ln }u_n \asymp n \mbox{ln }\Phi$$

et finalement

$$n \asymp \frac{\mbox{ln }u_n}{\mbox{ln }\Phi}$$

ce qu’on note $n=O(\mbox{ln }u_n)$ : La profondeur (donc, à un facteur près, le temps mis à parcourir l’arbre) d’un arbre binaire équilibré est en "log(n)", ce qui est très bon si on compare à d’autres algorithmes bien connus, de complexité polynomiale ($O(n^p)$) voire exponentielle ($O(p^n)$). Reste à voir si le temps mis à équilibrer l’arbre ne diminue pas trop les performances lorsqu’il s’agit de parcourir celui-ci, mais ceci est une autre histoire...

En conclusion

Tout ceci ressemble quand même beaucoup à des maths, non ? Et même des maths de haut niveau, surtout si on s’attaque à des problèmes plus complexes d’algorithmique, où la fonction génératrice vérifie une équation algébrique polynomiale, voire une équation différentielle. Dans ce cas on utilise souvent le théorème des résidus !

Sans parler du fait que l’un des sept problèmes de la fondation Clay concerne lui aussi l’algorithmique !

L’algorithmique, comme toute science qui se respecte, possède sa « bible », facétieusement titrée L’art de la programmation des ordinateurs par son auteur, Donald Knuth. En effet, si la programmation est un art, l’algorithmique est une science, et l’ouvrage de D. Knuth décrit bel et bien cette science et non la programmation elle-même.

Et c’est bien de programmation qu’il s’agit en Seconde, et pas de calculs comme ceux qui ont été exposés ci-dessus (et qui, rappelons-le, concernent un des exemples les plus simples du tome 3 du Knuth !).

Sur les arbres équilibrés (on utilise aussi l’expression « un arbre AVL »), on consultera avec intérêt l’article de Ben Pfaff sur le sujet, ou, de façon plus générale, le cours d’algorithmique de Jean-Jacques Lévy pour l’école polytechnique.