Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

51 ALGORITHMIQUE ET APPRENTISSAGE DE LA PREUVE Simon MODESTE, Sylvain GRAVIER E

51 ALGORITHMIQUE ET APPRENTISSAGE DE LA PREUVE Simon MODESTE, Sylvain GRAVIER ERTé Maths à Modeler, Irem de Grenoble Cécile OUVRIER-BUFFET ERTé Maths à Modeler Irem de Paris 7 REPERES - IREM. N° 79 - avril 2010 questions. Si bien que la recherche de pro- cédures effectives est, aujourd’hui encore plus, une problématique centrale des mathé- matiques. Le rôle de l’algorithme est si impor- tant qu’il est au centre d’une discipline propre, l’algorithmique, à l’intersection entre mathé- matique et informatique et dont l’essor actuel est considérable. Face à cette évolution de la science mathé- matique et à la présence grandissante de l’informatique et de ses applications autour de nous, l’enseignement des mathématiques Introduction L’algorithme est un objet méconnu. Sou- vent vu comme un objet de l’informatique, on l’associe à la programmation. Cependant, l’algorithme est avant tout un objet des mathématiques. « Avant tout », car la notion d’algorithme précède de beaucoup l’infor- matique. Le terme trouve d’ailleurs son ori- gine dans le nom al-Khwarizmi, nom de l’auteur du plus ancien traité d’algèbre connu, datant du IXème siècle. Bien sûr, la forma- lisation de ce concept doit beaucoup aux avancées de l’informatique. Cette dernière a aussi enrichi les mathématiques de nouvelles Résumé : Dans cet article, nous présentons tout d’abord une étude épistémologique sur la place et le rôle de l’algorithme dans la science mathématique. Nous étudions les différents aspects de l’algorithme suivant une dichotomie outil-objet, puis nous développons le lien privilégié qu’il entretient avec la preuve. En s’appuyant sur cette étude, nous proposons une analyse des pro- grammes du lycée ainsi que des manuels. Nous proposons, dans un troisième temps, une situation de recherche en classe mettant en jeu l’algorithme. Les résultats d’expérimentations de cette situation montrent comment la construction d’algorithmes, leur preuve et l’analyse de leur complexité peuvent être questionnées en classe. REPERES - IREM. N° 79 - avril 2010 52 ALGORITHMIQUE ET APPRENTISSAGE DE LA PREUVE doit être requestionné. En 2000, la commis- sion Kahane proposait l’introduction d’une « part d’informatique dans l’enseignement des sciences mathématiques et dans la formation des maîtres » (Kahane, 2000, p. 1). Aujourd’hui, c’est dans les programmes de seconde que l’algorithmique trouve une place. Cette pré- sence dans l’enseignement mathématique pourrait entraîner des malentendus entre les communautés mathématique et informatique, notamment concernant la légitimité des ensei- gnants de mathématiques à enseigner l’algo- rithmique. Et bien que ces derniers puissent pen- ser que l’informatique est loin de leurs pré- occupations, l’algorithmique relève bien de problématiques mathématiques. Se pose aussi une question de formation. A priori, peu d’enseignants ont étudié l’algorithmique en tant que telle dans leur cursus et l’algorith- me risque de devenir un simple outil infor- matique pour les mathématiques. On peut alors s’interroger : quel accueil les ensei- gnants de mathématiques vont-ils faire à l’algorithmique ? Il semble donc essentiel d’aborder la ques- tion de l’introduction de l’algorithme dans l’enseignement des mathématiques d’un point de vue didactique. Ces questions ont été peu abordées et la didactique s’est surtout inté- ressée à la programmation et à l’outil algorithme plus qu’à l’objet mathématique. On peut citer des travaux récents tels que Nguyen (2005) qui s’intéresse à l’introduction d’éléments de programmation à l’aide de la calculatrice ou Schuster (2004) qui étudie l’introduction de problèmes d’optimisation combinatoire au secondaire. On peut aussi citer les thèses de Cartier (2008) et Ravel (2003), où l’algorith- me est étudié dans des domaines mathéma- tiques particuliers : la théorie des graphes en spécialité mathématique de terminale ES pour Cartier et l’arithmétique de la spéciali- té mathématique en terminale S pour Ravel. Dans cet article, c’est l’algorithme en tant qu’objet mathématique que nous allons étu- dier, sans nous placer dans un champ mathé- matique en particulier. Pour mieux appréhender les questions que soulève l’algorithme, il faut se pencher sur son rôle dans les mathématiques et sur les dif- férents aspects qu’il revêt. En s’appuyant sur la dialectique outil-objet développée par Régi- ne Douady (1986), on peut les classer sui- vant qu’ils relèvent de l’aspect « outil » du concept ou de l’aspect « objet » : l’algorithme n’est pas uniquement un outil pour la résolution de problèmes mais c’est aussi un objet mathé- matique à part entière, pour lequel il existe un cadre d’étude précis. Précisons : Ainsi, nous disons qu’un concept est outil lorsque nous focalisons notre intérêt sur l’usage qui en est fait pour résoudre un pro- blème. Un même outil peut être adapté à plu- sieurs problème, plusieurs outil peuvent être adaptés à un même problème. Par objet, nous entendons l’objet culturel ayant sa place dans un édifice plus large qui est le savoir savant à un moment à un moment donné, reconnu socialement. (Douady, 1986, p. 9) Dans une première partie, nous allons étu- dier plus en profondeur le concept d’algo- rithme afin de mieux comprendre en quoi il peut être objet d’enseignement en mathéma- tiques. Nous nous intéresserons ensuite à la place du concept d’algorithme dans les pro- grammes et manuels. Ce sera l’objet d’une deuxième partie. La troisième partie se cen- trera sur l’étude d’une situation pour mani- puler l’objet algorithme. REPERES - IREM. N° 79 - avril 2010 53 ALGORITHMIQUE ET APPRENTISSAGE DE LA PREUVE 1. — L’algorithme, un objet qui questionne l’activité mathématique et l’enseignement 1.1 Définition de l’algorithme, différents aspects pour un même concept Pour présenter ces différents aspects, nous nous appuyons sur des extraits de la défi- nition du terme « algorithme » issue du dic- tionnaire des mathématiques (Bouvier et al., 2005). Cet ouvrage présente l’algorithme d’un point de vue généraliste et évoque les approches mathématique et informatique du concept. Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver avec certitude (c’est-à-dire sans indétermina- tion ou ambiguïté), en un nombre fini d’étapes, à un certain résultat et cela indé- pendamment des données. Un algorithme ne résout donc pas un problème unique mais toute une classe de problèmes ne dif- férant que par les données mais gouvernés par les mêmes prescriptions. (Bouvier et al., 2005, p. 27) Cette définition, qui est assez couran- te dans les ouvrages généralistes, met en avant trois aspects de l’algorithme. Le pre- mier aspect est d’être soumis à un enjeu de vérité, de preuve : un algorithme doit fonctionner avec certitude quel que soit le problème donné. Un autre aspect est que l’algorithme est un outil de résolution de problèmes. Plus précisément, un algo- rithme permet de résoudre une classe de pro- blèmes. Le troisième aspect qui apparaît ici est qu’un algorithme est effectif, il s’applique à des données finies et résout un problème en un nombre fini d’étapes : il peut être mis en œuvre par un opérateur. La notion d’algorithme est indissociable de cet aspect, comme le souligne Chabert : Aujourd’hui sous l’influence de l’informatique, la finitude devient une notion essentielle contenue dans le terme algorithme, le dis- tinguant de mots plus vagues comme pro- cédé, méthode ou technique. […] Finitude du nombre des opérations et du nombre des données, mais finitude aussi de la résolution, c’est-à-dire que chaque étape doit pouvoir être réalisée selon un processus fini -ce qui n’est pas le cas, par exemple, du quotient de deux nombres réels incommensurables. On parle aussi de procédé effectif, c’est-à-dire per- mettant d’obtenir effectivement le résultat (en un temps fini). (Chabert, 1994, p. 6) Une autre question se pose alors : Tout ce qui est effectif, une formule par exemple, est-il un algorithme ? Pour Bouvier et al. (2005) la réponse est oui. Plus précisément, une formule peut être vue comme un algorithme dont les prescrip- tions ne varient pas en fonction des données. Il semble donc que la notion d’algorithme englobe celle de procédure effective, mais nous verrons plus loin que ces « algorithmes- formules » ont un intérêt limité du point de vue de l’algorithmique (paragraphe 2.2). Le développement de l’informatique a bien sûr une influence importante sur l’algo- rithmique et soulève des questions d’implé- mentation de l’algorithme. Ces questions de programmation et de langages informatiques ne seront pas étudiées ici. Comme le souligne Bouvier et al. (2005), des questions se posent aussi quant à l’efficacité de la mise en œuvre de ces algorithmes : la question des temps de calcul, c’est-à-dire le nombre d’étapes élé- REPERES - IREM. N° 79 - avril 2010 54 ALGORITHMIQUE ET APPRENTISSAGE DE LA PREUVE mentaires qu’effectue un algorithme en fonc- tion de la taille des données, mais aussi la ques- tion de la taille mémoire, c’est-à-dire la place nécessaire pour stocker les différentes struc- tures de données, correspondant à la com- plexité en temps et en espace de l’algorithme. Un nouvel aspect est ici évoqué : la com- plexité. Les questions d’existence d’algorithme pour certains problèmes et de leur complexi- té ont conduit à un cadre théorique d’étude de l’algorithme en tant qu’objet : l’hypothèse fondamentale de la théorie des algorithmes est que tout algorithme peut être réalisé par une machine de Turing particulière et aussi, par conséquent par une machine de Turing uploads/Philosophie/ iwr10007-pdf.pdf