UA 5 : Utilisation des algorithmes de tri(suite)

# UA 5 : Utilisation des algorithmes de tri(suite) ## Objectifs et prérequis Ce chapitre vise à approfondir la compréhension des algorithmes de recherche, en particulier la recherche dichotomique, après avoir étudié les algorithmes de tri. L’élève doit être capable de comprendre les conditions nécessaires à l’application de la recherche dichotomique, de l’exécuter pas à pas sur un tableau trié, d’en analyser la complexité et de la comparer à la recherche séquentielle. Il doit également savoir l’appliquer à des problèmes concrets issus du contexte camerounais et africain. **Prérequis** : - Maîtrise des notions de tableau (déclaration, accès aux éléments, parcours). - Compréhension des algorithmes de tri (tri à bulles, tri par sélection, tri par insertion) étudiés dans les unités précédentes. - Notions de base en complexité algorithmique (O(n), O(log n)). - Capacité à rédiger un algorithme en pseudocode ou en langage proche du français structuré. --- ## I. Recherche d’un élément dans un tableau ### Contexte Dans de nombreuses applications informatiques, il est fréquent de devoir vérifier la présence d’une valeur spécifique dans une collection de données. Par exemple, dans un système de gestion des notes des élèves d’un lycée au Cameroun, on peut vouloir vérifier si un élève ayant un certain numéro d’inscription est présent dans la liste. De même, dans un répertoire téléphonique d’une entreprise à Douala ou Yaoundé, rechercher un contact par nom nécessite une opération de recherche. Deux méthodes principales existent : la recherche séquentielle et la recherche dichotomique. Cette leçon introduit la recherche séquentielle comme point de départ pour comprendre la nécessité d’optimiser la recherche lorsque le tableau est trié. ### Définitions et faits clés La **recherche séquentielle** (ou recherche linéaire) consiste à parcourir les éléments du tableau un par un, du premier au dernier, jusqu’à trouver l’élément cherché ou à atteindre la fin du tableau. > **À retenir** : La recherche séquentielle fonctionne sur un tableau non trié ou trié, mais elle n’exploite pas l’ordre éventuel des données. Elle ne nécessite aucune condition particulière sur l’organisation des données, ce qui la rend universelle mais potentiellement lente dans le pire des cas. ### Algorithme de recherche séquentielle Voici l’algorithme en pseudocode : ``` Algorithme : RechercheSequentielle Données : T : tableau de n éléments, x : élément à chercher Résultat : indice de x dans T si trouvé, -1 sinon Début i ← 0 Tant que i < n ET T[i] ≠ x faire i ← i + 1 Fin Tant que Si i < n alors Retourner i Sinon Retourner -1 Fin Si Fin ``` ### Exemple concret (contextualisé Cameroun) Dans un lycée de Yaoundé, les notes de mathématiques des 30 élèves d’une classe de Première sont stockées dans un tableau `Notes` dans l’ordre d’arrivée des copies (non trié). Le professeur veut savoir si un élève a obtenu 18/20. - `Notes = [12, 15, 9, 18, 7, 14, ...]` (30 éléments) - On cherche `x = 18` - L’algorithme vérifie : T[0]=12≠18 → i=1 ; T[1]=15≠18 → i=2 ; T[2]=9≠18 → i=3 ; T[3]=18=18 → arrêt, retourne 3. Dans le pire des cas (élément absent ou en dernière position), il effectue 30 comparaisons. ### Complexité - **Meilleur cas** : O(1) (élément en première position). - **Pire cas** : O(n) (élément absent ou en dernière position). - **Cas moyen** : O(n/2) ≈ O(n). ### Vocabulaire à retenir - Recherche séquentielle - Parcours linéaire - Meilleur cas / Pire cas - Complexité en temps - Tableau non trié ### Exemple de sujet type examen avec plan **Sujet** : Dans un centre de santé à Bamenda, les numéros de patients ayant consulté aujourd’hui sont enregistrés dans un tableau `Consultations` dans l’ordre d’arrivée. On veut savoir si le patient numéro 457 est présent. 1. Expliquer pourquoi on peut utiliser une recherche séquentielle ici. 2. Écrire l’algorithme de recherche séquentielle en pseudocode. 3. Donner le pire cas en nombre de comparaisons si le tableau contient 50 éléments. 4. Que se passe-t-il si le tableau est trié ? Peut-on faire mieux ? Justifier. **Plan attendu** : I. La recherche séquentielle ne nécessite pas de tri → adaptée ici. II. Algorithme : initialisation d’un indice, boucle tant que pas trouvé et pas fin de tableau, retour de l’indice ou -1. III. Pire cas : 50 comparaisons. IV. Si trié, on peut utiliser la recherche dichotomique pour réduire la complexité à O(log n). --- ## II. Exécution d’un algorithme de recherche dichotomique ### Contexte Lorsque le tableau est trié selon un ordre croissant (ou décroissant), il devient possible d’exploiter cette propriété pour réduire considérablement le nombre de comparaisons nécessaires à la recherche. C’est le principe de la **recherche dichotomique** (ou recherche binaire). Elle est largement utilisée dans les systèmes où des recherches fréquentes sont effectuées sur de grandes listes ordonnées : annuaires téléphoniques, dictionnaires, bases de données de notes d’élèves, etc. Dans un contexte africain, imaginez un registre des naissances dans une région du Nord-Cameroun, trié par ordre alphabétique des noms : trouver un nom spécifique devient beaucoup plus rapide avec cette méthode. ### Définitions et faits clés La **recherche dichotomique** fonctionne en divisant répétitivement le tableau en deux moitiés et en ne conservant que la moitié où l’élément peut se trouver, en fonction de la comparaison avec l’élément du milieu. > **À retenir** : La recherche dichotomique nécessite que le tableau soit **trié dans un ordre connu** (croissant ou décroissant). Elle repose sur la propriété suivante : si `T[milieu] < x`, alors `x` ne peut se trouver que dans la moitié droite ; si `T[milieu] > x`, alors `x` ne peut se trouver que dans la moitié gauche. ### Algorithme de recherche dichotomique (version itérative) Voici l’algorithme en pseudocode : ``` Algorithme : RechercheDichotomique Données : T : tableau trié de n éléments (ordre croissant), x : élément à chercher Résultat : indice de x dans T si trouvé, -1 sinon Début gauche ← 0 droit ← n - 1 Tant que gauche ≤ droit faire milieu ← (gauche + droit) div 2 Si T[milieu] = x alors Retourner milieu Sinon Si T[milieu] < x alors gauche ← milieu + 1 Sinon droit ← milieu - 1 Fin Si Fin Tant que Retourner -1 Fin ``` ### Exemple concret (contextualisé Afrique) Dans un lycée de Garoua, les notes de physique des 15 élèves d’une classe de Première sont triées par ordre croissant : `Notes = [8, 9, 10, 10, 11, 12, 12, 13, 14, 14, 15, 16, 17, 18, 19]` On cherche si un élève a obtenu 14/20. - Initialisation : `gauche = 0`, `droit = 14` - **Itération 1** : `milieu = (0+14) div 2 = 7` → `T[7] = 13` Puisque 13 < 14 → `gauche = 7 + 1 = 8` - **Itération 2** : `gauche = 8`, `droit = 14` → `milieu = (8+14) div 2 = 11` → `T[11] = 16` Puisque 16 > 14 → `droit = 11 - 1 = 10` - **Itération 3** : `gauche = 8`, `droit = 10` → `milieu = (8+10) div 2 = 9` → `T[9] = 14` Trouvé ! Retourne 9. Seulement 3 comparaisons ont été nécessaires, contre jusqu’à 15 en recherche séquentielle. ### Variante : recherche dichotomique décroissante Si le tableau est trié par ordre décroissant, l’algorithme s’adapte en inversant les comparaisons : > **À retenir** : Dans un tableau trié par ordre décroissant, si `T[milieu] < x`, alors on cherche à gauche ; si `T[milieu] > x`, on cherche à droite. Exemple : Tableau des âges des encadreurs d’un centre de formation à Ngaoundéré, trié décroissant : `[45, 42, 40, 38, 35, 32, 30]`. On cherche 38. ### Complexité À chaque étape, la taille du tableau considéré est divisée par 2. Le nombre d’étapes nécessaires est donc le plus petit entier `k` tel que `n / 2^k < 1`, soit `k > log₂(n)`. > **À retenir** : La complexité en pire cas de la recherche dichotomique est **O(log₂ n)**. - Meilleur cas : O(1) (élément au milieu dès la première étape). - Pire cas : O(log₂ n). - Pour n = 1 000 000 : environ 20 comparaisons (contre 1 000 000 en séquentielle). ### Tableau comparatif : Recherche séquentielle vs dichotomique | Critère | Recherche séquentielle | Recherche dichotomique | |--------------------------|------------------------------|---------------------------------------| | État du tableau | Trié ou non trié | **Doit être trié** (croissant ou décroissant) | | Meilleur cas | O(1) | O(1) | | Pire cas | O(n) | **O(log₂ n)** | | Nombre de comparaisons (n=100) | Jusqu’à 100 | Jusqu’à 7 (puisque 2⁷=128 > 100) | | Adapté à | Petits tableaux, données non triées | Grands tableaux triés, recherches fréquentes | | Exemple d’usage | Liste d’attente non triée | Annuaire téléphonique, dictionnaire | ### Vocabulaire à retenir - Recherche dichotomique - Recherche binaire - Tableau trié (croissant/décroissant) - Borne inférieure / supérieure - Division par deux de l’intervalle - Logarithme en base 2 - Complexité O(log n) ### Exemple de sujet type examen avec plan **Sujet** : Dans une bibliothèque scolaire de Maroua, les livres sont rangés par ordre croissant de leur code ISBN. On veut vérifier si un livre ayant le code 978-9956-000-01-2 est présent dans le registre contenant 256 entrées. 1. Justifier l’usage de la recherche dichotomique dans ce contexte. 2. Écrire l’algorithme de recherche dichotomique pour un tableau trié par ordre croissant. 3. Calculer le nombre maximal de comparaisons nécessaires dans le pire cas. 4. Que se passe-t-il si le code cherché est plus petit que tous les codes du registre ? Décrire l’évolution des bornes. **Plan attendu** : I. Le tableau est trié (ISBN croissant) → recherche dichotomique applicable et efficace. II. Algorithme : initialisation des bornes, boucle tant que gauche ≤ droit, calcul du milieu, comparaison, mise à jour des bornes. III. 2⁸ = 256 → donc au maximum 8 comparaisons (puisque 2⁷=128 < 256 ≤ 256=2⁸). IV. À chaque étape, `T[milieu] > x` → `droit = milieu - 1` → les bornes se réduisent vers la gauche jusqu’à ce que `gauche > droit` → retour -1. --- ## Synthèse du chapitre - La recherche séquentielle parcourt le tableau élément par élément, sans condition sur l’ordre, avec une complexité en pire cas de O(n). - La recherche dichotomique exploite le tri du tableau pour éliminer la moitié des éléments à chaque étape, réduisant la complexité à O(log₂ n). - Elle nécessite un tableau trié (croissant ou décroissant) et ne fonctionne pas sur un tableau non trié. - Son efficacité devient significative dès que le nombre d’éléments dépasse une trentaine. - Elle est largement utilisée dans les systèmes réels : annuaires, dictionnaires, bases de données, systèmes de notes scolaires. - La maîtrise de sa logique (bornes, milieu, mise à jour) est essentielle pour résoudre des problèmes de recherche optimisée. - La comparaison entre les deux méthodes permet de choisir l’algorithme adapté selon les contraintes du problème (état des données, fréquence des recherches). --- ## Glossaire - **Recherche séquentielle** : Méthode de recherche qui parcourt les éléments d’un tableau un à un jusqu’à trouver l’élément cherché ou atteindre la fin. - **Recherche dichotomique** : Algorithme de recherche qui réduit de moitié l’intervalle de recherche à chaque étape en comparant l’élément cherché avec celui du milieu d’un tableau trié. - **Tableau trié** : Tableau dont les éléments sont arrangés selon un ordre spécifique (croissant ou décroissant). - **Borne inférieure (gauche)** : Indice représentant le début de l’intervalle actuellement considéré dans la recherche dichotomique. - **Borne supérieure (droit)** : Indice représentant la fin de l’intervalle actuellement considéré dans la recherche dichotomique. - **Indice du milieu** : Position calculée comme la moyenne entière des bornes inférieure et supérieure. - **Complexité en temps** : Mesure du nombre d’opérations élémentaires (comme les comparaisons) en fonction de la taille de l’entrée. - **O(n)** : Notation asymptotique indiquant que le temps de croissance est linéaire par rapport à la taille de l’entrée. - **O(log₂ n)** : Notation asymptotique indiquant que le temps de croissance est logarithmique en base 2 par rapport à la taille de l’entrée. - **Pire cas** : Scenario d’entrée qui entraîne le nombre maximal d’opérations pour un algorithme donné. - **Meilleur cas** : Scenario d’entrée qui entraîne le nombre minimal d’opérations pour un algorithme donné. - **Logarithme en base 2** : Fonction qui répond à la question : « À quelle puissance doit-on élever 2 pour obtenir ce nombre ? » Utilisée pour analyser la dichotomie.