Recherches¶

11-02-2023

Objectifs

Travailler sur les listes.
Comparer les algorithmes de recherches sur les listes.
Utiliser un module de représentation graphique de données.

Implantation des algorithmes de recherche¶

Le module algo_recherches_squel.py fourni est à renommer en algo_recherches.py. Les exemples ne doivent pas être modifiés. Il faut compléter les fonctions de façon à ce que les doctests ne produisent plus d’erreurs.

Les fonctions suivantes sont à implanter dans le module algo_recherches.py fourni. Les docstring* sont fournies avec doctests. Vous devez faire en sorte que les tests n’échouent plus.

À réaliser

Implantez l’algorithme de recherche séquentielle dans une liste.
algo_recherches.recherche_sequentielle(x, liste, cmp=<function compare>)¶
Recherche séquentiellement un élément dans une liste.
Paramètres
x – (any) un élément

l – (list) une liste
Renvoie

(bool) True si x appartient à l, False sinon

CU

x doit être comparable aux éléments de l

Exemples
>>> recherche_sequentielle(1, []) False >>> l = list(range(10)) >>> recherche_sequentielle(5, l) True >>> recherche_sequentielle(5.5, l) False
Écrivez un prédicat est_triee prenant en paramètre une liste d’entiers, et qui renvoie True si la liste est triée, et False dans le cas contraire.
algo_recherches.est_triee(liste, cmp=<function compare>)¶
Paramètres
liste – (list) une liste

cmp – (function) une fonction de comparaison
Renvoie

(bool) True si la liste est triée, False sinon

CU

les éléments de l sont comparables avec cmp

Exemples
>>> est_triee([]) True >>> est_triee([1, 2, 3]) True >>> est_triee(list(range(10, 0, -1))) False
Implantez l’algorithme de recherche séquentielle dans une liste triée.
algo_recherches.recherche_sequentielle_triee(x, liste, cmp=<function compare>)¶
Recherche séquentiellement un élément dans une liste triée.
Paramètres
x – (any) un élément

l – (list) une liste
Renvoie

(bool) True si x appartient à l, False sinon

CU

x doit être comparable aux éléments de l, l est triée

Exemples
>>> recherche_sequentielle_triee(1, []) False >>> l = list(range(10)) >>> recherche_sequentielle_triee(5, l) True >>> recherche_sequentielle_triee(5.5, l) False
Implantez l’algorithme de recherche dichotomique dans une liste triée.
algo_recherches.recherche_dichotomique(x, liste, cmp=<function compare>)¶
Recherche par dichotomie d’un élément.
Paramètres
x – (any) un élément

l – (list) une liste
Renvoie

(bool) True si x appartient à l, False sinon

CU

x doit être comparable aux éléments de l, l est triée

Exemples
>>> recherche_dichotomique(1, []) False >>> l = list(range(10)) >>> recherche_dichotomique(5, l) True >>> recherche_dichotomique(5.5, l) False

La suite du TP est à réaliser dans un module comparaison_recherches.py

Construction de liste¶

L’expression suivante permet de créer la liste des entiers de 1 à 99
```
list(range(0, 100))
```

Compter le nombre de comparaisons¶

Pour compter le nombre de comparaisons effectuées par les différents algorithmes de recherche, nous allons une nouvelle fois utiliser le décorateur count du module ap2_decorators.

Pour compter le nombre de comparaisons effectuées par la fonction est_triee, il faut :

décorer la fonction de comparaison ;

initialiser le compteur associé à la fonction à 0 ;

appeler la fonction est_triee ;

lire la valeur associée au compteur.

Par exemple, en supposant que la fonction compare ait été décorée :

>>> compare.counter = 0
>>> est_triee(list(range(100)))
True
>>> compare.counter
99
>>> compare.counter = 0
>>> est_triee(list(range(99, -1, -1)))
False
>>> compare.counter
1

Le premier appel a nécessité 99 comparaisons ; le second une seule.

Comparaison des nombres de comparaisons effectuées par les trois fonctions de recherche.¶

