Le tri systolique
Les
documents disponibles sur cette page ainsi que le contenu de la page
sont mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International 
Notions abordées :
Cette activité présente un algorithme de tri original, qui va plus vite que tous les algorithmes de tris classiques et qui de fait peut être testé avec de grands groupes. On aborde la notion d'algorithme au travers d'un exemple particulier, qui implique tous les participants, (presque) quelle que soit la taille du groupe (testé à plus de 60 personnes). Dans un deuxième temps on peut réfléchir à la correction de l'algorithme (pourquoi il marche) mais également à sa complexité (en combien de temps/d'étapes il termine).
Public :
Dans un algorithme de tri l'opération incontournable est la comparaison de deux valeurs. C'est à peu près tout ce qu'on exige. L'application de l'algorithme peut donc se faire dès le plus jeune âge. Pour la partie prise de recul, surtout le temps d'exécution de l'algorithme, il vaut mieux attendre la fin de primaire.
Cette activité a été conçue pour pouvoir être abordée dès le primaire voire la fin de maternelle. Elle a été testée avec des lycéens et avec un public non scientifique. La tester sur des "petits" est parmi les projets.
Matériel :
Pour cette activité, le matériel nécessaire est très limité. Il suffit d'avoir des "machins" pour lesquels on sait définir un ordre. En fonction de l'âge cela peut être :- des cartes avec des nombres écrits dessus
- des cartes avec des points (en nombre différent d'une carte à l'autre) dessinés dessus
- des objets à trier par poids croissant
- des mots à trier par ordre alphabétique
- des événements historiques à trier par date
- ... et plus selon votre imagination
Principe :
Cette activité consiste à mettre en oeuvre un algorithme de tri, en impliquant les participants. Elle peut se faire avec des groupes de taille variée, mais est moins impressionnante si le nombre de participants est petit (par exemple inférieur à 8-10). Pour commencer on met les participants en file indienne et on donne à chacun une valeur, puis on suit l'algorithme :
- La personne en tête de la file avance d'un pas (et tout le monde derrière elle aussi) puis fait demi tour pour faire face à la personne qui était derrière elle,
- elle compare sa valeur avec celle de la personne à présent en face d'elle, et échange si elle n'avait pas déjà la plus grande des deux,
- puis elle avance encore d'un pas et compare/échange si besoin avec la personne suivante,
- dès qu'une personne se trouve en tête de file elle va avancer d'un pas puis faire elle-même demi tour pour comparer sa valeur avec les autres, et prendre la plus grande valeur le cas échéant,
- une fois qu'une personne, après avoir comparé sa valeur avec les autres, se retrouve en fin de file, elle se met à l'arrière de la file mais cache sa valeur dans son dos et ne la montre plus à personne,
- et quand tout le monde est passé par la fin de la file, l'algorithme est terminé.
Et là si tout va bien toutes les valeurs sont triées, de la plus grande en tête de file à la plus petite en queue de file.
Et pourquoi systolique ? cela vient de la biologie, car au fil des comparaisons les valeurs circulent, ici dans une file (dans des tableaux systoliques sur les liens trouvés sur internet), un peu comme le flux du sang dans le coeur (systole = contraction des chambres du coeur).
Extensions :
Toutes intéressantes mais à faire toutes ou sélectionner en fonction du public/du temps :
- Correction : comment justifie-t-on qu'après l'exécution de l'algorithme les valeurs sont bien triées ? Pour le faire on va d'abord prouver que la première personne de la file va avoir la plus grande valeur. On peut ensuite réfléchir au cas de la deuxième personne et ainsi de suite
- Complexité : combien de comparaisons fait-on avec cet algorithme ? (en pratique si on a n personnes la première fait n-1 comparaisons, la deuxième n-2... et la dernière 0) Et si une étape consiste à ce que chacun-e avance d'un pas puis compare sa valeur avec celle de la personne en face, combien d'étapes cela prend-il ? (en pratique le premier se compare avec les n-1 autres (pendant que tout le monde le suit chacun son tour) et quand le premier arrive à la fin le dernier commence à se comparer (avant il attendait l'arrivée du premier) et il va se comparer encore avec n-2 personnes (qui vont lui voler sa valeur si elle est grande). Une fois que le dernier arrive en tête de file tous les autres ont fini, et personne ne va lui montrer sa valeur, donc plus de comparaisons. Au final on aura n-1 + n-2 étapes, soit environ 2 fois n. Et c'est vraiment *très* rapide, bien plus que les algorithmes de tri habituel, mais rendu possible uniquement parce que chaque porteur de valeur est capable de calculer, et que donc à un moment on a toutes les valeurs qui sont comparées en même temps, deux à deux. En pratique dans un ordinateur classique, même s'il fait du parallélisme, on a un nombre maximum de calculs qu'on peut faire en même temps. Il ne pourra donc pas faire 5000 comparaisons en même temps s'il a 10 000 valeurs, et 500 000 d'un coup s'il a 1000 000 de valeurs. C'est donc un modèle bien particulier qui marche mieux en débranché que dans un ordinateur.
- Essayer des variantes de l'algo, par exemple prendre la plus petite valeur au lieu de la plus grande valeur, avancer de deux personnes (au lieu d'une) entre deux comparaisons,...
Liens :
- Une vidéo de l'activité en situation de spectacle a été réalisée lors du concours Jeux Fabrique, et est accessible ici (de 35:15 à 48:50)
Photos :
Cette activité a été beaucoup moins testée que d'autres et je ne dispose pas de photos pour le moment.