Objectifs

Dans cet exercice, nous regardons deux manières de rechercher un nombre dans une suite de nombres, afin de mettre en évidence que le fait que l'on peut avoir plusieurs manières d'atteindre un objectif, et que ces manières de faire ne sont pas forcément aussi intéressantes les une que les autres.

Mise en place

Cette activité se fait en classe, où l'on pourra comparer au tableau, ou sur papier, les deux algorithmes proposés.

Objectifs de l'activité

Cet exercice illustre la différence d'efficacité entre un algorithme de recherche et un autre. Les algorithmes de recherche sont un autre type d'algorithme (avec les algorithmes de tri) relativement simple à comprendre.

Supposons que l'on aie une suite de nombres triés, on veut chercher un nombre dans cette suite (pour savoir s'il existe dans cette suite, par exemple). Il existe, bien évidemment, plusieurs manières de rechercher ce nombre... Ce qui permet de remarquer la différence d'efficacité entre ces méthodes.

Les deux algorithmes à comparer

Présentons les deux algorithmes de l'exercice. Supposons que l'on ait cette suite de nombres triés en ordre croissant (il est ici supposé que la liste des nombres est déjà triée): 1 4 6 9 13 15 16, et que l'on veut savoir si 14 est dans la suite. Voici les deux algorithmes:

• la recherche séquentielle: l'idée est de simplement parcourir la suite de nombre, à la recherche de 14. On commence donc par le début: 1 n'est pas 14 mais il est possible que 14 soit après... donc on continue dans la liste. 4 n'est pas 14 mais il est possible que 14 soit après... Donc on continue dans la liste. 6 n'est pas 14, mais 14 peut être après, donc on continue dans la liste. On fait la même chose jusqu'à ce qu'on arrive soit au nombre recherché (on l'a trouvé! il est donc dans la liste) soit à un nombre plus grand que le nombre recherché. C'est ce qui va arriver dans ce cas... On va arriver à 15, qui est plus grand que 14, et donc, 14 ne peut plus être après (puisque l'a liste est triée). On sait donc que 14 n'est pas dans la liste. Dans le pire des cas, on va devoir parcourir TOUTE la liste pour s'en apercevoir. Dans le cas présent, on a du faire 6 comparaisons.
• la recherche dichotomique: l'idée est de couper la liste à chaque fois en deux. Pour rappel, la liste au départ est [1 4 6 9 13 15 16]. On commence donc au milieu, qui est 9 dans ce cas-ci. on remarque que 14 est plus grand que 9, donc on ne doit pas regarder tout ce qui est à gauche de 9, mais on doit regarder ce qui est à sa droite. On s'occupe donc de la liste [13 15 16]. On prend donc le milieu de la partie à la droite de 9 qui est 15 (car 15 est au milieu de [13 15 16]). 14 étant plus petit que 15, on doit donc regarder ce qui est à gauche de 15 (seul 13 est à gauche de 15, on a donc la liste [13], qui ne contient qu'un seul nombre). On regarde donc dans la liste de ce qui est à gauche de 15, c'est-à-dire [13], et comme 14 n'est pas 13 et que 13 est le seul élément restant dans la liste, on peut dire que 14 n'est pas dans la liste de nombres de départ... On a donc du faire 3 comparaisons seulement! (Pour les plus matheux d'entre vous, dans le pire des cas, on va devoir faire un nombre de comparaisons logarithmique par rapport au nombre de nombres dans la liste). Ce qui est à retenir, c'est que cette méthode demandera moins de comparaisons que la première dans quasiment tous les cas! Elle est donc plus efficace.

Pour les plus matheux qui veulent en savoir plus, on peut aller un peu plus loin: pour éviter les mauvaises surprises, les informaticiens s'intéressent toujours au pire des cas. Quel est le pire des cas pour la recherche séquentielle? Que le nombre recherché ne s'y trouve pas ou qu'il soit à la fin de la liste, on fait alors autant de comparaison qu'il y a d'éléments dans la liste. Si on reprend la liste d'exemple ci-dessus, cela en fait 7. Quel est le pire des cas pour la recherche dichotomique? Que le nombre recherché ne s'y trouve pas car on doit aller jusqu'à la fin avec une liste qui ne contient qu'un élément. Si on reprend la liste d'exemple ci-dessus, ça fait 1 comparaison pour avoir une liste réduite de 3 (= 7 div 2) éléments, une deuxième pour avoir une liste de 1 (=3 div 2) éléments. Et une dernière quand la liste ne comporte plus qu'un seul élément. Donc, 3 comparaisons. C'est le principe du logarithme: "combien de plis faut-il faire dans une feuille pour obtenir une épaisseur de 1cm sachant que l'épaisseur d'une feuille est de 0.1 mm". (Souvenez-vous, le logarithme, c'est l'inverse de l'exponentielle, cette fonction qui augmente très vite, on plie une feuille, on a 2 épaisseurs. On plie une deuxième fois, on a 4=2² épaisseurs. On plie une troisième fois, on a 8=2³ épaisseurs. Ensuite, 16 puis 32, 64 128, ... Pour n plis, on a 2ⁿ épaisseurs. Et bien, 2ⁿ, c'est l'exponentielle, n c'est le logarithme). Et les matheux savent que log(x) est toujours plus petit que x, c'est pourquoi la recherche dichotomique est plus efficace que la recherche séquentielle.

Conclusion de l'activité

On peut constater, même par intuition, la différence d'efficacité entre ces deux algorithmes. L'idée est que de telles différences existent entre beaucoup de méthodes qui ont le même but/le même rôle. Il faut donc faire un choix de méthode intelligent, quand on veut gagner du temps lors de l'exécution!

Cependant, il faut également être attentif aux conditions d'application d'une méthode. Une variante de la première technique (la recherche séquentielle) peut être réalisée même si la liste n'est pas préalablement triée (on compare le nombre recherché à tous les éléments de la liste un à un jusqu'au bout). Par contre, la seconde méthode dépend entièrement du fait que la liste est triée par ordre croissant.

Lors de cette activité, les élèves vont appliquer à une liste de nombres les deux méthodes et compter le nombre d'opérations. Ils en déduiront d'une part que les deux méthodes permettent d'obtenir le même résultat mais que l'une est généralement plus efficace que l'autre. Ils seront donc introduit à la complexité algorithmique.

• Fiche pédagogique (pdf, docx)
• Synthèse pour les élèves (pdf, docx)
• Matériel:
  • Représentation de la recherche dichotomique (pdf, odg)
  • Représentation de la recherche séquentielle (pdf, odg)