Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Dichotomie

En algorithmique, la dichotomie (du grec « couper en deux ») est un processus itératif de recherche où à chaque étape l'espace de recherche est restreint à l'une de 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é 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 (informatique) (en anglais, divide and conquer) appliquée au cas particulier de la recherche itérative d'une solution, où le traitement des sous-espaces exclus de la recherche et sa recombinaison peuvent être court-circuités.

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? ».

Autre exemple

Cette méthode est très efficace pour la recherche des zéros approchés d'une fonction à condition que la fonction soit approchée par une fonction linéaire au voisinage du zéro cherché:

Soit f(x) une fonction telle que:

• f(a) < 0
• f(b) > 0
• f est strictement croissante entre les points a et b (a < b)

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

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

A titre d'exemple, une implémentation simple de cet algorithme est donnée 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é à 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.

Par exemple, je rencontre un probléme lorsque je groupe 6 appareils. Cela tombe systématiquement en panne et je ne sais pas du quel cela provient. Par conséquent je les groupe par 3 et j'attends. Si des deux groupe tombent en panne je peut en déduire que cela vient d'une faiblesse du modèle de mes 6 appareils. Si un seul des deux groupes tombe en panne j'en déduit que c'est un appareil qui pose probléme, je n'ai plus qu'a grouper 2 des 3 appareils suceptible d'être la source de ma panne: en 3 temps maximum j'ai testé mes 6 appareils.