Méthode des périmètres
L’algorithme d’Archimède pour calculer $\pi$ se décrit finalement très simplement : À partir de deux périmètres $a$ et $b$ tels que $a \leqslant \pi \leqslant b$, on en trouve deux nouveaux par doublement du nombre de sommets des polygones inscrit et circonscrit, revenant à remplacer $b$ par la moyenne harmonique de $a$ et $b$ puis $a$ par la moyenne géométrique de $a$ et de $b$ (en l’occurence, le nouveau $b$).
La justification la plus simple étant basée sur les formules trigonométriques de doublement des angles, est difficilement envisageable en Seconde, mais la programmation est assez facile pour un élève de Seconde, qui pose souvent la question « mais comment a-t-on calculé toutes ces décimales de $\pi$ ? »
En JavaScript, avec l’interpréteur en ligne sur le wiki de « Keops », on peut faire quelque chose comme ceci :
function MoyenneGeo(x,y) { // moyenne géométrique
return Math.sqrt(x*y); // racine du produit
}
function MoyenneHarmo(x,y) { // moyenne harmonique
var u=1/x;
var v=1/y;
var z=(u+v)/2; // moyenne des inverses
return 1/z; // puis on inverse
}
var a=2*Math.sqrt(2); // périmètre inscrit
var b=4; // périmètre circonscrit
while (b-a>1e-6) {
b=MoyenneHarmo(a,b);
a=MoyenneGeo(a,b);
afficher(a,b);
}On eût pu faire plus court mais créer des fonctions pour les deux moyennes géométrique et harmonique et leur donner un nom français facilite la lecture du code. De plus, au lieu de créer un affichage de l’encadrement à la fin, on a préféré afficher a et b à chaque étape, à fin de débogage.
En effet cet algorithme comprend une boucle à sortie conditionnelle (ici on sort de la boucle « while » lorsque la différence entre a et b est suffisamment petite, par exemple inférieure à un millionnième).
Lorsqu’une boucle est exécutée un nombre prédéderminé de fois (par exemple « for n=1 to 10 » exécutée 10 fois), aucune question ne se pose sur le fait qu’un jour on en sort : Au bout de 10 fois, on en sort, de cette boucle. Mais lorsqu’elle contient une condition de sortie, on ne sortira de la boucle que lorsque la condition sera vraie, et si la condition n’est jamais vraie, on ne sort jamais de la boucle !
Quand un algorithme converge
La plupart des algorithmes de calcul numérique visent à approcher la limite d’une suite par un terme de rang suffisamment grand de la suite. Il est donc difficile de trouver des exemples d’algorithmique à la fois simples, pertinents et intéressants pour les élèves sans évoquer le vocabulaire des suites, ce qui présente au moins deux inconvénients :
- Le cours sur les suites ne sera fait qu’en Première ;
- Avec un tableur, c’est plus facile...
L’exemple ci-dessus calcule d’ailleurs une valeur approchée de la limite commune des deux suites adjacentes $a_n$ et $b_n$ définies par :
$\left\{ \begin{array}{rcl} a_{n+1} & = & \sqrt{a_n b_{n+1}} \\ b_{n+1}&=&\frac{a_n b_n }{a_n + b_n} \end{array} \right.$
L’exemple ci-dessous, ultraclassique, a été construit avec le présent CarScript :
u="U"; k="k";
for(n=1;n<100;n++){
v=Point("x_u","_k*x_u*(1-x_u)");
SetHide(v,true);
z=Vector(u,v);
SetRGBColor(z,Math.round(n/100*255),255-Math.round(n/100*255),0);
u=v;
v=Point("_k*x_u*(1-x_u)","k*x_u*(1-x_u)");
SetHide(v,true);
z=Vector(u,v);
SetRGBColor(z,Math.round(n/100*255),255-Math.round(n/100*255),0);
u=v;
}sur une figure CaRMetal comprenant à l’origine, un curseur k, un bout de parabole d’équation y=kx(1-x), et un point U sur l’axe des abscisses (on peut télécharger la figure CaRMetal en cliquant sur la copie d’écran) :
Elle illustre les notions d’analyse suivantes :
- Si $1
- Dans ce cas la limite est solution de $kx(1-x)=x$ (point fixe de la fonction).
- Par contre, si $k>3$, la suite ne converge pas. Dans ce cas précis, elle ne tend pas vers $\infty$ non plus.
Par analogie, on continue à dire d’un algorithme qu’il converge si la condition de sortie de la boucle est inéluctablement atteinte un jour. Ainsi, les algorithmes dont toutes les boucles s’effectuent un nombre prédéterminé de fois, convergent tous. Bonne nouvelle !
Mais lorsqu’un algorithme converge, vers quoi converge-t-il ? Là encore, vers un point fixe ! Mais ici, le point fixe est un état de l’ordinateur, laissé invariant par l’exécution de la boucle. Par exemple, la fonction de deux variables $(a,b) \mapsto (a,b-a)$ si $a\leqslant b$ a pour point fixe $(p,0)$ où $p$ est le pgcd de $a$ et $b$ : On reconnaît l’écriture récursive de l’algorithme d’Euclide.
Un exemple plus simple est fourni par la transformation de Kaprekar, donnée ci-dessous sous la forme d’une figure CaRMetal (que l’on peut télécharger en cliquant dessus) :
À partir d’un nombre de 4 chiffres non tous égaux entre eux, on considère deux nombres : Le grand nombre, obtenu en écrivant les 4 chiffres dans l’ordre décroissant, et le petit nombre, obtenu en mettant les 4 chiffres dans l’ordre croissant. La transformée de Kaprekar du nombre de 4 chiffres initiaux est la différence entre le grand nombre et le petit nombre.
Kaprekar a démontré que l’application au plus 11 fois de cette transformation finit par donner l’unique point fixe non nul de cette transformation. Il est donc facile de trouver le nombre dit « de Kaprekar » avec le fichier ci-dessus. En passant on voit sa résistance aux bogues (lorsque le nombre de chiffres n’est pas 4, le résultat est fantaisiste, mais on peut continuer à manipuler la « figure »). Voir plus bas sur les effets des bogues.
L’idée très simple mais géniale [1] selon laquelle lorsqu’un algorithme converge, c’est vers un état de l’ordinateur qui est insensible au travail de la boucle, est dûe à Haskell Curry au sein du lambda calcul, sur lequel sont basés les langages fonctionnels (ou partiellemnent fonctionnels tels que Scheme, Python, JavaScript (ces deux derniers non fonctionnels ... et l’archétype du langage fonctionnel, qui s’appelle haskell : L’idée d’Haskell Curry est à la base d’un langage qui porte son prénom, et donc Haskell Curry s’est fait « curryifier », et est devenu un point fixe de son propre principe !
Sur l’intérêt des langages fonctionnels, on consultera avec bonheur ou intérêt l’article de Guillaume Connan sur MathemaTICE.
Quand un algorithme ne converge pas
Certaines boucles n’ont pas de conditions de sorties, comme par exemple les algorithmes de surveillance ou les horloges. Mais lorsqu’à cause d’un bogue, une condition d’arrêt n’est jamais atteinte, on dit que le programme plante. Des exemples intéressants de bogues sont décrits dans cet article.
L’exemple ci-dessus a donné lieu à un phénomène intéressant lui aussi : Le bogue était qu’à cause d’une erreur de typographie, j’avais calculé le double de la moyenne harmonique, au lieu de la moyenne harmonique elle-même :
b=2*MoyenneHarmo(a,b);dans la boucle : Alors les suites a et b tendent vers l’infini, et la condition d’arrêt « b proche de a » n’est jamais atteinte : Mon programme pi plante ! L’éditeur JavaScript en ligne affiche ceci (vers la fin) :
8.535321255762653e+153 1.3328354915163168e+154
1.332835491516317e+154 2.0812930107887445e+154
Infinity 3.250048955276523e+154 On voit que JavaScript considère $a$ comme infini, et $b\simeq 3,25 \times 10^{154}$. Comme $+\infty$ est largement supérieur à tous les nombres, y compris à $3,25 \times10^{154}$, la condition de sortie est bel et bien atteinte !
Ceci dit lorsqu’un programme plante, on s’en rend compte (l’exécution de la boucle est beaucoup trop lente) et le rôle du prof de maths de Seconde sera aussi d’essayer de comprendre comment l’élève a fait planter son programme. Lorsqu’un programme plante, les conséquences peuvent en être fâcheuses : Mémoire remplie de plus en plus, ressources indisponibles pour les autres processus, etc. Si par exemple un programme Java plante, il suffit de redémarrer la machine Java et seul le programme sera perdu [2]. Si un programme plante alors qu’on le met au point, il tend à faire planter avec lui l’environnement de développement sous lequel on est en train de l’écrire, voire dans certains cas, de l’ordinateur entier... Si, si, ça arrive !
C’est un « détail » auquel il faut penser quand on choisit l’outil de programmation, à moins qu’on aime s’arracher les cheveux ! Tester des environnements de programmation de ce point de vue est assez facile, il suffit d’écrire un programme comme celui-ci :
afficher("Et les Shadoks pompaient...");
for(n=0;n<10;n=n){afficher("...pompaient...");}Et bien, il est rassurant de voir que l’explorateur qui exécute ce programme (en l’occurence, Mozilla) affiche un message d’erreur au bout de quelques secondes, me permettant de récupérer la main.
Avec la version CarScript, le bouton Restore de l’éditeur de CarMetal résout le problème. Malgré des tentatives multiples, l’auteur de cette page n’a jamais réussi à faire planter l’éditeur lua de Enigma, ni les « délires » faits sous Scratch (il suffit de cliquer sur le bouton « stop » pour reprendre la main). Par contre, l’outil Algobox, pourtant très intéressant [3], ainsi que le célèbre Python m’ont valu quelques sueurs froides (obligation d’utiliser le « moniteur système » d’Ubuntu pour « tuer » ces outils).
Ainsi, les outils ne sont pas égaux devant le plantage, et plus un programme s’exécute loin de la machine (surcouche de surcouche, voire serveur en ligne comme lua, ruby ou xcas par exemple), plus il sera lent mais sûr. Et en la matière, la sûreté est plus importante que la rapidité...
L’idéal serait un outil qui, avant même l’exécution, détermine d’avance s’il y aura plantage. Hélas, un tel outil, non seulement n’existe pas, mais même n’existera jamais, d’après un théorème d’Alan Turing ! Sur ce sujet, un nouvel article dans « Images de maths ».
Commentaires