Dichotomie

Le cours qui suit est issu de : http://sciencesappliquees.com/

Introduction

Le fait qu'un tableau soit trié, par exemple par ordre croissant, facilite de nombreuses opérations.

L'une d'entre elles est la recherche d'un élément. En effet, il suffit de comparer la valeur recherchée avec la valeur située au milieu du tableau.

Si elle est plus petite, on peut restreindre la recherche à la moitié gauche du tableau. Sinon, on la restreint à la moitié droite du tableau.

En répétant ce procédé, on divise la zone de recherche par deux à chaque fois 1. Très rapidement, on parviendra soit à la valeur recherchée, soit à un intervalle devenu vide. On appelle cela la recherche dichotomique.

On connait tous ce principe, pour l'avoir appliqué étant enfant pour deviner un nombre en ayant comme réponses à nos tentatives "c'est plus petit" ou "c'est plus grand". Ce principe est connu en informatique sous le nom de diviser pour mieux régner et il est appliqué dans de nombreux algorithmes.

La recherche dichotomique en est l'expression la plus simple.

Mise en œuvre en Python

Pour fixer les idées, supposons que l'on souhaite définir une fonction qui recherche la valeur v dans le tableau t.

def recherche_dichotomique( t , v):

Le tableau t est supposé trié par ordre croissant. Cette fonction pourrait se contenter de renvoyer un booléen indiquant la présence de v dans t.

Cependant, on va faire un effort supplémentaire, en renvoyant une position dans le tableau t à laquelle se trouve la valeur v, le cas échéant. II se pose donc la question de savoir ce que va renvoyer notre fonction lorsque la valeur v n'apparait pas dans le tableau t.

On choisit ici de renvoyer la valeur None dans ce cas.

Pour mettre en œuvre la recherche dichotomique, on va délimiter la portion du tableau t dans laquelle la recherche est actuellement réduite à l'aide de deux indices g et d.

Initialement, ces deux indices délimitent l'intégralité du tableau.

g = 0

d = len(t) - 1

On peut se représenter la situation courante avec le petit dessin suivant.

0 g d

t = [éléments < v, .... ..........., éléments > v]

Le programme va alors répéter le principe de dichotomie tant que cette portion n'est pas vide, c'est-à-dire tant que la condition g <= d est vraie. On le fait avec une boucle while.

while g <= d:

# invariant : 0 <= g et d < len(a)

# invariant : v ne peut .se trouver que clans t

II faut maintenant examiner l'élément central pour prendre notre décision. On calcule sa position dans une variable m, en faisant la moyenne de g et d.

m = (g + d) // 2

Attention à bien utiliser ici la division entière, c'est-a-dire l'opération // et non pas l'operation /, sans quoi on pourrait obtenir des valeurs décimales comme 2.5 et ensuite une erreur lors de l'accès au tableau t.

Une fois la valeur de m calculée, ii faut se représenter ainsi la situation.

0 g m d

t = [éléments < v, ...... , ? , ...... éléments > v]

On va maintenant comparer v à t[m] et il y a trois cas possible pour la valeur v :

- v est plus grande;

- v est plus petite;

- v est égale à la valeur t[m].

Si elle est plus grande, alors la recherche peut se restreindre à la moitié droite.

On modifie donc la valeur de g en conséquence.

if t[m] < v:

g = m + 1

Si en revanche elle est plus petite, on se restreint à la moitié gauche.

On modifie donc la valeur de d en conséquence.

if t[m] > v:

d = m - 1

Si enfin les deux valeurs sont egales, c'est qu'on a trouve une occurrence de la valeur v.

On renvoie alors l'indice m comme résultat de la fonction.

else :

return m

Il se peut qu'on finisse par sortir de la boucle, parce que la condition g <= d n'est plus vraie. Cela signifie que la valeur v ne peut pas se trouver dans le tableau, car il ne contient plus que des valeurs strictement plus petites que v (à gauche) ou strictement plus grandes (à droite).

On renvoie alors None pour signaler l'échec de notre recherche dichotomique.

return None

Le code complet est donc le suivant :

def recherche_dichotomique(t, v):

    """renvoie une position de v dans le tableau t,

    supposé trié, et None si v ne s'y trouve pas"""

    g = 0

    d = len(t) - 1

    while g <= d:

        # invariant : 0 <= g et d < len(t)

        # invariant : v ne peut se trouver que dans t[g. d]

        m = (g + d) // 2

        if t[m] < v:

            g = m + 1

        elif t[m] > v:

            d = m - 1

        else:

            return m

    # la valeur ne se trouve pas dans le tableau 

    return None

Correction

Vérifions que le programme de dichotomie est correct.

