Pédagogie de l'informatique

Maurice Nivat
 

   Concernant l'enseignement de l'informatique au lycée et la programmation, il s'agit surtout de la démystifier dès le début du cours...

   Je persiste à penser que le tri a une vertu pédagogique essentielle. D'abord il ne présente aucune difficulté de nature mathématique. Ensuite on peut l'effectuer à la main, sur un paquet de cartes. Je pense que cette partie manuelle, destinée à montrer que le programme que l'on est amené à écrire pour un ordinateur, quel que soit le langage employé, vaut tout autant pour un homme et n'a rien de « magique », est très importante.

Tri par sélection simple

   On cherche le plus petit élément de la suite à trier, on l'enlève et on le met à la fin de la suite triée qu'on constitue, puis on recommence jusqu'à épuisement de la suite à trier.

   Écrire le programme et le faire tourner sur des exemples pas trop petits, à la machine et à la main.

   On peut examiner la variante dans laquelle on ne dispose pas d'espace autre que celui qu'occupe la suite de départ.

Tri par sélection quadratique

   On fragmente la suite de départ en un certain nombre de morceaux, de l'ordre de la racine carrée de la longueur de la suite : on cherche les plus petits éléments de chacun des morceaux que l'on met dans une suite auxiliaire C. Le plus petit des éléments de C est le plus petit de la suite de départ : on le prend et on le met à la première place de la suite triée que l'on constitue. En même temps on l'enlève du morceau dont il était issu, on cherche le plus petit élément de ce morceau ainsi amputé et on remplace dans C l'élément enlevé par ce plus petit élément.

   Et on recommence jusqu'à épuisement de la suite de départ.

   Mise en oeuvre avec écriture d'un programme que l'on fait tourner à la machine et à la main.

   À la main, on peut confier à des élèves chacun des morceaux, à un autre élève la gestion de la suite auxiliaire C et à un denier la gestion de la suite finale.

   S'apercevoir que cette méthode de sélection quadratique va plus vite et éventuellement calculer grossièrement le nombre de comparaisons effectuées de l'ordre de n×√(n) contre n².

   Quand les élèves ont compris cela, ils ont compris ce qu'est la programmation de base.

Tri optimal par interclassement

   Définir l'interclassement de deux suites ordonnées et constater que cela prend (m + n – 1) comparaisons d'interclasser deux suites de longueur m et n.

   Constituer autant de suites ordonnées de longueur deux que possible en triant les suites formées du premier et du deuxième élément de la suite à trier, du troisième et du quatrième, etc. Il reste ou non un élément tout seul.

   Constituer par interclassement des suites précédentes prises deux à deux autant de suites ordonnées de longueur 4 que possible, plus une suite résiduelle de longueur 1, 2 ou 3.

   Et continuer en constituant des suites de longueur 8, 16, 32, etc. jusqu'à épuisement.

   Mettre en oeuvre à la machine et à la main, s'apercevoir que l'on va beaucoup plus vite. Expliquer pourquoi, cela dépend évidemment de la familiarité qu'ont les élèves avec la fonction exponentielle. S'ils n'en ont que très peu, ce que j'imagine, ceci est une bonne façon de leur faire toucher du doigt cette fonction et sa croissance.

   Donner une version récursive du même programme ou plutôt d'autres programmes en n×log(n), on peut en imaginer autant qu'on veut selon la façon dont on fragmente en deux la suite initiale à trier pour ré-appliquer le programme de tri sur chaque moitié avant l'interclassement final.

*
*     *

   Avec ces trois exemples on est arrivé au coeur de la programmation. Mais je rajouterais bien encore un exercice ou deux.

