Algorithmes de Recherche (Introduction)

Les élèves retiennent mieux les concepts algorithmiques quand ils les expérimentent physiquement ou numériquement. Pour la recherche linéaire, manipuler des données tangibles ou coder une simulation rend visible ce qui reste abstrait dans un cours théorique. Cette approche active transforme une notion technique en une compétence concrète et mémorable pour les élèves.

• 3ème
• Vers le Lycée : Maîtrise et Raisonnement Mathématique
• 3 activités
• 15 min–45 min

Objectifs d’apprentissage

1. Identifier les étapes d'une recherche linéaire dans une liste non triée.
2. Comparer l'efficacité d'une recherche linéaire avec une méthode de recherche intuitive pour une liste donnée.
3. Concevoir un algorithme simple décrivant les étapes d'une recherche linéaire.
4. Expliquer pourquoi le tri préalable d'une liste peut améliorer la vitesse de recherche.
5. Évaluer le nombre d'opérations nécessaires dans le pire des cas pour une recherche linéaire.

Jeu de rôle

⏱ 20 min·Classe entière

Jeu de rôle: Recherche dans le Noir

Un élève a les yeux bandés et doit trouver une carte cible parmi 20 cartes retournées (liste non triée). Il ne peut retourner qu une carte à la fois. La classe compte le nombre d essais. On recommence avec les cartes triées et une stratégie dichotomique pour comparer.

Préparation et détails

Comment un algorithme de recherche permet-il de trouver rapidement une information dans une grande quantité de données ?

Conseil de facilitation: Pendant le jeu de rôle 'Recherche dans le Noir', placez les élèves dans une pièce sombre et imposez des contraintes de déplacement pour simuler une liste non triée, ce qui rend l’algorithme de recherche linéaire immédiatement tangible.

Setup: Espace ouvert ou bureaux réorganisés pour la mise en scène

Materials: Fiches de personnage (contexte et objectifs), Fiche de mise en situation (scénario)

• Appliquer
• Analyser
• Évaluer
• Conscience sociale
• Conscience de soi

Penser-Partager-Présenter

⏱ 15 min·Binômes

Penser-Partager-Présenter: Combien d Étapes ?

Chaque élève estime le nombre maximum d étapes pour trouver un élément dans une liste de 100 éléments (recherche linéaire), puis dans une liste triée de 100 éléments (recherche dichotomique). En binôme, ils comparent leurs estimations et justifient leur raisonnement.

Préparation et détails

Justifiez l'importance de l'efficacité d'un algorithme de recherche.

Conseil de facilitation: Lors du Penser-Partager-Présenter, fournissez des listes de tailles différentes et demandez aux élèves de calculer le nombre d’étapes avant de partager leurs réponses, ce qui les force à réfléchir avant de discuter.

Setup: Disposition de classe standard ; les élèves se tournent vers leur voisin

Materials: Consigne de discussion (projetée ou distribuée), Optionnel : fiche de prise de notes pour les binômes

• Comprendre
• Appliquer
• Analyser
• Conscience de soi
• Compétences relationnelles

Cercle de recherche

⏱ 45 min·Petits groupes

Cercle de recherche: Coder un Moteur de Recherche

Par groupes, les élèves programment en Scratch ou Python un algorithme de recherche linéaire qui parcourt une liste de prénoms et signale si le prénom cherché est présent. Les groupes les plus avancés ajoutent un compteur d étapes pour mesurer l efficacité.

Préparation et détails

Design un algorithme simple pour rechercher un élément dans une liste non triée.

Conseil de facilitation: Pour la Collaborative Investigation, divisez la classe en petits groupes et attribuez à chacun une liste de données à trier ou non, afin que chaque groupe vive concrètement le compromis entre tri et recherche linéaire.

Setup: Groupes en îlots avec accès aux ressources documentaires

Materials: Corpus de documents sources, Fiche de suivi du cycle de recherche, Protocole de formulation de questions, Canevas de présentation des résultats

