Innovation Pédagogique
Institut Mines-Telecom

Une initiative de l'Institut Mines-Télécom avec un réseau de partenaires

Une démarche pédagogique pour résoudre des exercices d’algorithmique

17 novembre 2015 par Gilles Retours d’expériences 811 visites 0 commentaire
UNE DEMARCHE POUR RESOUDRE DES EXERCICES D’ALGORITHMIQUE
La démarche MVR : méthode, vérification, résultat


Résumé
Cet article présente une démarche pédagogique (MVR) introduite pour résoudre les exercices d’un cours d’algorithmique en formation d’ingénieur au niveau postbac français. Après avoir rappelé les retours d’expériences qui ont inspiré sa mise au point, les 3 étapes de cette démarche sont présentées : méthode, vérification, et résultat, ainsi que sa mise en œuvre à l’Ecole nationale d’ingénieurs de Brest.

Mots-clés : méthode, vérification, algorithmique, formation, ingénieur.

Jacques Tisseau, Pierre De Loor, Sébastien Kubicki, Alexis Nédélec, Marc Parenthoen
Ecole Nationale d’Ingénieurs de Brest, France
{tisseau,deloor,kubicki,nedelec,parenthoen}@enib.fr


~~~~~~~~~~~~~~~~~~~~~


Un article publié au VIIIe Colloque des Questions de Pédagogie dans l’Enseignement Supérieur, Brest, 17, 18 et 19 Juin 2015.


I. INTRODUCTION

Ce document présente la démarche suivie pour répondre aux exercices qui accompagnent le cours d’« Initiation à l’algorithmique » du semestre S1 à l’Ecole nationale d’ingénieurs de Brest (ENIB). Cette démarche, dite MVR pour Méthode-Vérification-Résultat, est structurée en 3 étapes :

  1. expliciter une méthode générique de résolution pour résoudre des problèmes équivalents à celui qui est posé (étape M comme Méthode) ;
  2. expliciter une technique alternative ou complémentaire connue pour vérifier le résultat obtenu en appliquant la méthode générique précédente (étape V comme Vérification) ;
  3. appliquer la méthode générique de résolution (M) et la technique de vérification (V) au cas particulier de l’énoncé pour obtenir le résultat attendu par l’exercice (étape R comme Résultat). Cette démarche repose sur les retours d’expériences de plusieurs années d’enseignement et sa mise en œuvre conduit à une triple évaluation des exercices selon une notation adaptée dans le cadre d’un contrôle continu systématique.

II. RETOURS D’EXPERIENCES

II.1 Contexte

L’Ecole nationale d’ingénieurs de Brest (ENIB) est une école publique d’ingénieurs du Ministère français de l’éducation nationale, de l’enseignement supérieur et de la recherche qui forme en 5 ans des ingénieurs généralistes en ingénierie des systèmes industriels dans les domaines de l’électronique, de l’informatique et de la mécatronique.
Le cours concerné ici est le cours d’informatique du premier semestre de l’année postbac (semestre S1) dont l’objectif principal est l’acquisition des notions fondamentales de l’algorithmique et de leur mise en œuvre à travers l’utilisation du langage Python [Tisseau, 2009]. Il s’agit d’un enseignement de 42h réparties régulièrement sur 14 semaines : 1h30 de cours-td en salle banalisée toutes les semaines (par groupes de 36 étudiants maximum) et 3h de laboratoire en salle informatique toutes les deux semaines (par groupes de 24 étudiants maximum). L’équipe pédagogique est composée de 5 enseignants-chercheurs permanents en informatique qui travaillent ensemble depuis plusieurs années et qui, au fil des ans, ont fait émerger 3 réflexions méthodologiques principales concernant une démarche à suivre pour poser et résoudre les exercices du cours d’informatique : ne pas se tromper d’objectif, expliciter l’implicite et encourager la rédaction.

II.2 Ne pas se tromper d’objectif

