Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°15 - Mai 2009 > Pourquoi utiliser (aussi) des langages (...)

Pourquoi utiliser (aussi) des langages fonctionnels au lycée ?
Moteur de recherche
Mis en ligne le 24 mai 2009, par Guillaume Connan

L’algorithmique fait une entrée remarquée dans le nouveau programme de Seconde. Il y est fait clairement mention de l’apprentissage de l’affectation, des entrées-sorties et des boucles comme allant de soi, ce qui sous-entend que seule existe la programmation impérative. Cependant la programmation fonctionnelle est une alternative beaucoup plus proche des mathématiques et de leur enseignement dans le secondaire. Nous verrons dans quelle mesure l’enseignement de l’algorithmique via les langages fonctionnels est moins perturbante pour l’élève et le professeur n’ayant pas reçu de formation récente en algorithmique.

Cet article a été repris dans Repères-Irem n° 81

I. Programmation impérative / Programmation fonctionnelle

I.1 Conventions

L’objet de cet article n’est pas d’envisager ces deux modes de programmation avec le point de vue de l’informaticien cherchant la méthode la plus rapide mais avec celui d’un professeur de mathématiques s’adressant à des élèves débutants dans ce domaine [1].
Nous ne parlerons pas d’un logiciel en particulier. Cependant, pour les applications pratiques, nous utiliserons XCAS [2], logiciel multifonctions spécialement conçu pour être utilisé en classe de mathématiques et OCAML [3], logiciel utilisant la programmation fonctionnelle.

I.2 Programmation impérative

La programmation impérative est la plus répandue (Fortran, Pascal, C,...) et la plus proche de la machine réelle. Son principe est de modifier à chaque instant l’état de la mémoire via les affectations.
Ce mode de programmation présente plusieurs défauts pour un lycéen :

– il s’éloigne des mathématiques en utilisant l’affectation comme base de programmation. Une même variable peut prendre des valeurs tout à fait différentes selon le moment où on l’évalue alors qu’un élève de seconde découvre les fonctions qui à un nombre donné associe une unique image ;

– la mémoire est constamment modifiée par le programme : le programmeur doit à chaque instant connaître son état pour savoir ce que représentent les variables affectées ;

– on est obligé de créer des variables temporaires pour que certaines zones de la mémoire restent dans un certain état : cela est source de nombreux bogues dus à une mauvaise maîtrise de la chronologie des affectations.

Prenons l’exemple très simple d’un programme déterminant le successeur d’un entier.
Une case mémoire nommée n reçoit comme valeur 1 :

n:=1:;

Écrivons une fonction plus_n qui ajoute k à n :


plus_n(k):={
n:=n+k;
return(n);
}:;

Alors plus_n(3)renvoie 4 et si on demande à nouveau plus_n(3) on obtient 7.

Ainsi plus_n n’est pas une fonction au sens mathématique car 3 peut avoir des images distinctes !
Bien sûr, il existe des moyens d’y remédier. Par exemple :

 
n:=1:;

plus_n_bis(k):={
local temp;
temp:=n+k;
return(temp);
}:;

Cette fois plus_nbis(3) renvoie toujours 4 grâce à l’affectation locale donc provisoire de la mémoire sous l’étiquette temp.
Il s’agit d’une subtilité informatique qui pourrait sembler difficile à assimiler par tous les élèves de Seconde mais qui est souvent le préalable à toute démarche de programmation impérative. Vu sous cet angle, les efforts nécessaires à l’enseignement de la notion d’affectation ne semblent pas servir la cause mathématique...
L’algorithme ici est cependant fort simple et nous aurions pu nous passer d’affectation :

 
n:=1:;
plus_n(k):={
return(n+k);
}:;

Dans la plupart des cas, ce genre d’algorithme sera englobé dans un algorithme plus complexe et on ne pourra se passer d’affectation si on garde une démarche impérative comme nous le verrons dans les exemples suivants.

1.3 Programmation fonctionnelle

