Algo Dichotomie

Identification

Infoforall

7 - Recherche dichotomique

⏪

⏬

⏩

1 - Trier

2 - Principe

3 - Algo/coût

4 - Python

5 - Terminaison

6 - FAQ

Nous avons vu que parcourir un tableau élément par élément nécessite un algorithme dont le coût est linéaire : sa complexité est 𝓞(n).

Nous allons voir aujourd'hui comment faire mieux que cela mais sur un tableau particulier : un tableau trié.

La triche en informatique
C'est à partir d'ici qu'Alice triche !

Et oui, on peut tricher avec des données triées en ordre croissant.

  • La plus petite est dans la première case : t[0].
  • La plus grande est dans la dernière case : t[len(t)-1] ou même en Python t[-1].
  • On peut trouver si un élément est présent avec un coût logarithmique 2 !

Et c'est pour cela, qu'en informatique, on préfère travailler avec des données triées et placer au bon endroit une nouvelle donnée qui vient d'arriver plutôt que de la placer juste à la fin. On perd un peu de temps lors du placement, mais on en gagne bien plus ensuite...

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...

Evaluation ✎ : -

Documents de cours : open document ou pdf

1 - Trier un tableau avec Python

⇩ ⇧ ⤊

L'opération de tri est fondamentale en informatique.

Lorsqu'on sait qu'on va régulièrement devoir rajouter des données dans un tableau, il y a deux façons d'agir :

  1. On insère la nouvelle donnée à la fin du tableau
    • Avantage : opération de rajout très rapide
    • Désavantage : tableau non trié donc recherche ultérieure longue
  2. On insére la nouvelle donnée de façon à avoir un tableau trié
    • Avantage : tableau trié donc recherche par dichotomie possible et plus rapide
    • Désavantage : l'insertion est un peu plus longue à faire

Voici d'abord une fonction creer() qui génére un tableau aléatoire d'entiers compris entre 0 et 100. La fonction creer() crée le tableau par par compréhension. Cette méthode de création se comprend en allant de la droite vers la gauche.

  1. D'abord, on a une boucle qui sera réalisée nb fois.
    2. 10
    t = [random.randint(0,100) for x in range(nb)]
  2. Dans chacune des cases, on place un nombre au hasard entre 0 et 100.
    3. 10
    t = [random.randint(0,100) for x in range(nb)]

01° Placer la fonction proposée en mémoire et faire quelques appels dans la console pour vérifier son bon fonctionnement. Par exemple en créant des listes de 10 ou 50 éléments.

1 2 3 4 5 6 7 8 9 10 11
import random def creer(nb): """Fonction qui renvoie un tableau de nb éléments compris entre 0 et 100 :: param nb(int) :: un entier positif correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nb éléments compris entre 0 et 100 """ t = [random.randint(0,100) for x in range(nb)] return t
>>> creer(5) [81, 78, 52, 42, 25] >>> creer(5) [73, 62, 88, 69, 81]

Si on veut stocker le résultat fourni par la fonction, il faudra le stocker dans une variable.

>>> t1 = creer(5) >>> t1 [11, 34, 31, 56, 88]

Question : quelle est la précondition sur paramètre nb selon la documentation ?

...CORRECTION...

>>> help(creer) Help on function creer in module __main__: creer(nb) Fonction qui renvoie un tableau de nb éléments compris entre 0 et 100 :: param nb(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nb éléments compris entre 0 et 100

La précondition est donc que ce soit un entier et qu'il soit positif.

Un utilisateur pourrait envoyer un string, rien ne l'empêche. de faire cela. Mais si cela provoque une erreur, c'est de sa faute : il n'a pas respecté la précondition notée dans la documentation !

Voyons maintenant deux façons de trier les tableaux en utilisant les outils natifs de Python.

1 - Fonction native sorted()

La fonction native sorted() renvoie une copie triée du tableau transmis à la fonction.

Cela veut dire que le tableau originel n'est pas modifié : il est toujours dans le désordre.

>>> t = creer(10) >>> t [13, 55, 54, 57, 12, 80, 16, 72, 30, 99] >>> tab_trie = sorted(t) >>> tab_trie [12, 13, 16, 30, 54, 55, 57, 72, 80, 99] >>> t [13, 55, 54, 57, 12, 80, 16, 72, 30, 99]
  • Avantage : on garde en mémoire la configuration initiale des donnnées
  • Désavantage : ça prend deux fois plus de place en mémoire puisqu'il y a deux versions des données.
2 - Méthode des tableaux sort()

La méthode sort() modifie en place le tableau sur laquelle elle agit.

>>> t = creer(10) >>> t [13, 55, 54, 57, 12, 80, 16, 72, 30, 99] >>> t.sort() >>> t [12, 13, 16, 30, 54, 55, 57, 72, 80, 99]
  • Avantage : moins de place mémoire nécessaire
  • Désavantage : on ne connait plus l'état initial du tableau.

Attention à cette erreur courante

La méthode sort() ne renvoie rien, enfin si : None.

Taper ceci ne fait donc que remplacer votre tableau initial par une variable qui contiendra None :

>>> t = creer(10) >>> t [13, 55, 54, 57, 12, 80, 16, 72, 30, 99] >>> t = t.sort() >>> t

Ben voilà, c'est malin : t est vide !

Différencier facilement les deux

Voici un moyen mnémotechnique :

  • sorted : le tableau initial est toujours dans le désordre.
  • sort : le tableau initial est désormais trié.

02° Utiliser une instruction dans la console (une des deux façons de faire précédentes) pour obtenir une version triée du tableau ci-dessous. Fournir les instructions et le tableau trié.

t = [49, 13, 95, 90, 57, 82, 13, 59, 1, 11, 55, 25, 23, 66, 60, 76, 88, 10, 86, 60, 57, 35, 3, 62, 65, 22, 95, 33, 5, 76, 93, 24, 98, 16, 20, 70, 68, 47, 61, 19, 60, 6, 16, 37, 36, 96, 80, 28, 0, 54, 99, 65, 90, 71, 88, 41, 86, 81, 42, 38, 15, 62, 79, 46, 63, 100, 68, 45, 99, 41, 30, 91, 15, 77, 2, 83, 11, 52, 52, 7, 40, 29, 32, 32, 32, 17, 34, 42, 71, 73, 94, 75, 69, 30, 85, 98, 42, 34, 86, 54]

Le plus beau, c'est que ça fonctionne aussi avec les strings. On peut ainsi trier une liste de mots par ordre alphabétique (qu'on nomme aussi ordre lexicographique).