Commençons par montrer que le programme ne va pas échouer en accédant au tableau t en dehors de ses bornes. Le seul accès au tableau t se fait à l'indice m, dans la boucle while. Cet indice m est calcule comme la moyenne (arrondie vers le bas) de g et d, dont on sait qu'ils vérifient l'inégalité g <= d car on est dans la boucle. Par ailleurs, l'inégalité 0 < g est un invariant de boucle, de même que l'inégalité d < len(t). Par conséquent, à l'intérieur de la boucle, on a toujours

0 < g < m < d <len(t)

cc qui garantit un accès légal au tableau t. Lorsque g ou d est modifié dans la boucle, on peut vérifier que les inégalités 0 < g et d < len(t) sont bien préservées.

L'étape suivante consiste à montrer que, si on renvoie un entier, alors ii s'agit bien d'une position où la valeur v apparait. C'est ce que l'on appelle la correction de l'algorithme. C'est immédiat, car l'instruction return m n'est effectuée que lorsque l'égalité t[m] = v est vérifiée. En effet, on vient de vérifier que les deux conditions t[m] < v et t[m] > v sont fausses.

II faut également montrer que, si on renvoie la valeur None, alors la valeur v n'apparaît pas dans le tableau t (sans quoi il suffirait de toujours renvoyer None). C'est ce que l'on appelle la complétude de l'algorithme. Elle est mêms évidente que la correction. En effet, nous pourrions avoir raté des éléments du tableau t par accident, par exemple si nous avions écrit g = m + 2 au lieu de g = m + 1. Pour montrer la complétude, on identifie l'invariant de boucle suivant :

la valeur v ne peut se trouver que dans t[g...d] .

C'est vrai initialement, car g et d sont initialisées à 0 et len(t) - 1 respectivement. Lorsque g ou d est modifié dans la boucle, on peut vérifier que cet invariant est bien préserve. Dans le premier cas, on a t[m] < v et on effectué g = m + 1. Or, le tableau étant trié, on a donc

t [g . .m-1] < t [m] <v

et donc la valeur v ne peut pas se trouver dans t[g..m] .

Elle ne peut donc se trouver que dans t [m+1 . d], c'est-à-dire t[g.. d]. On raisonne de même lorsque t[m] > v et que d prend la valeur m - 1.

Enfin, il convient de montrer que notre programme ce termine toujours. Si par exemple nous avions écrit

g = m au lieu de g = m + 1, alors absolument tout ce que nous venons de démontrer ci-dessus resterait valable, mais le programme ne se terminerait plus dans certains cas. Pour montrer que notre programme se termine toujours, on peut remarquer que la valeur entière d — g est un variant:

elle décroit d'au moins une unité à chaque itération de la boucle while, tout en restant positive ou nulle (car g < d dans la boucle).

Elle ne peut décroitre infiniment. On finira donc par avoir d < g et une sortie de boucle, si on n'a pas trouvé la valeur v avant cela.

Efficacité

Le temps d'exécution de recherche_dichotomique est directement proportionnel à ce nombre.

Plaçons-nous dans le pire cas, lorsque la valeur v n'apparait pas dans le tableau t, ce qui nous oblige à répéter la boucle jusqu'à ce que l'intervalle soit vide. Prenons l'exemple d'un tableau de taille 100.

A la première itération, on va se restreindre à un sous-tableau contenant 49 ou 50 éléments, selon le coté choisi.

Prenons le cas le moins favorable, avec 50 éléments.

A la seconde itération, on va se retrouver avec au plus 25 éléments, puis au plus 12 à la suivante, et ainsi de suite.

Au total, on ne fera jamais plus de 7 tours de boucle. II suffit donc d'examiner au plus 7 valeurs parmi les 100. De la même manière, on peut montrer que 20 itérations sont toujours suffisantes, dans le pire des cas, pour rechercher une valeur dans un tableau d'un million d'éléments.

On peut le déterminer empiriquement en répétant des divisions par deux en partant d'un million, jusqu'à obtenir 0.

Inversement, et plus rigoureusement, on peut chercher la plus petite puissance de 2 qui dépasse la taille du tableau.

Ainsi, les valeurs données ci-dessus s'expliquent par 2⁷ > 100 et 2²⁰ > 10⁶.

De manière générale, pour un tableau t de taille n, le temps d'exécution de recherche_dichotomique(t, v) est dans le pire des cas égal au plus petit entier k tel que :

2^k > n.

Le tableau ci-dessous donne quelques valeurs de k en fonction de n.

n k

10 4

100 7

1 000 10

1 000 000 20

1 000 000 000 30

Comme on le constate, le nombre k d'étapes croit très lentement avec la taille n du tableau.