Les étudiants de l’ENIB sont issus des voies scientifique (Bac S) et technique (Bac TI2D) de l’enseignement secondaire. C’est pourquoi, pour donner du sens aux exercices d’algorithmique, de nombreux exemples sont empruntés aux mathématiques, à la physique et plus généralement aux sciences de l’ingénieur.
Ces emprunts interdisciplinaires sont absolument nécessaires pour participer au décloisonnement des disciplines... que les étudiants ont progressivement appris à cloisonner et à isoler au cours de leur scolarité. Mais ils posent le problème de l’objectif thématique de l’exercice. En effet, les étudiants peuvent être si perturbés par la thématique secondaire (par exemple les mathématiques ou la physique) qu’ils en oublient la thématique principale (ici l’algorithmique), ce qui n’est évidemment pas le but recherché par l’exercice d’algorithmique.
On s’attache alors à expliciter l’objectif thématique de l’exercice et à renseigner au mieux les éléments nécessaires aux thématiques secondaires. On rappelle aux étudiants que l’évaluation porte sur l’objectif thématique principal et non sur les thématiques secondaires.

II.3 Expliciter l’implicite

En algorithmique, on cherche à caractériser différentes propriétés d’un algorithme telles que sa validité, sa réutilisabilité, sa robustesse, sa complexité ou encore son efficacité [Dowek et al, 2011]. Il faut donc progressivement développer chez l’informaticien débutant des réflexes de validation, de réutilisation, de protection, d’évaluation ou encore d’adaptation au support matériel. L’acquisition de ces réflexes méthodologiques doit être évaluée au même titre que l’acquisition des connaissances proprement dites comme l’affectation, l’alternative ou l’itération. Il faut donc expliciter auprès des étudiants ces objectifs méthodologiques et ne pas les cantonner au niveau d’objectifs implicites plus ou moins pris en compte dans l’évaluation d’une réponse à un exercice donné.
En premier lieu, il faut s’assurer que l’algorithme est valide : réalise-t-il exactement la tâche pour laquelle il a été conçu ? On demande alors explicitement aux étudiants de proposer une démarche de vérification de leurs réponses. Dans un deuxième temps, on s’intéresse à sa généricité : l’algorithme est-il réutilisable pour résoudre des tâches équivalentes à celle pour laquelle il a été conçu ? On propose alors aux étudiants d’appliquer leur méthode sur un grand nombre d’exercices équivalents. Dans un troisième temps, on s’attachera à le rendre robuste : l’algorithme est-il protégé de conditions anormales d’utilisation ? La précision des conditions d’application permet de traiter cette propriété de robustesse.
Ces trois premières propriétés (validité, réutilisabilité, robustesse) trouveront plus tard leur prolongement « naturel » dans la spécification des fonctions : paramétrage (réutilisabilité), préconditions (robustesse) et jeux de tests (validité). En ce qui concerne les propriétés d’un algorithme telles que la complexité (combien d’instructions élémentaires seront exécutées pour réaliser la tâche pour laquelle l’algorithme a été conçu ?) et l’efficacité (l’algorithme utilise-t-il de manière optimale les ressources du matériel qui l’exécute ?), elles sont abordées au travers d’exemples précis, leur étude systématique ne relevant pas du cours d’« Initiation à l’algorithmique » de l’ENIB.
Dans tous les cas, on s’attache donc à préciser le ou les objectifs méthodologiques de l’exercice qui seront alors évalués explicitement au même titre que l’objectif thématique.

II.4 Encourager la rédaction

La rédaction « en bon français » de la réponse à un exercice ne constitue pas le point fort des jeunes étudiants de l’ENIB. Les réponses sont (trop) souvent libellées « simplement » sous forme de valeurs, de formules, de diagrammes ou de codes informatiques : aucune explication « en bon français » ne vient compléter ni expliciter la réponse, ni la démarche qui a conduit à cette réponse, encore moins la critique de la solution proposée. Et pourtant, si la réponse à la question est attendue, les éléments de discours qui l’accompagnent le sont tout autant, d’autant plus dans une formation d’ingénieurs qui vise à former des professionnels qui devront rédiger des cahiers des charges, des spécifications et des conceptions détaillées, des recettes de tests, des notes de synthèse, écrites comme orales, ou encore des réponses à des appels d’offres. Le métier d’ingénieur ne peut se contenter d’une valeur, d’une formule, d’un diagramme ou d’un code : s’il faut être capable de trouver une solution à un problème donné, il faut aussi savoir « défendre » rationnellement la solution proposée. L’argumentaire qui accompagne la solution proposée doit permettre de mieux comprendre cette solution et augmenter ainsi la confiance du « lecteur » dans les compétences du « rédacteur » à résoudre le problème posé.
On s’attache alors à prendre en compte explicitement la rédaction dans l’évaluation de la réponse. Pour cela, il faut le plus souvent, soit augmenter le temps accordé à l’exercice, soit diminuer le nombre d’exercices à résoudre dans un temps imparti, pour permettre à l’étudiant « rédacteur » de soigner cet aspect important de sa réponse.

