Activité (déconnectée) – Initiation aux algorithmes de tri

Dans cette activité, les participant.e.s vont d’abord se trier pour expérimenter différents algorithmes de tri. Puis, ielles vont exécuter un algorithme de tri coopératif, en suivant un réseau de tri tracé au sol.

Dessiner le parcours au sol (à l’aide d’une craie ou de scotch) :

Variantes :

Si vous souhaitez utiliser des nombres dans la seconde phase, prévoyez d’imprimer ou d’écrire un nombre par participant.e.s. Pour éviter les ambiguïtés, chaque nombre ne doit être utilisé qu’une seule fois.

Expliquer aux participant.e.s le contexte suivant :

Dans le monde de l’informatique, on aime ne pas avoir à dire aux ordinateurs tout ce qu’ils ont à faire. On aimerait par exemple donner une fois la recette des crêpes à un ordinateur et qu’il puisse ensuite en faire des milliards. Ces « recettes » sont appelées des algorithmes. Parmi les algorithmes les plus célèbres, il existe les algorithmes de tri.
Le problème est tout bête : par exemple, j’ai une série d’objets que je souhaite ranger par taille.

Dire aux participant.e.s de se mettre en file dans le désordre, sauf une personne choisie au hasard, qui va être la « trieuse ». Choisir ensemble un critère de tri (âge, taille, couleur du t-shirt,… le plus simple étant la taille), et un ordre (croissant ou décroissant), puis demander à la trieuse de mettre les participant.e.s dans l’ordre (en indiquant à telle personne de se mettre avant telle autre, et ainsi de suite).

Demander à la trieuse d’expliquer comment elle a réalisé son tri (il n’y a pas besoin d’être précis, il faut juste mettre en avant que c’est une façon de trier). Demander au groupe si quelqu’un a une idée d’une autre façon de faire. Si oui, cette personne devient la trieuse ; le groupe se remélange et on refait un tri.

Si personne n’a d’idée, faire vous-même la trieuse, par exemple en triant d’un bout à l’autre (tri à bulle) : comparer les deux premières personnes, les permuter si nécessaire, puis comparer la 2è et la 3è personne, les permuter si nécessaire, et ainsi de suite jusqu’à la fin de la file, puis recommencer du début, jusqu’à ce que toute la file soit triée.

Demander au groupe de comparer les deux méthodes de tri : est-ce qu’une a l’air meilleure que l’autre ? Pourquoi ? Mettre en avant que l’intérêt principal, c’est le temps que ça prend de trier : plus vite on va, mieux c’est. Mais qu’est-ce qui détermine le temps que ça prend ? Le nombre de comparaisons (de calcul) qui est fait, la situation de départ (plus il y a de désordre, plus on prendra de temps), et le nombre de choses à trier (plus il y a d’éléments, plus on prendra du temps).

Expliquer qu’il existe de nombreuses manières de trier des objets. Toutes n’ont pas la même efficacité, puisque certaines vont demander plus de calculs. Donner l’exemple du tri par sélection : on prend l’objet le plus petit, on le met en premier puis on recommence. Mais lorsqu’on commence à classer un nombre important d’objets, ce tri n’est plus efficace.

Demander aux participant.e.s ce qu’est pour eux un « nombre élevé d’objets ». Plusieurs milliards, il faut trouver des méthodes plus efficaces.

L’une de ces méthodes est la coopération. Le principe est simple si une classe entière fait cuire des crêpes, elle ira beaucoup plus vite que si un enfant doit faire cuire des crêpes pour tout le monde.

Nous allons faire un jeu pour illustrer cette idée.

1. Répartir les participant-es en groupes de 6 personnes, un groupe à la fois utilise le réseau dessiné au sol.

2. Chaque membre du groupe choisit une carte et se place au hasard sur l’une des 6 cases de départ.

3. Ensuite chacun part en suivant la ligne, arrivé au niveau d’un cercle, l’enfant attend qu’un camarade arrive.

4. Lorsque les deux sont sur le cercle, ils comparent les nombres qu’ils ont, celui qui a le plus petit prend le chemin de gauche, l’autre le chemin de droite.

5. On continue jusqu’à ce que l’on arrive de l’autre côté.

Faire remarquer aux enfants qu’ils sont maintenant classés. Demander combien de calculs (comparaison) étaient effectués simultanément à chaque fois.

Réponse : 3. Faire remarquer que si un enfant avait dû faire toutes les comparaisons, il aurait mis beaucoup plus de temps (et se serait senti très seul…).

Il faut conclure sur l’intérêt du réseau de tri. Les participant.e.s ont déjà normalement pu réaliser qu’il était plus rapide qu’un tri normal mais il utilise également davantage de ressources (par exemple ici 3 « ordinateurs »). Bien évidemment, il faut un grand nombre de données à traiter. Essayer de trouver d’autres exemples ou le fait de faire des actions en parallèle est plus efficace. (Exemples : trier des livres, porter des courses. Exemples tirés de la science pour montrer l’importance : Facebook et la taille des bases de données, ils ont plusieurs milliards d’utilisateurs avec beaucoup d’infos : nom, prénom, âge, ville, occupation et doivent traiter les données, eux aussi utilisent de la programmation en parallèle pour ça…).

En fonction du public vous pouvez continuer :

En fait aujourd’hui, les scientifiques utilisent énormément cette technique car les objets que l’on traite sont devenus gigantesques. En effet, avec la révolution numérique la quantité de données à disposition du public a explosé. Les scientifiques et les industriels en particulier doivent traiter plus de données que jamais. La « Big Data » est là pour traiter ce problème. Elle consiste à réduire la quantité d’informations et à la synthétiser, ce qui est très intéressant c’est que le concept qui se cache derrière est la programmation en parallèle. On découpe les données entre un grand nombre d’ordinateurs où chacun traite une partie des données. Elles sont ensuite réunies.

Conseil médiation 

Pour aller plus plus loin sur le sujet, nous vous conseillons de vous référer à la fiche outil « Algorithmes et langages de programmation«