À propos de didactique de l'informatique (suite)

Françoise Gaydier
 

Dans ce deuxième extrait de ma thèse, je présente une méthode pour construire une itération.

J'ai ajouté en annexe une illustration concrète de cette méthode.

3. Enseignement de méthodes de programmation dans l'initiation à l'informatique

   Jacques Arsac était professeur d'informatique à l'université Paris VII, après avoir été chercheur en physique. Il a su, comme on vient de le voir, très vite réaliser que l'enseignement de l'informatique, dans sa partie programmation, posait des problèmes didactiques spécifiques. On pourrait dire qu'il a été l'un des acteurs en France qui a permis que la programmation passe d'une pratique essentiellement empirique, à une activité scientifique. Son souci premier était que les élèves de lycée, s'ils devaient être initiés à la programmation, le soient d'emblée à une « bonne » programmation : « mon programme est juste parce que je l'ai construit par des méthodes qui m'assurent qu'il est juste ».

   L'une de ces méthodes concerne la construction d'une itération à partir d'une « situation », c'est à dire d'une hypothèse supposée vraie en un point donné de la boucle, à chaque passage dans la boucle. Cette hypothèse s'énonce dans les termes : « supposons que j'aie déjà fait une partie du travail », hypothèse qu'on décline au cas par cas, en l'adaptant au problème concret à résoudre. Après avoir regardé si le travail est terminé (« est-ce fini ? », question qui amène à définir un booléen qui sera le critère d'arrêt de la boucle), il s'agit alors de déterminer les actions à effectuer (i.e. : les instructions à introduire dans le programme), pour « avancer le travail ». Il reste enfin à déterminer les valeurs initiales des variables pour que l'hypothèse soit satisfaite au premier passage dans la boucle (étape d'initialisations des variables).

   Évidemment cette méthode doit être rapprochée du raisonnement par récurrence, qui est généralement enseigné dans les seules classes scientifiques, au niveau de la terminale.

   La situation est ce qu'on appelle un invariant de boucle, notion qui peut être un élément de preuve du programme.

   Rogalski (1989) a analysé cette méthode dans un cadre de recherche didactique en informatique.

« L'enseignement de l'informatique à des élèves (ou des étudiants), qui ne sont pas a priori de futurs professionnels de l'informatique, pose des problèmes didactiques aussi épineux que ceux rencontrés par les enseignants des différentes disciplines "traditionnelles". L'informatique y apparaît à la fois comme un objet, relevant d'un domaine scientifique avec ses concepts propres, et comme un outil pour contribuer à résoudre les problèmes d'autres domaines.

Parmi ses spécificités - du point de vue du contenu et du point de vue des élèves [1] – celle d'être une discipline de service, liée à de multiples pratiques professionnelles, a (indirectement ?) conduit au problème de l'enseignement de méthodes de programmation. La réflexion sur l'efficacité du travail des programmeurs professionnels a en effet convergé, vers la fin des années soixante, avec des approches de nature formelle et les travaux sur la programmation structurée (Dahl, Dijktra, Moare, 1972). » 

(...)

   Rogalski poursuit, à propos de l'enseignement de méthodes de programmation :
« Cela a conduit à concevoir la structure d'un programme de façon hiérarchique et modulaire, à élaborer des méthodes de programmation dans le domaine professionnel et à engager une réflexion sur les conséquences à en tirer dans le domaine de l'enseignement de la programmation, indépendamment de la perspective professionnelle.

L'hypothèse didactique était "qu'une programmation méthodique dès les premiers apprentissages évite de prendre des habitudes de programmation empirique et désordonnée, tout en facilitant la résolution des problèmes de programmation" (Rogalski, Samurçay, Hoc). 

Plusieurs années d'expérience d'enseignement de l'informatique dans l'option des lycées conduisent à penser que les difficultés d'enseignement de méthodes ont été sous-estimées. Avant de pousser à des révisions déchirantes (C. Pair, 1988), il n'est pas inutile d'analyser plus précisément le ou les objets d'enseignement relatifs aux méthodes de programmation pour essayer d'identifier les propriétés de situations d'enseignement propres à faire acquérir par les élèves cette approche méthodique reconnue comme nécessaire. »

   Rogalski souligne d'autres difficultés spécifiques à la discipline informatique :
« Un premier obstacle apparaît dans l'acquisition de l'itération, et de méthodes appropriées à l'écriture de programmes itératifs ou récursifs. On peut exprimer cet obstacle sous deux formes différentes. D'une part la maîtrise de la dialectique entre exécution d'actions (ou "calculs") avec son caractère dynamique, et succession de situations (ou "relations") avec un caractère statique de la situation semble au cœur de l'acquisition des constructions itératives ou récursives.

D'autre part, la variable informatique doit être conçue comme une fonction de l'exécution ; une telle dualité variable/fonction n'est pas spécifique à l'informatique mais elle n'est jamais apparue dans le "passé cognitif" des élèves (qui maîtrisent en général fort mal à l'issue de l'enseignement secondaire les relations variable-fonction). La notion d'invariant qui est au cœur de la présentation de l'itération par J. Arsac peut difficilement recevoir une signification sans la maîtrise de cette double perspective. »

   Nous avons pensé utile ce bref aperçu sur quelques problèmes didactiques soulevés lors de l'enseignement de l'informatique en lycée comme une discipline en tant que telle, enseignement dispensé dans les années 1980-1990.

   Il n'apparaît pas que l'utilisation quotidienne dans diverses institutions de l'outil informatique par les élèves sous la forme de logiciels fermés, prêts à l'emploi, ait pu profondément modifier les problèmes didactiques posés par la prescription à des élèves des années 2010 de tâches relevant de l'algorithmique-programmation, que ce soit pour faire des simulations informatiques d'expériences aléatoires, que ce soit dans le cadre d'un enseignement de l'algorithmique-programmation.

4. Les connaissances stables en algorithmique programmation

   L'évolution rapide de la science informatique et du matériel ont pu amener dans les années 1980 à douter de la stabilité des connaissances dans cette discipline.

   En 2010, la réalité de connaissances spécifiques à la science informatique n'est plus discutée.

   Nous renvoyons à la thèse de Georges-Louis Baron (1987) et aux manuels universitaires variés édités en 2011 pour accompagner un enseignement de l'algorithmique-programmation : trente ans d'écart n'ont pas fondamentalement changé les bases de l'algorithmique-programmation, même si certaines problématiques ont pu évoluer, en particulier les problèmes de complexité en temps et en espace, du fait du changement d'échelle des problèmes que l'informatique peut traiter, grâce essentiellement aux augmentations considérables de l'espace mémoire et de la rapidité de calcul.

   Par contre les lignes de partages restent discutées entre les champs des mathématiques et de l'informatique.

   Dans sa thèse, Nguyen Chi Thanh (2005) semble attribuer l'algorithmique aux mathématiques pour ce qui concerne les algorithmes fondamentaux, les structures de données (tableaux, arbres, ensembles, listes, fichiers), l'analyse de complexité et les techniques de conception d'algorithmes :
« Ainsi l'algorithmique cherche à étudier l'algorithme indépendamment de sa mise en œuvre dans une machine ».

   La programmation est alors selon Nguyen Chi Thanh « l'ensemble des activités qui permettent l'écriture des programmes informatiques pour leur exécution dans une machine ».

   Il s'agit de transformer l'algorithme en un ensemble d'instructions dans un langage de programmation donné, instructions exécutables par la machine. Ces instructions sont structurées, dans les langages impératifs, par des instructions de contrôles : séquentialité, instructions conditionnelles, instructions itératives.

   Sans s'enfermer dans la question de la légitimité de la place de l'algorithmique dans le champ des mathématiques (« programmes 2010 » de seconde et de première), on peut constater qu'il demeure beaucoup d'ambiguïtés : l'algorithmique étudie-t-elle l'algorithme (par exemple complexité en temps de calcul, complexité en espace mémoire) comme le disent Arsac (1988) précédemment cité, et Nguyen Chi Thanh, ou donne-t-elle des méthodes pour écrire des algorithmes, ou encore s'agit-il de quelque chose qui est très proche de la programmation, comme peut le laisser entendre l'utilisation du mot « algorithmique » dans certains contextes ?

   Un document à destination des enseignants édité par le ministère de l'Éducation nationale s'intitule : Algorithmique (document référencé [1] dans la bibliographie) ; on trouve dans sa tables des matières : « Quelques généralités sur l'algorithmique ».
(...) dans un sous-paragraphe intitulé « Algorithmes et démarche algorithmique » :
« La sensibilisation de l'élève à la question de la "démarche algorithmique" pourra se faire en évitant toute technicité ou exposé systématique. On pourra sur ce thème consulter des publications réalisées dans le cadre des IREM.

Les compétences suivantes pourront être identifiées et travaillées :
- comprendre et analyser un algorithme préexistant ;
- modifier un algorithme pour obtenir un résultat particulier ;
- analyser la situation : identifier les données d'entrée, de sortie, le traitement... ;
- mettre au point une solution algorithmique : comment écrire un algorithme en "langage courant" en respectant un code, identifier les boucles, les tests, des opérations d'écriture, d'affichage... ;
- valider la solution algorithmique par des traces d'exécution et des jeux d'essais simples ;
- adapter l'algorithme aux contraintes du langage de programmation : identifier si nécessaire la nature des variables... ;
- valider un programme simple. »

(...)

   En fait, il semble que les « compétences » évoquées dans ce texte touchent de très près à la programmation.

   La mise au point de l'« interface » entre un algorithme et le code (programme) de cet algorithme dans un langage de programmation donné est une étape qu'on ne peut occulter : elle peut être extrêmement réduite pour les simulations d'expériences aléatoires que nous présentons ici, et beaucoup plus complexe pour l'écriture d'un programme pour résoudre une équation f(x) = 0 par la méthode de dichotomie à une précision donnée.

   Lorsqu'on a pu encadrer la solution de l'équation à résoudre entre a et b, on calcule le signe de l'image de (a + b)/2 par f, ce qui permet d'obtenir un nouvel encadrement de la solution, intervalle dont l'amplitude est la moitié de celle de l'encadrement précédent : savoir tout cela est nécessaire, et c'est pratiquement la définition de l'algorithme de résolution de l'équation par dichotomie. Cependant cela n'éclaire pas sur les lignes de programme qu'il convient d'écrire.

   Il reste à trouver la « façon de faire » (Arsac (1988) déjà cité) ; ce n'est pas un problème d'algorithmique au sens mathématique : trouver une méthode mathématique pour résoudre un problème, étudier la complexité de cette méthode (éventuellement en prenant en compte son implémentation en machine) ; il s'agit « seulement [de] trouver, face à un problème donné, une méthode qui en viendra à bout. » (Arsac, idem).

   Peut-être conviendrait-il de distinguer, au moins au niveau de l'enseignement secondaire, l'algorithmique mathématique de l'algorithmique-programmation : nous avons déjà employé cette formulation (avec ou sans trait d'union) pour laisser apparaître que notre propos se situe plus près du programme que de considérations de complexité (par exemple).

   Cette question : « par quel bout commencer ? » renvoie à la mise en œuvre d'heuristiques au sens recommandé par la délégation générale à la langue française et aux langues de France (JO du 16 septembre 1989) : une heuristique est une « méthode de résolution de problèmes, non fondée sur un modèle formel et qui n'aboutit pas nécessairement à une solution ».

   Ce peut être par exemple la méthode des situations évoquée par Arsac pour construire une itération.

   Ce peut être également une analyse descendante du problème, débouchant sur une décomposition du problème en problèmes plus simples, etc.

   Dans l'introduction du cours polycopié intitulé « Algorithmes et programmation » pour les étudiants de l'école Polytechnique, Cori et Lévy (2011) écrivent :
