G-ALG : Gestion d'ALGorithmes                            gilles.hunault@univ-angers.fr       pourquoi G-ALG ? Table des matières cliquable   1. Nécessité d'un langage algorithmique   2. Choix d'un langage algorithmique   3. Multiplicité et qualité des solutions en algorithmique   4. Extensions naturelles   5. Comment enseigner le développement informatique, la programmation et l'algorithmique ? 1. Nécessité d'un langage algorithmique Tout programme met en oeuvre une méthode, des idées, ce qui signifie que tout programme repose sur un algorithme, qu'il soit implicitement présent dans les neurones du programmeur ou explicitement transcrit sous forme de texte dans un fichier. Dès lors qu'il existe, pourquoi ne pas l'écrire rigoureuseument ? La traduction de l'algorithme en programme, traduction non pas mécanique mais fine, adaptée aux finesses (ou aux roueries) du langage, voire du système d'exploitation, en sera facilitée. Un langage algorithmique est donc, selon nous, obligatoire, à la fois pour s'affranchir de la machine, des langages de programmation et pour formaliser le travail à accomplir, pour spécifier l'enchainement des actions, nommer les variables... ou pour discuter de la méthode, vérifier qu'on traite bien tous les cas. Lorsqu'on veut enseigner le développement informatique -- ce qui est beaucoup plus vaste que d'enseigner juste la programmation dans un langage donné -- la première étape est d'expliciter comment on passe du problème posé à une solution, voire à plusieurs solutions. Il ne s'agit pas de montrer, laissons ce soin à la philosophie, comment penser mais bien comment raisonner comme un ordinateur et décrire et tester les actions à enchainer pour obtenir un résultat donné avec un niveau de détail correspondant à celui des instructions élémentaires de l'algorithmique. Si on veut en plus utiliser un langage algorithmique dans le but d'enseigner la programmation, il faut un langage clair, facilement compréhensible par des débutants, qualités que n'ont pas les langages réels. Pour dialoguer entre humains, il faut un langage humain simplifié. Or les langages comme C, C++, Perl, Python, R... n'ont pas été conçus pour cela. Pour dialoguer entre français, il faut un langage en français simplifié. Là encore, C, C++, Perl, Python, R... ne répondent pas à cette attente. Ecrire un algorithme est un travail structuré, réfléchi. Le langage algorithmique doit obéir à des règles strictes de vocabulaire, de syntaxe et de sémantique. Le risque à trop formaliser, à trop imposer, est de définir un langage algorithmique trop proche d'un langage de programmation, voire de confondre le langage algorithmique avec un langage de programmation francisé, perdant à la fois souplesse, concision et lisibilité. On pourra consulter à ce sujet la page «les aventures de Guillemet et Point-virgule». 2. Choix d'un langage algorithmique Que doit donc contenir un langage algorithmique simple, souple mais complet ? Certainement pas toute l'algorithmique, mais le noyau "dur" de l'algorithmique impérative fondamentale, c'est-à-dire la partie commune à la plupart des langages comme C, Java, Javascript, Pascal, Perl, Php, Python, Rexx, R, Ruby... Il doit donc permettre l'écriture de commentaires, réaliser des affectations, des tests et des boucles, utiliser des tableaux, disposer d'un mécanisme de définition et d'appel de sous-programmes. Pas plus. Un tel langage -- et il ne pourra pas servir d'introduction pour des langages "spéciaux" comme APL, Lisp, Prolog ou Sql -- ne doit donc pas utiliser de pointeurs, ni des structures de données trop compliquées car ces éléments ne font pas partie du "coeur" de l'algorithmique impérative fondamentale. Au contraire, la notion simple de tableau "naturel" avec des indices qui commencent à 1 est importante et doit être suffisante à ce titre car elle est pédagogique, intuitive : quand on compte sur ses doigts, on commence à 1... De même, la notion de sous-programme doit pouvoir tout masquer avec une syntaxe unifiante. Vouloir exposer l'indirection doit pouvoir s'écrire avec une fonction pointeur(x), désigner le fils gauche de l'élement courant dans un arbre binaire peut se formaliser via filsGauche(arbreBin,eltCour) s'il faut vraiment introduire ces notions... A nos yeux, apprendre à écrire des algorithmes c'est s'astreindre à une grande rigueur, une grande précision. C'est aussi compléter le code écrit par une analyse de l'exhaustivité de la solution et avec une vérification via autant de tests que nécessaires. Si on doit comparer 3 valeurs, combien d'étudiant(e)s savent combien de cas il faut envisager, par exemple en supposant les valeurs distinctes ? Ce n'est pas un langage algorithmique ou un langage réel de programmation qui donne la réponse parce qu'il s'agit d'un problème d'analyse combinatoire. Mais seul un langage algorithmique permet de ne pas se focaliser sur le typage et les nombreuses relations d'ordre sous-jacentes aux types. Seul un système de validation qui connait tous les cas possibles et qui vérifie l'exactitude du code pour chaque cas garantit la qualité de l'algorithme. C'est pourquoi nous proposons le système pédagogique G-ALG avec son le langage nommé GALG qui n'est ni original ni ésotérique : il doit juste être vu comme une formalisation de l'intersection de la plupart des instructions impératives. Sa ressemblance avec tous les langages existants via l'instruction SI pour un test, l'instruction POUR pour une boucle à nombre déterminé d'itérations etc. est voulue et le rend facile à apprendre et à traduire. Par contre, son point fort, et il ne pas transiger sur ce point, est qu'il est écrit en français et que les messages d'erreurs, cohérents et succints, sont aussi écrits en français. Il n'y a pas en G-ALG de «unexpected end of file» quand il manque un guillemet mais bien un message parlant d'une erreur de guillemet. Nombre d'enseignants de mathématiques ne se rendent pas toujours compte de la difficulté à mémoriser la règle des signes quand on a une dizaine d'années. De même, nombre d'enseignants en informatique, au bout de plusieurs années d'utilisation des langages classiques, ne se rendent pas compte que les étudiants ont déjà du mal à choisir le type d'instruction (test en SI ou boucle TANT QUE ?). Alors leur demander d'écrire directement IF ou WHILE est très compliqué. La même remarque s'applique à la syntaxe "évidente" des expressions parenthésées et des combinaisons logiques avec des ET et des OU quand on les pratique depuis une décennie mais qui est en fait incompréhensible quand on débute, sans parler des symboles !&|^, [ ou { que les étudiants n'ont jamais utilisé sur le clavier et du point-virgule dont on ne sait jamais si c'est un séparateur ou un terminateur... Pour vous rendre compte de la difficulté à faire deux choses en même temps, vous pouvez essayer de comprendre pourquoi, en APL le code      +/V÷ρV ← ? 10 ρ50 s'optimise en      (+/V)÷ρV ← ? 10 ρ50 tout en écrivant ce code à l'aide du site TryAPL sachant que le schéma du clavier est ci-dessous...       De même, si, en tant que programmeur R expérimenté, on peut écrire les yeux fermés et sans y penser une expression comme print(cbind( paste("LIGNE",sprintf("%03d",1:nrow(df)),sep="") )) il est clair qu'en initiation cela se révélera catastrophique et qu'il faut sans doute détailler la génération des indices, le formatage des nombres entiers, la concaténation, et donc, écrire, de façon progressive, pour obtenir le même résultat, les instructions qui suivent : nbLignes <- nrow(df) numLignes <- 1:nbLignes idLignesNum <- sprintf("%03d",numLignes) idLignesCar <- paste("LIGNE",idLignesNum,sep="") print( cbind( idLignesCar ) ) Voici ce que cela produit sur un exemple avec les deux codes : [1,] "LIGNE001" [2,] "LIGNE002" [3,] "LIGNE003" [4,] "LIGNE004" [5,] "LIGNE005" [6,] "LIGNE006" On consultera la page VSS concernant les choix retenus dans G-ALG pour avoir un langage simple et lisible. 3. Multiplicité et qualité des solutions en algorithmique Contrairement aux mathématiques, où par exemple l'équation x+1=0 n'admet qu'une seule solution x=-1, il y a toujours une multiplicité de solutions et d'écritures en algorithmique. Ainsi pour garder une copie de la variable NBE, on peut utiliser une variable nommée sauveNBE ou la nommer NBE_copie. De même, l'instruction SI (a<b) ALORS action_1 SINON action_2 FINSI est strictement équivalente à l'instruction SI (b>=a) ALORS action_2 SINON action_1 FINSI pour les cas usuels. Il nous semble qu'enseigner l'algorithmique, c'est-à-dire la résolution informatisée de problèmes au sens large, doit inclure cette réflexion. Ainsi, "la" bonne solution élémentaire au problème «comment trouver le plus petit et le plus grand élément d'une liste (au sens usuel du terme) de valeurs ?» est bien sûr «trier la liste par ordre croissant» car le premier élément est alors le plus petit et le dernier est le plus grand. Une solution avec parcours explicite de la liste est souvent ce qui est demandé par les enseignants, mais ce n'est pas la solution la plus immédiate, au niveau conceptuel. C'est pourquoi le langage algorithmique doit permettre toutes les solutions. Il n'est pas difficile d'imaginer une fonction nommée TRI même si elle est sans doute difficile à écrire si le tri est multi-critères. Qu'un "vrai" langage donné dispose d'une telle fonction et qu'on sache bien l'utiliser (penser par exemple à la difficulté de faire comprendre la transformée schwarzienne en Perl) est un autre problème. Selon nous, faire chercher plusieurs solutions et en discuter les avantages et les inconvénients doit faire très rapidement partie de l'enseignement de l'algorithmique impérative fondamentale car cela développe le sens de l'analyse, de la recherche et de la comparaison de solutions. Le langage G-ALG sert "juste" à formaliser ces solutions. Comment tester alors et valider un algorithme ? La réponse qui s'impose sans doute (pour une fois, soyons modeste !) est de passer par un cahier des charges très précis. Cela signifie notamment qu'il faut nommer les variables à utiliser, fixer parfois les règles du jeu, en interdisant (pas de boucle POUR...), ou en imposant (on utilisera la fonction SOMME()...), afin de guider les apprenant(e)s là où on veut qu'ils ou elles aillent dans la résolution pour que l'ordinateur soit en mesure de vérifier le code. On pourra consulter les exercices dans notre catalogue pour avoir une idée de ce que cela implique comme travail de travail pour l'enseignant. Heureusement pour les enseignant(e)s, tout ne peut pas être testé, validé. Ainsi la qualité des commentaires, leur adéquation avec le code ne sont pas validables, que ce soit dans notre système pédagogique ou via n'importe quel ordinateur parce que cela demande de comprendre la langue écrite, ce qui va bien au-delà d'une vérification d'une égalité de contenus de variables. 4. Extensions naturelles Il est clair pour nous qu'au-delà de l'algorithmique élémentaire, il y a non pas une algorithmique avancée mais des algorithmiques avancées. Selon l'enseignant(e), une fois les bases posées du socle commun, on peut envisager : d'approfondir l'écriture de sous-programmes, fonctions et procédures, puis présenter la récursivité, la complexité, les fonctions anonymes, le passage de paramètres par nom plutôt que par position, la notion d'évènement et de call-back ; d'introduire l'utilisation (et la ré-implémentation ?) des structures de données comme les piles, les files, les queues, les arbres, les graphes ; de se focaliser sur la résolution de problèmes via l'utilisation de bibliothèques de sous-programmes données : sur le site rdocumentation, on accède à plus de 2 millions de fonctions R réparties dans plus de 15 000 "packages", comme les fonctions read.xls(), connectedComponents() ou longestCommonSubsequence() à titre d'exemple qui sont sans doute utiles -- mais difficiles à bien ré-implémenter ; sur le site pypi on trouve plus d'un millions de fichiers répartis sur plus de 130 000 projets Python ; d'insister le traitement de chaines de caractères, les dates et leurs fonctions, les expressions régulières, les conversions, les encodages et l'écriture multilingue ; d'introduction le typage, la représentation en machine, l'indirection, les pointeurs, les tables de hachage, le cryptage ; de présenter la programmation fonctionnelle, la programmation logique, la programmation littérale... Le langage de G-ALG n'a pas pour vocation d'aller aussi loin. Il sert de premier langage, comme les premiers livres de l'enfance. Au-delà, il faut passer au choix difficile du langage réel et de la traduction de l'algorithme dans ce langage, choix souvent escamoté par les enseignants. Ainsi, pour passer de plusieurs fichiers formatés en prénom, nom comme Marie DUPONT Jean Smith Emile zola ... aux fichiers formatés avec le nom en premier, comme DUPONT Marie SMITH Jean ZOLA Zola ... combien d'enseignants d'informatique prennent le temps et font l'effort d'expliquer que le langage AWK est le plus adapté et que C, C++ ou Java, Perl, Python... ne sont pas les bienvenus ici, sauf à titre d'exercice ? 5. Comment enseigner le développement informatique, la programmation et l'algorithmique ? Un(e) mathématicien(ne) qui utilise Maple, un(e) biologiste confrontée à R pour des statistiques élémentaires, un(e) physicien(ne) mettant au point un script Scilab, un développeur Web avec ses programmes Php et Javascript, un(e) bioinformaticien(ne) qui interface du code Python et Perl n'ont pas besoin de pointeurs, de Java ou de C++. Et ce qu'ils/elles font est aussi "noble" qu'un programme d'optimisation ou d'intelligence artificielle. Selon nous, enseigner l'algorithmique doit tenir compte de l'ensemble des langages et de leur quasi-intersection minimale. Le plus important, dans un premier temps, est de montrer comment réfléchir à un problème, comment trouver au moins une solution "à la main", comment la décrire pour pouvoir la coder. C'est pourquoi dire la méthode à utiliser est une étape importante, plus proche de la rédaction littéraire que du codage en assembleur. Si on rédigeait bien la méthode, les ordinateurs seraient capables de programmer d'eux-mêmes la solution, un peu comme en Prolog quand on sait comment rédiger ses connaissances déclaratives. Décrire la méthode en termes de parcours, d'énumérations, de tests... permet de mettre du recul, d'avoir presque un regard extradiégétique sur le problème à résoudre. Dans un second temps, l'entrainement à lire des algorithmes plutôt que d'écrire des algorithmes nous parait souvent sous-estimé. Que font les enfants au CP ? Ils commencent par lire des phrases avant d'en écrire. Pour l'algorithmique, cela devrait être pareil. Demander à un(e) étudiant(e) de dérouler un algorithme ligne par ligne est bien plus formateur qu'on ne le croit au premier abord. Ensuite, faire modifier des algorithmes est aussi très important. Par exemple donner un algorithme qui trouve la première occurrence du maximum et le faire modifier pour qu'il en trouve la dernière occurrence révèle le soin et la précision qu'il faut apporter à la fois à l'algorithme et à sa documentation. Demander à trouver "la" position du maximum se révèle être un problème mal posé quand le maximum est présent plusieurs fois et qu'on résoud "à la main" ce problème. Tester la robustesse d'un algorithme et son exhaustivité est la troisième étape. Il ne faut pas la négliger, car le risque est de fournir une solution partielle, qui ne fonctionnera que dans des cas particuliers, ou pas pour tous les cas. Ouvrir un fichier pour le lire sans avoir vérifié qu'il existe, c'est manquer de bon sens et ni l'algorithmique ni un langage particulier ne peuvent régler ce problème. De même, dans une conversion pouce/cm tester juste si l'unité est "pouce" est incomplet car "pouces" est sans doute acceptable aussi. L'enseignement de l'algorithmique doit donc passer par des exemples variés, à lire d'abord, puis à modifier et à écrire, enfin. Réussir des exercices «courts et naifs» met l'apprenant(e) en confiance, le rassure et le gratifie (merci à la neuropyschologie pour son concept de récompense immédiate). Encore faut-il disposer d'un système de validation plus que de vérification, ce que nous fournissent pas les cours classiques et a fortiori les langages réels. Heureusement, G-ALG est là pour valider... Nous vous encourageons à regarder les premiers exercices de notre catalogue, dans les différents modes et dans les différentes rubriques pour vous convaincre que l'objectif visé n'est pas l'algorithmique en tant que telle mais bien la mise en confiance et la lecture de la syntaxe. Exemples : les bonbons : on pourra vérifier dans l'interface que l'exécution de l'analyse affiche le bon résultat mais que la validation donne un score de 0 %. calcul du périmètre : attention, il n'y a pas d'affichage (et c'est voulu). calcul du prix hors taxe sachant le prix unitaire et le nombre d'articles... Raffiner et optimiser un algorithme est souvent la dernière étape avant le passage à la traduction dans un langage existant de programmation. Cette traduction n'est d'ailleurs pas une mince affaire. Il est bien sûr possible de traduire mot à mot, et c'est ce que permet $GALG mais ce n'est souvent pas une bonne traduction car chaque langage a ses spécificités. Ainsi, permuter le contenu des variables $a et $b en PHP s'écrit "anti-naturellement" list($a,$b) = array($a,$b) ; Aucun cours d'algorithmique, aucun langage algorithmique, aucun dictionnaire de langages ne peut prétendre enseigner cette traduction, pas plus qu'expliquer pourquoi l'expression française un bol de café se traduit en anglais par a cup of tea quand on ne connait pas les usages... Enseigner la programmation en APL, C, Java, CAML, Javascript... requiert de parler des spécificités du langage sous-jacent (absence de mots, présence de pointeurs, style fonctionnel, utilisation d'évènements...) même si le "coeur" du langage fait appel aux mêmes concepts fondamentaux de variables, d'instructions, de boucles, de fonctions... Donc G-ALG ne peut et doit être qu'une étape, importante, certes, mais non suffisante pour enseigner le développement. Par contre, ce qu'il apporte, c'est une syntaxe précise avec la possibilité de vérification, de traduction élémentaire, voire d'exécution pour savoir si la solution trouvée fonctionne... Et les exercices du catalogue fournissent une panoplie d'exercices à résoudre, pour s'entrainer. De plus quand ils ont un modèle de validation, on est assuré que les tests garantissent la robustesse et l'exhaustivité du code. On trouvera plus d'explications sur le mécanisme de validation des algorithmes ici. A l'heure (2018) où l'algorithmique et la programmation commencent à être systématiquement enseignées au lycée, à l'aide de Python notamment, via des interfaces comme AlgoBox il est bon de rappeler qu'aucun langage, qu'aucune interface ne peut imposer toutes les bonnes pratiques telles que : écrire des commentaires intra et extradiégétiques ; initialiser les variables (quand on doit les déclarer) ; indenter le code ; mettre les fins de structure sur des lignes séparées ; décomposer les actions à réaliser ; factoriser du code similaire ; afficher la date, l'heure, savoir calculer une durée entre deux dates (pour prouver qu'un algorithme est plus rapide qu'un autre) ; résoudre "à la main" le problème, quitte à simplifier des étapes. C'est pourquoi G-ALG n'est pas qu'un langage, mais aussi un ensemble d'exercices et de contraintes, comme pour le problème PMG ou l'interface de l'exercice périmètre. De plus la partie Analyse d'un algorithme ouvre le champ libre à tout type de contrainte pour induire la qualité du code. Nous reproduisons ici un exemple d'une telle analyse : Fichier monalgo.lvm issu de galg -a monalgo.alg ================================================= * Liste des variables (par ordre alphabétique) Variable Ligne de première Nombre de utilisation références # nmoins1 14 3 # som2dern 15 2 # som3prem 13 2 # tabVentes 8 2 # tailleTab 7 5 ** Aucune variable de fichier dans cet algorithme. *** Liste des tableaux (par ordre alphabétique) Tableau Dims. Ligne de première Nombre de utilisation références # tabVentes 1 13 5 **** Liste des modules ou fonctions (par ordre alphabétique) Fonction Arité Ligne de première Nombre de utilisation références # afficheTableau 1 17 1 # entierAuHasard 2 7 1 # tableauAuHasard 3 8 1 Il y a peut-être un identificateur en homonymie à savoir : tabVentes Tableau et Variable Fichier monalgo.nbi issu de galg -a monalgo.alg ================================================= 20 ligne(s) en tout 5 ligne(s) commentaire(s) seul(s) 7 ligne(s) vide(s) 8 instruction(s) au niveau 1 0 est le niveau maximal d'imbrication 2 instructions ECRIRE 5 instructions AFFECTER 1 instruction APPELER 0 instruction SI 0 instruction POUR 0 instruction TANT_QUE 0 instruction REPETER 0 instruction FONCTION 0 instruction OUVRIR 0 instruction FERMER 0 instruction LIRE Fichier monalgo.lst issu de galg -a monalgo.alg ================================================= ERR LIG | INS PRO 001 | ## xmp05.alg ; auteur : gH 002 | ## somme des trois premiers éléments d'un tableau 003 | ## et de ses deux derniers éléments 004 | 005 | ## validation-via : premdernv ## 006 | 007 | 001 affecter tailleTab <-- entierAuHasard(5,10) 008 | 002 affecter tabVentes <-- tableauAuHasard(tailleTab,0,20) 009 | 010 | # pour validation : appeler affecteVARSpourVALIDATION() 011 | 012 | 013 | 003 affecter som3prem <-- tabVentes[1] + tabVentes[2] + tabVentes[3] 014 | 004 affecter nmoins1 <-- tailleTab - 1 015 | 005 affecter som2dern <-- tabVentes[nmoins1] + tabVentes[tailleTab] 016 | 017 | 006 appeler afficheTableau(tabVentes) 018 | 019 | 007 ecrire " somme des trois premiers éléments " , som3prem 020 | 008 ecrire " somme des deux derniers éléments " , som2dern On trouvera dans le document galg-vpl.pdf et sur la page galg-vpl.php quelques éléments sur l'intégration de G-ALG dans Moodle à l'aide du plugin VPL.   Code-source de cette page.

 

 

   Retour à la page principale de   (gH)