L’objectif est de compter le nombre de comparaisons effectuées par les trois algorithmes de recherche, puis de comparer les résultats obtenus.

Cette comparaison doit s’effectuer sur des listes triées, et nous allons comparer les algorithmes pour des listes de longueurs variant de 1 à 100.

À réaliser

Définissez une constante
```
LONGUEURS_LISTES = (1, 2, …, 100)
```
cette constante contient les longueurs des listes dans lesquelles nous allons effectuer les recherches.
Écrivez une fonction entiers_aleatoires(n) prenant en paramètre un entier n et qui renvoie une liste \(\ell\) de longueur longueur n telle que \(\ell[i]\) est un entier aléatoire compris entre \(0\) et \(i\) (compris).
comparaison_recherches.entiers_aleatoires(n)¶
Renvoie une liste d’entiers aléatoires.

Paramètres

n – (int) un entier

Renvoie

(list) une liste l de longueur n telle que l[i] est

choisi au hasard dans l’intervalle entier [0, i] :CU: Aucune :Exemples:
>>> l = entiers_aleatoires(100) >>> all(l[i] in range(i+1) for i in range(len(l))) True
Utilisez votre fonction pour définir une liste

LISTE_ENTIERS = entiers_aleatoires(100).
Construisez une liste de nombres
```
comparaisons1 = [ n1, n2, , n100 ]
```
Où ni désigne le nombre de comparaisons effectuées par la fonction recherche_sequentielle pour rechercher l’élément LISTE_ENTIERS[i-1] dans la liste [0, 1, …, i]. Remarquez qu’il s’agit d’une recherche fructueuse.
Construisez de même deux listes comparaisons2 et comparaisons3 pour les deux autres fonctions de recherche dans le cas d’une recherche fructueuse.

Représentation graphique¶

Vous allez maintenant visualiser les données mesurées. Pour cela vous allez utiliser certaines fonctionnalités du module matplotlib.

À faire

Tapez la commande:
```
from matplotlib import pyplot as plt
```

Avant de tracer les courbes, commençons par un petit exemple. Supposons que l’on souhaite tracer une ligne brisée passant les points de coordonnées \(A(1, 2)\), \(B(2, 5)\), \(C(4, 0)\).

À faire

Au niveau de l’interpréteur Python tapez les commandes:

>>> abscisses = [1, 2, 4]
>>> ordonnees = [2, 5, 0]
>>> plt.plot(abscisses, ordonnees, color='blue')
>>> plt.show()

La commande plot construit la ligne \(ABC\). Et la commande show ouvre une fenêtre contenant le graphique produit.

Remarques :

la commande show est bloquante. Ceci signifie qu’il n’est
pas possible de continuer à interagir avec l’interpréteur Python tant que la fenêtre graphique n’est pas fermée.
Il existe d’autres couleurs comme par exemple : 'black', 'red', 'green', …

À réaliser

Tracez la courbe représentant le nombre de comparaisons effectuées par la fonction recherche_sequentielle en fonction de la longueur de la liste.

Tracez de même les deux autres courbes.

Il est possible d’obtenir les trois courbes sur un seul et même graphique. Il suffit pour cela d’appeler les trois méthodes plot avant la commande show.

La méthode savefig permet d’enregistrer le graphique produit sous forme d’un fichier image. Elle s’utilise à la place de show et prend en paramètre le nom du fichier :

>>> plt.savefig('recherches_fructueuses.png')

Produisez un graphique avec les trois courbes de recherches fructueuses. Cherchez comment ajouter une légende. Vous devez obtenir quelque chose comme la figure ci-dessous.
Expliquez pourquoi seules deux courbes sont visibles dans le graphique ci-dessus.
Produisez un graphique avec les trois courbes de recherches pour des recherches infructueuses (ajoutez par exemple 0.5 aux nombres cherchés).
Commentez les graphiques obtenus.

Recherches¶

Implantation des algorithmes de recherche¶

Construction de liste¶

Compter le nombre de comparaisons¶

Comparaison des nombres de comparaisons effectuées par les trois fonctions de recherche.¶

Représentation graphique¶

Table des matières

Sujet précédent

Cette page