Accueil » Publications » Le Bulletin Vert » Dans nos classes » MÉDÉE : Une méthode pour construire (...)
  APMEP   MÉDÉE : Une méthode pour construire des algorithmes

Article du bulletin 489

Adhérer ou faire un don

Langer Bernard

- 2 juillet 2012 -

Nous allons exposer, étape par étape, le principe d’une méthode d’analyse appelée méthode déductive, médée en abrégé. Médée a été largement utilisé dans le cadre de l’enseignement de l’Option Informatique dans les années 80. La méthode est générale et peut être utilisée pour toutes les constructions d’algorithmes. Elle est issue des travaux de Claude Pair sur la construction systématique des programmes menés au CRIN de Nancy.

Méthode Marche rationnelle de l’esprit pour arriver à la connaissance ou à la démonstration d’une vérité : La méthode se différencie de la théorie. Ensemble ordonné de manière logique de principes, de règles, d’étapes, qui constitue un moyen pour parvenir à un résultat : Méthode scientifique. (Petit Larousse)

Pour illustrer la construction d’algorithmes avec Médée, intéressons-nous à un problème particulièrement simple : le calcul de la somme $\frac{n_1}{d_1} + \frac{n_2}{d_2}$ de deux fractions dont il faudra afficher le résultat sous forme de fraction irréductible. Pour simplifier (encore) l’énoncé nous supposerons que ${n_1,d_1,n_2,d_2}$ sont des entiers naturels avec bien sûr ${d_1}$ et ${d_2}$ non nuls.

Le calcul demandé se résume à $\frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1 \times(d \div d_1)+n_2\times(d\div d_2) }{d}$ , d étant le PPCM de ${d_1}$ et ${d_2}$.

La fraction obtenue n’étant pas nécessairement irréductible, il faudra simplifier le résultat en divisant numérateur et dénominateur par leur PGCD. Par exemple :

$$\frac{7}{12} + \frac{13}{15} = \frac{35+52}{60} = \frac{87}{60}=\frac{29}{20}$$

L’analyse se déroule en plusieurs étapes et consiste à remplir un unique tableau comportant trois colonnes :

• La première est nommée lexique. On y précise le type (entier, décimal, caractère, etc.) et la signification des variables utilisées.

• La troisième est intitulée définitions. Elle contient les diverses instructions de l’algorithme. Pour des raisons qui apparaîtront clairement dans ce qui suit, ces instructions sont énoncées dans le désordre.

• Grâce à une numérotation, la deuxième colonne précisera l’ordre dans lequel les instructions doivent être exécutées.

Signalons que les instructions utilisées sont liées aux possibilités du processeur (humain ou machine) qui les exécutera. On pourrait par exemple imaginer que ce processeur soit en mesure de traiter directement l’addition de fractions en donnant un résultat simplifié. Dans ce cas l’algorithme cherché se réduit trivialement à une seule instruction !

Nous supposerons donc que les fonctions PGCD et PPCM ne sont pas primitives.

Les étapes de la construction de l’algorithme :

Étape 1 :

On commence par énoncer clairement le résultat à obtenir. Dans notre exemple, le résultat à obtenir consiste à écrire deux entiers : le numérateur de la somme et le dénominateur de la somme. Les noms de ces deux variables NS et DS sont recopiés dans le lexique en précisant leur type (ici deux éléments de $\mathbb{N}$) ainsi que leur signification (le mot variable est à prendre au sens de conteneur permettant de stocker un élément qui aura été calculé ou saisi manuellement).

Étape 2 :

À cette étape ainsi qu’à toutes les étapes suivantes, on puise un élément du lexique (ici NS) et on donne sa définition dans la colonne éponyme. Toutes les variables utilisées qui ne figurent pas encore au lexique y sont recopiées (ici N et P).

Puisque NS est définie, nous cochons cette variable dans la colonne du lexique.

Étape 3 :

On poursuit la démarche entamée au cours des étapes suivantes…

Étape 4 :

Étape 5 :

Étape 6 :

Étape 7 :

Remarque  : une donnée est une valeur non calculable qui est en général saisie au clavier…

Étapes 8 – 9 – 10 :

Étape 11 : la numérotation

D’une manière évidente, les diverses instructions ne peuvent pas être exécutées dans l’ordre où elles ont été écrites.

La numérotation des instructions se fait en recherchant dans la colonne des définitions la première instruction dont tous les paramètres nécessaires à son exécution sont connus.

Ainsi P ne peut être calculé que lorsque N et D l’ont été. Mais N ne sera calculable qu’après avoir déterminé D, etc.

La numérotation des instructions n’est en général pas unique et il est d’usage de démarrer par la saisie des données.

Étape 12 : les fonctions

Il reste à « fabriquer » les fonctions PPCM et PGCD.