« Notre cours doit être compris comme une initiation à l'informatique, et plus exactement à l'algorithmique et à la programmation. Il s'adresse à des personnes dont nous tenons pour acquises les connaissances mathématiques : nulle part on n'expliquera ce qu'est une récurrence, une relation d'équivalence ou une congruence. Il est orienté vers l'algorithmique, c'est-à-dire la conception d'algorithmes (et non leur analyse de performance), et la programmation, c'est-à-dire leur implantation pratique sur ordinateur (et non l'étude d'un - ou de plusieurs - langage(s) de programmations). »

(...)

   Nous trouvons ici explicitement l'acception de l'algorithmique comme : la conception d'algorithmes.

   La programmation d'un algorithme est conçue comme son « implantation pratique sur ordinateur ».

   Cori et Lévy parlent de style de programmation : il y a plusieurs grandes classes de langages de programmation (langages impératifs, langages fonctionnels, langages déclaratifs, langages récursifs, tableurs etc., un même langage pouvant relever de plusieurs classes).

L   La mise en œuvre d'un algorithme dans une classe de langage donnée amènera un certain style de programmation.

   Et comme le soulignent Cori et Lévy, à l'intérieur d'une même classe de langages, il peut y avoir divers styles. Ils donnent l'exemple de deux programmes en langage C pour calculer π :
