Convergence des algorithmes

jeudi 16 juillet 2009
par  Alain BUSSER

Lorsqu’un algorithme fait vraiment ce qu’il est censé faire (s’arrêter puis afficher le résultat voulu), on dit qu’il converge. On va voir que ce terme n’est pas dû au hasard, et on va voir aussi ce qu’il se passe lorsqu’un algorithme ne converge pas...

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 :

  1. Le cours sur les suites ne sera fait qu’en Première ;
  2. 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) :

CarMetal - 72.2 ko
la toile d’araignée

Elle illustre les notions d’analyse suivantes :

  • Si 1<k<3, la suite des itérées de kx(1-x) converge.
  • 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)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) :

CarMetal - 5.2 ko
Kaprekar

À 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 ».


[1les idées géniales sont souvent très simples ; c’est la réciproque qui n’est pas toujours vraie...

[2comment peut-on alors l’évaluer ? Il faudra prévoir des notes de plantage...

[3Il est libre, gratuit, multiplateforme, ressemble aux langages objets mais est en français, il comprend une boucle à condition d’arrêt, on entre les instructions avec la souris, par choix dans des menus, il oblige l’élève à déclarer les variables pour pouvoir les utiliser...


Commentaires

Logo de Alain BUSSER
jeudi 28 janvier 2010 à 17h32 - par  Alain BUSSER

Bonne année : Le nombre 2010 réalise le maximum dans l’algorithme de Kaprekar...

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 8 février 2017, 14h-18h, campus du Tampon, amphi 120 B
- Mercredi 8 mars 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 12 avril 2017, 14h-18h, campus du Tampon
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6

Semaine des mathématiques

Du 23 mars au 4 avril 2017 dans l’académie de la Réunion.


Brèves

À 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

jeudi 23 février 2017

Publication

732 Articles
Aucun album photo
125 Brèves
11 Sites Web
126 Auteurs

Visites

3 aujourd'hui
741 hier
1930768 depuis le début
14 visiteurs actuellement connectés