Petit jeu

   Ceci est un tableau carré 5×5 occupé par 24 pions de deux espèces, les X et les Y. La case centrale est vide.

   Les pions se meuvent comme les cavaliers sur l'échiquier.

   À chaque coup, on peut déplacer un pion, pour lui faire occuper la case vide, la case qu'il occupait devenant vide à son tour.

   Le but est de transporter tous les X à la place des Y et tous les Y à la place des X par une suite de coups.

   Y jouer à la main, rien n'est plus facile que de dessiner sur un carton un carré 5×5 et de se munir de 24 pions de deux espèces.

   Si vous y arrivez en moins de 50 coups vous êtes bon, si c'est en moins de 45 coups vous êtes très bon, en moins de 40 vous êtes franchement excellent !

   Écrire un programme qui y fait jouer la machine en laissant ouvert le choix du pion que l'on déplace à chaque coup.

   Peut-on donner une règle de choix du pion que l'on déplace qui soit bonne ? On appellera ça une stratégie.

   Réfléchir à des stratégies, les mettre en oeuvre à la machine et à la main.

   Et maintenant, que faire pour trouver le nombre minimum de coups (36 si mes souvenirs sont bons) : faire voir aux élèves que c'est la longueur du plus court chemin menant de la situation initiale à la situation finale dans un graphe que l'on définit aisément mais qui est trop gros pour qu'on puisse le dessiner à la main, il a 25!/12! sommets.

   Chercher cet optimum à la machine avec l'algorithme de plus court chemin le plus naïf.

Problème de stratégie. Échecs chinois linéaires

   Deux joueurs s'affrontent.

   Au début la situation est la suivante ou une analogue

   Les pions blancs à gauche sont en nombre égal à celui des pions noirs à droite et entre eux il y a un certain nombre de cases vides.

   À chaque coup, les blancs peuvent déplacer n'importe lequel de leurs pions dans la première case vide à sa droite et les noirs peuvent déplacer n'importe lequel de leurs pions dans la première case vide à leur gauche.

   Le gagnant est le joueur qui a transporté tous ses pions à la place qu'occupaient au début les pions de l'autre.

   Les blancs jouent les premiers.

   Jouer à ce jeu, y faire jouer les élèves.

   Réfléchir à des stratégies, par exemple à chaque coup chaque joueur déplace le pion qui peut effecteur le déplacement le plus long, ou bien à chaque coup chaque joueur déplace le pion de tête (le plus à droite pour les blancs, le plus à gauche pour les noirs) ou encore chaque joueur déplace le pion de queue. Voilà au moins trois stratégies que l'on appellera respectivement stratégie du mouvement, de l'avant et de l'arrière.

   Faire jouer stratégie contre stratégie, y faire jouer des ordinateurs après avoir écrit les programmes voulus.

   Que se passe-t-il si les deux ordinateurs (joueurs) suivent la même stratégie ? Les blancs gagnent-ils toujours ?

   Existe-t-il une stratégie gagnante qui assure aux blancs la victoire quoi que fassent les noirs ?

   Éventuellement passer à deux dimensions en jouant par exemple sur un carré avec comme position de départ :

*
*     *

   J'imagine un enseignement extrêmement concret dépourvu de tout ce qui peut ressembler à un théorème, avec toujours le souci de faire à la main d'abord ce qu'on veut faire faire à la machine. Et celui de toujours décrire en français d'abord les algorithmes que l'on veut traduire en programmes. Le langage de programmation employé importe finalement très peu. On ne pense pas dans un langage de programmation. Il faut apprendre d'abord, et avant tout, aux élèves à réfléchir avant de programmer. Cette réflexion est très différente de celle à laquelle sont amenés les élèves dans les autres cours, que ce soit de mathématiques ou de physique : dans un premier temps, au niveau d'une classe de terminale S, elle ne doit guère être basée que sur le bon sens et la nécessité d'exprimer, de décrire, en français et dans un langage de programmation qui n'est qu'une commodité d'écriture, des suites d'opérations et des algorithmes ou stratégies de calcul et de jeu.

Maurice Nivat

___________________
Association EPI
Mai 2010