Mathématice, intégration des Tice dans l'enseignement des mathématiques  

Dix-chotomie !
Moteur de recherche
Cet article expose la construction d’algorithmes à l’aide d’une méthode qui a fait ses preuves : la méthode déductive, en abrégé  : Médée. Largement exploitée dans le cadre de l’enseignement de l’Option Informatique dans les années 80, la méthode est générale et utilisable dans toutes les constructions d’algorithmes. Elle est issue des travaux de Claude Pair, menés au CRIN de Nancy, sur la construction systématique des programmes.

Cette méthode a d’indéniables vertus pédagogiques et mérite d’être utilisée dès la phase d’apprentissage.

L’exemple choisi illustre la démarche déductive sans vouloir prétendre à une quelconque originalité sur le plan mathématique. En particulier elle n’est sans doute pas plus efficace que la classique dichotomie.

La lecture de l’article est complétée et sera grandement facilitée, en visualisant le diaporama joint. Nous y renverrons le lecteur le moment venu.

1 Un peu de mathématiques pour commencer

Le graphique ci-contre représente la fonction définie par $f(x) = x^3 - 6x + 1$ sur l’intervalle [-3 ; 3].

Puisque f est continue, strictement croissante sur I = [2 ; 3] et qu’elle change de signe sur I, le théorème des valeurs intermédiaires permet d’affirmer qu’il existe dans I une unique valeur α telle que f(α) = 0.

Sous les hypothèses ci-dessus, la méthode de la dichotomie (du grec dikhotomia diviser en deux) permet de trouver une valeur approchée de la solution α.

Nous ne décrirons pas cette méthode itérative bien connue qui consiste à diviser l’intervalle I en deux sous-intervalles et à localiser la solution dans l’un d’entre-eux.

Sous les mêmes hypothèses de départ, il est possible d’étendre le principe de la dichotomie en « découpant » l’intervalle I en dix sous-intervalles tous de même longueur et en localisant la solution dans l’un de ces sous-intervalles.

Prenons par exemple comme intervalle initial $I_0 = [2 ; 3]$. Le graphique ci-contre montre qu’en découpant l’intervalle $I_0$ en 10 sous-intervalles de même longueur 0,1 la solution se trouve dans $I_1 = [2,3 ; 2,4]$. Une façon de localiser la solution à l’aide d’un calcul consiste à trouver le seul sous-intervalle [u ; v] pour lequel $f(u) \times f(v) \leq 0$ (dans ce cas $f(u)$ et $f(v)$ sont de signes contraires)

On recommence alors un nouveau balayage en utilisant l’intervalle $I_1 = [2,3 ; 2,4]$, etc.

En notant $I_n = [a_n ; b_n]$ la suite des intervalles obtenus en itérant le processus précédent il est clair que :
- La suite $(a_n)$ est croissante majorée par $b_0$
- La suite $(b_n)$ est décroissante minorée par $a_0$
- La différence $(b_n - a_n) = \frac{b_0 - a_0}{10^n}$ tend vers 0 lorsque n tend vers l’infini.

Nous pouvons donc conclure que les suites $(a_n)$ et $(b_n)$ sont adjacentes et par conséquent convergentes vers la solution α cherchée.

Si on précise à l’avance le nombre d de décimales exactes attendues on pourra arrêter le processus dès que la longueur de l’intervalle $[a_n ; b_n]$ est inférieure à $10^{-d}$. Finalement on choisira comme valeur approchée le centre du dernier intervalle.

Voilà pour la partie mathématique (conforme au programme actuel de terminale S).

2 Construction de l’algorithme

Un algorithme est une liste ordonnée d’instructions obtenue durant la phase d’analyse du problème.

L’analyse Médée se déroule en plusieurs étapes et consiste à remplir un 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 en général é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 pour conduire au résultat.

Signalons que les instructions utilisées sont liées aux possibilités du processeur (humain ou ordinateur) qui les exécutera. On pourrait par exemple imaginer que ce processeur soit en mesure de traiter directement la résolution d’équations de la forme $f(x) = 0$ sur un intervalle donné. Dans ce cas l’algorithme recherché se réduirait trivialement à une seule instruction !

La manière de conduire l’analyse est présentée dans le diaporama joint. Nous invitons le lecteur à consulter cette présentation.

Pour une bonne compréhension voici quelques précisions complémentaires :

L’affectation Lorsqu’on écrit $x = a + 3$ il s’agit d’une affectation. Le processeur calcule le nombre $a + 3$ puis le range dans la variable $x$.
Les Itérations Il arrive très souvent que dans les processus itératifs on soit amené à modifier la valeur d’une variable en fonction de sa valeur précédente (l’augmenter de 1 par exemple). Pour éviter l’écriture ambigüe $x = x + 1$ on préférera $x = @ x + 1$ le caractère @ se lira dans ce cas « ancien » : la nouvelle valeur de $x$ est égale à son ancienne valeur augmentée de 1.

