L’algorithme d’Euclide

vendredi 10 juillet 2009
par  Alain BUSSER

L’écriture itérative de l’algorithme d’Euclide présente l’avantage d’être courte et intéressante (parce que portant sur l’arithmétique). C’est donc un des exemples les plus simples illustrant la notion de boucle à sortie conditionnelle (à part peut-être ce jeu). Ceci dit le même algorithme illustre aussi la brièveté des codes basés sur la récursivité...

L’algorithme d’Euclide est basé sur le fait que le pgcd de a et b est aussi égal au pgcd de b et r, où r est le reste de la division euclidienne de a par b (en supposant que a>b) [1]. Pour l’implémenter, on a donc besoin de deux variables a et b, et chaque passage dans la boucle remplace a par b et b par r. Ces remplacements doivent être parfaitement simultanés sinon le calcul est entaché d’erreur (doit-on remplacer a par l’ancien b ou par le nouveau b ?).


Calcul parallèle

On en arrive donc à la recherche d’un algorithme parallèle : Si deux ordinateurs calculent chacun de son côté, l’un a, l’autre b, à eux deux ils iront deux fois plus vite en moyenne que si un seul d’entre eux faisait tout le travail à lui seul. À condition que ce soit possible !

Affectation simultanée

L’affectation simultanée de deux variables est la spécialité du langage Lua, qui en plus possède un interpréteur en ligne, ça tombe bien ! Donc si on copie-colle le script suivant dans la fenêtre qui est à l’adresse ci-dessus, on peut calculer des pgcd par la méthode d’Euclide :

a=3600
b=3024
while(b>0) do
   a,b = b,a % b
end
io.write("Le pgcd des deux nombres est ",a,"\n")

Comparer avec Python :

a=3600
b=3024
while (b>0):
    a,b = b,a % b
print "Le pgcd est ", a

Et avec CoffeeScript :

pgcd = (a,b) ->
    [a,b] = [b,a%b] until b is 0
    a
alert pgcd 3600, 3024

En réalité il ne s’agit pas réellement de calcul parallèle mais de calcul matriciel : Lua considère que a,b est un vecteur dont les deux coordonnées sont mises à jour simultanément. Donc le même raccourci est implémentable avec SciLab ou Euler Math Toolbox puisque ces logiciels sont basés sur le calcul matriciel.

Un variante intéressante parce que graphique est ce CaRScript, qui calcule un pgcd sur une figure comprenant un point A (et on voit les étapes du calcul si on affiche les coordonnées de A) :

Move("A",3600,3024);
while(Y("A")>0){
        Move("A",Y("A"),X("A")%Y("A"));
        Pause(1000);
}

Le langage à la mode en calcul parallèle est Scratch, alors autant essayer avec Scratch : Puisqu’il y a deux variables à traiter, on peut les confier à deux lutins [2]. Le plus grand des deux nombres entiers (qui s’appelait a ci-dessus) est confié au lutin « Pégé » [3] et le plus petit au lutin « CéDé », représenté par un CD-Rom à droite de PéGé [4]. Le pgcd ne sera donc pas calculé par un acteur mais par PéGé et CéDé en travail collaboratif. Le remplacement simultané des deux variables « Nombre de PéGé » et « Nombre de CéDé » mène à un calcul faux (le pgcd est égal à 0, quelles que soient les valeurs de a et b). On doit donc créer une variable abritant temporairement le reste de la division euclidienne de a par b, le temps que a soit remplacé par b. La synchronisation des transformations de données se fait par des messages envoyés par la « scène » aux deux lutins. En calcul parallèle, on parle de sémaphore (informatique). Finalement, le calcul est partagé entre PéGé et CéDé, mais la scène joue le rôle de chef d’orchestre en synchronisant le travail de PéGé et de CéDé. Cette synchronisation se fera par envoi et réception de messages.

Pour commencer, il faut créer un projet Scratch, et ajouter à la scène les deux lutins PéGé et CéDé :

En cliquant sur un lutin, on voit apparaître à droite de l’écran, comment il est fait ; en particulier ses algorithmes, initialement vides.

