Recherche dichotomique

Recherche dichotomique

Dichotomie

La dichotomie (« couper en deux » en grec) est, en algorithmique, un processus itératif ou récursif de recherche où, à chaque étape, l'espace de recherche est restreint à l'une des deux parties.

On suppose bien sûr qu'il existe un test relativement simple permettant à chaque étape de déterminer l'une des deux parties dans laquelle se trouve une solution. Pour optimiser le nombre d'itérations nécessaires, on s'arrangera pour choisir à chaque étape deux parties sensiblement de la même « taille » (pour un concept de « taille » approprié au problème), le nombre total d'itérations nécessaires à la complétion de l'algorithme étant alors logarithmique en la taille totale du problème initial.

L'algorithme s'applique typiquement à la recherche d'un élément dans un ensemble fini ordonné et organisé en séquence. La fonction de « taille » du problème sera alors le cardinal de l'espace (fini) de recherche, et à chaque étape, on coupera l'espace de recherche en deux parties de même taille (à un élément près) de part et d'autre de l'élément médian.

La dichotomie peut être vue comme une variante simplifiée de la stratégie plus générale diviser pour régner appliquée au cas particulier de la recherche itérative d'une solution, où le traitement des sous-espaces exclus de la recherche et de sa recombinaison peuvent être court-circuités.

Sommaire

Exemple

Prenons un exemple simple et ludique pour illustrer le mécanisme de recherche par dichotomie :

Pierre propose à Paul le jeu suivant: « choisis en secret un nombre compris entre 0 et 100; je vais essayer de le deviner le plus rapidement possible, mais tu ne dois répondre à mes questions que par oui ou par non ». Paul choisit 65 et attend les questions de Pierre:

  • est-ce que le nombre est plus grand que 50? (100 divisé par 2)
  • oui
  • est-ce que le nombre est plus grand que 75? ((50 + 100) / 2)
  • non
  • est-ce que le nombre est plus grand que 63? ((50 + 75 + 1) / 2)
  • oui
Pierre réitère ses questions jusqu'à trouver 65. Par cette méthode itérative, Pierre est sûr de trouver beaucoup plus rapidement le nombre qu'en posant des questions du type « est-ce que le nombre est égal à 30? ».

Algorithme

//déclarations
 début, fin, val, mil : Entier
 t : Tableau [0..100] d'entier
 trouvé : Booléen
 
//initialisation
 début <- 0 
 fin <- 100
 trouvé <- faux

//Question
 Répéter
  Afficher "Valeur recherchée ? (entre 0 et 100)"
  Saisir val
 Jusqu'à début<=val et val<=fin

//Boucle de recherche
  Répéter
   mil <- début + ((fin-début) / 2)
   Si t[mil] = val alors
     trouvé <- vrai
   Sinon
     Si val > t[mil] Alors
       début <- mil + 1
       Si t[début] = val Alors
         mil <- début
         trouvé <- Vrai
       FinSi
     Sinon
       fin <- mil – 1
       Si t[fin] = val Alors
         mil <- fin
         trouvé <- vrai
       FinSi
     FinSi
    FinSi
   Jusqu’à trouvé ou ( début >= fin )
//Affichage du résultat
 Afficher "La valeur est ", val

Autre exemple

Cette méthode est très efficace pour la recherche des zéros approchés d'une fonction continue au voisinage du zéro cherché (théorème des valeurs intermédiaires), à condition qu'on puisse déterminer le signe de f((a+b)/ 2) à chaque itération. Elle prend alors le nom de méthode de dichotomie :

Soit f(x) une fonction telle que:

  • f(a) < 0
  • f(b) > 0
  • f est continue strictement croissante sur [a;b] (a < b)

Alors une dichotomie permet de trouver rapidement la valeur y telle que f(y) = 0.

  1. Partir du couple de valeurs (a, b);
  2. Évaluer la fonction en (a+b)/2;
  3. Si f((a+b)/ 2) < 0, remplacer a par (a+b)/2, sinon remplacer b par (a+b)/2;
  4. Recommencer à partir du nouveau couple de valeurs jusqu'à ce que la différence entre les deux valeurs soit inférieure à la précision voulue.

Une implémentation simple de cet algorithme se trouve dans l'article Objective Caml.

Champ d'application

En dehors des considérations mathématiques la méthode de détection de problème par dichotomie peut être appliquée à de nombreux processus.

Par exemple, en industrie, si un produit passant par x phases de transformation présente une anomalie, il est très pratique d'utiliser la dichotomie pour analyser les transformations (ou processus) par groupe plutôt que un par un. Cela permet aussi d'effectuer des réglages précis par étape.

La méthode de dichotomie peut, par exemple, être utilisée si l'on rencontre un problème lorsque l'on groupe 6 appareils. Le système tombe toujours en panne sans que l'on sache de quel appareil cela provient. On peut alors les regrouper par 3 et effectuer un test. Si les deux groupes tombent en panne, on peut en déduire que cela vient probablement d'une faiblesse du modèle des 6 appareils. Si un seul des deux groupes tombe en panne, on en déduit que c'est un appareil de ce groupe qui pose problème. Il n'y a plus qu'à grouper 2 des 3 appareils susceptibles d'être la source de la panne : en 3 temps maximum, on teste ainsi les 6 appareils.

Il faut toutefois émettre l'hypothèse que deux appareils ne puissent « tomber » en panne simultanément. Cette situation est, de façon théorique, quasi-impossible mais, dans les faits, peut se produire macroscopiquement puisque le test de vérification de l'état de marche global est effectué à intervalles plus grands que le risque de survenue des pannes. Ca ne compromet évidemment pas la méthode, mais restreint cependant son champ de validité : un seul élément doit être recherché pour qu'elle soit opérationnelle.

  • Portail de la logique Portail de la logique
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Dichotomie ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recherche dichotomique de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Dichotomique — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Dichotomique », sur le Wiktionnaire (dictionnaire universel) en biologie, clé dichotomique en… …   Wikipédia en Français

  • Algorithme De Recherche — Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions… …   Wikipédia en Français

  • Algorithmes de recherche — Algorithme de recherche Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un… …   Wikipédia en Français

  • Algorithme de recherche — Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions… …   Wikipédia en Français

  • Groupe Italien de Recherche sur les Orchidées Sauvages — Association Acronyme G.I.R.O.S. Typologie Association de promotion sociale Intérêtn Orchidées sauvages …   Wikipédia en Français

  • Fonction racine carrée — Racine carrée La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½. Une tablette d argile datée du XLVIIIe siècle av. J. C. montre que les Babyloniens connaissaient la racine carrée de deux …   Wikipédia en Français

  • Puissance un demi — Racine carrée La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½. Une tablette d argile datée du XLVIIIe siècle av. J. C. montre que les Babyloniens connaissaient la racine carrée de deux …   Wikipédia en Français

  • Racine Carree — Racine carrée La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½. Une tablette d argile datée du XLVIIIe siècle av. J. C. montre que les Babyloniens connaissaient la racine carrée de deux …   Wikipédia en Français

  • Racine Carrée — La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½. Une tablette d argile datée du XLVIIIe siècle av. J. C. montre que les Babyloniens connaissaient la racine carrée de deux et un… …   Wikipédia en Français

  • Racine carree — Racine carrée La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½. Une tablette d argile datée du XLVIIIe siècle av. J. C. montre que les Babyloniens connaissaient la racine carrée de deux …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”