Introduction
Les nouveaux programmes de mathématiques qui vont être mis en place à la rentrée 2016 font une part importante à l’algorithmique et à la programmation. La « science informatique », enjeu scientifique autant qu’économique du XXIe siècle, se devait d’avoir un enseignement scolaire. La nouvelle organisation des spécialités de terminale par la création de l’ISN (Informatique et sciences du numérique) a été un premier pas dans la réintroduction [1] de l’informatique comme discipline scolaire. Introduit maintenant dès le cycle 3, cet enseignement est présenté dans le domaine des systèmes naturels et des systèmes techniques comme contribuant à former le raisonnement des élèves. Cet enseignement dispensé à la fois dans le cadre des mathématiques et de la technologie propose d’apporter aux élèves « des clés de décryptage d’un monde numérique en évolution constante » (p. 94).
Du point de vue des mathématiques, les problèmes qui se posent et qui ne sont certainement pas simples à résoudre sont les problèmes d’articulation avec les autres notions à enseigner. Pas simple si on fait l’hypothèse d’une volonté, d’une part de ne pas créer une bulle qui se développerait en dehors de tout contexte, et d’autre part pour ne pas ramener cette démarche à un simple exercice mettant en jeu des tâches et des techniques, sans apporter des justifications théoriques de ces techniques. Autrement dit pour ne pas récréer, en référence à Chevallard, une salle nouvelle d’un musée, d’art moderne certes, mais qui peut rapidement devenir poussiéreux !
De fait les questions qui se posent se situent d’une part au niveau du rôle des connaissances mathématiques dans l’enseignement de l’informatique et en premier lieu de l’algorithmique. Et d’autre part au niveau des apprentissages des compétences visées par les programmes. L’exemple du concept de preuve qui est central en mathématiques dans le cycle 4 va devoir s’articuler en tant qu’objet d’enseignement avec la preuve d’un algorithme et les méthodes spécifiques qui y sont afférentes. Comment gérer ces relations, comment faire en sorte que les compétences développées se nourrissent plutôt qu’elles ne s’opposent ? La question est d’autant plus cruciale que l’enseignement de l’informatique va se trouver « à cheval » entre le cours de mathématiques et le cours de technologie. Si on peut y voir d’intéressants développements permettant de conduire des EPI fructueux pour les deux disciplines, cette dualité peut également conduire à des enseignements séparés au risque de voir se développer deux « informatiques scolaires », celle des mathématiques et celle de la technologie. Ces questions de l’articulation des enseignements de l’informatique en mathématiques et en technologie posent des questions pratiques d’organisation et de relation tout autant que des questions d’ordre épistémologique prenant en compte les épistémologies propres des mathématiques et de la (ou des) technologie.
Outre le fait que l’enseignement de l’algorithmique est une nouveauté pour le collège, les programmes encouragent à « écrire, mettre au point et exécuter un programme simple ». La question du passage de l’algorithme au programme se pose alors et nécessite le choix d’un langage de programmation et donc le choix d’un paradigme de programmation et d’un langage ayant sa propre syntaxe. On distingue habituellement deux grands paradigmes : la programmation impérative et la programmation déclarative. La programmation impérative consiste à donner des ordres à la machine qu’elle va exécuter en suivant l’ordre des instructions :
mettre 0 dans S
Pour j allant de 1 à n faire
mettre S+j dans S
finPour
Au contraire, la programmation déclarative stipule des règles, des faits et laisse la machine tirer la conclusion de cet ensemble de règles :
S(n)=0 si n=0 et n+S(n-1) sinon.
Parmi les langages, le paradigme dominant permet une classification. Ainsi, C, Python, Java,... sont classés dans les langages impératifs, Prolog, CAML, SQL dans les langages déclaratifs. Comme dans toute classification, d’une part les frontières ne sont pas si étanches et d’autre part, les classes sont grossières et demandent à être affinées : on peut redécouper en sous catégories les langages déclaratifs : langages fonctionnels (Lisp, Caml, Scheme), et langages logiques (Prolog, Sql,...) ; ce qui est intéressant en revanche est la traduction d’un même algorithme dans des langages différents. Regardons par exemple, l’algorithme d’Euclide traduit dans des langages différents :
Caml
let rec pgcd a b=match b with
|0 → a
|_ → pgcd b (a mod b) ;;
Prolog
pgcd(X,X,X).
pgcd(X,Y,D):- X<Y, Z is Y-X, pgcd(X,Z,D).
pgcd(X,Y,D):- Y<X, pgcd(Y,X)
Lisp
(DE PGCD (M N)
(LET ((X (PGCD1 M N)))
(IF X X (LIST M ’ET N ’SONT ’PREMIERS ’ENTRE ’EUX))))
(DE PGCD1 (M N)(COND
((> M N) (PGCD1 N M))
((= (REM N M) 0)
(IF (= M 1) () M))
(T (PGCD1 (REM N M) M)) ))
Algobox
VARIABLES
2 A EST_DU_TYPE NOMBRE
3 B EST_DU_TYPE NOMBRE
4 R EST_DU_TYPE NOMBRE
5 DEBUT_ALGORITHME
6 LIRE A
7 LIRE B
8 AFFICHER « PGCD de »
9 AFFICHER A
10 AFFICHER « et »
11 AFFICHER B
12 TANT_QUE (B !=0) FAIRE
13 DEBUT_TANT_QUE
14 R PREND_LA_VALEUR A%B
15 A PREND_LA_VALEUR B
16 B PREND_LA_VALEUR R
17 AFFICHER « = PGCD de »
18 AFFICHER A
19 AFFICHER « et »
20 AFFICHER B
21 FIN_TANT_QUE
22 AFFICHER « = »
23 AFFICHER A
24 FIN_ALGORITHME
Ces quelques exemples montrent bien s’il en était encore besoin, le délicat passage de l’algorithme à la programmation et renvoie aux problèmes de syntaxe inhérents à toute utilisation d’un langage, fut-il minimisé, comme c’est le cas pour Algobox ou Scratch, par le glisser-déposer d’expressions pré-construites.
La lecture des nouveaux programmes du cycle 4 montre une insistance sur la programmation événementielle en lien avec les développements actuels de l’informatique et de ses applications dans l’industrie : « Le fil conducteur de mon enseignement sera le traitement du temps et des événements dans les systèmes informatiques, domaine où notre pays a tenu un rôle particulièrement innovant dans la recherche et dans l’industrie . » Gérard Berry, leçon inaugurale au Collège de France. C’est certainement cette insistance qui a conduit à proposer l’utilisation du logiciel Scratch(MIT) et ainsi la possibilité d’utiliser un même logiciel pour le cours de technologie (Scratch peut être le langage d’interface pour le fonctionnement de robots) et le cours de mathématiques, même si ses possibilités (ou ses contraintes) ne sont certainement pas optimisées pour faire le lien entre les mathématiques et l’algorithmique. A travers les exemples proposés dans les programmes de mathématiques, il est possible de mettre en évidence quelques notions fondamentales dont on pourra dire qu’elles constituent les connaissances essentielles visées par ces programmes. Ainsi les jeux dans les labyrinthes, les jeux de Pong, les jeux de Nim et autres jeux à stratégie gagnante renvoient à une programmation événementielle, les calculs simples sur les calendriers, ou dans un répertoire sont davantage liés à une programmation impérative et à la gestion des données et dans une certaine mesure au typage des variables.
Un deuxième aspect qui semble devoir être mis en avant est le concept de parallélisme qui apparaît dans la progression des programmes : « progressivement, ils développent de nouvelles compétences, en programmant des actions en parallèle,... » . Ce concept est assez naturellement implémenté « en actes » dans un logiciel comme Scratch ; il suffit en effet de construire deux suites d’instructions qui démarrent avec le même signal. La difficulté est plus ici de relier cette construction assez naturelle au concept lui-même. Il me semble que des activités sans ordinateurs peuvent plus facilement faire comprendre ce concept. Une simple multiplication « per gelosia » peut illustrer de belle manière le parallélisme. Avec des élèves de CM2, j’ai fait calculer le produit de deux « grands » nombres du type 123456789 multiplié par 987654321 dans une « battle de multiplications ». Deux équipes s’affrontaient pour calculer ce produit. Une fois le calcul écrit dans deux tableaux (comme celui reproduit ci-dessous), dans chaque équipe, chaque « joueur » a la responsabilité d’une colonne, et la multiplication s’effectue « en parallèle ». Une fois toutes les multiplications réalisées, chacun est responsable de deux diagonales dont il s’agit d’additionner les nombres. La encore les additions se font en parallèle. Il reste une dernière tâche pour atteindre le résultat : le report des retenues qui lui doit se faire séquentiellement. (Voir l’exemple sur le petit film).
Ainsi de nombreuses questions se posent concernant les choix du langage et leur pertinence eu égard aux objectifs des programmes, mais aussi pour l’articulation avec les mathématiques et les relations qui pourront exister entre la création d’algorithmes, les stratégies d’informatique débranchée et l’écriture effective de « programmes simples »...
Dans la partie suivante, je voudrais témoigner d’activités d’introduction conduites avec des élèves de primaire et du secondaire pour une introduction à l’algorithmique et la programmation dans le cadre des activités de la maison des mathématiques et de l’informatique (MMI) de Lyon.
La maison des mathématiques et de l’informatique a commencé ses activités à la rentrée 2012. Elle propose des expositions, des ateliers et stands d’activités mathématiques ainsi que des conférences. Elle a également pour vocation de fédérer, d’organiser et d’amplifier les diverses actions de diffusion mathématique et informatique qui ont lieu à Lyon et dans sa région. Dans ce cadre, nous accueillons des classes de tous les niveaux pour des ateliers mathématiques et informatique ; en particulier, les ateliers « découverte de l’algorithmique et de la programmation » ont un grand succès. Je décris ci-dessous quelques unes des activités proposées et les réactions des élèves ou des professeurs, même si aucune méthodologie spécifique d’observation n’a été mise au point. Il s’agit donc plus d’un témoignage que d’une analyse du travail réalisé.
Des activités de la MMI
Un tour de magie
J’accueille souvent les enfants en leur proposant le tour de magie suivant qui m’a été soufflé par Nathalie Revol :
Liste 1
| 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 |
Liste 2
| 2 | 3 | 6 | 7 | 10 | 11 | 14 | 15 | 18 | 19 | 22 | 23 | 26 | 27 | 30 | 31 |
Liste 3
| 4 | 5 | 6 | 7 | 12 | 13 | 14 | 15 | 20 | 21 | 22 | 23 | 28 | 29 | 30 | 31 |
Liste 4
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
Liste 5
| 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
Je demande à un élève de choisir un nombre entre 1 et 31 et de le montrer à toute la classe mais en me le cachant soigneusement. Je demande alors si le nombre est présent dans la liste 1, dans la liste 2, dans la liste 3, dans la liste 4, dans la liste 5.
Immédiatement après qu’ils m’aient répondu, je peux donner le nombre choisi. La réaction est invariablement « c’est parce que tu connais les nombres » ou « moi aussi je sais ». Je propose alors à un élève de prendre ma place et de prendre son temps pour répondre. Bien sûr, les enfants n’arrivent pas à découvrir le nombre choisi et je leur demande alors de réfléchir : quel est le « truc » ? Comment sont faites ces listes ?
Assez rapidement, le secret de la première liste contenant tous les impairs est percé. Tout comme l’étrange présence de 31 dans toutes les listes. Mais les autres ? Les plus malins arrivent à découvrir que le nombre choisi est la somme des premiers nombres des listes dans lequel il apparaît. Je dois alors reprendre la main et expliquer le codage en base 2. Tout s’éclaire alors : la liste 1 contient les nombres qui dans l’écriture binaire se terminent par 1 ; la deuxième liste contient les nombres ayant un 1 à la deuxième position, etc. Ainsi, en répondant qu’un nombre est présent dans la liste i c’est dire que le ieme chiffre du nombre est un 1 et sinon c’est un 0. Il suffit alors de faire la somme des puissances de 2 pour « deviner » le nombre choisi. C’est une façon ludique de présenter la base 2, la base des ordinateurs.
Quelques algorithmes fondamentaux
Les algorithmes de tri sont souvent considérés comme des algorithmes fondamentaux ; je les mets en scène en utilisant des balances Roberval et des boîtes, toutes identiques mais de poids différents. L’activité consiste à ranger les boites dans l’ordre de la plus légère à la plus lourde en comparant le poids de deux boîtes à la fois. Les enfants sont souvent décontenancés par l’activité et cherchent à jauger « à la main » la plus lourde (ou la plus légère) ; malheureusement la mesure au jugé n’est guère efficace et nécessairement une stratégie doit être mis en place. Généralement, les enfants réussissent à construire un algorithme de tri dans l’action mais ne réussissent pas à le décrire et le travail de mise en commun consiste à formaliser un peu le tri qu’ils ont construit, puis de montrer d’autres tris. Pour ce faire, avec 8 élèves, je mets en place un tri fusion (regardez aussi le tri fusion mis en danse !) pour les ranger du plus petit au plus grand. La fusion est toujours un grand moment !
Dans le même ordre d’idée, les algorithmes de parcours de graphes sont utilisés dans un jeu : un des deux joueurs voit le graphe, le second ne le voit pas doit le dessiner en écoutant les consignes de son partenaire. Comment le décrire ? En parcourant le graphe ! L’intérêt de ce jeu c’est que non seulement il peut y avoir une auto-correction mais encore il montre l’équivalence de deux dessins différents représentant le même graphe.
D’autres ateliers s’appuient sur les réalisations du site « Unplugged computer science » qui propose des activités autour des grands résultats de la théorie des graphes : coloration d’un graphe, arbre couvrant minimum, parcours de graphes et d’arbres, etc. Les codes correcteurs d’erreur, les algorithmes de compression donnent aussi l’occasion d’activités ludiques tout comme les fameuses tours de Hanoï qui sont une excellente occasion de présenter le concept de récursivité.
Les Bee Bots sont des petits robots qui se « programment » à la façon d’un logo simplifié : avancer, tourner à droite, tourner à gauche, reculer, faire une pause. Après quelques essais sur une grille pour bien comprendre le fonctionnement, je demande à une équipe de quatre élèves de jouer avec quatre bee bots ; le but du jeu est de faire traverser le tapis de jeu à chaque bee bot sans bien sûr qu’elles ne se carambolent mais aussi en partant ensemble et en arrivant ensemble (Figure 1). Les quatre joueurs doivent se mettre d’accord pour réussir à programmer « en parallèle » les quatre robots.
J’insiste toujours sur la prévision, c’est à dire l’écriture de quatre programmes qui vont devoir s’exécuter en même temps. Les premiers essais sont souvent l’occasion d’un magnifique embouteillage au centre du tapis, mais progressivement, les stratégies se mettent en place, comme par exemple, cette équipe d’élèves qui a utilisé massivement les « pauses » pour faire se déplacer l’une après l’autre les bee bots. Cet épisode a été l’occasion pour moi de parler de complexité et de demander une amélioration des programmes...
Fig.1 : Une bee bot et le tapis de jeu
Ces différentes activités permettent d’aborder l’algorithmique et la programmation sans jamais toucher un ordinateur tout en évoquant des concepts fondamentaux de l’algorithme et de la programmation.
Complexité
Avec les plus grands (en général les élèves de lycée) j’aborde la question de la complexité d’une façon expérimentale en utilisant le temps de réalisation d’algorithmes. La complexité d’un algorithme vue d’une façon pratique et mettant en jeu la lecture graphique d’un temps en fonction de la taille des données peut permettre une première approche du concept informatique de complexité en le reliant aux connaissances mathématiques en cours de construction.
Sur cet exemple dans le logiciel Sage (en fait en utilisant le langage Python), j’ai programmé une fonction qui mesure le temps d’exécution d’un programme.
def duree(f,l):
t = cputime()
f(l)
tps=cputime(t)
return tps
D’une façon très élémentaire, si j’écris une première fonction qui est une simple boucle la représentation graphique du temps d’exécution en fonction de la taille des données montre bien ce caractère linéaire du temps d’exécution.
def boucle(n):
l=[]
for i in range(n):
pass
Fig. 2 : Les temps d’exécution en fonction de la taille des données d’une boucle simple
De la même façon, cette deuxième fonction constituée de deux boucles imbriquées va s’exécuter en temps quadratique et la représentation graphique laisse à voir cette complexité.
def boucle2(n):
for i in range(n):
for j in range(n):
pass
Fig. 3 : Les temps d’exécution en fonction de la taille des données de deux boucles imbriquées
Ces mesures du temps en fonction de la taille des données peuvent alors être utilisées sur les algorithmes de tri sur lesquels les élèves ont travaillé et montrent clairement les différences de complexité des algorithmes. Le travail mathématique de preuve de la complexité n’est pas abordé dans le temps de la visite à la MMI mais les professeurs peuvent s’en saisir pour prolonger ces activités en classe.
Conclusion
L’algorithmique et la programmation sont aujourd’hui incontournables dans l’enseignement des mathématiques en collège et au lycée. On peut s’en réjouir ou le déplorer, mais l’informatique entre de plus en plus à l’école comme discipline scolaire, ancrant l’école dans le monde contemporain. Les liens qui peuvent être faits avec l’enseignement des mathématiques sont encore à explorer ; ils offrent des opportunités nouvelles d’investigation et posent des questions d’ordre didactique et épistémologique. Ces questions concernant cet enseignement sont d’une part liées au rôle des connaissances mathématiques dans l’enseignement de l’informatique et en premier lieu de l’algorithmique. L’exemple du concept de preuve qui est central en mathématiques va devoir s’articuler en tant qu’objet d’enseignement avec la preuve d’un algorithme et les méthodes spécifiques qui sont afférentes. On peut bien sûr imaginer des situations dans lesquelles les concepts mathématiques en cours d’apprentissage pourront constituer des éléments d’appui pour créer des situations permettant d’aborder les concepts d’algorithmique avec les élèves. C’est ce que les exemples développés dans ce texte veulent proposer dans les ateliers de la maison des mathématiques et de l’informatique de Lyon, mais peuvent tout à fait « entrer » dans les classes.