II existe une fonction mathématique, appelée logarithme, qui permet d'exprimer et de calculer k à partir de n. Mais elle n'est pas au programme de mathématiques de première général.

Pour 1 milliard d'éléments, on a seulement besoin d'examiner 30 valeurs dans le pire des cas, ce qui veut dire que notre recherche dichotomique sera instantanée. C'est donc là un algorithme extrêmement efficace.

Le cours qui suit est issu de : https://www.numerique-sciences-informatiques.fr/

Méthode dichotomique

Vous avez probablement joué au jeu 'trouve un nombre entre 1 et 100' et proposé 50. Si la réponse est 'perdu, c'est plus' vous proposez 75 et si l'on vous répond 'perdu c'est moins' vous proposez 62...C'est une recherche dichotomique !

Faire une recherche dichotomique, c'est chercher une valeur dans un tableau en prenant le milieu de l'ensemble des solutions possibles (qui sont donc rangées) pour éliminer la moitié des possibilités à chaque étape.

On utilise cette méthode pour résoudre f(x)=0 sur des fonctions strictement croissantes.

L'algorithme itératif

Voici l'algorithme itératif de la recherche dichotomique dans un tableau trié par ordre croissant. Itératif car on va utiliser une boucle. Il existe un algorithme récursif (fonction qui s'appelle elle même) que nous verrons en terminale.

➦ mettre debut à 0

➦ mettre fin à taille du tableau

➦ mettre trouve à Faux

➦ cherche est la valeur cherché

➦ tant que pas trouve et debut< fin

➦   index_milieu reçoit la partie entière de ()(debut+fin)/2)

➦   si liste[milieu] ==cherche

➦     trouve reçoit Vrai

➦   sinon

➦     si cherche>liste[milieu]

➦       debut reçoit milieu+1

➦     sinon

➦       fin reçoit milieu

➦ si trouve

➦   affiche milieu

➦ else

➦   affiche 'valeur non trouvée'

A vous de coder cela en python ou pourquoi pas en javascript dans une page html avec un formulaire qui demande la valeur min et max et longueur de liste. Puis qui construit et ordonne une liste de nombre. Le programme cherche ensuite une valeur aléatoire dans la liste et vous affiche les étapes (l'intervalle restant).

Terminaison : le variant de boucle

Puisque l'on a une boucle, on peut raisonnable s'interroger sur la terminaison de cet algorithme.

Dans le tant que, il y a la condition debut<=fin qui signifie que le tableau n'est pas vide. On va s'intéresser à la variable longueur=fin-debut qui est un entier. longueur est appelé un variant de boucle. Comme longueur décroit à chaque boucle, debut<=fin finira par être faux.

Pour prouver la terminaison d'une boucle on peut utiliser variant de boucle, cad un entier naturel qui décroit strictement à chaque itération.

Détaillons la preuve: on note E la fonction partie entière et on rappelle que E(x)<=x.

on note longueur_n la taille du tableau à l'étape n.

On passe à l'étape n+1:

• soit je trouve le nombre cherché, fin de l'algorithme
• soit fin=milieu-1. Alors
• longueur_n+1=fin_n+1-debut_n+1
• =E((fin_n+debut_n)/2)-1-debut_n≤ ((fin_n+debut_n)/2)-1-debut_n=longueur_n/2-1≤longueur_n-1< longueur_n.
• Donc longueur_n décroit dans ce cas.
• soit debut=milieu+1. Alors
• longueur_n+1=fin_n+1-debut_n+1
• =fin_n-(E((fin_n+debut_n)/2)+1)= fin_n-E((fin_n+debut_n)/2)-1.
• On utilise le fait que x-1< E(x) et donc -E(x)< 1-x. Du coup on a
• longueur_n+1 < fin_n +1 - (fin_n+debut_n)/2-1=longueur_n/2<=longueur_n.
• donc longueur_n décroit !
• Si longueur_n est strictement décroissante et est un entier naturel, cette variable finira par valoir 0 et l'algorithme par s'arrêter.

Complexité

La complexité est en log(n).

La démonstration ci-dessous n'est pas au programme de 1ère.

Soit un tableau de taille n, on note k le nombre d'opérations réalisées alors k est aussi le nombre d'itérations puisqu'il y a une opération par itération. La taille de l'intervalle de recherche est divisé par 2 à chaque itération, donc à l'étape k, l'intervalle mesure E(n/2^k) et, comme l'intervalle le plus petit a une longueur de 1, 1≤E(n/2^k)≤n/2^k.

Si on multiplie par 2^k on a: 2^k≤n.

En passant au logarithme décimal, on obtient: klog(2)≤log(n) donc k≤log(n)/log(2)=log₂(n).