Les langages fonctionnels bannissent totalement les affectations. Ils utilisent des fonctions au sens mathématique du terme, c’est-à-dire qu’une fonction associe une unique valeur de sortie à une valeur donnée en entrée. Les effets négatifs listés précédemment disparaissent donc. Les fonctions peuvent être testées une par une car elles ne changent pas selon le moment où elles sont appelées dans le programme. On parle de transparence référentielle. Au contraire, une procédure avec effets de bord ne dépend pas uniquement des arguments entrés et donc peut changer de comportement au cours du programme.

La récursivité est le mode habituel de programmation avec de tels langages : il s’agit de fonctions qui s’appellent elles-mêmes. Pendant longtemps, la qualité des ordinateurs et des langages fonctionnels n’était pas suffisante et limitaient les domaines d’application de ces langages.
La notion de récursion n’était jusqu’à maintenant pas au programme de Seconde mais apparaît maintenant dans le thème « phénomènes d’évolution ».

Si nous reprenons notre exemple précédant, nous pouvons faire exprimer aux élèves que l’entier suivant n est égal à 1+ l’entier suivant n − 1 : on ne sort pas des limites du cours de mathématiques et on n’a pas besoin d’introduire des notions d’informatique en travaillant sur cette notion.

On peut écrire un algorithme ainsi :

      si n = 0 alors
          1
      sinon
          1+ successeur de n - 1
Algorithme 1 : successeur d’un entier - version récursive

La récursivité n’est pas l’apanage des langages fonctionnels. Par exemple XCAS permet d’écrire des programmes
récursifs :

   plus_1_rec(k):={
    if(k==0){1}
    else{1+plus_1_rec(k-1)}
  }:;  

Pas de problème pour plus_1_rec(700) mais plus_1_rec(7000) dépasse les possibilités de calcul du logiciel.
Et oui, un langage impératif ne traite pas efficacement le problème de pile, c’est pourquoi pendant longtemps seuls les algorithmes impératifs ont prévalus.


Remarque :
par défaut, XCAS s’arrête au bout de 50 niveaux de récursion. Pour aller plus loin, il faut cliquer sur
config à côté de save. Régler alors la fenêtre recurs à 1000 par exemple.

Utilisons à présent le langage fonctionnel CAML, développé par l’INRIA [4] . Même s’il intègre des aspects impératifs pour faciliter l’écriture de certains algorithmes, il est en premier lieu un langage fonctionnel qui en particulier gère très efficacement la mémoire de l’ordinateur pour éviter sa saturation lors d’appels récursifs.

  # let rec plus_1_rec(k)=
      if k=0 then 1
      else 1+plus_1_rec(k-1);;

Alors par exemple :

  # plus_1_rec(36000);;
  - : int = 36001

Mais

  # plus_1_rec(3600000);;
  Stack overflow during evaluation (looping recursion?).

La pile où sont stockés les résultats intermédiaires créés par la récursion est en effet saturée.
Aujourd’hui, les langages fonctionnels sont très efficaces et gèrent de manière intelligente la pile. Ils le font soit automatiquement, soit si la fonction utilise une récursion terminale, c’est-à-dire si l’appel récursif à la fonction n’est pas enrobé dans une autre fonction.
Ici, ce n’est pas le cas car l’appel récursif plus_1_rec(k-1) est enrobé dans la fonction x -> 1 + x.
On peut y remédier en introduisant une fonction intermédiaire qui sera récursive terminale :

 
# let rec plus_1_rec_temp(k,resultat)=
               if k=0 then resultat
               else plus_1_rec_temp(k-1,resultat+1);;

puis on appelle cette fonction en prenant comme résultat de départ 1 :

 
# let plus_1_rec_bis(k)=
     plus_1_rec_temp(k,1);;

Alors :

  # plus_1_rec_bis(360000000);;
  - : int = 360000001

Il n’y a donc aucun problème pour traiter 360 millions d’appels récursifs !
Dans un premier temps, en Seconde, on peut laisser de côté ce problème de récursion terminale et se contenter de travailler sur de petits entiers. Ainsi, on peut choisir de travailler avec CAML ou XCAS par exemple, même si ce dernier n’est pas un langage fonctionnel.

