Objectifs

Cette activité illustre la partie exécution de l'algorithme. En suivant l'algorithme de réseau de tri donné, comme une machine, les élèves vont pouvoir trier des nombres. De plus, la notion de parallélisme des tâches leur sera introduite.

Mise en place

L'activité se déroule en extérieur, le réseau de tri étant tracé sur le sol. Cette dernière peut être transformée pour être réalisée en intérieur, en traçant le réseau de tri au tableau ou sur une feuille de papier.

Cette activité est inspirée de l'activité "La course contre la montre" ("Beat the Clock") de cs-unplugged que vous pouvez retrouver à l'adresse: http://csunplugged.org/sorting-networks. Pour plus de renseignements sur cs-unplugged, voir: http://csunplugged.org/.

Explications

Comme expliqué dans l'introduction, les algorithmes sont une séquence d'instructions qui sont réalisées dans le but d'obtenir un résultat (qui peut être la résolution d'un problème). Cependant, il est à noter que l'on peut suivre, c'est à dire exécuter, cette suite d'instructions de plusieurs manières.

• De manière séquentielle: la manière la plus simple et intuitive... On réalise la première instruction, puis la deuxième quand la première est terminée, puis la troisième quand la deuxième est terminée, et ainsi de suite. C'est ce que l'on fait le plus souvent dans une recette de cuisine.
• De manière parallèle: une manière moins intuitive, mais souvent plus efficace. Le principe, ici, est de réaliser plusieurs instructions EN MEME TEMPS. En effet, certaines instructions ne sont pas dépendantes d'autres, et peuvent donc se faire simultanément. Reprenons l'exemple de la recette de cuisine, imaginez que vous devez mettre un plat dans le four, et préparer un oeuf sur le plat. Ces deux instructions sont indépendantes, ce qui veut dire que si vous n'êtes pas seul, vous pouvez mettre le plat dans le four EN MEME TEMPS qu'une autre personne prépare l'oeuf! Pas besoin d'attendre que le plat soit dans le four pour commencer à préparer l'oeuf. C'est ce que l'on appelle le parallélisme. Remarquez que l'on peut très bien réaliser séquentiellement les tâches qui peuvent être parallélisées (ce n'est pas parce que mettre le plat dans le four est indépendant de la préparation de l'oeuf que vous DEVEZ le faire de manière parallèle... Typiquement, si vous êtes seul, vous allez devoir le faire séquentiellement). Cette manière de réaliser les instructions est plus efficace, car, évidemment, si plusieurs choses sont faites en même temps, c'est toujours plus rapide que de faire une chose après l'autre. Pour pouvoir exécuter un algorithme parallèle, "il ne faut pas être seul", d'un point de vue informatique, il faut disposé de plusieurs ordinateurs ou de plusieurs processeurs dans un même ordinateur.

Il est intéressant de donner cette intuition aux élèves. Non seulement il est possible de créer une suite d'instructions capable de résoudre un problème, mais en plus, il est possible de faire plusieurs choses en même temps! On n'est pas toujours obligé d'attendre que les instructions précédentes soient réalisées pour continuer.

A propos de l'exercice

L'exercice du réseau de tri illustre l'aspect de parallélisme. Il montre qu'il est possible de trier une suite de nombres en réalisant plusieurs comparaisons en même temps. On n'est pas obligé de faire une comparaison, puis une autre, puis une autre, etc... Les élèves vont donc comparer leur nombre avec celui d'un autre élève, pendant que d'autres élèves compareront en même temps leurs nombres. Ainsi, le tri sera plus rapide. D'autres activités présentent des algorithmes de tri séquentiels, elles peuvent être réalisées au préalable mais ce n'est pas indispensable.

Cette activité est inspirée de l'activité "La course contre la montre" ("Beat the Clock") de cs-unplugged que vous pouvez retrouver à l'adresse: http://csunplugged.org/sorting-networks. Pour plus de renseignements sur cs-unplugged, voir: http://csunplugged.org/.

• Fiche pédagogique (pdf Δ, docx Δ)
• Synthèse pour les élèves (pdf Δ, docx Δ)
• Matériel:
  • Explication en image (version pdf)
  • Autres réseaux de tri (version pdf)

Cette activité est inspirée de l'activité "La course contre la montre" ("Beat the Clock") de cs-unplugged que vous pouvez retrouver à l'adresse: http://csunplugged.org/sorting-networks. Pour plus de renseignements sur cs-unplugged, voir: http://csunplugged.org/.