III. LA DEMARCHE MVR

III.1 Explicitation de la méthode

Etant donné un énoncé qui propose à l’étudiant de résoudre un exercice portant sur un cas particulier donné, la première étape (M) de la démarche MVR consiste à décrire une méthode générique qui, lorsqu’on l’appliquera, permettra de résoudre le cas particulier considéré ainsi que tout problème équivalent à celui qui est posé.
Pour un débutant, cette étape d’explicitation d’une méthode générique est une étape difficile. Elle nécessite de développer des capacités d’abstraction qui mettent en œuvre des mécanismes d’induction pour favoriser le passage de données particulières à des propositions plus générales. C’est également une étape difficile parce que la description d’une méthode peut difficilement se résumer à une valeur, une formule, un diagramme ou un code informatique. Elle nécessite une phase rédactionnelle rigoureuse et suffisamment détaillée pour qu’un lecteur averti puisse appliquer sans hésiter la méthode décrite.
Cette étape permet ainsi de développer des capacités d’abstraction et des capacités rédactionnelles absolument nécessaires aux futurs ingénieurs.

III.2 Vérification du résultat

Etant donné un résultat obtenu par application d’une méthode générique pour résoudre un problème particulier, la deuxième étape (V) de la démarche MVR consiste à vérifier ce résultat par des méthodes alternatives ou complémentaires de celle déjà utilisée.
Pour un débutant, cette étape de vérification du résultat obtenu est assez difficile car il s’agit avant tout de remettre en cause son propre travail. Dans le meilleur des cas, le débutant estime que la vérification consiste simplement à refaire les mêmes calculs, le même raisonnement ou la même démarche : c’est effectivement la moindre des choses que de ré-appliquer la méthode pour vérifier qu’on ne s’est pas trompé en l’appliquant la première fois. Mais la vérification consiste plutôt à changer de point de vue sur le problème et à utiliser d’autres méthodes pour « estimer » la validité du résultat. Il peut effectivement exister plusieurs méthodes alternatives pour résoudre un même problème. Résoudre alors le problème par deux méthodes différentes et obtenir le même résultat renforce bien entendu la « confiance » en ce résultat. Mais dans bien des cas, il s’agit plutôt de méthodes complémentaires, le plus souvent sous forme d’heuristiques, qui permettent de détecter que le résultat est certainement faux, comme par exemple la preuve par 9 en calcul élémentaire ou l’analyse dimensionnelle en physique. Et si de telles méthodes complémentaires ne détectent pas que le résultat est faux, alors ça renforce ici encore la « confiance » que l’on peut avoir dans le résultat obtenu.
Cette étape permet ainsi de développer l’esprit critique des futurs ingénieurs en insistant sur le souci de vérification systématique de ses propres résultats comme de ceux provenant d’autres sources (collègues, articles, internet...). Et par ailleurs, penser la vérification du résultat avant d’obtenir le moindre résultat permet aussi de se projeter dans l’usage futur de la méthode en l’anticipant au sein de projets d’ingénierie plus complexes.

III.3 Application de la méthode

Etant données une méthode générique pour résoudre un ensemble de problèmes équivalents et une technique de vérification associée, la troisième étape (R) de la démarche MVR consiste à appliquer la méthode à un problème particulier et à vérifier le résultat obtenu par l’heuristique de vérification.
Pour un débutant, cette étape d’application d’une méthode générique est une étape assez facile. Elle nécessite de développer des capacités d’exécution qui mettent en œuvre des mécanismes de déduction pour réaliser le passage de propositions générales à un cas particulier.
Cette étape permet ainsi de développer des capacités d’exécution en respectant rigoureusement des consignes imposées. Elle met ainsi en évidence des capacités techniciennes qui seront très utiles aux futurs ingénieurs dans leur mission d’encadrement d’équipes d’ouvriers et de techniciens.

