Des vidéos d’algorithmes qui montrent le code s’exécuter pour de vrai
Ce qui fait qu’une animation d’algorithme enseigne : des étapes exactes, le code éclairé près de l’image, une petite entrée suivie, une question. Les preuves.
Par l’équipe Chasca 6 min de lecture
Une animation d’algorithme enseigne quand chaque étape à l’écran est exacte, quand le code est montré à côté de l’image pendant qu’il s’exécute, et quand on invite le spectateur à réfléchir à l’étape suivante au lieu de seulement regarder. La recherche sur la visualisation d’algorithmes depuis les années 1990 va dans le même sens : l’image compte moins que l’attention avec laquelle le spectateur la suit, et un petit exemple complet vaut mieux qu’un grand exemple dont on saute des étapes.
Les animations d’algorithmes aident-elles les élèves à apprendre ?
Elles le peuvent, à une condition. La méta-étude sur l’efficacité de la visualisation d’algorithmes de Christopher Hundhausen, Sarah Douglas et John Stasko a passé en revue 24 études expérimentales et montré que ce que les apprenants faisaient d’une visualisation prédisait son succès mieux que son apparence : les études fondées sur des apprenants qui déroulaient activement l’algorithme obtenaient les meilleurs résultats.
Un groupe de travail mené par Thomas Naps en a tiré une taxonomie de l’engagement : ne pas regarder, regarder, répondre (dire ce qui va se passer), modifier (essayer d’autres entrées), construire et présenter. Quand Scott Grissom, Myles McNally et Thomas Naps ont comparé ces niveaux sur des algorithmes de tri simples, l’apprentissage progressait à mesure que les élèves passaient de la simple observation à la réponse et à la modification.
Une vidéo se regarde, elle commence donc au niveau « regarder ». Elle peut quand même poser des questions : une bonne explication s’arrête avant une étape, demande quel nombre bouge ensuite, puis montre la réponse. Et une vidéo faite avec l’entrée du spectateur, ou celle de ses devoirs, le rapproche du niveau « modifier ».
Pourquoi chaque étape doit-elle être exacte ?
Parce qu’un algorithme, ce sont ses étapes. Un échange au mauvais endroit, ou un pointeur décalé d’une case, enseigne un autre algorithme, et l’élève qui apprend avec lui reporte l’erreur dans son propre code. Les animations faites à la main sont dessinées étape par étape, si bien que même les meilleures sautent des passages (« on laisse la récursion faire le reste ») et ne montrent que l’exécution que leur auteur a eu le temps de dessiner.
Quand Clifford Shaffer et ses collègues ont dressé l’état des lieux dans Algorithm Visualization: The State of the Field, ils ont trouvé des centaines de visualisations, inégalement réparties entre les sujets et de qualité variable. Un enseignant qui en cherche une juste, complète et dans la langue de ses élèves n’en trouve souvent aucune.
La solution est d’exécuter l’algorithme. Une vraie exécution ne peut ni sauter une étape ni en inventer une : l’image, la ligne éclairée et les variables viennent toutes de ce que le code a réellement fait.
Pourquoi montrer le code à côté de l’image ?
Parce que le code est ce que les élèves écrivent, déboguent et ce sur quoi on les interroge en entretien et en examen. La visualisation de programmes, qui montre l’état d’un programme pendant qu’il s’exécute ligne par ligne, est une manière d’enseigner bien établie : la revue des systèmes de visualisation de programmes de Juha Sorva, Ville Karavirta et Lauri Malmi en couvre des dizaines, et l’Online Python Tutor de Philip Guo a fait connaître l’idée à un très large public.
Une vidéo d’algorithme réunit les deux : la structure de données en image, le code pendant qu’il s’exécute et les variables entre les deux. Quand la ligne 11 s’éclaire au moment où 6 et 5 sont comparés, l’élève voit ce que fait if a[j] <= pivot au lieu de seulement le lire.
De quoi une bonne explication d’algorithme a-t-elle besoin ?
Nous avons étudié 16 des explications d’algorithmes les plus regardées sur YouTube, du tri et de la recherche dichotomique jusqu’à Dijkstra et la programmation dynamique. Les meilleures partagent une grammaire :
- Une question, puis une règle. Elles commencent par une question ou une image du quotidien (des villes et des routes, une étagère de livres), puis donnent la seule idée à garder en tête pendant l’exécution : « tout ce qui est à gauche de i est au plus le pivot ».
- Une petite entrée, suivie pas à pas. La vidéo médiane consacre environ la moitié de son temps à exécuter un exemple, en général de 6 à 11 valeurs ou de 7 à 13 nœuds.
- La structure d’appoint à côté de l’image. Une file ou une pile dessinée à côté du graphe, une ligne de mémoïsation à côté de la récursion.
- Peu de couleurs, expliquées une fois. L’élément courant d’une couleur, les éléments terminés d’une autre, les pointeurs en courtes flèches nommées.
- L’étape clé au ralenti. Les premières étapes une à une, puis plus vite, puis de nouveau lentement là où c’est important.
- Une vérification et une limite. Le résultat vérifié par rapport à la règle, et une limite nommée honnêtement (un pire cas, des poids négatifs).
- Le grand O en une ligne, avec des nombres. Rares sont celles qui comptent les comparaisons de leur propre exécution, ce qui rend la croissance visible.
Ce qu’aucune des 16 ne faisait : faire avancer le code et l’image ensemble pendant toute l’exécution, montrer un panneau des variables ou être narrée dans une autre langue que l’anglais.
Comment en créer une avec Chasca ?
La compétence Algorithmes visuels (Algorithm visuals) de Chasca crée toute la vidéo à partir d’une phrase :
- Nommez l’algorithme. Ouvrez Create, choisissez la compétence « Algorithm visuals » et tapez ce qu’il faut expliquer, par exemple « les plus courts chemins de Dijkstra depuis le nœud 0, en Java » ou « recherche dichotomique de 23 dans 2, 5, 8, 12, 16, 23, 38 ». Donnez vos propres données si vous le souhaitez ; elles restent assez petites pour être suivies à l’écran.
- Choisissez le langage du code. Python, Java, C++ ou JavaScript, dans le réglage Code de la compétence ou dans votre demande. Choisissez un aspect sombre ou clair, le narrateur et la langue de la vidéo.
- Recevez la vidéo. L’algorithme est exécuté sur vos données, et la narration est écrite d’après cette exécution : d’abord une question, l’entrée et la règle, l’exécution suivie avec le code éclairé ligne par ligne et les variables sous les yeux, l’étape clé au ralenti, le résultat vérifié, puis une courbe de la façon dont le travail augmente, avec le compte de cette exécution dessus.
La bibliothèque couvre le tri, la recherche, les deux pointeurs et les fenêtres glissantes, les chaînes de caractères, les piles et les files, les tables de hachage, les listes chaînées, les arbres, les tas, les graphes, la récursion et la programmation dynamique. Pour la comparer à Manim, Motion Canvas et aux enregistreurs d’écran, voyez les meilleurs outils pour créer des vidéos de visualisation d’algorithmes.
Sources
- Hundhausen, C. D., Douglas, S. A., and Stasko, J. T. (2002). A meta-study of algorithm visualization effectiveness. Journal of Visual Languages and Computing, 13(3), 259–290.
- Naps, T. L., et al. (2002). Exploring the role of visualization and engagement in computer science education. ACM SIGCSE Bulletin, 35(2), 131–152.
- Grissom, S., McNally, M. F., and Naps, T. (2003). Algorithm visualization in CS education: comparing levels of student engagement. Proceedings of SoftVis 2003, 87–94.
- Shaffer, C. A., et al. (2010). Algorithm visualization: the state of the field. ACM Transactions on Computing Education, 10(3).
- Sorva, J., Karavirta, V., and Malmi, L. (2013). A review of generic program visualization systems for introductory programming education. ACM Transactions on Computing Education, 13(4).
- Guo, P. J. (2013). Online Python Tutor: embeddable web-based program visualization for CS education. Proceedings of SIGCSE 2013, 579–584.
Transcription de la vidéo Ce que dit le narrateur dans la vidéo explicative de 1:05 ci-dessus.
How can you sort these numbers without repeatedly finding the smallest?
These 7 numbers need sorting. Through i, values stay at most the pivot. Orange marks executing code; green means done.
Line 8 picks pivot 5. Line 11 leaves 8 right because it exceeds 5.
3 belongs left. Which number will it swap with?
3 swaps with 8; 1 and 2 also move left because neither exceeds 5.
5 lands between the sides, permanently placed.
Recursion partitions the left around 2; single numbers need no sorting.
8 separates 6 and 9; the pivot rule now holds everywhere. Worst-case work is quadratic.
The chart marks 10 comparisons for 7 numbers; average work grows as n log n.
Partition, then sort each side: that's how you order the numbers.
Questions fréquentes
Elles le peuvent, et ce que les élèves font pendant qu’ils regardent compte le plus. Une méta-étude de 24 expériences a montré que la façon dont les apprenants s’engagent avec une visualisation d’algorithme prédit son succès mieux que ce qu’elle montre, et une étude ultérieure a vu l’apprentissage progresser quand les élèves passaient de la simple observation à des réponses à des questions sur l’animation.
Parce que le code est ce que les élèves écrivent et ce sur quoi portent les entretiens et les examens. Voir la ligne qui s’exécute à côté du changement qu’elle produit relie les deux ; des outils de visualisation de programmes comme Python Tutor reposent sur cette idée.
Assez petite pour suivre chaque étape : les explications d’algorithmes les plus regardées suivent des tableaux de 6 à 11 valeurs (8 en général) et des graphes de 7 à 13 nœuds, et consacrent environ la moitié de la vidéo à cette seule exécution.
La compétence Algorithmes visuels de Chasca en crée une à partir d’une phrase comme « tri rapide sur 8, 3, 6, 1, 9, 2, 5 en Java » : elle exécute l’algorithme sur ces données et le raconte pas à pas, le code éclairé ligne par ligne à côté de l’image, en Python, Java, C++ ou JavaScript.
Oui. La compétence Algorithmes visuels narre dans n’importe laquelle des 79 langues de Chasca ; le code et les noms de ses variables restent tels que le langage de programmation les écrit.