Lorsqu’on crée une variable comme « nombre de CéDé », on peut soit en faire une variable d’instance propre au lutin, soit une variable globale, accessible à tous les lutins (et à la scène, au besoin). Comme chaque lutin a besoin d’accéder à toutes les variables (soit pour les modifier, soit pour les afficher), on fait le second choix :

La scène va donc synchroniser les lutins :

  • le démarrage du programme se fait lorsqu’on clique sur le drapeau vert, il consiste à initialiser les variables, puis
  • entrer dans une boucle qui prend fin (ainsi que le programme) lorsque le reste euclidien est devenu nul, auquel cas le nombre de PéGé est devenu le pgcd cherché.
    • Dans cette boucle, la scène envoie le message « divisez » puis attend que tout le monde soit synchronisé,
    • et envoie le message « échangez »

Le lutin PéGé a deux fonctions, selon le message qu’il reçoit :

  • si c’est le message « divisez » il s’active et effectue la division puis affiche le résultat ;
  • si c’est le message « échangez » c’est que c’est le tour de CéDé de travailler, alors PéGé fait une pause en attendant que CéDé ait fini, et pendant ce temps, se contente de rêver à son nombre :

Quant à CéDé, il n’effectue aucun travail si le message ne lui est pas destiné (« divisez » veut dire que c’est au tour de PéGé de travailler). Mais si le message qu’il reçoit est « échangez » il effectue l’échange en deux étapes :

  1. il met b dans a ;
  2. il met r dans b :

Pour calculer le pgcd de 3600 et 3024, on va donc sur le projet et on clique sur le drapeau vert. On voit alors ceci :

Puis, petit à petit, les variables sont affichées, et à la fin, CéDé affiche le PéGéCéDépgcd :

Si on veut calculer le pgcd d’autres nombres que 3600 et 3024, on peut modifier le projet, soit en mettant d’autres valeurs que 3600 et 3024, soit en ajoutant au projet des instructions d’entrée avec « demander » (« capteurs » en bleu clair).

Version graphique avec Scratch

La scène peut être munie d’un ou plusieurs « arrière-plans », dont l’un représente un repère ; or l’algorithme d’Euclide peut être implémenté graphiquement en modifiant des coordonnées. On peut simuler un point mobile en prenant le lutin « ball » et en le redimensionnant. Au passage on coche les cases correspondant à abscisse (x) et à ordonnée (y) ce qui a pour effet d’afficher les coordonnées dans l’écran :

Ensuite, l’affectation simultanée des deux variables appelées a et b ci-dessus, se fait naturellement si a et b sont les coordonnées du lutin. Par exemple pour calculer le pgcd de 220 et 136 :

On peut même demander au lutin de laisser une trace de son passage :

Le projet est ici

On peut se diriger vers l’algorithme de tracé de segment de Bresenham avec la programmation graphique de l’algorithme d’Euclide avec soustractions, avec la même situation de départ mais cet algorithme pour le lutin :

Il laisse une trace dessinée de l’algorithme d’Euclide :

Le projet est ici


Réalisation itérative

Cette réalisation où un seul processus fait séquentiellement le remplacement de a par b et b par le reste de la division euclidienne (avec une troisième variable pour les raisons évoquées ci-dessus) peut très bien être faite sous Scratch, mais je lui préfère personnellement JavaScript, en raison de la rapidité de la mise au point (y compris le débogage) avec les outils de développements existants : En bref, j’ai préféré choisir un outil plutôt qu’un langage.

Avec ce magnifique interpréteur en ligne qui est particulièrement adapté à des TP en Seconde (surtout si on s’en sert hors-ligne, ainsi on n’est pas tributaire d’un bon fonctionnement du réseau), le code produit en quelques minutes, débogage compris [5] est celui-ci :

var a=demander("Quel est le plus grand des deux nombres ?");
var b=demander("Quel est le plus petit des deux nombres ?");
while(b>0){
  var t=a%b;
  a=b;
  b=t;
}
afficher("Le pgcd des deux nombres est ",a);

Autre outil particulièrement efficace, l’éditeur de CaRMetal donne quelque chose de plus « pro » avec des fenêtres d’alerte du plus bel effet ; le « CarScript » est légèrement différent du précédent :