IV. MISE EN OEUVRE

IV.1 Contexte

Les « Questionnements de cours » [Tisseau, 2012] qui accompagnent le cours d’« Initiation à l’algorithmique » du semestre S1 à l’ENIB sont conçus de façon plutôt ascendante (de l’exemple au concept) [Astolfi, 2008] et se veulent complémentaires des notes de cours qui, elles, sont conçues plutôt classiquement de façon descendante (du concept à l’exemple). Chaque questionnement concerne un point particulier du cours. Il est structuré en 5 parties de la manière suivante :
Exemple : dans cette partie, des questions « simples » sont posées sur un problème « connu » de la « vie courante » afin d’introduire le concept informatique sous-jacent. On y trouve des exemples tels que ranger un meuble à tiroirs, déterminer sa mention au Bac, planter un clou ou encore trier un jeu de cartes. Cette partie est principalement traitée de manière informelle par les étudiants eux-mêmes, individuellement ou en groupe.

  1. Généralisation : dans cette partie, les concepts informatiques sous-jacents dans les exemples précédents sont présentés et introduits à l’aide de questions plus informatiques. On y aborde les concepts d’affectation, de tests et d’alternatives, de boucles, de spécification de fonction, de récursivité ou encore de manipulation de séquences. En général, cette partie est traitée par l’enseignant.
  2. Applications : des exemples « simples » d’application sont ensuite proposés. Le premier exemple est en général traité in extenso par l’enseignant en suivant la démarche MVR, les autres par les étudiants, en groupe ou individuellement.
  3. Entraînement : cette partie est une préparation à l’évaluation qui a lieu en début de séance suivante. Les étudiants y travaillent chez eux entre les deux séances, individuellement ou en groupe. Cet entraînement est lui-même structuré en 3 parties :
  4. Enoncé : on présente ici le problème que l’on souhaite traiter.
  5. Exemple : un exemple est traité en détail dans cette partie en suivant la démarche MVR.
  6. Questions : des questions de même difficulté sont proposées ici pour permettre à chaque étudiant de s’entraîner sur le problème à traiter. La résolution de 2 ou 3 de ces exemples l’aide ainsi à induire (à faire émerger) la méthode générique qui est attendue ainsi qu’à mener explicitement les vérifications souhaitées.
  7. Révisions : cette partie fait le lien entre les questionnements de cours [Tisseau, 2012] et les notes de cours [Tisseau, 2009].

IV.2 Evaluations

Chaque contrôle donne lieu a une triple évaluation de la part de l’enseignant : une évaluation concerne la qualité de l’explicitation de la méthode générique (M), une autre la pertinence de la vérification du résultat (V) et la troisième la qualité du résultat obtenu (R). Ainsi, le résultat à la question posée, dont se contentent le plus souvent les étudiants, n’est plus le seul élément de réponse attendu : il est également demandé aux étudiants d’expliciter la méthode utilisée ainsi que les vérifications menées. CNISF

La grille de notation adoptée doit permettre de « soulager » l’enseignant dans sa tâche de correction et d’aider les étudiants à mener leurs propres évaluations. Un exercice cherche à évaluer un objectif particulier : la notation exprime alors simplement la « distance » qui reste à parcourir pour atteindre cet objectif. Quatre distances sont ainsi pré-définies selon une métaphore de la cible :
0 : « en plein dans le mille ! » (l’objectif est atteint)
1 : « pas mal ! » (on est proche de l’objectif)
2 : « juste au bord de la cible ! » (on est encore loin de l’objectif)
3 : « la cible n’est pas touché ! » (l’objectif n’est pas atteint)

Ayant choisi de ne garder qu’un petit nombre de niveaux pour « faciliter » l’évaluation, le choix de 4 niveaux a finalement été préféré à 2, 3 ou 5 niveaux. Une notation sur 2 niveaux (tout ou rien) est un peu trop caricaturale. Avec un (petit) nombre impair de niveaux (3 ou 5), l’expérience montre que, dans le doute, le correcteur a tendance à choisir plus facilement le niveau intermédiaire (1 ou 3) alors qu’avec un nombre pair de niveau (ici 4), il doit « choisir son camp » : objectif plutôt atteint (0 ou 1) ou plutôt raté (2 ou 3). En fait, il existe un cinquième niveau qui correspond à une absence au contrôle, sanctionnée par la note 4 (l’objectif n’a pas été visé), dite note « minimale ».