Comment fait Python ? Il suffit de regarder la valeur UNICODE du premier caractère et de trier par rapport à cette valeur. On obtient l'ordre alphabétique mais les majuscules sont prioritaires car A c'est 65, B c'est 66..., mais a c'est 97.

Ainsi un mot commençant par A passera avant un mot commençant par a.

UNICODE - Fonctions natives ord() et chr()

ASCII est une table de conversion qu'on peut considérer comme un standard. On travaille sur un octet et on dispose donc de valeurs allant de 0 à 255. La norme ASCII n'impose que les associations caractère-valeur de 0 à 127.

UNICODE est lui une simple association entre un nombre et un caractère. Il comporte quasiment tous les glyphes et caractères que l'humanité utilise. On ne préoccupe pas de savoir comment on encode concrétement ce nombre en mémoire. UNICODE est une simple association caractère-valeur. Nous verrons en fin d'année comment UTF-8 permet d'encoder la valeur UNICODE.

Fonction native ord()

En Python, on peut trouver la valeur UNICODE d'un caractère en utilisant la fonction native ord.

>>> ord('A') 65 >>> ord('B') 66 >>> ord('a') 97 >>> ord('z') 122 >>> ord('ç') 231

Ainsi, lorsque Python doit classer des mots, il place les mots commençant par ç après les mots en z puisque la valeur unicode du ç est supérieure à celle du z !

Fonction native chr()

C'est l'inverse : on lui donne un caractère et elle renvoie la valeur UNICODE correspondante.

>>> chr(65) 'A' >>> chr(231) 'ç' >>> chr(9821) '♝' >>> chr(9822) '♞' >>> chr(9823) '♟'

