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

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 :


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}

\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.3 ko
Scalable Vector Graphics - 10.3 ko
Scalable Vector Graphics - 8 ko
Scalable Vector Graphics - 8 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 13 septembre 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 4 octobre 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 11 octobre 2017, 14h-18h, campus du Tampon
- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Du 13 au 18 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

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.

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

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 25 septembre 2017

Publication

766 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

490 aujourd'hui
1251 hier
2102985 depuis le début
39 visiteurs actuellement connectés