2 Comparaison impératif/récursif : quelques exemples

2.1 Suites

La relation $u_{n+1} = 3u_n + 2$ valable pour tout entier naturel $n$ et la donnée de $u_0 = 5$ constituent un algorithme de calcul récursif de tout terme de la suite $(u_n)$. De telles suites peuvent être rencontrées dans le thème d’étude « phénomènes d’évolution ».
Sa traduction dans des langages sachant plus ou moins traiter de tels algorithmes est directe.
Par exemple, en XCAS cela devient :

  u(n,uo):={
  if(n==0){return(uo)}
  else{3*u(n-1,uo)+2}
  }

et en CAML :

  # let rec u(n,uo)=
         if n=0 then uo
         else 3*u(n-1,uo)+2;;

Pour la plupart des langages, de telles définitions, qui collent au plus près à la situation mathématique, limitent les capacités de calcul de l’ordinateur car les différentes valeurs calculées sont stockées dans une pile.
Cela a entraîné la création d’algorithmes plus longs à écrire et plus éloignés des mathématiques mais qui avaient à l’époque l’intérêt de soulager la mémoire de l’ordinateur : au lieu de stocker de nombreuses valeurs dans une pile, on affecte une seule case mémoire aux valeurs de la suite qui sera ré-affectée, au fur et à mesure du déroulement du programme.
Cela donne en XCAS :

  u_imp(n,uo):={
  local k,temp;
  temp:=uo;
  for(k:=1;k<=n;k:=k+1){
  temp:=3*temp+2;
  }
  return(temp);
  }

Il y avait un problème mathématique et s’y ajoute un mécanisme informatique, l’affectation, qui pourrait dans un premier temps s’avérer perturbant pour des élèves de Seconde.

2.2 Partie entière

La partie entière n’est pas explicitement au programme de seconde mais sa détermination algorithmique enrichit l’étude des ensembles de nombres.
On peut définir la partie entière d’un réel x comme étant le plus grand entier inférieur à x.

2.2.1 Algorithme récursif