• Analyser
• Évaluer
• Créer
• Autogestion
• Conscience de soi

Enseigner ce sujet

Commencez par une activité physique qui place les élèves dans la peau d’un algorithme, car la recherche linéaire se comprend mieux par l’action que par l’explication. Évitez de présenter le tri comme une solution universelle : insistez sur le coût du tri et les situations où il n’est pas nécessaire. Utilisez des exemples concrets, comme chercher un mot dans un dictionnaire non trié, pour ancrer la réflexion dans des situations réelles que les élèves peuvent visualiser.

À quoi s’attendre

Les élèves distinguent quand la recherche linéaire est efficace et quand elle ne l’est pas. Ils expliquent le lien entre la taille d’une liste et le nombre d’étapes nécessaires. Ils appliquent l’algorithme à des cas concrets, sur papier ou en code, avec précision et sans confusion entre liste triée et non triée.

Attention à ces idées reçues

Idée reçue courante

Pendant le jeu de rôle 'Recherche dans le Noir', certains élèves pourraient croire que la recherche linéaire est toujours inefficace.

Ce qu'il faut enseigner à la place

Pendant le jeu de rôle, chronométrez les élèves pour trouver un élément dans des listes de 10, 50 et 100 objets. Faites-leur comparer les temps et conclure que pour de petites listes, la recherche linéaire reste efficace malgré son apparente simplicité.

Idée reçue courante

Pendant la Collaborative Investigation, des élèves pourraient penser qu’il faut toujours trier une liste avant de chercher.

Ce qu'il faut enseigner à la place

Pendant la Collaborative Investigation, attribuez à chaque groupe une liste triée et une liste non triée. Demandez-leur de chercher le même élément dans les deux listes et de mesurer le temps réel d’exécution, ce qui illustrera le coût du tri pour une seule recherche.

Idées d'évaluation

Vérification rapide

Après le Penser-Partager-Présenter 'Combien d’Étapes ?', présentez une courte liste de nombres et demandez aux élèves d’écrire les étapes exactes qu’un algorithme de recherche linéaire suivrait pour trouver un nombre donné. Comptez le nombre d’étapes nécessaires pour évaluer leur compréhension de l’algorithme.

Question de discussion

Pendant le Penser-Partager-Présenter, demandez : 'Imaginez que vous cherchez un mot dans un dictionnaire non trié. Comment cela changerait-il votre méthode de recherche par rapport à un dictionnaire normal ?' Encouragez les élèves à comparer les deux scénarios en termes de temps et d’effort.

Billet de sortie

Après le jeu de rôle 'Recherche dans le Noir', demandez aux élèves de définir en une phrase ce qu’est une 'liste non triée' et de donner un exemple concret où une recherche linéaire est inefficace. Ils doivent aussi proposer une amélioration possible.

Extensions et étayage

• Challenge : Proposez aux élèves de trouver un algorithme plus efficace que la recherche linéaire pour une liste triée, puis demandez-leur de justifier pourquoi il est plus rapide.
• Scaffolding : Pour les élèves en difficulté, montrez une liste de 5 éléments et demandez-leur de dessiner les étapes de recherche étape par étape avec des flèches ou des couleurs.
• Deeper : Invitez les élèves à comparer la recherche linéaire avec une recherche dichotomique sur une liste de 1 000 éléments, en calculant le nombre d’étapes théoriques pour chaque méthode.

Vocabulaire clé

Algorithme de recherche linéaire	Une méthode qui consiste à parcourir une liste élément par élément, du début à la fin, pour trouver une valeur spécifique.
Liste non triée	Une collection d'éléments dont l'ordre n'est pas défini selon une règle particulière (par exemple, ordre alphabétique ou numérique croissant).
Itération	Chaque passage d'une boucle dans un algorithme, représentant l'examen d'un élément de la liste.
Condition d'arrêt	Le critère qui détermine la fin d'une recherche, soit parce que l'élément est trouvé, soit parce que la liste est entièrement parcourue.