19 - Cours - Parcours séquentiel et dichotomie

Parcours séquentiel d’une liste

Le parcours séquentiel d'une liste correspond à atteindre et observer un à un tous les éléments de la liste dans l'ordre.

Par exemple, pour chercher la présence d'une valeur dans une liste donnée, on peut parcourir séquentiellement la liste et comparer chaque élément à la valeur cherchée.

Rappels sur les listes

Une liste est une structure qui peut contenir des éléments.

On peut se représenter une liste comme des « cases » consécutives contenant des valeurs :

5	3	5

• Le nombre d’éléments d’une liste est appelée sa longueur, cette longueur est fixe.
• Les éléments d’une liste sont (en général) tous du même type (par exemple sont tous des entiers, ou tous des caractères, etc.). Ce n’est pas une obligation en Python, contrairement à d’autres langages.
• Chaque élément est repéré par un indice. Dans ce cours, on considèrera que les indices sont compris entre 0 et len(L)-1 si L est le nom la liste.
• La valeur de l’élément d’indice i est obtenu par la notation L[i].
• On change la valeur de l’élément d’indice i par affectation : L[i] = valeur.

Rappel sur le slicing

Soit L = [-1, 2, 4, 0, 12, 9]

• L[2:4] donne [4, 0]
• L[:3] donne [-1, 2, 4]
• L[3:] donne [0, 12, 9]

Tester si une liste est triée

La fonction est_triee(liste) prend en argument une liste d’entiers. Cette fonction doit renvoyer True lorsque tous les éléments de cette liste sont en ordre croissant, c’est-à-dire rangés du plus petit au plus grand. Compléter le code de cette fonction  (à faire en exercice) :

🐍 Script Python

  def est_triee(liste):
      """
      liste - liste d'entiers (list)

      Sortie : booléen - True si liste est triée en ordre croissant, False sinon.
      >>> est_triee([2, 6, 8, 9])
      True
      >>> est_triee([])
      True
      >>> est_triee([2, 3, 4, 1])
      False
      """
      pass
      ### A COMPLETER

Aide : Il suffit de parcourir chaque élément de la liste de l’indice 0 à l’indice le plus grand en vérifiant, pour chaque élément, qu’il est plus petit que celui qui le suit.

Exercice issu du sujet 0 :

Dichotomie

Origine

Etymologie du mot dichotomie : du grec ancien διχοτομία, dikhotomia (« division en deux parties »), mot lui-même composé de δίχα, díkha (« en deux ») et de τομός, tomós (« section, coupure »).

Problèmes de recherche d'élement

La recherche d’un élément dans une liste fait partie des problèmes fréquemment rencontrés en informatique. Lorsqu'on n'a pas d'information sur les éléments de la liste, on va faire une recherche séquentielle, qui parcourt tous les éléments de la liste du début à la fin.

Nombre de tours de boucles

Je cherche un nombre dans une liste triée de 100 nombres entiers de 1 à 100. Si j’utilise un parcours séquentiel dont le code est rappelé ci-dessous, de combien d’étape(s) aurai-je besoin dans le meilleur des cas ? Dans le pire des cas ? En moyenne ?

🐍 Script Python

  def chercher(liste, x):
      """ Renvoie True si x est dans la liste, False sinon
      liste: une liste (type list)
      x: un entier (type int)
      """
      for i in range(len(liste)):
          if liste[i] == x:
              return True
      return False # tous les éléments ont été parcourus sans trouver x

Recherche dans une liste triée

Lorsque la liste est triée, il existe des algorithmes de recherche plus performants que la recherche séquentielle.

Nous voulons donc chercher un élément dans une liste triée (dans l’ordre croissant).

Principe de la recherche dichotomique, exemples à la main

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 une liste en prenant le milieu de l’ensemble des solutions possibles (qui sont donc rangées) pour éliminer la moitié des possibilités à chaque étape.

Combien faut-il d’étape(s) avec cette stratégie pour deviner un nombre entier entre 1 et 100, au minimum ? Au maximum ?

Ainsi, dans le cas d’une liste triée, l’algorithme de dichotomie permet d’améliorer la performance de la recherche. Ce gain de performance sera d’autant plus notable lorsque le nombre d’éléments de la liste est important.