03° Utiliser le programme suivant qui

  • Ligne 01 : on place une phrase sans ponctuation en mémoire
  • Ligne 03 : on utilise la méthode split() sur ce string (en utilisant l'espace comme caractère séparateur) pour créer un tableau t contenant les mots de la phrase, un mot par case.
  • Ligne 04 : on utilise la fonction native sorted() pour créer un nouveau tableau trié t_trie, qui est donc une copie (triée) du tableau précédent.
  • Lignes 06+ : on utilise la fonction native print() pour afficher les deux tableaux.
1 2 3 4 5 6 7 8 9
phrase_sans_ponctuation = "Voici la phrase qui contient deux fois voici pour montrer que UNICODE ne traite pas de la même façon le V et le v" t = phrase_sans_ponctuation.split(' ') t_trie = sorted(t) print('Tableau initial :') print(t) print('\nTableau trié :') print(t_trie)

Questions

  1. Pourquoi les mots commençant par "V" sont-ils devant les mots commençant par "v" dans le tableau trié ?
  2. Pourquoi le mot "UNICODE" est-il devant le mot "contient" alors qu'on compare 'U" et "c" ?
  3. Pourquoi "V" est-il devant "Voici" ?

...CORRECTION...

Le plus simple pour répondre à cela est d'aller voir les codes UNICODE du V et du v.

>>> ord('V') 86 >>> ord('v') 118

Puisque l'ordinateur classe les caractères en fonction de l'UNICODE, le V va passer devant le v.

De la même façon, la valeur UNICODE du U est plus petite que la valeur UNICODE du c.

Tableau initial ['Voici', 'la', 'phrase', 'qui', 'contient', 'deux', 'fois', 'voici', 'pour', 'montrer', 'que', 'UNICODE', 'ne', 'traite', 'pas', 'de', 'la', 'même', 'façon', 'le', 'V', 'et', 'le', 'v'] Tableau trié : ['UNICODE', 'V', 'Voici', 'contient', 'de', 'deux', 'et', 'façon', 'fois', 'la', 'la', 'le', 'le', 'montrer', 'même', 'ne', 'pas', 'phrase', 'pour', 'que', 'qui', 'traite', 'v', 'voici']

Maintenant que vous savez trier des tableaux de nombres ou de caractères, nous allons voir comment faire des recherches plus rapides que de simples recherches linéaires.

2 - Principe de la recherche dichotomique

⇩ ⇧ ⤊

Voyons maintenant le fonctionnement de la dichotomie.

La condition de base pour pouvoir réaliser cette recherche est d'avoir un tableau trié qu'on notera t.

Nous l'avons déjà rencontré lors de l'activité 'Alice Déménage'. Il suffit de chercher au mileu des données restantes. Les données étant triées, on pourra supprimer de la zone de recherche soit toute la partie de gauche, soit toute la partie de droite.

04° Nous cherchons la position éventuelle de 40 dans un tableau trié de 20 cases indicés de 0 à 19.

On commence donc la recherche dans un intervalle d'indices [0;19].

On a donc les curseurs gauche et droite placés de cette façon : g vaut 0 et d vaut 19.

On peut donc faire une première recherche et le calcul de l'indice central donne :

c = (0+19)//2, soit c = 9.

g c d
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

On tombe donc sur une case centrale t[9] contenant 60.

Question :

Que doit-on faire maintenant ?

  1. Bouger le curseur de gauche en appliquant la formule g = c + 1 pour que g pointe la case 10 ?
  2. Bouger le curseur de droite en appliquant la formule d = c - 1 pour que d pointe la case 8 ?

...CORRECTION...

On voit que la case centrale t[9] contient 60.

Le tableau étant trié, il ne sert plus à rien de chercher 40 dans les cases dont l'indice est supérieur à 9 : elles contiennent nécessairement 60 ou plus.

Il faut donc bouger le curseur de droite.

On ne supprime rien : on déplace juste le curseur d en le plaçant à gauche du curseur central.

  • d = c - 1
    • et donc d devient égal à 8.
g d c
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

05° Deuxième recherche. Maintenant, on cherche dans l'intervalle d'indices [0;8].

  • g vaut 0
  • d vaut 8
  • donc c = (0+8)//2, soit c = 4.
    • g c d
    Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
    Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Question :

Que doit-on faire maintenant ?

  1. Bouger le curseur de gauche en appliquant la formule g = c + 1 pour que g pointe la case 5 ?
  2. Bouger le curseur de droite en appliquant la formule d = c - 1 pour que d pointe la case 3 ?

...CORRECTION...

On voit que la case centrale t[4] contient 18.

Le tableau étant trié, il ne sert plus à rien de chercher 40 dans les cases dont l'indice est inférieur à 4 : elles contiennent nécessairement 18 ou moins.

Il faut donc bouger le curseur de gauche pour limiter la recherche aux indices compris dans [5;8].

On ne supprime rien : on déplace juste le curseur g en le plaçant à droite du curseur central.

  • g = c + 1
    • et donc g devient égal à 5.
c g d
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

06° Troisième recherche. Maintenant, on cherche dans l'intervalle d'indices [5;8].

  • g vaut 5
  • d vaut 8
g d
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

3 questions :

  1. Calculer le nouvel indice central c à considérer
  2. Quelle est le contenu t[c] de la case c dans le tableau t ?
  3. Que vont devenir les valeurs des indices g et d ?

...CORRECTION...

On effectue le calcul suivant :

c = (5+8)//2, soit c = 6

Rappel : division normale 13 / 2 donne 6,5, mais division euclidienne 13 // 2 donne 6, la partie entière de 6,5.

On voit que la case centrale t[6] contient 37.

Le tableau étant trié, il ne sert plus à rien de chercher 40 dans les cases dont l'indice est inférieur à 6 : elles contiennent nécessairement 37 ou moins.

Il faut donc bouger le curseur de gauche pour limiter la recherche aux indices compris dans [7;8].

c g d
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

On ne supprime rien : on déplace juste le curseur g en le plaçant à droite du curseur central.

  • g = c + 1
    • et donc g devient égal à 7.

07° Quatrième recherche. Maintenant, on cherche dans l'intervalle d'indices [7;8].

  • g vaut 7
  • d vaut 8
g d
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

4 questions :

  1. Calculer le nouvel indice central c à considérer
  2. Quelle est le contenu t[c] de la case c dans le tableau t ?
  3. Que vont devenir les valeurs des indices g et  ?
  4. Qu'est-ce qui nous permet de savoir que la recherche est maintenant terminée ?

...CORRECTION...

On effectue le calcul suivant :

c = (7+8)//2, soit c = 7

Rappel : division normale 15 / 2 donne 7,5, mais division euclidienne 15 // 2 donne 7, la partie entière de 7,5.

On voit que la case centrale t[7] contient 59.

Le tableau étant trié, il ne sert plus à rien de chercher 40 dans les cases dont l'indice est supérieur à 7 : elles contiennent nécessairement 59 ou plus.

On ne supprime rien : on déplace juste le curseur d en le plaçant à gauche du curseur central.

  • d = c - 1
    • et donc d devient égal à 6.

Il faut donc bouger le curseur de droite pour limiter la recherche aux indices compris dans [7;6] !

d g
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

On voit qu'il ne sert plus à rien de chercher puisque le curseur de droite est maintenant plus petit que le curseur de gauche.

08° Deux questions :

  1. Combien de comparaisons entre t[c] et 40 avant de savoir que 40 n'est pas présent dans l'une des 20 cases ?
  2. Par combien divise-t-on à peu près le nombre de cases encore à fouiller à chaque étape ?

Pour vous aider, voici les différentes étapes sous forme d'animations :

Etape 1

L'intervalle de départ [ 0 ; 19 ] contient 20 éléments.

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Etape 2

On travaille maintenant que l'intervalle d'indice [0;8] qui contient 9 élements.

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Etape 3

On travaille dans l'intervalle [5;8] qui contient 4 éléments

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Etape 4 : Intervalle [7;8] qui contient 2 éléments

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Puisque d < g, il ne reste plus rien à explorer et nous n'avons pas trouvé notre élément.

Conclusion : 40 n'appartient pas à notre tableau.

...CORRECTION...

Le tableau contient 20 cases mais il ne faut que 4 recherches avant de conclure.

A chaque étape, on voit qu'on divise le nombre de cases restantes par la moitié des cases restantes plus 1 puisqu'on peut supprimer également la case centrale :

20 cases -> 9 cases -> 4 cases -> 2 cases -> 0 case.

09° Réaliser une recherche du nombre 50 dans le tableau à l'aide d'une recherche dichotomique.

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Elément 18 23 25 35 48 50 58 68 70 73 75 79 80 82 85 89

Description de l'étape 1

On travaille dans [0;15].

g = 0 et d = 15.

On a donc c = (0+15) // 2 = 7.

Puisque t[7] > 50, on peut arrêter de chercher sur les indices 7+.

On calcule donc d = c - 1 = 7 - 1 = 6.

Rédiger les étapes suivantes de la recherche dichotomique de 50 dans ce tableau.

...CORRECTION...

En image puis avec les explications :

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Elément 18 23 25 35 48 50 58 68 70 73 75 79 80 82 85 89

Etape 1

  • on considère  g = 0 .
  • on considère  d = 15 .
  • On calcule l'indice central à l'aide d'une division entière : (0+15)//2 donne 7. On aura donc  c = 7 .
  • Comme  t[7] = 69  et donc  t[7] > 50 , on "supprime" la partie droite en modifiant d.
  • On impose donc  d = 7 - 1 = 6 

Etape 2

  • on considère  g = 0 .
  • on considère  d = 6 .
  • On calcule l'indice central à l'aide d'une division entière : (0+6)//2 donne 3. On aura donc  c = 3 .
  • Comme  t[3] = 35  et donc  t[3] < 50 , on "supprime" la partie gauche en modifiant g.
  • On impose donc  g = 3 + 1 = 4 

Etape 3

  • on considère  g = 4 .
  • on considère  d = 6 .
  • On calcule l'indice central à l'aide d'une division entière : (4+6)//2 donne 5 On aura donc  c = 3 .
  • Comme  t[5] = 50 , on vient de trouver la bonne valeur.

10° Nous avons fait 3 comparaisons pour effectuer cette recherche de 50 dans le tableau de 16 cases. Deux questions :

  1. Combien de comparaisons aurait-on dû faire avec une recherche linéaire ?
  2. Quel est le coût d'une recherche classique case par case ?
  3. Combien de cases supprimées à chaque étape avec la recherche linéaire ?
  4. Le coût d'une recherche dichotomique est-il meilleur ou moins bon que le coût d'une recherche linéaire ?
  5. Quelle est la condition sur le tableau pour pouvoir profiter d'une recherche dichotomique ?

...CORRECTION...

  1. Il aurait fallu faire 16 comparaisons avec la recherche linéaire dans un tableau de 16 cases.
  2. Puisqu'on se rend compte qu'avec 100 cases, il aurait fallu 100 lectures, on peut dire que le coût de la recherche linéaire est ... linéaire.
  3. Avec une recherche linéaire, on ne supprime qu'une case à chaque étape.
  4. La recherche dichotomique a donc un meilleur coût puisqu'on supprime au moins la moitié des cases restantes à chaque étape.
  5. Mais pour cela, il faut que le tableau soit trié.

3 - Algorithme et coût

⇩ ⇧ ⤊

Vous avez normalement bien compris le principe général, à savoir :

  • TANT QUE g <= d ET qu'on n'a pas trouvé l'élément x
    • Rechercher l'indice central c puis lire t[c] de façon à séparer les trois cas suivants :
      • SI t[c] < : on supprime la partie gauche de la zone de recherche en utilisant g = c + 1
      • SI t[c] > : on supprime la partie droite de la zone de recherche en utilisant d = c - 1
      • SI t[c] = x : l'élément x est présent à la position c.

Nous allons maintenant écrire l'algorithme à utiliser de façon plus formelle. Pour l'instant, il faudrait encore réflechir avant d'écrire la fonction Python correspondante.

11° Regardez cette animation : nous cherchons la position éventuelle de x = 40 dans un tableau trié de 20 cases indicés de 0 à 19.

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Une fois que vous aurez vu le déroulé, regardez à nouveau l'animation en associant chaque étape au principe de déroulement de l'algorithme qu'on donne ci-dessous :

  • Etape 1  on initialise les variables en plaçant
    • le curseur g à 0
    • le curseur d à 19
    • la réponse r à -1 (valeur choisie pour l'échec de la recherche).
  • Etape 2 : TANT QUE (g <= d) ET que (r vaut -1) :
    • On calcule l'indice central en prenant le milieu c = (g + d) // 2.
    • SI t[c] > x cherché
      • on bouge le curseur de droite avec d = c - 1.
    • SINON SI t[c] < x cherché
      • on bouge le curseur de gauche avec g = c + 1.
    • SINON (c'est le 3e cas : t[c] vaut x)
      • r = c
  • Etape 3 : on renvoie r qui vaut donc soit -1, soit un indice positif correspondant à la position de x dans le tableau.

12° Pourquoi le TANT QUE est-il beaucoup plus adapté à la situation qu'un POUR dans cet algorithme ?

...CORRECTION...

Tout simplement car il s'agit bien d'une boucle non bornée : dès qu'on trouve l'élément cherché, on peut arrêter.

Algorithme de recherche dichotomique

But : fournir l'indice de la première occurrence trouvée d'un élément x dans un tableau t. La valeur de réponse de -1 indique l'absence de x dans le tableau.

Description des entrées / sortie

  • ENTREES :
    • x : un élément voulu qu'on tente de rechercher dans le tableau
    • t : un tableau trié contenant un ensemble d'éléments.
      • PRECONDITON : le tableau est trié en ordre croissant.
    • (entrée optionnelle selon le langage d'implémentation) longueur : le nombre d'éléments dans le tableau
  • SORTIE : un entier correspondant à un indice i du tableau tel que t[i] contient bien x, ou la réponse vide (-1 par exemple).
t  ⇒   RECHERCHER   ⇒ 
et indice ou "vide"
x

Algorithme

Dans l'algorithme ci-dessous, l'opérateur // désigne une division euclidienne.

    r ← -1

    g ← 0

    d ← longueur - 1

    TANT QUE (g <= d) ET (r vaut -1)

      c ← (g + d) // 2

      SI t[c] < x

        on modifie g pour "supprimer" la partie gauche

        g ← (c + 1)

      SINON SI t[c] > x

        on modifie d pour "supprimer" la partie droite

        d ← (c - 1)

      SINON

        x est l'élément de t[c] : on sort du TANT QUE en modifiant r

        r ← c

      Fin du Si

    Fin Tant que

    Renvoyer r

13° Répondre aux questions suivantes  :

  1. Quelle est la condition devenue fausse qui va provoquer l'arrêt du TANT QUE si x ne se trouve pas dans le tableau ?
  2. Que vaut r à la fin de l'algorithme si on ne trouve pas l'élément x  ?
  3. Quelle est la condition devenue fausse qui va provoquer l'arrêt du TANT QUE si x se trouve dans le tableau ?

...CORRECTION...

  1. Si x ne se trouve pas dans le tableau, on finira par ne plus avoir g <= d. Le TANT QUE ne pourra alors provoquer un nouveau tour de boucle.
  2. Dans ce cas, r contiendra toujours la valeur par défaut -1.
  3. Si on tombe sur une case t[c] qui contient x, la valeur de r va alors être modifiée à c, et donc la condition r vaut -1 ne sera plus vérifiée.

Maintenant que l'algorithme est bien formalisé, nous allons pouvoir étudier son coût.

Logarithme 2 d'un entier

Le logarithme base 2 est la fonction réciproque de la fonction exponentielle base 2.

Pour trouver sa valeur, il suffit d'écrire le nombre \(n\) voulu sous forme d'une puissance de 2. La valeur du logarithme base 2 est justement cette puissance :

Si on peut écrire \(n=2^{x}\) alors $$\log_{2}(n)=\log_{2}(2^{x})=x$$

$$\log_{2}(2)=\log_{2}(2^{1})=1$$

$$\log_{2}(4)=\log_{2}(2^{2})=2$$

$$\log_{2}(8)=\log_{2}(2^{3})=3$$

$$\log_{2}(16)=\log_{2}(2^{4})=4$$

$$\log_{2}(32)=\log_{2}(2^{5})=5$$

$$...$$

Exemple avec 16 (ou 24)

>>> import math >>> math.log2(16) # notez bien que 16 = 24 4.0

Exemple avec 32 (ou 25)

>>> import math >>> math.log2(32) # notez bien que 32 = 25 5.0

Exemple avec 64 (ou 26)

>>> import math >>> math.log2(64) # notez bien que 64 = 26 6.0

Exemple avec 17 (ou 24+1)

>>> import math >>> math.log2(17) 4.087462841250339

On voit donc que \(\log_{2}(17)\) est un nombre entre 4 et 5 car \(16\lt17\lt32\).

14° Trouver à l'aide de Python les valeurs des logarithmes base 2 de 128, 150 et 256.

Justifier ensuite les valeurs trouvées pour 128 et 256.

...CORRECTION...

>>> import math >>> math.log2(128) 7.0 >>> math.log2(150) 7.22881869049588 >>> math.log2(256) 8.0

On peut justifier très facilement les valeurs en remarquant que les fonctions logarithmes et exponentielles sont des fonctions réciproques :

$$\log_{2}(128)=\log_{2}(2^{7})=7$$

$$\log_{2}(256)=\log_{2}(2^{8})=8$$

Nombre d'étapes maximales de la recherche dichotomique

On divise à chaque fois le nombre d'éléments encore dans l'intervalle de recherche par 2, on peut prévoir le nombre maximal d'étapes dans le pire des cas lorsqu'on effectue une recherche par dichotomie.

Nous allons montrer que le nombre d'étapes correspond à 1 + l'arrondi inférieur du \(\log_{2}(n)\) où \(n\) représente le nombre d'éléments dans le tableau.

Si \(n\) est le nombre d'éléments du tableau, la recherche dichotomique se fait dans le pire des cas avec un nombre d'étapes correspondant à  : $$nbr\ d'étapes=\lfloor{\log_{2}(n)}\rfloor+1$$

L'arrondi inférieur est noté à l'aide des sortes de crochets orientés vers le bas autour du log2.

On voit donc immédiatement que la recherche dichotomique :

  • possède un coût logarithmique
  • possède une complexité en \(\mathcal{O}(\log_{2}(n))\) (car il s'agit bien du pire des cas, parfois on fait mieux encore)

Exemple avec un tableau de 16 valeurs

Description de la recherche dans le pire des cas (pas de chance, on tombe du côté où il reste le plus de cases à tester !)

  • Etape 1 : un tableau trié de 16 cases. On garde 8 cases et on supprime l'élément central et les 7 cases restantes.
  • Etape 2 : un tableau trié de 8 cases. On garde 4 cases et on supprime l'élément central et les 3 cases restantes.
  • Etape 3 : un tableau trié de 4 cases. On garde 2 cases et on supprime l'élément central et la case restante.
  • Etape 4 : un tableau trié de 2 cases. On garde 1 case et on supprime l'élément central.
  • Etape 5 : un tableau trié de 1 cases. C'est la dernière case à fouiller.

Conclusion : autant d'étapes que log2(16)+1.

$$\log_{2}(16)+1=\log_{2}(2^{4})+1=4+1=5$$

Exemple avec un tableau de 17 valeurs

Description de la recherche dans le pire des cas (pas de chance, on tombe du côté où il reste le plus de cases à tester !)

  • Etape 1 : un tableau trié de 17 cases. On garde 8 cases et on supprime l'élément central et les 8 cases restantes.
  • Etape 2 : un tableau trié de 8 cases. On garde 4 cases et on supprime l'élément central et les 3 cases restantes.
  • Etape 3 : un tableau trié de 4 cases. On garde 2 cases et on supprime l'élément central et la case restante.
  • Etape 4 : un tableau trié de 2 cases. On garde 1 case et on supprime l'élément central.
  • Etape 5 : un tableau trié de 1 cases. C'est la dernière case à fouiller.

Conclusion : autant d'étapes que l'arrondi inférieur de \(\log_{2}(17)+1\).

$$nbr\ d'étapes=\lfloor{\log_{2}(17)}\rfloor+1=\lfloor{4.0874}\rfloor+1=4+1=5$$

A titre d'exemple, sur un tableau trié d'un million de valeurs :

  • Recherche linéaire : 1 000 000 de cases à fouiller dans le pire des cas
  • Recherche dichotomique : 20 cases à fouiller dans le pire des cas !

    • $$nbr\ d'étapes=\lfloor{\log_{2}(1000000)}\rfloor+1=\lfloor{19.931568}\rfloor+1=19+1=20$$

>>> import math >>> math.log2(1000000) 19.931568569324174 >>> math.floor(math.log2(1000000)) + 1 20

15° Prévoir le nombre maximum de comparaisons pour trouver un élément dans un tableau trié de 10 millions d'éléments.

Sans faire le calcul, combien va-t-on avoir de comparaisons si le tableau passe à 20 millions d'éléments (le double) ?

...CORRECTION...

>>> import math >>> math.log2(10000000) 23.253496664211536

Nous pouvons donc écrire ceci :

$$nbr\ d'étapes=\lfloor{\log_{2}(10.000.000)}\rfloor+1=\lfloor{23.253496664211536}\rfloor+1=23+1=24$$

Si on double le nombre de données, on va juste rajouter une étape visant à revenir à ...10 millions de données ensuite.

Pour 20 millions de données, on monte donc à 25 étapes.

Si vous n'êtes pas convaincu, voici le calcul :

$$nbr\ d'étapes=\lfloor{\log_{2}(10.000.000)}\rfloor+1=\lfloor{24.253496664211536}\rfloor+1=24+1=25$$

Si vous voulez vous amuser à prévoir le nombre de coups sur différents exemples, voici un tableau automatisée où vous pouvez créer des valeurs aléatoires et faire une recherche sur une valeur donnée.

Valeur cherchée :

Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

4 - Implémentation en Python

⇩ ⇧ ⤊

Il reste à voir comment réaliser cela avec Python.

16° Implémenter l'algorithme en Python en utilisant l'algorithme fourni et en complétant le prototype de la fonction recherche_dicho(), jusqu'à passer le test automatique composé des deux assertions.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def recherche_dicho(t, x): """Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param t(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (int) :: l'indice de l'élément ou -1 .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE de façon croissante .. Précondition 3 :: x doit être du même type que les éléments du tableau """ pass test = [4, 40, 400, 4000] assert recherche_dicho(test, 400) == 2 assert recherche_dicho(test, 5) == -1
Rappel de l'algorithme (qu'il va falloir apprendre par coeur)

    r ← -1

    g ← 0

    d ← longueur - 1

    TANT QUE (g <= d) ET (r vaut -1)

      c ← (g + d) // 2

      SI t[c] < x

        on modifie g pour "supprimer" la partie gauche

        g ← (c + 1)

      SINON SI t[c] > x

        on modifie d pour "supprimer" la partie droite

        d ← (c - 1)

      SINON

        x est l'élément de t[c] : on sort du TANT QUE en modifiant r

        r ← c

      Fin du Si

    Fin Tant que

    Renvoyer r

La solution est dans la question suivante.

17° Utiliser le programme ci-dessous pour voir quelques résultats. Il incorpore la fonction recherche_dicho().

Question :

Quelle est la ligne qui provoque l'affichage purement pédagogique sur les différents intervalles étudiés lors du déroulement dans la fonction recherche_dicho() ?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
import random def creer(nb): """Fonction qui renvoie un tableau de nb éléments compris entre 0 et 100 :: param nb(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nb éléments compris entre 0 et 100 """ t = [random.randint(0,100) for x in range(nb)] return t def recherche_dicho(t, x): """Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param t(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (int) :: l'indice de l'élément ou -1 .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE de façon croissante .. Précondition 3 :: x doit être du même type que les éléments du tableau """ r = -1 g = 0 d = len(t) - 1 while g <= d and r == -1: print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if t[c] < x: g = c + 1 elif t[c] > x: d = c - 1 else: r = c return r if __name__ == '__main__': tab_test = sorted( creer(100) ) print(tab_test) numero = recherche_dicho(tab_test, 5) print(numero)

Voici quelques exemples :

[1, 2, 2, 4, 4, 5, 6, 7, 8, 8, 11, 12, 13, 15, 15, 16, 16, 17, 17, 18, 21, 21, 24, 24, 25, 25, 26, 27, 29, 31, 31, 32, 33, 34, 35, 38, 39, 42, 42, 45, 45, 46, 48, 49, 50, 52, 55, 56, 56, 58, 59, 61, 61, 61, 62, 62, 63, 64, 65, 66, 66, 67, 71, 74, 75, 75, 75, 76, 76, 76, 77, 78, 78, 83, 83, 83, 84, 84, 84, 85, 85, 86, 88, 88, 88, 88, 89, 90, 90, 90, 92, 93, 94, 94, 94, 94, 96, 97, 98, 100] Un tour de boucle avec l'intervalle [0; 99] Un tour de boucle avec l'intervalle [0; 48] Un tour de boucle avec l'intervalle [0; 23] Un tour de boucle avec l'intervalle [0; 10] 5

[0, 0, 1, 1, 2, 2, 3, 5, 6, 7, 7, 10, 12, 14, 16, 16, 17, 18, 18, 18, 19, 21, 23, 26, 26, 26, 29, 29, 31, 34, 34, 36, 37, 37, 38, 39, 41, 41, 42, 42, 43, 44, 44, 45, 45, 45, 46, 46, 47, 49, 50, 50, 51, 52, 52, 53, 54, 60, 60, 60, 66, 66, 68, 68, 70, 71, 71, 72, 73, 73, 74, 74, 75, 75, 78, 79, 80, 81, 82, 83, 85, 86, 86, 87, 88, 88, 89, 89, 89, 90, 90, 92, 93, 93, 95, 98, 99, 99, 100, 100] Un tour de boucle avec l'intervalle [0; 99] Un tour de boucle avec l'intervalle [0; 48] Un tour de boucle avec l'intervalle [0; 23] Un tour de boucle avec l'intervalle [0; 10] Un tour de boucle avec l'intervalle [6; 10] Un tour de boucle avec l'intervalle [6; 7] Un tour de boucle avec l'intervalle [7; 7] 7

18° Quelqu'un propose cette version. Elle fonctionne parfaitement bien.

  • Quel est son avantage par rapport à la version précédente ?
  • Quel est son désavantage par rapport à la version précédente ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def recherche_dicho(tableau, x): """Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param t(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (int) :: l'indice de l'élément ou -1 .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE de façon croissante .. Précondition 3 :: x doit être du même type que les éléments du tableau """ g = 0 d = len(tableau) - 1 while g <= d: print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if tableau[c] < x: g = c + 1 elif tableau[c] > x: d = c - 1 else: return c return -1

...CORRECTION...

Avantage : la fonction est plus facile à comprendre :

  • On a besoin que d'une seule condition pour le TANT QUE puisqu'on stoppe brutalement la boucle en utilisant un return à l'intérieur de la boucle.
  • Plus de nécessité de créer une variable de stockage de la réponse non plus du coup.

Désavantage : la fonction n'est plus "propre" algorithmiquement.

  • Elle va être plus compliqué de démontrer sa correction puisqu'on peut très bien sortir du TANT QUE sans aucun lien avec la condition affichée derrière le TANT QUE.
  • Elle possède deux portes de sortie à surveiller. Idem, la correction est d'autant plus complexe à démontrer et la postcondition devrait être vérifiée à deux endroits si on le voulait.

5 - Preuve de terminaison

⇩ ⇧ ⤊

Nous avions vu que le coût de la recherche dichotomique est logarithmique. Montrons maintenant que cet algorithme se termine.

Preuve de terminaison

La preuve de terminaison d'un algorithme permet d'affirmer qu'il s'arrête de façon certaine sur toutes les entrées valides qu'on lui fournit (c'est à dire les entrées respectant les préconditions).

Preuve de terminaison : si les deux propositions suivantes sont vraies alors la boucle s'arrête :

  • Proposition A : les boucles s'expriment sous la forme TANT QUE VARIANT > 0
  • Proposition B : le VARIANT est une suite d'ENTIERS strictement décroissante.

(A et B) implique alors que l'algorithme se termine.

Attention à la négation

(A et B) implique que l'algorithme s'arrête TOUJOURS.

NON (A et B) ou encore (NON A) ou (NON B) d'après De Morgan n'implique rien de particulier.
Il est possible que l'algorithme ne boucle jamais, boucle parfois ou boucle toujours.

19° Montrer que TANT QUE g <= d revient à écrire TANT QUE VARIANT > 0. On pourra même montrer que cela revient en réalité à écrire TANT QUE longueur_restante > 0

...CORRECTION...

 TANT QUE g <= d 

 TANT QUE 0 <= ( d - g ) 

 TANT QUE ( d - g ) >= 0 

 TANT QUE ( d - g ) > -1 

 TANT QUE ( d - g + 1) > 0 

Or que vaut justement cette grandeur d - g + 1 ?

Il s'agit de la longueur_restante de l'intervalle qu'on étudie.

g d
Indice 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Elément 18 23 25 35 48 50 58 68 70 73 75 79 80 82 85 89

Comme vous le voyez, prouver la terminaison revient à prouver que longueur_restante décroît strictement à chaque fois qu'on fait un tour de boucle.

C'est plutôt évident : que le nombre d'éléments soit pair ou impair, on supprime toujours de la recherche l'élément central s'il n'est pas le bon, en plus du côté gauche ou du côté droit.

  1. Cas où l'intervalle contient un nombre impair d'éléments : longueur vaut 2k+1 = k + 1 + k

    2. Avec k=3 :              

    Avec k=2 :            

    Avec k=1 :          

    Avec k=0 :         

    Quelque soit le cas, on supprimera bien au moins l'élément orange central de la recherche.

  2. Cas où l'intervalle contient un nombre pair d'éléments : longueur vaut 2k = (k-1) + 1 + k

    3. Avec k=3 :            

    Avec k=2 :          

    Avec k=1 :        

    Quelque soit le cas, on supprimera bien au moins l'élément orange central de la recherche.

    Conclusion : on supprime toujours au moins 1 élément à chaque tour de boucle TANT QUE.

20° Nous venons de montrer que les deux propositions suivantes sont vraies :

  • Proposition A : la boucle non bornée peut s'écrire sous la forme TANT QUE longueur_restanteN > 0
  • Proposition B : longueur_restanteN est une suite de valeurs entières diminuant d'au moins un élément à chaque tour de boucle

Conclure sur la terminaison de cet algorithme.

...CORRECTION...

L'algorithme se termine donc dans tous les cas puisque :

  1. sa boucle s'exprime sous la forme while un > 0
  2. avec un variant un qui correspond à une suite d'entiers strictement décroissante.

Or, nous savons que (1) + (2) implique que l'algoritme se termine.

On retrouve la même notion qu'avec PRECONDITON ⇒ POSTCONDTION.

Ici (P1 ET P2) ⇒ TERMINAISON veut dire que :

  • Si P1 et P2 sont vraies toutes les deux, TERMINAISON est vraie.
  • Si P1 ou P2 sont faux, on ne peut rien dire au sujet de TERMINAISON : la terminaison peut-être vraie ou fausse.

Question finale° Compléter la fonction à trou recherche_dicho() pour qu'elle réalise bien une recherche dichotomique.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def recherche_dicho(t, x): """Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param t(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (int) :: l'indice de l'élément ou -1 .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE de façon croissante .. Précondition 3 :: x doit être du même type que les éléments du tableau """ r = ... g = ... d = ... while ... and ...: c = ... if t[c] < ...: ... elif ...: ... else: ... return ...

6 - FAQ

⇩ ⇧ ⤊

J'ai également vu O(log2 n). C'est quoi ce truc ?

Il s'agit de la fonction logarithme (ici en base 2).

C'est une fonction extrêmement utile : on peut la voir en première approximation comme la fonction qui renvoie la puissance de 2 permettant d'écrire le nombre.

Quelques exemples avec Python

>>> import math >>> math.log2(1) 0.0

Pourquoi ? Simplement car 1 = 20. On renvoie 0.

>>> math.log2(2) 1.0

Pourquoi ? Simplement car 2 = 21. On renvoie 1.

>>> math.log2(4) 2.0

Pourquoi ? Simplement car 4 = 22. On renvoie 2.

>>> math.log2(8) 3.0

Pourquoi ? Simplement car 8 = 23. On renvoie 3.

Le mieux, c'est que cela fonctionne également avec les valeurs qui ne sont pas une puissance entière de 2 !

>>> math.log2(6) 2.584962500721156

Pourquoi ? Simplement car 6 = 22.584962500721156. On renvoie 2.584962500721156. Si vous avez bien compris l'activité sur les floats, vous devriez comprendre qu'il s'agit certainement d'une valeur approximative.

Il existe un logarithme pour toutes les bases possibles et imaginables.

Le logarithme base 10 donne ainsi log10(1000) = 3 puisque 1000 = 103

Ou encore le logarithme népérien ln qui est en lien avec la fonction exponentielle : ln(20) = 2.995732273553991 car on peut écrire

  • 20 = e2.995732273553991 ou encore
  • 20 = exp(2.995732273553991)

Et c'est lié au fait qu'avec un tableau de 1 million d'éléments, la méthode dichotomique ne prend qu'une vingtaine d'étapes au pire

Oui.

>>> math.log2(1E6) 19.931568569324174

Log et Lg, c'est différent ?

Oui.

Lorsqu'on parle simplement de log, on parle du log dans une base donnée. Si c'est rien n'est précisé, c'est certainement la base 10.

Habituellement, si on note juste log, on parle du log10.

Si on note lg(x), on parle de log2(x) dans un contexte informatique. Cela évite de noter log10(x). On note juste lg(x)

Attention donc au contexte dans lequel apparaît un logarithme.

Log et Ln, c'est différent ?

Oui.

Lorsqu'on parle simplement de log, on parle du log dans une base donnée. Si c'est rien n'est précisé, c'est certainement la base 10.

Lorsqu'on parle de ln, on parle du logarithme népérien en mathématiques. Vous le verrez en terminale.

Sauf que dans les documents informatiques, on parle souvent du logarithmique base 2. On devrait le noter log2 ou log2. Mais souvent, la complexité ou le coût apparaît sous la forme lg (voir au dessous) mais aussi parfois ln. Pourquoi ? Tout simplement car log2(x) = ln (x) / ln (2). ln 2 n'est donc qu'un coefficient multiplicateur. C'est un peu comme un coût en 0.5n3 qu'on noterait juste n3.

Attention donc au contexte dans lequel apparaît un logarithme.

Petit résumé des notations

On voit juste log : c'est certainement log10.

On voit juste lg : c'est certainement log2.

On voit juste ln : c'est le logarithme népérien.

Activité publiée le 05 04 2020
Dernière modification : 13 04 2024
Auteur : ows. h.


⏪

⏫

⏩