A l’instar des définitions données par récurrence, il est clair que l’écriture $x = @ x + 1$ n’a de sens que si l’on donne une valeur initiale à $x$. Cette valeur est notée $x_i$ . Sa présence doit être systématique dès qu’on utilise le caractère @ devant une variable.

Dans le même ordre d’idée $x_f$ désigne la valeur finale de $x$ en sortie de boucle.
Les booléens Une variable booléenne (encore appelée booléen) est une variable qui peut prendre l’état logique VRAI ou l’état FAUX. Ainsi lorsqu’on écrit $x = (a = b^2)$, $x$ est un booléen qui prend la valeur VRAI lorsque a est égal à $b^2$ et FAUX sinon. Attention cependant au signe « = » dans l’expression précédente : le premier est le symbole d’affectation ($x$ prend la valeur…), le second est l’opérateur de comparaison (concernant l’assertion « a est égal à $b^2$ »).

Si $x$ est un booléen, on pourra par exemple écrire : si $x$ alors
Les listes Le type de données « intervalle » n’est en général pas implémenté directement dans les langages de programmation. Nous pourrions utiliser la programmation objet offerte par les langages modernes pour construire et utiliser de manière élégante un type intervalle. Mais dans le cadre d’une initiation on peut contourner le problème en considérant qu’un intervalle (fermé) est une liste de deux réels (la borne inférieure et la borne supérieure). On pourra alors représenter l’intervalle fermé [a ; b] par le tableau I tel que I[0] = a et I[1] = b.

L’algorithme obtenu est le suivant :

Remarques :

- Une remarque concernant la fonction localiseDans :
On constate que dans la boucle « répéter tantque » h est évaluée à chaque itération alors que sa valeur ne change pas ! Il est donc judicieux d’évaluer h (une seule fois) à l’extérieur de la boucle.
- L’expression $sol = ent(centre(J) \times 10^d) \times 10^{-d}$ peut laisser perplexe… En fait ent désigne la partie entière d’un réel et si par exemple le centre de l’intervalle J est 1,756 nous obtenons pour d = 2 : $centre(J) \times 10^d = 1,756 \times 10^2 = 175,6 $
$ent(centre(J) \times 10^d) = 175$
$ent(centre(J) \times 10^d) \times 10^{-d} = 175 \times 10^{-2} = 1,75$

3 Le codage

Coder l’algorithme consiste à le traduire dans un langage de programmation disponible sur un ordinateur. Cette phase terminale est essentiellement technique. Souvent impressionnante pour le novice elle ne soulève pas de difficultés particulières mais nécessite, au début, la consultation fréquente des manuels relatifs à la syntaxe et aux possibilités du langage.

- la version définitive de l’algorithme. Grâce aux fonctions couper/coller il est facile de réécrire l’algorithme dans l’ordre d’exécution des instructions, la colonne centrale devenant alors inutile…
- un codage en langage Python de l’algorithme que nous venons d’élaborer.

Cet algorithme est loin d’être parfait lorsqu’on le met en œuvre sur un ordinateur. En particulier si l’intervalle de départ ne contient pas de solution à l’équation, la fonction localiseDans bouclera , puisqu’il n’y aura pas de changement de signe sur cet intervalle…

Marienthal, 19 avril 2010

Annexes Annexe 1 : Diaporama
Zip - 631.5 ko
La méthode déductive Médée présentée sur un exemple
Format pptx (Microsoft Office 2007)

Annexe 2 : PROGRAMME PYTHON

Zip - 693 octets
Dix-chotomie.py
from math import *
# ************
# Fonction f *
# ************
def f(x) :
   y=x**3-6*x+1
   return y
# *****************
# Fonction centre *
# *****************
def centre(I) :
   c=(I[0]+I[1])/2
   return c
# *******************
# Fonction longueur *
# *******************
def longueur(I) :
   l=I[1]-I[0]
   return l
# ***********************
# Fonction localiseDans *
# ***********************
def localiseDans(I):
   k=0
   print "[",I[0]," , ",I[1],"]"
   h=longueur(I)/10.0
   changeSigne=0
   while not(changeSigne):
       u=I[0]+k*h
       v=u+h
       changeSigne=(f(u)*f(v)<=0)
       k=k+1
   J[0]=u
   J[1]=v
   return J
# ********************
# Début du programme *
# ********************
d=input("Nombre de decimales ?")
a=input("Borne de gauche de l'intervalle ?")
b=input("Borne de droite de l''intervalle ?")
J=[a,b]
print "Debut du programme..."
epsilon=10**(-d)
while (longueur(J)>epsilon) :
   J=localiseDans(J)
sol= floor(centre(J)*10**d)*10**(-d)
print "La solution cherchée est : ",sol


Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197