Algorithme de la recherche dichotomique

Voici le principe de la recherche dichotomique avec une liste triée dans l’ordre croissant :

• Si la liste est vide : répondre négativement, la recherche est finie.

• Sinon, trouver la valeur centrale de la liste (centre gauche si l’effectif est pair) et comparer cette valeur à l’élément cherché :

• si la valeur est celle que l’on recherche : répondre positivement, la recherche est finie ;

• sinon si la valeur est strictement plus petite que l’élément cherché, reprendre la procédure avec la seconde moitié de la liste ;

• sinon, reprendre la procédure avec la première moitié de la liste.

On recommence donc le procédé tant que la taille de la liste dans laquelle on cherche l’élément est supérieure ou égale à 1.

Cette méthode de recherche dichotomique est formalisée en 1946 par John Mauchly, physicien américain qui a participé à la conception de l’ENIAC, un des premiers ordinateurs. En revanche, l’idée d’utiliser une liste triée pour faciliter la recherche date de -220 av.J.C, à Babylone.

Exemples

Nous allons rechercher l’élément 5 dans la liste triée [1, 2, 5, 9, 10, 14, 17, 24, 41]

1	2	5	9	10	14	17	24	41
1	2	5	-	-	-	-	-	-
	-	5	-	-	-	-	-	-

Cherchons à présent l’élément 7 (qui est absent !) dans la même liste :

1	2	5	9	10	14	17	24	41
1	2	5	9	-	-	-	-	-
-	-	5	9	-	-	-	-	-
-	-	-	9	-	-	-	-	-

Questions sur la dichotomie (sujet 0)

Nombre d’étapes

Compléter le tableau ci-dessous donnant le nombre maximum d’étape pour chacun des deux algorithmes de recherche :

Taille de la liste	0	1	2	4	8	16	32	64	128	N
Recherche séquentielle
Recherche dichotomique

Remarque

Si N est une puissance de 2, par exemple \(N=2^k\), alors on dit que \(k\) est le logarithme en base 2 de \(N\). Tester par exemple dans la console Python :

🐍 Script Python

  >>> from math import *
  >>> log(128, 2)
  7.0

On a donc : \(log_2(128) = 7\), et \(log_2(256) = 8\), et en fait \(log_2(210) = 7,7\).

Autrement dit, l’arrondi supérieur du \(log\) en base d’un entier \(n\) est le nombre de chiffres utilisés pour représenter \(n\) en base 2.

Le log est toujours lié à une base, les plus utilisées sont \(2\) et \(10\), et pour les mathématiciens, il y a également \(e\) qui est la base du logarithme népérien, mais nous ne nous en occuperons pas ici.

!!! "Attention" Sur une calculatrice “ln” est le logarithme népérien (en base \(e\)), et “log” est par défaut le logarithme en base \(10\). On passe du log en base \(2\) au log en base \(10\) à une multiplication près : \(log_{2}(n) = \dfrac{log_{10}(n)}{log_{10}(2)}\).

Implémentation

Pour les élèves à l’aise, essayer d’implémenter en Python, via une fonction, la recherche dichotomique. Aide pour les élèves moins à l’aise :

🐍 Script Python

  def recherche_dichotomique(liste, element):
      """
      liste doit être triée dans l'ordre croissant
      Renvoie True si l'élément est dans la liste, False sinon
      """
      indice_debut = #... (compléter)
      indice_fin = #... (compléter)
      while indice_debut <= indice_fin:
          indice_centre = (indice_debut+ indice_fin) // 2
          valeur_centrale = #... (compléter)
          if valeur_centrale == element: # element est trouvé !
              return #... (compléter)
          elif valeur_centrale < element:# on cherche dans la seconde moitié
              indice_debut = indice_centre + 1
          else:# on cherche dans la première moitié
              indice_fin = indice_centre - 1
      return #... (compléter)# element non trouvé

  L = [1, 2, 5, 9, 10, 14, 17, 24, 41]
  print(recherche_dichotomique(L, 5))
  print(recherche_dichotomique(L, 7))

Modifier la fonction précédente afin qu’elle renvoie l’indice de l’élément si il est trouvé, et False sinon.