« Ce programme fait un nombre inconsidéré d'appels au préprocesseur et beaucoup trop d'effets de bord. Il est illisible. Il faut avoir une conception simple et donc esthétique des programmes. On n'est plus à l'époque où tout se joue à l'instruction machine près. La puissance des ordinateurs a rendu très viable la programmation sans optimisations excessives. Tout l'art du programmeur, et notamment du programmeur C, est de comprendre les quelques endroits critiques d'un programme, en général très peu nombreux, où les optimisations sont nécessaires. Donc le programme cryptique précédent, ou tout autre bourré d'optimisations inutiles sera mauvais et donc interdit. »

   La différence entre les deux programmes évoqués – différence de style – relève d'un parti pris du programmeur (les optimisations), parti pris qui est extérieur à l'algorithme (il s'agit du calcul de π par le développement en série : π/4 = arctan(1) = Σ (-1)ⁿ / (2n+1) ), et qui est extérieur au langage de programmation.

5. Les descriptions d'algorithme

   Pour ce qui concerne les simulations informatiques d'expériences aléatoires envisageables au lycée, il semble que l'on puisse laisser de côté la question : « comment construit-on un algorithme ? » dans la mesure où les algorithmes en jeu sont simples (imitation au plus près de l'expérience aléatoire), y compris pour ce qui concerne l'environnement informatique qui permettra d'effectuer un traitement statistique des résultats produits.

   Par contre, il apparaît que la traduction d'un algorithme en un programme (code) exécutable sur machine, est conçue en tenant compte du langage de programmation dans lequel il doit être traduit (par exemple : le langage possède-t-il dans ses structures de contrôle les boucles « tant que », les boucle « jusqu'à » ?).

   Nous faisons l'hypothèse que cette traduction pose pour les élèves plus de problème qu'il n'y paraît à lire les documents d'accompagnement des programmes proposés aux enseignants, documents que nous commenterons dans le chapitre suivant.

   L'interface que nous évoquions dans le paragraphe précédent est une étape intermédiaire entre l'algorithme et le programme (programme au sens du code exécutable par la machine), étape que nous appellerons dans la suite : description de l'algorithme.

   On n'envisage pas la même description d'algorithme selon que l'on s'autorise une programmation récursive ou non (la différence de classe de langages amène deux styles de programmation).

   Ainsi pour la programmation du calcul de n! = 1×2× ... ×n , en vue de la programmation dans un langage impératif, la description de l'algorithme pourra être :

Entrer N
mettre F à 1
Pour J allant de 1 à N faire :
   F reçoit F × J
Fin de faire

   En vue de la programmation dans un langage récursif, la description de l'algorithme reposera sur la remarque que n! = n × (n – 1)! et sa description pourra se faire par :

Entrer N
Si N = 1 alors Factorielle(N) = 1 sinon Factorielle(N) = N × Factorielle(N-1)

   La création d'une feuille de calcul sur tableur [2] et la création d'un programme dans un langage impératif ne peuvent pas a priori [3] reposer sur une même description d'algorithme :
Un programme dans un langage de programmation impératif est un enchaînement dans le temps d'instructions qui ont pour effet de modifier, au cours de l'avancement de l'exécution du programme, les valeurs qui se trouvent dans les diverses mémoires. L'interprétation (en général le sens, en relation avec les objectifs assignés au programme) de ces valeurs dépend du temps, c'est à dire du degré d'avancement de l'exécution du programme.

   L'interprétation des résultats d'une feuille de calcul de tableur est fondée sur les relations qu'entretiennent entre elles les cellules, une fois le calcul de la feuille effectué.

   Cette étape de la description de l'algorithme produit un texte qui prend à la fois en compte la classe de langage de programmation dans lequel sera écrit le programme (code), et le style de programmation propre au programmeur.

   Ce texte peut être traduit pratiquement directement dans le langage de programmation visé, et tout autre langage appartenant aux mêmes classes.

   De tels textes seront présentés et commentés dans le prochain chapitre : ils sont extraits de documents à destination des enseignants, accompagnant les « programmes 2010 ». Nous n'avons retenu que ceux qui ont trait aux simulations d'expériences aléatoires.

   Ces textes sont présentés comme les « algorithmes », ce qui paraît impropre, tant ils sont pratiquement isomorphes à leur traduction dans le langage de programmation, et dans la mesure où l'on voit pour certains d'entre eux que le texte est conforme à certains partis pris, certaines heuristiques du programmeur, ce que nous avons appelé plus haut le style de programmation du programmeur. Nous préférons les considérer comme des descriptions d'algorithmes prêtes à être traduites dans les langages de programmation de la classe des langages pour laquelle ces descriptions ont été conçues.

Françoise Gaydier,
docteur en sciences de l'éducation,
professeure de l'option informatique (1981-1991),
professeure de mathématiques.

Cet article est sous licence Creative Commons (selon la juridiction française = Paternité - Pas de Modification). http://creativecommons.org/licenses/by-nd/2.0/fr/

Bibliographie

Arsac J. (1989). La didactique de l'informatique : un problème ouvert ? Contribution au Colloque francophone sur la didactique de l'informatique (1988). Actes publiés par l'EPI.
http://epi.asso.fr/fic_pdf/dossiers/d07p009.pdf

Baron G.-L. (1987). La constitution de l'informatique comme discipline scolaire, le cas des lycées, Thèse en sociologie de l'Éducation, Université René Descartes, Paris

Cori R., Lévy J.-J. (2011). Algorithmes et programmation. Cours de tronc commun. École Polytechnique.
http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/

Dijkstra E. W., Dahl O. J., Moare C. A. R. (1972). Structured programming, Academic Press, London.

Gaydier F. (2011). Simulation informatique d'expérience aléatoire et acquisition de notions de probabilité au lycée, thèse soutenue à l'Université Paris 5 René Descartes, laboratoire EDA.
http://tel.archives-ouvertes.fr/tel-00826073

Nguyen C. T. (2005). Étude didactique de l'introduction d'éléments d'algorithmique et de programmation dans l'enseignement mathématique secondaire à l'aide d'une calculatrice. Thèse. Université Joseph Fourier, Grenoble.

Pair C. (1988). Je ne sais (toujours) pas enseigner la programmation, dans la Revue Informatiques n° 2, p. 5-14.

Rogalski J. (1989). Enseignement de méthodes de programmation dans l'initiation à l'informatique. Contribution au Colloque francophone sur la didactique de l'informatique (1988). Actes publiés par l'EPI.
http://epi.asso.fr/fic_pdf/dossiers/d07p061.pdf

Rogalski J., Samurcay R., Hoc J.M . (1988). L'apprentissage des méthodes de programmation comme méthode de résolution de problème, Le Travail Humain, 51.

[1] « Ressources pour la classe de seconde, algorithmique », (« programmes 2010 »)
http://media.eduscol.education.fr/file/Programmes/17/8/Doc_ress_algo_v25_109178.pdf

Annexe

J'ajoute en annexe de ce texte une « façon de faire » pour la résolution d'une équation par dichotomie (algorithme qui vient d'être décrit), façon de faire qui permet d'obtenir des descriptions d'algorithme qui en résultent, selon divers styles.

Hypothèses mathématiques :
f est une fonction continue et strictement décroissante sur l'intervalle [a ; b] ; ƒ(a) ≥ 0 et ƒ(b) < 0.

Cahier des charges :
obtenir une valeur approchée à ε près de l'unique solution α de l'équation ƒ(x) = 0.

Une façon de faire

1. Situation : (= invariant de boucle)

« On a déjà fait une partie du travail » :
la solution cherchée se trouve entre u et v, et f(u) ≥ 0 et f(v) < 0, les valeurs de u et v étant respectivement aux adresses U et V.

2. Est-ce fini ?

   C'est fini si la précision attendue est atteinte, c'est à dire si v – u < ε.

    Là intervient un choix (style), décidé par le programmeur s'il connaît un peu de mathématiques ; on peut en effet calculer à l'avance le nombre N d'itérations nécessaires pour obtenir la précision voulue : N = Ent[(b - a) / (ε ln 2)] + 1, où Ent désigne la fonction partie entière.

   Pour diverses raisons le programmeur peut décider de décrire l'algorithme

1. avec une boucle « répéter N fois »,
2. avec une boucle « tant que » contrôlée par un compteur I d'itérations :
   « faire tant que I < N »,
3. avec une boucle « tant que v – u ≥ ε.

    On peut aussi décrire l'algorithme avec des boucles « jusqu'à » que je n'expliciterai pas ici pour ne pas alourdir mon propos, mais aussi parce que cela ne correspond pas trop à mon style personnel de programmation : les boucles « jusqu'à » ont l'inconvénient que le test s'effectue après les instructions du corps de la boucle, donc il faut tenir compte qu'il y aura au moins un passage dans la boucle, ce qu'il faut éviter pour certains algorithmes.

   Ces choix, qui vont faire partie du style du programme final, peuvent reposer sur des considérations pédagogiques (faire un peu de maths ou avoir une idée de la rapidité de l'algorithme en comparaison d'un algorithme par balayage), ou sur des contraintes liées au langage de programmation à disposition, ou des choix « esthétiques » personnels du programmeur, etc.

   Dans le cas (2), la variable I doit être interprétée dans la situation :
la solution cherchée se trouve entre u et v, et f(u) ≥ 0 et f(v) < 0 et on a déjà divisé I fois l'intervalle [a ; b].

3. Avancer le travail

Calculer w = f((u+v)/2) α ranger à l'adresse W
si w < 0 alors α se trouve dans l'intervalle [u ; (u + v)/2] sinon α se trouve dans [(u + v)/2 ; v].

Ce qui devient dans la description d'algorithme où ← code l'instruction d'affectation :
W ← f((U + V)/2) 
Si W < 0 alors V ← (U + V)/2 sinon U ← (U + V)/2 ;

et dans le choix (2) :
I ← I + 1

4. Initialisations

   La situation décrite en 1. doit être satisfaite au premier passage dans la boucle : cela inclut entre autres la saisie des données a, b et ε , aux adresses A, B et E, mais aussi les initialisations de U, V, et I pour la variante (2), et N pour les version (1) et (2).
entrer A ; entrer B ; entrer E ;
U ← A ; V ← B ;
variante (2) et (1) : N ← Ent[(B - A) / (E × ln 2)] + 1
variante (2) : I ← 0 ;

   Voici regroupées dans un tableau trois descriptions de l'algorithme de résolution de l'équation par dichotomie.

   Chacune de ces description peut être traduite codée pratiquement automatiquement dans un langage impératif.

NOTES

[1] La question des spécificités de l'informatique est liée étroitement au problème des diverses transpositions didactiques qui peuvent être utilisées pour passer d'une connaissance du domaine scientifique ou des pratiques professionnelles à un objet d'enseignement. Les deux types de transposition sont également en relation avec les représentations qu'ont les enseignants sur l'informatique et ce qu'ils souhaitent que se représentent les élèves. Le point de vue des spécificités de l'informatique est développé dans (Rogalski, 1987a).

[2] Nous laissons ouverte la question « peut-on encore parler de langage de programmation ? »

[3] Même s'il est possible de « simuler » une boucle dont le nombre de répétitions est connu d'avance, comme cela est pratiqué précisément pour les simulations qui nous intéressent ici, lorsqu'elles se font sur tableur.