Objectifs

Cette activité met en évidence la partie conception d'un algorithme. Les élèves vont être amené à construire un algorithme de tri. La notion de sous-problème leur sera également introduite.

Mise en place

L'activité se déroule en classe, avec l'aide du tableau ou de feuilles de papier.

Déroulement

Utiliser un algorithme, c'est simple, mais avant cela, il faut le construire! Il s'agit de l'étape de conception et c'est ce que l'on va essayer de faire avec les élèves. Pour cela, on va utiliser un algorithme de tri intuitif, le tri par sélection.

Cet exercice se décompose en trois étapes:

• chercher comment faire pour trouver le plus petit élément (et en écrire l'algorithme (la suite d'instructions))
• chercher comment faire pour trier des éléments, maintenant que l'on sait comment trouver le plus petit (et en écrire l'algorithme)
• exécuter l'algorithme trouvé par les élèves

Explications

Cet exercice permet de comprendre que l'on peut trouver un sous-problème dans un problème (dans notre cas, trouver le plus petit élément est un sous-problème du problème général qui est de trier les éléments). On pourra alors faire en sorte qu'un élève représente l'algorithme du sous-problème (il va permettre de trouver le plus petit élément) et qu'un élève représente l'algorithme général.

Mais commençons par donner l'intuition du problème et du sous-problème. Supposons que l'on aie 5 nombres mélangés dans une liste de nombres (par exemple: 4 7 5 1 9). Le but, le problème général, est de trier cette liste de nombres. Pour cela, on va utiliser un sous-problème (un problème moins compliqué, qui va aider dans la résolution du problème général). Dans notre cas, le but de notre sous-problème sera de trouver le plus petit nombre de la liste. De cette manière, on pourra chercher le plus petit nombre et le mettre de côté, puis chercher le second plus petit nombre et le mettre après le premier, etc...

Ce qui donnerait:

nombres mis sur le côté: aucun pour le moment liste de nombres: 4 7 5 1 9

sous-problème (recherche du plus petit nombre): 1

nombres mis sur le côté: 1 liste de nombres: 4 7 5 9

sous-problème (recherche du plus petit nombre): 4

nombres mis sur le côté: 1 4 liste de nombres: 7 5 9

sous-problème (recherche du plus petit nombre): 5

nombres mis sur le côté: 1 4 5 liste de nombres: 7 9

sous-problème (recherche du plus petit nombre): 7

nombres mis sur le côté: 1 4 5 7 liste de nombres: 9

sous-problème (recherche du plus petit nombre): 9

nombres mis sur le côté: 1 4 5 7 9 liste de nombres: il n'y en a plus

Comme la liste de nombres de départ est vide, on a considéré tous les éléments de la liste, et donc on s'arrête. On observe qu'en utilisant le sous-problème à chaque étape, on a pu résoudre le problème général qui était de trier une liste de nombres. Cet algorithme est très intuitif et sera probablement celui qui sera le plus rapidement trouvé par les élèves. Il s'agit donc de leur faire trouver le sous-problème (trouver le plus petit nombre d'une liste de nombres), et d'en écrire l'algorithme (voir la fiche pour la suite d'instructions). Ensuite, ils vont devoir trouver l'algorithme de tri qui utilise l'algorithme du sous-problème (voir la fiche pour la suite d'instructions). Finalement, une fois l'algorithme trouvé, ils vont devoir le suivre pour comprendre qu'une fois trouvé, il suffit d'exécuter l'algorithme, instruction par instruction, pas besoin de faire plus (il va donc falloir qu'ils suivent rigoureusement les étapes).

L'algorithme qui résout le problème général (le tri) est appelé le tri par sélection. Vous l'aurez deviné, le nom vient du fait que l'on sélectionne le plus petit nombre de la liste de nombres pour le mettre de côté.

Remarque

Il faut savoir que, sauf dans certaines situations particulières, il existe des algorithmes plus efficaces (voir le concept de complexité algorithmique) que le tri par sélection, mais ce dernier a l'avantage d'être très intuitif, et il est donc plus facile pour les élèves de trouver cet algorithme de tri.

• Fiche pédagogique (pdf, docx)
• Synthèse pour les élèves (pdf, docx)
• Matériel:
  • Représentation du tri par sélection (pdf, odg)
  • Représentation de "trouver le plus petit" (pdf, odg)