Puisque PPCM(a,b) × PGCD(a,b) = a × b, il suffira de connaître la valeur prise par l’une des fonctions pour en déduire immédiatement la valeur prise par l’autre. Notre choix se portera sur le calcul du PPCM. Il s’agit d’un choix arbitraire qui n’est sans doute pas le meilleur mais il évite d’écrire une n $^ {eme} $ fois l’algorithme d’Euclide ! L’idée retenue est la suivante :

Parmi les multiples de a, on cherche le premier qui est aussi multiple de b.

Quelques explications concernant les listes (suites finies) sont nécessaires :

L’algorithme du PPCM ci-dessus construit la liste des multiples de a inférieurs ou égaux à b. Cette liste est construite grâce à une itération qui est essentiellement une « fabrique de listes ». De fait une liste engendrée par itération apparaît toujours sous quatre occurrences distinctes dans l’analyse :

• La valeur initiale m $_i $ (lire « m initial »).

• L’ancienne valeur de m notée @m.

• La valeur courante m.

• La valeur finale m $_f $ (lire « m final »).

Cette approche a le mérite de clarifier ce qui ne l’est plus dans un programme où m, m $_i $, @m, m $_f $ se fondent en une désignation unique. L’écriture m = @m + a a le mérite de clarifier le processus d’affectation.

Étape 13 :

À ce stade l’algorithme est complet. Nous le reproduisons sous sa forme définitive ci-dessous :

L’algorithme obtenu grâce à cette démarche n’a pas la prétention d’être optimisé et il arrive parfois qu’une mise en œuvre sur un exemple permette de découvrir des améliorations simples à mettre en place.

Examinons par exemple ce qui se passe dans le calcul du PPCM.

Déterminons le PPCM de 35 et de 28, i.e. PPCM(35,28).

Le PPCM de 35 et 28 est m $_f $ = 140.

Nous aurions également pu calculer PPCM(28,35). Les itérations ne sont plus les mêmes pour un résultat bien sûr identique :

Le PPCM de 28 et 35 est m $_f $ = 140.

Sur cet exemple nous constatons que si l’on choisit comme premier argument le plus grand des deux entiers les itérations sont moins nombreuses. Il est donc judicieux d’ordonner au préalable les deux entiers. D’où une variante plus performante, bien que plus longue, du même algorithme :

Une fois l’algorithme obtenu il reste à l’exécuter ou le faire exécuter. L’exécuter à la main consiste en général à remplir des tableaux tels ceux présentés ci-dessus pour le calcul du PPCM. Néanmoins cette tâche devient vite fastidieuse, voire impossible à réaliser du fait de sa complexité et du temps nécessaire !

C’est là où l’ordinateur intervient. Mais, avant de pouvoir tester l’algorithme sur l’ordinateur, il faut le coder dans un langage de programmation. Cette tâche de codage est une tâche mécanique, peu gratifiante et qui doit absolument être précédée par une phase d’analyse telle que celle présentée ci-dessus. Ne pas se livrer à cette phase d’analyse conduit à de grandes pertes de temps et à des programmes spaghettis dont on ne maîtrise pas les méandres et qui sont impossibles à maintenir.

Nous donnons en annexe les codages en ALGOBOX, PYTHON et SCRATCH de l’algorithme précédent. Les remarques critiques qui précédent chaque codage n’engagent que leur auteur.

ANNEXE 1 : CODAGE ALGOBOX

Algobox est un excellent outil d’initiation qui ne permet cependant pas de développer des algorithmes après la classe de seconde.

La syntaxe très lourde le rend fastidieux à utiliser au-delà la phase d’initiation.

Écrire « m prend la valeur de m + D1 » ne résout pas la difficulté de l’instruction d’affectation.

Il n’est pas possible de coder des fonctions, ce qui oblige à écrire deux fois les instructions du calcul du PPCM (lignes 17-21 puis 24-28)

Codage

ANNEXE 2 : CODAGE PYTHON

Python est un vrai langage de programmation largement utilisé par la communauté scientifique.

Cependant les diverses versions ne sont pas francisées et interdisent en général l’affichage d’un texte comportant des caractères accentués. Cette situation nous fait malheureusement revenir une trentaine d’années en arrière.

Le typage dynamique des variables (le type d’une variable est défini par sa première affectation) n’est pas très pédagogique et peut être source de nombreuses confusions pour le débutant.

En revanche Python permet une programmation professionnelle (y compris la programmation de type objet) et offre une bibliothèque gigantesque, en particulier concernant les applications mathématiques.

Codage

ANNEXE 3 : CODAGE SCRATCH

Un langage surprenant et novateur.

Il est cependant très déroutant lors d’une première utilisation.

Les expressions algébriques sont très lourdes à construire et il ne semble pas adapté au codage d’algorithmes tels celui présenté dans cet article.

La boucle universelle répéter tant que est absente.

On ne peut pas construire de fonctions.

(Article mis en ligne par Annie LE LOUS)
 Accueil   Plan du site   Haut de la page   Page précédente