Qu’est-ce que l’algorithmique ?

mercredi 16 septembre 2009
par  Alain BUSSER

C’est bien de la programmation qu’on va faire en Seconde, et non de l’algorithmique. L’algorithmique est une science ayant pour but d’expliquer a posteriori le comportement des programmeurs, et s’adressant donc à ceux qui ont déjà une certaine connaissance de la programmation. De surcroît, les outils mathématiques dont l’algorithmique fait usage dépassent largement les acquis de la classe de Seconde...

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) :

PNG - 5.7 ko

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 :

n u_n
0 1
1 2
2 4
3 7
4 12
5 20
6 33
7 54
8 88
9 143
10 232

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 :

PNG - 3 ko

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.


Documents joints

Scalable Vector Graphics - 10.2 ko
Scalable Vector Graphics - 10.2 ko
Scalable Vector Graphics - 7.9 ko
Scalable Vector Graphics - 7.9 ko

Commentaires

Brèves

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Sur le Web : Hyper-vidéos pour l’algorithmique

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris