Les adaptations du programme de seconde qui entrent en vigueur à la rentrée 2017 apportent des changements majeurs dans la façon d’aborder l’écriture d’algorithmes, qui se double de plus de l’écriture de programmes informatiques dans un langage textuel, concis, interprété et répandu (dixit le texte), ce qui est une assez bonne périphrase pour décrire Python3.

Le changement principal est l’abandon du triptyque saisie/traitement/affichage pour privilégier l’écriture de fonctions informatiques. Un document sur Eduscol contient de nombreuses ressources de qualité pour les professeurs mais il ne met pas vraiment en exergue ce changement de paradigme.

Dans ce billet, qui fait suite à celui de l’an dernier, j’explore au travers d’un exemple en quoi consiste ce changement et son intérêt.

Nombres premiers, nombres pseudo-premiers

L’exemple que j’ai choisi consiste à écrire des algorithmes pour déterminer si un naturel non nul est premier, s’il est pseudo-premier, et à déterminer le plus petit entier pseudo-premier sans être premier. Cet exemple vise uniquement à illustrer le changement dans la façon d’écrire les algorithmes en général ; j’ignore totalement si on peut traiter un exemple de ce niveau en seconde, mais la façon d’écrire les algorithmes se retrouvera dans tout autre exemple. De la même façon, je ne cherche pas ici à discuter de l’efficacité (complexité) des algorithmes ni à les optimiser d’une quelconque façon.

Je n’ai bien sûr pas besoin de rappeler ce qu’est un nombre premier.

Dans ce billet, on dira qu’un naturel non nul \(n\) est pseudo-premier si pour tout entier naturel \(a < n\), \(a^n - a\) est un multiple de \(n\). Le petit théorème de Fermat assure que si un entier est premier, alors il est pseudo-premier. Cependant, la réciproque n'est pas vraie : il existe des nombres qui sont pseudo-premiers sans être premiers, il en existe même une infinité.

Algorithmique à l’ancienne

Pour ne pas alourdir l’exposé, je vais écrire les algorithmes directement et seulement en Python, même si la façon d’écrire les algorithmes dans l’ancien programme de mathématiques semble avoir été contrainte par les possibilités des langages des calculatrices.

Voici comment on pourrait présenter un algorithme de calcul de primalité. Il y a peut-être plus pédagogique, mais la seule chose qui m’intéresse ici est la façon dont l’algorithme se comporte et va pouvoir (ou pas) se combiner à d’autres.

n = int(input("Entrez un naturel non nul "))
if n == 1 :
  print("L'entier", n, "n'est pas premier")
else :
  k = 2
  while k < n and n % k != 0 :
     k = k + 1
  # à ce stade, k contient le plus petit diviseur non trivial de n
  if k == n :
    print("L'entier", n, "est premier")
  else :
    print("L'entier", n, "n'est pas premier")

Sous réserve de faute de frappe de ma part, cet algorithme fonctionne : on peut s’en servir pour connaitre la primalité d’un entier.

On peut de même calculer la pseudo-primalité :

n = int(input("Entrez un naturel non nul "))
if n == 1 :
  print("L'entier", n, "n'est pas premier")
else :
  a = 0
  while a < n and (a**n - a) % n == 0 : # a**n-a multiple de n
    a = a + 1
  if a == n :
    print("L'entier", n, "est pseudo-premier")
  else :
    print("L'entier", n, "n'est pas pseudo-premier")

Ceci fonctionne aussi.

Mais comment peut-on maintenant écrire simplement un programme qui donne le plus petit naturel pseudo-premier sans être premier ? Il y a une idée simple : on parcourt les entiers dans l’ordre croissant ; pour chacun, on regarde s’il est pseudo-premier, et si tel est le cas on vérifie qu’il est premier : la première fois que cette vérification échoue correspond au nombre cherché.

On veut donc appeler de façon répétée les algorithmes écrits précédemment, cas très fréquent en informatique. Mais on ne peut pas : chaque fois qu’on va exécuter l’algorithme de primalité dans la boucle, celui-ci va nous demander de saisir à la main et au clavier un entier à traiter. C’est complètement ingérable !

On est obligé de recopier les parties pertinentes des deux premiers algorithmes dans un gigantesque algorithme pour répondre à la question posée. Outre que c’est ridicule, l’algorithme résultant de cela sera lourd et on ne comprendra pas facilement sa structure. Enfin, cet algorithme lui-même ne pourra pas être utilisé dans un autre : on ne s’en sort pas !

La nouvelle et bonne méthode

Le problème auquel nous faisons face ci-dessus tient au fait que nous avons programmé un algorithme qui s’occupe à la fois du traitement algorithmique (le calcul de primalité proprement dit) mais aussi des entrées et sorties.

Le langage Python, comme tous les langages modernes, permet d’exprimer un traitement à faire sans imposer la façon dont sont obtenus les paramètres ni la façon dont est utilisée le résultat : c’est la notion de fonction.

Il n’y a pas grand chose à changer. Pour le calcul de primalité :

def estPremier(n) :
  if n == 1 :
    return False
  else :
    k = 2
    while k < n and n % k != 0 :
       k = k + 1
    # à ce stade, k contient le plus petit diviseur non trivial de n
    return k == n

Si on exécute ce programme, il ne se passe rien de visible. Mais il devient possible, dans la console Python, d’évaluer estPremier(7) et d’obtenir le résultat True.

De même pour la pseudo-primalité :

def estPseudoPremier(n) :
  if n == 1 :
    return False
  else :
    a = 0
    while a < n and (a**n - a) % n == 0 :
       a = a + 1
    return a == n

Et maintenant, on peut utiliser ces fonctions dans une autre !

def plusPetitPseudoPremierNonPremier(depart) :
  """Paramètre : un naturel, depart
  Résultat : un naturel, le plus petit entier supérieur à depart qui est
             pseudo-premier mais non premier"""
  n = depart
  while not estPseudoPremier(n) or estPremier(n) :  # on révise l'implication au passage !
    n = n + 1
  return n

Après avoir exécuté cette définition, on peut évaluer plusPetitPseudoPremierNonPremier(2) et obtenir 561.

Notez au passage que le texte que j’ai écrit entre triple guillemets est reproduit par la console Python si on exécute help(plusPetitPseudoPremierNonPremier) : c’est un très bon moyen de spécifier à un futur utilisateur de la fonction qu’on a écrite comment celui-ci doit s’en servir. Idéalement, il faut le faire pour chaque fonction qu’on écrit.

Conclusion

Le changement de paradigme opéré dans le programme de seconde nécessite de revoir entièrement la façon de présenter l’algorithmique et les algorithmes. Cependant les changements concrets à effectuer sont les mêmes à chaque fois et peuvent sans doute être apportés aux fiches d’activité de façon assez systématique.

Il ne s’agit pas nécessairement de traiter des exemples aussi avancés que celui que j’ai pris ; les activités actuellement utilisées vont probablement, pour la plupart, pouvoir être conservées en changeant simplement la façon d’écrire l’algorithme. Ainsi, même si la capacité à réutiliser les fonctions n’est pas immédiatement exploitée, le terrain sera préparé pour les années suivantes. À l’heure actuelle, les étudiants qui abordent l’informatique à un niveau plus complexe doivent commencer par désapprendre le triptyque saisie/traitement/affichage.

Bien sûr, ce changement suppose des modifications de fond dans la présentation initiale des choses, notamment l’introduction du concept de fonction. Cela n’est pas anodin dans la mesure où ce concept ne coïncide pas exactement avec celui de même nom en mathématiques, au risque d’une certaine confusion chez l’élève.

Il serait temps de dédier des heures spécifiques à l’enseignement de l’informatique et de recruter des professeurs spécialistes pour ce faire ; cela clarifierait les choses pour les élèves, dégagerait les collègues de math de la contrainte d’enseigner du mieux qu’ils peuvent des notions auxquelles ils n’ont pas eux-mêmes été formés et éviterait que cela empiète sur le temps consacré à l’enseignement des mathématiques proprement dites et notamment du raisonnement sans lequel il n’y a aucune informatique sérieuse possible (ni grand chose d’autre, du reste).