Objectifs

Dans cette activité, on demande de comparer deux manières de trier une suite et d'ajouter un élément dans cette suite, afin de remarquer que ces deux manières ne sont pas aussi efficaces l'une que l'autre. Il faut donc réfléchir sur le problème avant de commencer à écrire un algorithme qui va le résoudre.

Mise en place

L'activité se déroule en classe. L'exercice propose de trier des nombres, sur papier, mais l'on peut aussi trier des bouteilles de poids différents, par exemple.

Introduction

Cette activité se focalise sur la première étape de construction d'un algorithme: la réflexion. Cette étape est classique, mais primordiale. Comment peut-on écrire une suite d'instructions qui résout le problème, si on a pas réfléchi sur sa résolution? Ca semble impossible... De plus, même lorsque l'on a trouvé une manière de résoudre le problème, il peut être utile de réfléchir pour voir s'il n'est pas possible de le résoudre de manière plus efficace (voir la complexité algorithmique).

Comment réfléchir?

Réfléchir sur le problème n'est pas facile, il n'existe pas de méthode stricte à respecter pour comprendre un problème et savoir le modéliser. On appelle donc à l'intuition et surtout, à la bonne compréhension du problème. Cette capacité de réflexion se travaille. Modéliser un problème sous une forme plus claire, afin d'être capable de le résoudre, devient de plus en plus facile au fur et à mesure des exercices.

L'exercice de cette activité

L'exercice présenté dans cette activité est l'ajout et le tri d'un nombre dans une suite de nombres. Ce petit exercice de réflexion montre qu'il est possible d'avoir plusieurs manières de résoudre un problème. On peut ajouter le nombre au début de la suite de nombres et ensuite la trier, on peut aussi l'ajouter à la fin avant de la trier, on peut également trier d'abord la suite de nombres et enfin insérer le nombre au bon endroit, ... On peut voir que même pour cet exercice simple, il existe plusieurs manières de le résoudre.

Lien avec la complexité algorithmique

Afin de faire un lien avec la complexité algorithmique (il est utile de remarquer qu'il ne suffit pas de réfléchir un peu au problème, et de prendre la première solution qui nous vient en tête... il faut parfois envisager plusieurs possibilités pour résoudre le problème de manière plus efficace), présentons deux manières de voir ce problème simple.

Le problème est donc le suivant: on a une suite de nombres non-ordonnés, par exemple [9 12 3 7 1], et on veut un algorithme qui manipule cette suite de nombres pour qu'au final, on ait un nombre en plus, disons 10, et que cette suite soit triée. On doit donc à la fin obtenir le résultat [1 3 7 9 10 12]. Voici donc deux manières simples de le faire:

• On trie d'abord la suite de nombres, ce qui nous fait passer de [9 12 3 7 1] à [1 3 7 9 12]. Ensuite, on ajoute 10 dedans. On passe donc de [1 3 7 9 12] à [1 3 7 9 10 12].
• Une autre possibilité est d'ajouter 10 au début de la suite non-ordonnée. Ce qui fait qu'on passe de [9 12 3 7 1] à [10 9 12 3 7 1]. Et ensuite seulement, on trie cette dernière suite, ce qui donne [1 3 7 9 10 12].

On peut voir que dans les deux cas, on a obtenu le même résultat, on a résolu le problème. Cependant, on l'a fait de deux manières différentes, et, ce qui peut sembler faible comme changement, ne l'est pas. Dans les deux cas on trie toute la suite de nombres, mais on peut remarquer que la première méthode réalise 18 comparaison (13 pour trier puis 5 pour ajouter le 10) alors que la deuxième réalise 21 comparaisons (0 pour ajouter (car on ajoute directement au début de la liste, sans rien comparer) et 21 pour trier). Le nombre de comparaisons effectuées est donc différent alors que l'on arrive au même résultat. Il est donc important de choisir sa méthode avant de résoudre le problème.

En pratique...

Afin de présenter cela dans un exercice pour les élèves, on va demander à chacun d'eux de résoudre le problème avec les deux algorithmes différents (cités au dessus). En même temps, ils vont devoir compter le nombre de comparaisons qu'ils effectuent. De cette manière, ils vont pouvoir constater que pour résoudre le même problème, les deux méthodes n'ont pas un nombre de comparaison égal (l'une des deux méthodes est plus efficace que l'autre). L'algorithme de tri à utiliser est détaillé dans la fiche.

En résumé, l'exercice propose de réfléchir sur la manière de résoudre un problème, avant même de concevoir l'algorithme. Vous pouvez constater que l'on présente cela de manière implicite dans les activités liées à l'algorithmique. En effet, pour le problème qui est de trier une suite de nombres, plusieurs manières de voir le problème et de le résoudre ont été présentées (tri par insertion, tri par sélection, tri à bulles, réseau de tri, ...). Afin de constater qu'il y a plusieurs manières de résoudre ce problème et d'en choisir une, il a fallut passer par l'étape de réflexion.

• Fiche pédagogique (pdf, docx)
• Synthèse pour les élèves (pdf, docx)
• Matériel:
  • Pas de matériel spécifique pour cette activité.