Dichotomie

Infos
En algorithmique, la dichotomie (« couper en deux » en grec) est 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 sens
Dichotomie

En algorithmique, la dichotomie (« couper en deux » en grec) est 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.

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 entier : début, milieu, fin, val Tnb : Tableau d'entier //initialisation début
Sujets connexes
Algorithmique   Continuité   Court-circuit   Diviser pour régner (informatique)   Espace de recherche   Méthode de dichotomie   Navigateur Web   Nombre cardinal   Objective Caml   Optimisation (mathématiques)   Processus itératif   Récursif   Stratégie   Test   Théorème des valeurs intermédiaires  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^