a=Input("quel est le plus grand nombre ?");
b=Input("quel est le plus petit nombre ?");
while(b>0){
        var t=a%b;
        a=b;
        b=t;
}
Prompt("Le pgcd des deux nombres est "+a);

On voit une différence au niveau de la création de l’affichage : Alors que l’éditeur en ligne affiche une liste de variables dont certaines sont des chaînes de caractères, CaRMetal affiche un seul texte, obtenu en concaténant un vrai texte (chaîne de caractères) et un nombre. Et l’affichage se fait dans une fenêtre ad hoc et pas directement dans l’outil de développement. Cependant les versions diffèrent peu...

On peut même profiter de l’intégration de JavaScript dans le format « web 2.0 » pour créer un fichier html comme celui qui est téléchargeable ci-dessous (« pgcd.html »). Cependant cela nécessite une petite connaissance du langage html et n’est guère réalisable en classe (ou alors en devoir maison ?) sauf si on fournit aux élèves un gabarit où seul le code JavaScript reste à écrire (celui qui a été reproduit dans le tableau du bas de la page « pgcd.html »).

Réalisation récursive

Ceci dit, bien que nous quittions ainsi le programme de Seconde, la définition en tête de l’article « le pgcd de a et b est égal au pgcd de b et r » appelle une écriture récursive de l’algorithme. Surprenant, ça marche ! Bien que des langages soient spécialisés dans la récursivité (on pense à Maxima, pari->[http://pari.math.u-bordeaux.fr/down...] ou l’excellent xlogo mais il y en a plein d’autres), là encore une version JavaScript va être donnée, et là encore c’est plus à cause d’un outil qu’à cause du langage, puisqu’il s’agit d’un CarScript :

function gcd(a,b) {
        // Implémentation de l'algorithme d'Euclide pour calculer un pgcd
                if ((b % a) == 0){return (a);
                } else {return (gcd(a,b-a));
                }
}
for(i=1;i<4;i++){
        // numérateurs
        for(j=1;j<8;j++){
                // dénominateurs
                if(gcd(i,j) == 1){
                        // seulement si la fraction est irréductible
                        for(k=-4;k<4;k++){
                                // translations (pour éviter les trous)
                                a=Point("",k+i/j,1/j/j/2);
                                // centre du cercle
                                b=Point("",k+i/j,0);
                                // Point de contact avec l'axe des abscisses
                                c=Circle("",a,b);
                                SetRGBColor(c,32*i,2*i*j,16*j);
                                // La couleur du cercle dépend de sa taille
                                SetFilled(c,"true");
                                // On voit mieux si on le remplit
                                Hide(a);
                                Hide(b);
                                a=Point("",k-i/j,1/j/j/2);
                                b=Point("",k-i/j,0);
                                c=Circle("",a,b);
                                SetRGBColor(c,32*i,2*i*j,16*j);
                                SetFilled(c,"true");
                                Hide(a);
                                Hide(b);
                        }
                }
        }
}

Seules les 9 premières lignes concernent la fonction pgcd elle-même (fonction de deux variables soit dit en passant), le reste concerne une application de cette fonction pgcd, qui est utilisée dans la suite pour mettre des fractions sous forme irréductible : En effet, on montre que tous les cercles centrés sur les points de coordonnées \left( \frac{p}{q};\frac{1}{2q^2}\right) et ayant pour rayon \frac{1}{2q^2}, où \frac{p}{q} est irréductible, sont tangents ou disjoints. Un tel cercle s’appelle un cercle de Ford.

Le CarScript ci-dessus a servi à fabriquer la diapo numéro 5 de ce diaporama CaRMetal

Les threads de Python

Python n’a pas de lutins mais des threads : On va donc créer un diviseur et un échangeur qui effectuent respectivement la division et l’échange des données. Pour que chacun fasse son travail au moment où il est pertinent de le faire, on va les temporiser ; il faudra donc charger deux modules de Python :

  • threading qui gère les threads
  • time qui gère les pauses (« sleep »).

Le script doit donc commencer par ces imports :

from threading import *
import time

Le diviseur est défini comme un exemplaire de la classe Diviseur(). On doit commencer par définir celle-ci, en précisant qu’elle hérite de la classe Thread (le diviseur est donc bien un thread). Deux fonctions lui sont attribuées :

  • __init__ qui détermine ce qui se passe au moment où on crée le diviseur ;
  • run qui détermine ce qui se passe dans le thread une fois qu’on a démarré celui-ci avec start.

Lors de sa naissance, un diviseur se contente d’enregistrer les deux nombres a et b dont on veut calculer le pgcd, et d’afficher un message disant qu’il est prêt. Mais lorsqu’on le démarre, il fait 3 choses tant que la variable de l’échangeur n’est pas nulle :

  1. Il effectue la division euclidienne et stocke le reste dans la variable de l’échangeur ;
  2. Il affiche un message disant que la division est effectuée ;
  3. Il pique un petit somme (de 2 secondes) en attendant que l’échangeur ait fini son travail.

En Python cela donne

class Diviseur(Thread):
    def __init__(self,a,b):
        Thread.__init__(self)
        self.a = a
        self.b = b
        print "Diviseur OK"
    def run(self):
        while echangeur.r > 0:
                echangeur.r = self.a%self.b
                print "Diviseur divise ", self.a, " par ", self.b
                time.sleep(2)

Quant à l’échangeur, il n’a lui aussi que deux méthodes : __init__ qui affiche un faire-part de naissance et lui donne la variable r comme premier biberon, et run qui, tant que son contenu stomacal n’est pas vide, effectue ceci :

  1. faire une sieste d’une seconde en attendant que le diviseur ait fait son renvoi ;
  2. transférer la variable b (qui est au diviseur) dans a (qui est aussi au diviseur, ce n’est pas grave, il aime bien être palpé de l’intérieur par l’échangeur) ;
  3. transférer sa propre variable r dans b [6] (qui appartient toujours à l’échangeur) ;
  4. refaire une sieste en attendant que le diviseur ait divisé à nouveau :
class Echangeur(Thread):
    def __init__(self,r):
        Thread.__init__(self)
        self.r = r
        print "Echangeur OK"
    def run(self):
        while self.r != 0:
          time.sleep(1)
          diviseur.a = diviseur.b
          diviseur.b = self.r
          print "Echangeur echange ", diviseur.a, " et ", diviseur.b
          time.sleep(1)

Ensuite, il suffit de créer un diviseur et un échangeur, puis de les démarrer, les joindre au script pour qu’il attende la fin des threads, et affiche le pgcd au bon moment :

echangeur=Echangeur(1)
diviseur = Diviseur(3600,3024)
diviseur.start()
echangeur.start()
diviseur.join()
echangeur.join()
print "Le pgcd est ", diviseur.a

En exécutant ce script Python, on voit apparaître au fur et à mesure l’état des différents threads actifs, et à la fin, le pgcd. Il est conseillé de modifier les durées pour voir l’effet produit sur le script (en particulier, ce qu’il faut faire pour avoir un pgcd faux). C’est un excellent exercice sur les droites graduées...


[1Euclide opérait par soustractions successives, mais la division euclidienne de a par b revient à soustraire b à a répétitivement jusqu’à ce que le résultat soit plus petit que b : Encore une boucle à sortie conditionnelle !

[2vocabulaire propre à Scratch, traduction de l’anglais « sprite ».

[3PéGé est évidemment un pingoin, d’où son nom et son apparence (ou « costume »). On l’a choisi parmi les costumes de la bibliothèque.

[4En fait le « costume » est un bouton, c’est ce qui ressemblait le plus à un CD...

[5je ne sais pas pourquoi mais je n’arrive jamais à écrire l’algorithme d’Euclide correctement du premier coup...

[6cette vilaine manière d’échanger les contenus stomacaux n’est pas si dégoûtante que cela, puisque c’et ainsi qu’est fabriqué le miel


Documents joints

Euclide au format Scratch, zippé
Euclide au format Scratch, zippé
Euclide interactif (html+JavaScript)
Euclide interactif (html+JavaScript)

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


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 24 juillet 2017

Publication

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

Visites

306 aujourd'hui
292 hier
2063396 depuis le début
12 visiteurs actuellement connectés