On part du fait que la partie entière d’un nombre appartenant à [0 ; 1[ est nulle.
Ensuite, on « descend » de x vers 0 par pas de 1 si le nombre est positif en montrant que $|x| = 1 + |x - 1|$.
Si le nombre est négatif, on « monte » vers 0 en montrant que $|x| = -1 + |x + 1|$.

En CAML :

  # let rec partie_entiere (x)=
               if x >= 0. && x < 1.
                then 0.
                else if x > 0.
                          then          1. +. partie_entiere (x -. 1.)
                          else -.1. +. partie_entiere (x +. 1.);;

En XCAS :

  partie_entiere(x):={
  if((x>=0) and (x<1)){0}
  else{ if(x>0){1+partie_entiere(x-1)}
            else{-1+partie_entiere(x+1)}
        }
  }:;

On notera que l’algorithme récursif s’applique ici à des réels et non plus à des entiers : on dépasse ainsi le cadre des suites. Pour que l’algorithme fonctionne, on ne raisonne sur des intervalle et non plus sur une valeur initiale.

2.2.2 Algorithme impératif

Pour les nombres positifs, on part de 0. Tant qu’on n’a pas dépassé x, on avance d’un pas. La boucle s’arrête dès que k est strictement supérieur à x. La partie entière vaut donc k − 1.
Dans le cas d’un réel négatif, il faut cette fois reculer d’un pas à chaque tour de boucle et la partie entière est la première valeur de k à être inférieure à x :

      Entrées : x(réel)
      Initialisation : k <- 0
      début
          si x>=0 alors
              tant que k<=x faire
                  k<- k+1
              retourner k-1
          sinon
              tant que k>x faire
                  k<- k-1
              retourner k
      fin
Algorithme 2 : partie entière d’un réel quelconque

Avec XCAS en Français :

 pe(x):={
 local k;
 k:=0;
 si x>=0 alors
     tantque k<=x faire
         k:=k+1;
     ftantque;
     return(k-1);
 sinon
     tantque k>x faire
         k:=k-1;
     ftantque;
     return(k);
 fsi;
 }:;

Avec XCAS en anglais :

 pe(x):={
 local k;
 k:=0;
 if(x>=0){
     while(k<=x){k:=k+1};
     return(k-1);
           }
 else{
     while(k>x){k:=k-1};
     return(k);
      }
 }:;


2.2.3 Comparaison

Dans le premier cas, on réfléchit à la notion mathématique de partie entière. On met en place des résultats mathématiques intéressants.
Dans le deuxième cas, on utilise une affectation (k devient k + 1 ou k − 1) et une « boucle while » avec un test et une action d’affectation tant que le test est vrai. Il s’agit d’un traitement physique de la mémoire qui traduit un phénomène électronique et non mathématique. On perd donc de vue la notion mathématique mais on donne une vision dynamique de la recherche de la partie entière : on peut imaginer un petit « personnage » se promenant sur la droite des réels en faisant des pas de longueur 1 et qui continue à avancer tant qu ’ il n’a pas dépassé le réel.

2.3 Calculs de sommes

On veut par exemple calculer la somme des entiers de 1 à n.

2.3.1 Algorithme récursif

Il suffit de remarquer que cela revient à ajouter n à la somme des entiers de 1 à n − 1 sachant que la somme des entiers de 1 à 1 vaut... 1.

En XCAS :

som_ent(n):={
if(n==1){1}
else{n+som_ent(n-1)}
}:;

En CAML :

 
# let rec som_ent(n)=
       if n=1 then 1
       else n+som_ent(n-1);;

Par exemple :

# som_ent(100);;
- : int = 5050

On peut même généraliser cette procédure à n’importe quelle somme du type $\sum_{k=0}^{n}f(k)$ :

# let rec som_rec(f,ko,n)=
       if n=ko then f(ko)
       else f(n)+som_rec(f,ko,n-1);;

2.3.2 Algorithme impératif

     
Entrées : n(entier naturel)
Initialisation : S<-0
     début
         pour k de 1 à n faire
             S<- S+k
         retourner S
     fin
Algorithme 3 : somme des entiers de 1 à n

Traduction XCAS en français :

 som(n):={
 local S;
 S:=0;
 pour k de 1 jusque n faire
    S:=S+k;
 fpour;
 return(S)
 }

En anglais :

 som(n):={
 local S;
 S:=0;
 for(k:=1;k<=n;k++){S:=S+k};
 return(S)
 }

2.3.3 Comparaison

Ici encore, on ne sort pas des mathématiques avec l’algorithme récursif alors qu’on a une approche physique avec l’algorithme impératif : S vaut 0 au départ et on demande S en sortie ; S ne vaut donc plus 0 en général... Cela peut être troublant pour des élèves qui ont du mal à résoudre des équations simples et oublient ce qui se cache derrière
le symbole « = ». Il y aurait une égalité en mathématiques et une autre en informatique !
Cependant, cette manière de voir peut être une nouvelle fois plus intuitive : si on considère S comme le solde de son compte en banque, on surveille son compte régulièrement en ajoutant k à chaque visite.
La version impérative peut de plus être directement liée à l’écriture $\sum_{k=0}^{n}f(k)$
qu’on lit « somme des k pour k variant de 1 à n » où la boucle « pour » apparaît de manière naturelle.

2.4 Développement en fractions continues

2.4.1 Pratique du développement

– Vous connaissez l’algorithme suivant :

172 = 3 × 51 + 19 (1)
51 = 2 × 19 + 13 (2)
19 = 1 × 13 + 6 (3)
13 = 2 × 6+1 (4)
6 = 6 × 1+0 (5)

– On peut donc facilement compléter la suite d’égalité suivante :
$\frac{172}{51}=3+\frac{19}{51}=3+\frac{1}{\frac{51}{19}}=3+\frac{1}{2+\frac{13}{19}}=...$

– Quand tous les numérateurs sont égaux à 1, on dit qu’on a développé $\frac{172}{51}$ en fraction continue et pour simplifier l’écriture on note :

$\frac{172}{51}= [3 ; 2 ; . . . ]$

– Par exemple, on peut développer $\frac{453}{54}$ en fraction continue.

– Dans l’autre sens on peut écrire [2 ; 5 ; 4] sous la forme d’une fraction irréductible.
Nous allons construire des algorithmes correspondant au développement en fractions continues.

2.4.2 Version récursive

On suppose connus les algorithmes donnant le reste et le quotient d’une division euclidienne.

     
fc(a,b)
si b=0 alors
   retourner liste vide
sinon
   retourner [quotient(a,b),fc(b,reste(a,b))]
Algorithme 4 : fractions continues : version récursive

En XCAS :

 fc(a,b):={
 if(b==0){return([])};
 return(concat(iquo(a,b),fc(b,irem(a,b))))
 }:;

En CAML

 # let rec fc (a,b) =
         if b = 0
          then []
          else a/b :: fc(b,a-a/b*b);;

Remarques : On utilise élément :: liste pour rajouter un élément en début de liste. Par ailleurs CAML travaille par défaut avec des entiers donc a/b est le quotient entier de la division de a par b. Ainsi a-a/b*b est en fait le reste de la division euclidienne de a par b.

Dans les deux cas fc(172,51) renvoie [3,2,1,2,6]

2.4.3 Version impérative

     Entrées : 2 entiers a et b
     Initialisation :
     num <- a
     den<- b
     res<-reste(num,den)
     Liste<-vide
     début
         tant que res=0 faire
             Liste <-Liste,quotient(num,den)
             num <- den
             den <- res
             res <- reste(num,den)
     fin
     retourner [Liste,quotient(num,den)]
Algorithme 5 : Fractions continues : version impérative

Traduction XCAS :

 
frac_cont(a,b):={
 local num,den,res,Liste;
 num:=a;
 den:=b;
 res:=irem(num,den);
 Liste:=NULL;
 while(res>0){
       Liste:=Liste,iquo(num,den);
       num:=den;
       den:=res;
       res:=irem(num,den);
 }
 return([Liste,iquo(num,den)]);
 }:;

2.4.4 Comparaison

Dans la version récursive on reste dans les mathématiques même si l’on utilise une fonction qui à deux entiers associe une liste.
Dans la version impérative on est confronté au même problème ainsi qu’à la manipulation de plusieurs niveaux d’affectation et une boucle while.

2.5 Décomposition en base 2

2.5.1 Expérimentation

Une méthode pour obtenir l’écriture en base 2 d’un nombre est d’effectuer des divisions euclidiennes successives. Par exemple pour 11 :

11 = 2 × 5 + 1
= 2 × 2 × 2+1 +1
= 2 × 2 × (2 × 1) + 1 + 1
= $2 × (2^2 + 1) + 1$
= $2^3 + 2 + 1$
= $1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0$

L’écriture de 11 en base 2 est donc 1011 : c’est la liste des restes obtenus mais dans l’ordre inverse.
La méthode est facilement généralisable.

2.5.2 Version récursive

Notons $q_n$ et $r_n$ le quotient et le reste après n divisions.
$q_{n+1}$est le quotient entier de $q_n$ par 2 et on rajoute $r_{n+1}$ à notre liste de restes.
Après un certain nombre de divisions, le quotient sera strictement inférieur à 2.

      Binaire(n)
      Entrées : un entier n
      début
          si n<2 alors
              retourner n
          sinon
              retourner Binaire(quotient(n,2)),reste(n,2)
      fin
Algorithme 6 : Conversion binaire : version récursive

et en CAML :

  # let rec binaire n =
               if n<2
                  then [n]
               else binaire(n/2) @ [n mod 2];;

Remarque : On utilise liste 1 @ liste 2pour concaténer deux listes.

2.5.3 Version impérative

     Entrées : un entier n
     Initialisation :
     r <- le reste de la division de n par 2
     q <- le quotient de la division de n par 2
     R une liste contenant r au départ.
     début
         tant que q>0 faire
             r <- le reste de la division de q par 2
             q <- le quotient de la division de q par 2
             On ajoute r au début de la liste R.
         retourner R
     fin
Algorithme 7 : décomposition en base 2 En XCAS :

Comme dans la plupart des langages de calcul, le reste et le quotient de la division euclidienne de a par b sont obtenus respectivement avec irem(a,b) et iquo(a,b).
On concatène deux listes avec concat(L1,L2).

 base_deux(n):={
 local r,R,q;
 r:=irem(n,2);
 q:=iquo(n,2);
 R:=[r];
 tantque q>0 faire
   r:=irem(q,2);
   q:=iquo(q,2);
   R:=concat([r],R);
 ftantque;
 return(R);
 }:;

On peut bien sûr généraliser ceci à n’importe quelle base.

3 Calcul du PGCD par l’algorithme d’Euclide et un exemple d’application au calcul avec des fractions

Un sujet phare de la future Seconde est l’étude de l’algorithme d’Euclide. Il s’appuie sur la propriété suivante : si b est non nul,
PGCD(a, b) = PGCD(b, reste(a, b)) . C’est un mécanisme récursif qui se traduit naturellement.

En CAML :

 # let rec pgcd (a,b) =
                 if b=0
                  then a
                  else pgcd(b,a-a/b*b);;

En XCAS :

 pgcd(a,b):={
   if(b==0){return a}
   else{return pgcd(b,irem(a,b))}
 }:;

Cela va nous permettre de construire les opérations sur les fractions. Voyons comment procéder avec CAML.
On va représenter une fraction par une liste du type [numérateur ;dénominateur].

Pour prévenir toute division par zéro on va créer un opérateur traitant
les exceptions qu’on nommera Division_par_zero et qui nous servira de garde-fou :

# exception Division_par_zero;;

On invoquera cette exception avec la commande raise : étant donné le niveau d’anglais des élèves, cette commande est naturelle !...

On peut créer un opérateur qui simplifie les fractions :

# let simp([a;b]) =
if b=0 then raise Division_par_zero
else [a/pgcd(a,b);b/pgcd(a,b)];;

Ne pas tenir compte du Warning qui indique juste que le cas où on entre une liste vide n’a pas été prévu.

On peut tester cette fonction :

# simp([18;12]);;
- : int list = [3; 2]
# simp([1;0]);;
Exception: Division_par_zero.

On crée ensuite une somme simplifiée de fractions :

# let som([a;b],[c;d]) =
if b=0 or d=0 then raise Division_par_zero else
simp([a*d+b*c;b*d]);;

Par exemple :

# som([2;3],[1;6]);;
- : int list = [5; 6]

Une multiplication :

#  let mul([a;b],[c;d]) =
if b=0 or d=0 then raise Division_par_zero else
simp([a*c;b*d]);;

Par exemple :

# mul([3;2],[2;9]);;
- : int list = [1; 3]

Un inverse :

#  let inv([a;b]) =
if b=0 or a=0 then raise Division_par_zero else
simp([b;a]);;

Une division :

# let div([a;b],[c;d])=mul([a;b],inv([c;d]));;

Par exemple, voici comment entrer $1+\frac{2+\frac{3}{4}}{1-\frac{5}{6}}$

                                                             
 # som([1;1],div(som([2;1],[3;4]),som([1;1],[-5;6])));;
 - : int list = [35; 2]

Évidemment, c’est moins pratique que de taper le résultat sur une machine mais ça permet de réfléchir aux différentes opérations, à la notion de fonction,...

On aurait pu écrire les même instructions en XCAS.

4 Alors : algorithmes récursifs ou algorithmes itératifs ?

Beaucoup de professeurs (et donc d’élèves...) sont habitués à traiter certains problèmes à l’aide d’un tableur...qui fonctionne récursivement !
En effet, pour étudier par exemple les termes de la suite $u_{n+1} = 3u_n + 2$ de $n = 1$ à $n = 30$ avec $u_1 = 7$, on entre = 7
dans la cellule A1 et = 3*A29 + 2 dans la cellule A30 et on « fait glisser » de la cellule A30 jusqu’à la cellule A2. On a plutôt l’habitude de faire glisser vers le bas mais pourquoi pas vers le haut !
Passer d’un « faire glisser » à l’écriture de l’algorithme correspondant est une évolution naturelle ce que l’introduction d’un langage impératif n’est pas.
La notion de fonction est naturellement illustrée par l’utilisation d’un langage fonctionnel alors que les procédures des langages impératifs peuvent prêter à confusion.
Comme de nombreux collègues, j’assure des « colles MAPLE » en classes préparatoires scientifiques depuis plusieurs années. Les élèves de ces classes ont habituellement un niveau en mathématiques supérieur au niveau moyen rencontré en Seconde et pourtant la plupart des étudiants éprouve de réelles difficultés à maîtriser un langage de programmation impératif comme MAPLE et certains n’y arrivent pas après une année d’initiation !
Évidemment, nous n’aborderons pas les mêmes problèmes en Seconde mais pouvoir se concentrer sur les mathématiques et simplement traduire nos idées grâce au clavier de manière assez directe nous permettra de préserver nos élèves de nombreux pièges informatiques sans parler des notions trompeuses que l’affectation peut introduire dans leurs esprits.

Cependant, utiliser des algorithmes récursifs nécessite de maîtriser un tant soit peu... l’axiome de récurrence. Or cette étude a été réservée jusqu’à maintenant aux seuls élèves de Terminale S. L’étude des suites débute depuis de nombreuses années en Première et chaque professeur a fait l’expérience des difficultés des élèves à maîtriser cette notion.

Ainsi, même si (ou plutôt parce que) les algorithmes récursifs peuvent apparaître proches des notions mathématiques qu’ils permettent d’étudier, ils demandent de comprendre une notion mathématique délicate, la récurrence, même si l’étude des phénomènes évolutifs modélisés par une relation $u_{n+1} = f (u_n )$ entre au programme de Seconde !...

D’un autre côté, les algorithmes impératifs contournent la difficulté de la récurrence, facilitent l’étude de certains mécanismes comme le calcul matriciel, permettent parfois une illustration « physique » d’un phénomène mathématique mais au prix d’une gymnastique d’esprit qui pourrait s’avérer délicate pour des élèves parfois très peu à
l’aise avec le calcul algébrique de base.
Ils doivent cependant être étudiés car ils sont largement répandus dans le monde informatique. Il ne faut enfin pas oublier les difficultés que pourraient rencontrer des professeurs de mathématiques n’ayant pas réfléchi à ces problèmes d’algorithmique et qui ne pourront pas être formé(e)s avant de devoir enseigner une notion méconnue, sans manuels et sans le recul nécessaire.
Mais il ne faudrait pas pour autant abandonner l’idée d’initier les élèves à une « algorithmique raisonnée ». La notion de test par exemple (SI...ALORS...SINON) est tout à fait abordable par le plus grand nombre... et dans tout style de programmation. La notion de fonction peut être étudiée sans danger avec un langage fonctionnel et avec prudence avec un langage impératif. D’un point de vue plus informatique, faire découvrir aux élèves que le « dialogue » avec la machine ne se réduit pas à des « clics » mais que chacun peut « parler » presque directement à la machine en lui tapant des instructions est également un apprentissage enrichissant.
Mais les difficultés rencontrées par les étudiants débutants de l’enseignement supérieur doivent nous inciter à la prudence et à nous demander si un enseignement informatique optionnel en seconde et plus poussé dans les classes scientifiques supérieures ne serait pas plus souhaitable.
Quant au match récursif/impératif, il ne peut se terminer par l’élimination d’un des participants : il faut savoir que l’un ou l’autre sera plus adapté à la résolution d’un problème ce qui induit la nécessité de connaître différentes manières de procéder pour choisir la plus efficace. Cela accroît d’autant plus la difficulté d’une introduction improvisée de l’algorithmique au lycée...


notes

[1lui-même pouvant d’ailleurs appartenir à cette catégorie !...

[2Pour découvrir XCAS suivre ce lien

[3Pour une présentation de ce langage, suivre ce lien

[4Institut National de Recherche en Informatique et Automatique

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