IV.3 Contrôle continu

Chaque séance donne lieu a priori à une évaluation, à savoir : un QCM de 5’ en fin de séance ou un contrôle « MVR » de 30’ en début de séance pour les cours-td, et un contrôle sur machine de 30’ en début de séance de laboratoire. A la fin de chaque contrôle, il est demandé à chaque étudiant de s’auto-évaluer pour chacune des étapes de la méthode MVR selon la grille de notation à 4 niveaux de la section précédente. Enfin, une correction est proposée par l’enseignant juste après le contrôle, « à chaud ».
L’accumulation et la fréquence des contrôles, notés d’une séance à l’autre, permettent un suivi plus régulier et plus fin des apprentissages des étudiants. Ceux-ci travaillent plus et plus régulièrement en développant au fur et à mesure leurs capacités d’abstraction et leur esprit critique. Et de leur avis même, ils ont l’impression au bout du compte de mieux maîtriser leurs apprentissages.

V. CONCLUSION

La démarche MVR (Méthode-Vérification-Résultat) mise en place dans le cadre du cours d’« Initiation à l’algorithmique » du semestre S1 à l’ENIB, cherche à développer, à travers l’acquisition de compétences thématiques en informatique, des compétences plus transversales, nécessaires aux futurs ingénieurs : la capacité d’abstraction, l’esprit critique et la rigueur applicative.
C’est pourquoi la démarche MVR repose sur trois étapes bien distinctes :

  • l’explicitation d’une méthode générique de résolution d’une famille de problèmes équivalents pour développer la capacité d’abstraction de l’étudiant,
  • la vérification explicite du résultat pour développer son esprit critique,
  • l’application de la méthode proposée à un cas particulier pour développer sa rigueur applicative.

Sa mise en œuvre à travers un contrôle continu systématique, quoique récente, permet d’entrevoir quelques évolutions encourageantes. Les étudiants ne se contentent plus d’un simple résultat répondant strictement à la question posée mais s’engagent avec plus d’intérêt dans la généralisation de leur méthode et dans la remise en cause de leur propre résultat. Ils travaillent plus et plus régulièrement et enfin, ils ont l’impression de mieux maîtriser leurs apprentissages.
Cette démarche MVR s’inscrit finalement dans la famille des approches PDCA (Plan, Do, Check, Act) reprises dans les systèmes de management de la qualité des normes ISO 9000 [Deming, 1950] [Moen et Norman, 2009]. « Plan » serait ici l’étape « M », « Check » l’étape « V » et « Do » l’étape « R » ; « Act » qui correspond à un retour critique d’amélioration continue est réalisée en présentiel entre l’enseignant et l’étudiant.
Il reste que cette démarche est lourde à mettre en place pour un enseignant isolé et seules des équipes pédagogiques constituées pourront s’engager sereinement dans cette voie exigeante.

REFERENCES

Astolfi, J.P. (2008). "Le questionnement pédagogique". Economie et management, n°128, pp. 68-73.

Deming, W.E. (1950). Elementary Principles of the Statistical Control of Quality, JUSE (Union of Japanese Scientists and Engineers).

Dowek, G. et al (2011). Une introduction à la science informatique. Paris : CNDP-CRDP.

Moen, R. et Norman, C. (2009). Evolution of the PDCA cycle. Associates in Process Improvement, Detroit, (en ligne)

http://pkpinc.com/files/NA01MoenNormanFullpaper.pdf (page visitée en décembre 2014).

Tisseau, J. (2009). Initiation à l’algorithmique : notes de cours. Brest : ENIB.

Tisseau, J. (2012). Initiation à l’algorithmique : questionnements de cours. Brest : ENIB.

Licence : CC by-sa

Répondre à cet article

Qui êtes-vous ?
Ajoutez votre commentaire ici
  • Ce formulaire accepte les raccourcis SPIP [->url] {{gras}} {italique} <quote> <code> et le code HTML <q> <del> <ins>. Pour créer des paragraphes, laissez simplement des lignes vides.

Suivre les commentaires : RSS 2.0 | Atom