Dichotomie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Cet article ne cite pas suffisamment ses sources (février 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

En algorithmique, la dichotomie (« couper en deux » en grec) est une méthode qui consiste à diviser récursivement le problème à traiter en deux sous-problèmes, jusqu'à atteindre des problèmes simples qu'il est possible de résoudre directement. Il s'agit d'un cas particulier de la méthode diviser pour régner où le problème est toujours divisé en deux. Les algorithmes dichotomiques se prêtent naturellement à une écriture récursive, mais une approche impérative peut tout à fait être utilisée.

Un cas fréquent d'utilisation est la recherche dichotomique ; à chaque itération, c'est l'espace de recherche qui est alors divisé en deux. On suppose alors qu'il existe un test relativement simple permettant à chaque étape de déterminer dans quelle partie se trouve la 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.

Recherche dichotomique[modifier | modifier le code]

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

« Julie 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, en ne pouvant que te poser des questions auxquelles tu réponds par oui ou par non ».

Paul choisit 66 et attend les questions de Julie : * Julie sait que le nombre est entre 0 et 100 ; au milieu se trouve 50, elle demande donc : « Est-ce que le nombre est plus grand que 50 ? ». Paul répond « Oui ». * Julie sait maintenant que le nombre est entre 51 et 100 ; au milieu se trouve 75, elle demande donc : « Est-ce que le nombre est plus grand que 75 ? » Paul répond « Non » * Et ainsi de suite : « Plus grand que 63? (63 =(51+75)÷2) », « Oui », « Plus grand que 69 ?(69 =(63+75)÷2)  », « Non », « Plus grand que 66 ?(66 =(69+63)÷2)  », « Non », « Plus grand que 65 ? (65 ≈(63+66)÷2) », « Oui ». * Julie sait maintenant que le nombre est entre 66 et 66, autrement dit qu'il s'agit de 66 : elle a trouvé le nombre choisi par Paul.

Cette méthode itérative permet à Julie de trouver le nombre en posant en moyenne moins de questions que si elle procédait par des questions du type « Est-ce que le nombre est plus petit que 10 ?, 20 ? , 30 ?, etc. ». »

Le nombre maximal M de questions à poser afin d'obtenir la réponse est la valeur du premier exposant entier de 2 supérieur ou égal au nombre N de réponses possibles, ou encore M est le premier entier supérieur ou égal au logarithme en base 2 de N.

M = \lceil  \log_2(N) \rceil

Pour l'exemple de Julie et Paul, il y a N = 101 réponses possibles : le premier exposant de 2 supérieur à 101 est 128, soit 27, il faut donc un maximum M = 7 essais (26 = 64 serait trop faible). Ou encore :

M = \lceil \log_2(101) \rceil = \lceil 6,658211483... \rceil = 7

Algorithme[modifier | modifier le code]

Plus généralement, l'algorithme de dichotomie permettant de trouver une valeur val dans un tableau t de N+1 entiers trié par ordre croissant est le suivant :

//déclarations
 début, fin, val, mil, N : Entiers
 t : Tableau [0..N] d'entiers classé
 trouvé : Booléen
 
//initialisation
 début ← 0 
 fin ← N
 trouvé ← faux
 Saisir val

//Boucle de recherche
  Répéter
   mil ← partie entière((début + fin)/2)
   Si t[mil] = val alors
     trouvé ← vrai
   Sinon
     Si val > t[mil] Alors
       début ← mil+1
       
     Sinon
       fin ← mil-1
       
     FinSi
    FinSi
   // La condition début inférieur ou égal à fin permet d'éviter de faire
   // une boucle infinie si 'val' n'existe pas dans le tableau.
   Tant que trouvé = faux ET début ≤ fin
//Affichage du résultat
Si trouvé Alors
     Afficher "La valeur ", val , " est au rang ", mil
  Sinon
     Afficher "La valeur ", val , " n'est pas dans le tableau"
FinSi

Recherche de zéros[modifier | modifier le code]

La recherche par dichotomie peut être appliquée à la recherche des zéros approchés d'une fonction continue : il s'agit de la méthode de dichotomie.

Champ d'application[modifier | modifier le code]

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 qu'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 six 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. Cela 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.