II.3.4.1 Animation analogique d'algorithmes
L'animation d'algorithmes est un sujet particulièrement étudié dans le domaine de la visualisation de programmes et il est la source de nombreux systèmes existant aujourd'hui. Dans le chapitre IV de ce mémoire, nous comparons notre système avec des systèmes d'animations d'algorithmes existant aujourd'hui. Comme nous le précisons dans cette comparaison, notre critique principale envers ces systèmes et les représentations qu'ils proposent, quelle que soit la manière dont les animations graphiques sont spécifiées, est une sorte de glissement de l'objet fondamental de cette discipline. La recherche de représentations animées illustrant toutes les étapes d'un algorithme est déconsidérée par rapport à des aspects plus techniques comme :
· le moyen d'attacher une représentation ou une animation avec l'implémentation d'un algorithme,
· la construction d'outils sophistiqués permettant de décrire des représentations graphiques.
Comme nous le montrons dans notre critique de ces systèmes, ils aboutissent en général à des systèmes de visualisation des données qui ne se sont pas penchés sur la question de savoir si tous les différents aspects d'un algorithme, toutes les étapes qu'il décrit, sont bien représentés. Souvent, bien au contraire, les visualisations d'algorithmes ne montrent pas leur fonctionnement mais ses effets.
La représentation analogique d'algorithmes que nous allons détailler ici s'attache à montrer les différentes étapes constituant des algorithmes de tris de listes de nombres. Nous proposons une représentation unique, basée sur la conjonction de l'animation de l'évolution de la résolution et de la persistance de son historique. En effet, la plupart des visualisations d'algorithmes de tris proposées aujourd'hui ne prennent en compte que l'un ou l'autre de ces aspects alors qu'une visualisation efficace se doit, selon nous, d'inclure ces deux aspects simultanément. La figure 3.16, que nous expliciterons dans ce chapitre, montre deux vues de la représentation finale du tri par fusion de notre système.
Figure 3.16 Deux vues du tri par fusion
II.3.4.2 Description de la représentation analogique
La représentation analogique que nous avons implémentée pour illustrer le fonctionnement de différents algorithmes de tri se base sur l'utilisation d'histogrammes, représentation communément admise depuis Tufte [Tufte83] comme la plus efficiente pour visualiser des listes de nombres. Afin de visualiser la progression dans la résolution et de présenter son historique dans une même image, nous utilisons les trois dimensions de l'espace suivant le schéma présenté dans la figure 3.17. Le niveau de récursion apparaît du bas vers le haut de la fenêtre de visualisation. Les différentes données sont représentées horizontalement et la hauteur de leur représentation indique leur valeur.
Figure 3.17 Schéma explicatif de l'animation analogique
1 2 3 4
5 6 7 8
(1) appel initial
(2) à (4) appels récursifs
(3) à (8) retour des appels
Figure 3.18 Vues successives de l'animation de la copie d'une liste de quatre nombres
(de copie (l)
(if (null l) nil
(cons (car l) (copie (cdr l)))))
Figure 3.19 Code source de la copie d'une liste
Pour illustrer cette représentation sur un programme simple, la figure 3.18 présente l'application de notre animation sur la copie d'une liste de quatre nombres. Chacune des étapes de la résolution apparaît successivement, permettant une distinction visuelle entre les appels récursifs en entrée de leur sortie ainsi que les valeurs manipulées à chacune des étapes. Nous pouvons déduire de cette animation que le programme de copie de liste construit le résultat final après avoir totalement parcouru la liste et que son implémentation doit ainsi commencer par un appel récursif avec la liste privée de son premier élément puis, lorsque la liste est vide, retourner la concaténation du premier élément avec la copie du reste. De fait, ces déductions visuelles correspondent à l'exécution du programme présenté dans la figure 3.19.
Pour construire cette représentation analogique, notre système Zeugma a joué le rôle d'interface entre les programmes et la construction des représentations graphiques des étapes successives. En effet, nous avons voulu construire une animation générique d'algorithmes pouvant être appliquée à une série de programmes, sans avoir à modifier ni les programmes, ni l'animation, pour l'adapter à telle ou telle implémentation. Le code source de la définition de cette analogie est présenté dans l'annexe I.3 de ce mémoire. Notons néanmoins que cette animation peut être sujet aux mêmes critiques que celles énoncées page 87.
II.3.4.3 Application au tri rapide
Le premier exemple d'application de notre animation analogique à des algorithmes de tri est le tri rapide. L'implémentation de cet algorithme utilisé pour cette animation est présentée dans la figure 3.20. Nous avons choisi de lier l'animation de l'algorithme avec l'accès (en entrée ou en sortie) de la fonction tri_rapide. La figure 3.21 présente le film d'une partie de l'animation et la figure 3.22 deux vues de l'image finale de l'exécution.
; définition du tri rapide
(de tri_rapide (l)
(if l
(append (tri_rapide (partition (car l) (cdr l) 'le))
(cons (car l)
(tri_rapide (partition (car l) (cdr l) '>))))))
; partition d'une liste (lst) par rapport à un pivot (val) et un opérateur (op).
(de partition (val lst op)
(cond
((null lst) nil)
((op val (car lst)) (cons (car lst) (part val (cdr lst) op)))
(t (part val (cdr lst) op))))
Figure 3.20 Code source de l'implémentation du tri rapide
Les différentes étapes de l'algorithme, que notre animation doit mettre en évidence, sont :
1) la construction, à chaque étape, de deux partitions de la liste donnée en argument. La première contiendra les éléments plus petits que le premier élément de la liste et la seconde les éléments plus grands ou égaux à celui-ci.
2) Chaque nouvel appel récursif travaillera sur la partition reçue.
1 2 3 4
5 6 7 8
9 10 11 12
Figure 3.21 Film d'une partie du tri rapide (début)
13
Figure 3.21 Image finale du film d'une partie du tri rapide
Détaillons maintenant le déroulement du film :
· les proportions étant conservées d'un niveau de récursion à l'autre, nous pouvons voir que l'élément présent au troisième niveau de l'étape 3 est plus petit que le premier du second niveau de l'étape 2. De plus, les nouveaux éléments apparaissant à ce même niveau à l'étape 5 sont tous plus grands que ce dernier. Le programme prend visiblement en considération les plus petits éléments avant de traiter les plus grands.
· Les éléments présents dans la partie entrée (droite) du troisième niveau de l'étape 5 désignent les deux partitions des éléments du second niveau. On peut alors distinguer uniquement cinq éléments alors que le niveau précédent en contenait six. Il apparaît visuellement que l'élément manquant est le premier, utilisé comme pivot. Cet élément réapparaît toutefois en sortie du tri (partie gauche) des éléments de ce niveau, à l'étape 13.
· Le positionnement selon l'axe des abscisses, relatif au nombre d'appels récursifs ayant eu lieu à un niveau donné, justifie l'utilité de l'animation par rapport au simple affichage de l'historique complet : elle permet de distinguer la provenance des éléments. Par exemple, sur l'image de l'étape 13, les éléments du quatrième niveau ne sont pas issus des éléments centraux du troisième mais, comme le montrent les étapes 5, 6, 11 et 12, du travail de l'algorithme sur la seconde partition des éléments du deuxième niveau.
· La construction du résultat, une liste de nombres visiblement triée, est effectuée après que la liste argument ait été réduite à un seul élément (visible aux étapes 4 et 8). Puis, par sorties successives, l'élément pivot est placé entre les deux partitions (étapes 9 à 13).
Ainsi, de la combinaison d'une animation et de la persistance de l'historique nous avons pu déduire que :
1) les éléments d'un niveau de récursion sont successivement partitionés en plus petits et plus grands par rapport à l'élément présent en tête,
2) la partition a lieu tant que la liste contient plus d'un élément,
3) la construction de la liste triée est le résultat de la concaténation du tri des éléments plus petits, du pivot et du tri des éléments plus grands.
Cette description correspond bien à la description du tri rapide ainsi qu'à son implémentation.
Ces deux vues de la représentation analogique, présentées dans la figure 3.22, prises à la fin de l'exécution du programme, permettent de distinguer visuellement l'utilisation des trois dimensions dans la construction de la représentation. De plus, le tri de la seconde partition des éléments du premier niveau (absents dans la figure 3.21) illustre bien le fonctionnement de l'algorithme (par le passage du quatrième au cinquième niveau en entrée et en sortie par exemple).
Figure 3.22 Deux vues de l'image finale du tri rapide
II.3.4.4 Application au tri par fusion
Le second tri pris en exemple est le tri par fusion. L'intérêt de ce choix réside dans le fait que cet algorithme n'est en soi pas très différent du tri rapide. L'implémentation utilisée est présentée dans la figure 3.23, une partie du film de son exécution dans la figure 3.24 et la figure 3.16 présente deux vues de l'image finale de son exécution.
; définition du tri par fusion
(defun tri_fusion (l)
(if (null (cdr l)) l
(let (l1 (separe l)) ; l1 contiendra les deux parties de la séparation de l
(fusion (tri_fusion (car l1))
(tri_fusion (cdr l1))))))
; construit la séparation en deux listes égales d'une liste l
(defun separe (l l1 l2)
(if (null l) (cons l1 l2)
(separe1 (cdr l) (cons (car l) l1) l2)))
(defun separe1 (l l1 l2)
(if (null l) (cons l1 l2)
(separe (cdr l) l1 (cons (car l) l2))))
; fusionne, de manière ordonnée, deux listes
(defun fusion (l1 l2)
(cond
((or (null l1) (null l2)) (or l1 l2))
((< (car l1) (car l2)) (cons (car l1) (fusion (cdr l1) l2)))
(t (cons (car l2) (fusion l1 (cdr l2))))))
Figure 3.23 Code source du tri par fusion
De la même manière que pour le tri rapide, voyons si notre visualisation permet de comprendre l'algorithme sous-jacent au tri par fusion.
1 2 3
Figure 3.24 Partie du film du tri par fusion (début)
4 5 6
7 8 9
10 11 12
13 14 15
Figure 3.25 Suite du film du tri par fusion
16 17 18
19 20 21
22 23 24
Figure 3.25 Fin du film du tri par fusion
En remarque préalable à l'examen de ce film de l'animation du tri par fusion, on peut remarquer que, même s'il fonctionne en apparence comme le tri rapide vu précédemment (chaque niveau de récursion effectue une partition sur les éléments manipulés par le niveau inférieur), le nombre d'étapes nécessaires pour aboutir au même résultat (le tri de la moitié de la liste de départ) est nettement plus important que pour le tri rapide (24 par rapport à 13). Examinons ce que nous pouvons déduire visuellement de ce film :
· Puisque, comme dans le tri rapide, une partition est effectuée sur la liste de nombres triée, voyons si la représentation graphique animée nous donne des indications par rapport au moyen mis en _uvre pour effectuer cette partition. L'image numéro 2, par exemple, semble montrer que la partition ne s'effectue pas selon un critère lié à une valeur particulière mais par rapport à la position dans la liste : le dernier élément de la liste du second niveau est visiblement le premier de la liste du premier niveau. De plus, l'élément qui le précède ne semble pas suivre le premier du premier niveau mais se trouve être en troisième position. Ceci est confirmé par la présence, dans l'image 24, du même nombre d'éléments au premier niveau et au second : les éléments sont pris à raison d'un sur deux et, de plus, transmis en ordre inverse. Cette inversion apparaît également dans le passage du troisième au quatrième niveau des images 3 et 4, alors que l'image 10 illustre, pour ce même passage de niveau, la prise en compte d'un élément sur deux dans la partition des listes.
· Le second point est la construction du résultat : de la liste triée. Dans le cas où l'une des listes ne contiendrait qu'un élément, la construction du résultat semble être effectuée par simple concaténation (par exemple, le résultat construit dans l'image 12 est visiblement la concaténation des éléments du niveau supérieur de l'image 11). Dans le cas où les listes en jeu dans la construction du résultat contiendraient plus d'un élément, comme dans la construction du résultat de l'image 23, il semblerait que la concaténation soit intelligente dans le sens où les listes ne sont pas seulement mises bout à bout : la liste finale place à la bonne position les éléments des deux listes.
Les éléments déduits de l'observation du film de l'animation illustrent bien les points suivants de l'algorithme de tri par fusion :
1) le tri commence par deux appels récursifs97 avec chacun la moitié des éléments de la liste donnée en argument. Ces deux listes sont construites98 en prenant en compte un élément sur deux et en construisant des listes inversées par rapport à la liste originale.
2) La liste triée est le résultat d'une fusion99 ordonnée du résultat de ces appels récursifs.
Par contre, le point que cette représentation semble décrire de manière moins détaillée est le processus en jeu dans la fusion des listes afin de construire le résultat. Ceci est dû au fait que cette animation se base sur l'entrée et la sortie de la fonction tri_fusion du programme et qu'il faudrait s'attacher à visualiser le comportement de la fonction fusion, responsable de la fusion des listes, afin de voir clairement le processus alors en jeu. Mais, même avec la visualisation présentée, il est possible de déduire une concaténation prenant en compte chaque élément présent dans les listes, ce qui est synonyme de fusion.
II.3.4.5 Application au tri par insertion
; définition du tri par insertion
(defun tris_ins (l)
(if (null l) nil
(insert (car l) (tris_ins (cdr l)))))
; définition de l'insertion d'un élément à la bonne place dans une liste ordonnée.
(defun insert (e l)
(cond
((null l) [e])
((< e (car l)) (cons e l))
(t (cons (car l) (insert e (cdr l))))))
Figure 3.26 Code source du tri par insertion
Le dernier algorithme de tri présenté ici est le tri par insertion. Le code source de l'implémentation étudiée est présenté dans la figure 3.26 et une partie du film de l'animation dans la figure 3.27.
1 2 3
4 5 6
Figure 3.27 Film du tri par insertion
7 8 9
10 11 12
13 14 15
16 17 18
Figure 3.27 Film du tri par insertion (suite)
18 20 21
22 23 24
Figure 3.27 Film du tri par insertion (fin)
Il est important de noter ici que notre visualisation s'attache à illustrer le mécanisme en jeu dans l'insertion d'un élément à la bonne place mais, comme nous allons le montrer, elle permet également de visualiser la totalité de l'algorithme du tri par insertion. Examinons maintenant le film de l'animation construit par notre système. La fonction de l'implémentation à laquelle est attachée cette représentation est la fonction insert.
La première remarque visuelle est la présence, dans les données en entrée du programme, d'éléments de couleurs différentes. Ainsi, outre les éléments noirs déjà présents dans les exemples de visualisation des algorithmes de tri rapide et de tri par fusion, des éléments rouges et des éléments verts apparaissent dans la partie droite (correspondant à l'entrée) de l'animation.
Trois couples d'images nous donnent des indications par rapport à la signification des éléments de couleur rouge : ce sont les couples d'images 1 - 2, 7 - 8 et 19 - 20. Dans le couple 1 - 2, l'élément rouge, présent dans la partie entrée, disparaît dans la construction du résultat : il n'est pas pris en compte. On en déduit alors que cette couleur désigne des éléments neutres, sans valeur. Le couple 7 - 8 arrive après deux niveaux de récursion, les éléments verts à droite de chaque niveau ont successivement disparu et à leur place est apparu un élément rouge n'existant pas auparavant. Cette couleur semble ainsi désigner un élément présent une fois que les autres ont disparu, indiquant alors un espace vide. Cette dernière remarque s'applique également au couple 19 - 20, apparaissant, quant à lui après cinq niveaux de récursion.
Les éléments de couleur verte, comme ceux de couleur rouge, ne sont pas toujours présents en entrée du programme, contrairement aux éléments de couleur noire. De plus, dans toutes les images de l'animation, les éléments de couleur noire et rouge sont toujours isolés alors que les éléments de couleur verte peuvent constituer des groupes, visiblement toujours ordonnés. On peut aussi remarquer que les éléments verts qui apparaissent au premier niveau de récursion sont la copie conforme des éléments de sortie du même niveau à l'étape précédant leur apparition (cf. couples d'images 2 - 3, 4 - 5, 10 - 11 et 14 - 15).
Les éléments de couleur noire, toujours présents et isolés en entrée comme nous l'avons déjà remarqué, se retrouvent également toujours présents en sortie, dans le résultat. Ceci montre que ces éléments sont destinés à être ajoutés, dans la construction du résultat, à l'élément de couleur différente qui les accompagne. Par conséquent, le programme visualisé semble travailler avec deux données : une, de couleur noire, désignant un élément à placer dans l'autre, de couleur rouge ou verte.
Le placement des éléments de couleur noire dans ceux de couleur rouge ou verte semble alors suivre la démarche suivante :
· Si l'élément de droite est rouge, le résultat consiste en l'élément noir (à placer).
· Si l'élément de droite est vert, le programme progresse par appels récursifs successifs jusqu'au moment où le premier élément vert est plus grand que l'élément à placer, le résultat apparaissant alors à l'étape suivante (cf. couples d'images 3 - 4 et 12 - 13). Si cela n'arrive pas (l'élément noir est plus grand que tous les éléments verts), un élément rouge apparaît alors, ce que nous avons déjà remarqué.
On peut déduire des observations précédentes que le programme fonctionne comme suit :
1) Le programme trie une série d'éléments qui apparaissent successivement de couleur noire au premier niveau de récursion,
2) Les éléments sont placés, les uns après les autres, dans le résultat du tri des précédents,
3) Le placement des éléments s'effectue par la recherche de la bonne place dans les éléments déjà triés, par progression successive avec comparaison entre l'élément à placer et le premier élément de la liste où le placer.
Les deux premières étapes déduites de l'observation concernent des appels successifs au programme visualisé. Il apparaît ainsi que ce programme est une partie d'un autre programme qui l'utilise pour placer des éléments dans une liste de nombres. De fait, cet autre programme, que nous pouvons désigner comme méta-programme, fait appel au programme visualisé en conservant la valeur qu'il retourne puisqu'elle est présente à l'appel suivant. On peut alors déduire que la liste triée, à l'extrême gauche du premier niveau de l'image 24, est composée de tous les éléments noirs de la droite de ce même niveau. Sans autre information sur ce méta-programme, trois conjectures sont alors possibles :
1) il reçoit les données d'un autre programme et construit une liste triée au fur et à mesure en partant d'une liste vide100,
2) il parcourt une liste de nombres et construit à chaque étape une liste d'éléments triée (s'il fonctionne avec deux variables),
3) il parcourt la liste de nombres à trier jusqu'à la fin puis place successivement les éléments (du dernier au premier) à la bonne place (s'il fonctionne par construction en retour d'appel récursif comme les algorithmes déjà présentés).
En conclusion, les observations visuelles de cette animation nous ont permis de déduire le fonctionnement du programme insert présenté dans la figure 3.26 mais aussi de conjecturer le fonctionnement du programme tri_insert présenté dans la même figure. En effet, la première conjecture, si la visualisation est replacée dans le contexte de l'animation d'algorithmes de tri, perd alors de sa substance.
II.3.4.6 Conclusion
Notre animation analogique d'algorithmes de tris de listes de nombres, tout en se basant sur des éléments graphiques simples et communément utilisés pour ce type de visualisation, permet d'en déduire le fonctionnement par simple observation visuelle. La différence principale entre notre représentation analogique et celles que l'on trouve habituellement dans la littérature est la cohabitation des opérations effectuées sur les données avec la progression dans la résolution. De plus, il apparaît clairement que la persistance visuelle de ces informations est l'élément déterminant dans l'étude visuelle des animations. Dans notre critique par rapport aux autres systèmes de visualisation d'algorithmes présentée dans le chapitre IV de ce mémoire, nous insistons sur le fait que les visualisations proposées ne permettent pas de déduire toutes les étapes présentes dans les algorithmes de tri.
Notre visualisation, même si elle n'a pas été construite pour un algorithme précis, peut en fait s'appliquer à tout programme de manipulation de listes de nombres. Elle apporte l'élément manquant à une analyse visuelle complète du fonctionnement des algorithmes : un historique animé des différentes étapes aboutissant à la construction du résultat. De fait, ces éléments, appartiennent plus au fonctionnement des programmes qu'à la description habituelle des algorithmes. Ils peuvent être comparés à une trace graphique, et permettent de capturer la partie essentielle des algorithmes sous-jacents aux programmes représentés. C'est ce point qui illustre la partie analogique de la représentation : elle relie effectivement les différents points de l'exécution d'un programme de manipulation de listes de nombres à des objets graphiques, des choix de couleur, des animations et des dispositions spatiales dont la combinaison permet de déduire un comportement sous-jacent au programme.
Nous allons maintenant présenter notre système Zeugma, basé sur notre méthode de construction des représentations analogiques de programmes, avec lequel ont été construites toutes les représentations analogiques présentées dans ce chapitre.
97 Par la fonction lisp tri_fusion de l'implémentation présentée à la figure 3.24.
98 Par la fonction lisp separe.
99 Par la fonction lisp fusion.
100 Peut-être en utilisant des socket ou tout autre mécanisme de communication inter-processus, ou bien en conservant la liste des données triées dans une variable globale et en y plaçant des données...
This Web page was created using a Trial Version of Transit Central Station 3.2.