Recherches

04-04-2022

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.

  1. Implantez l’algorithme de recherche séquentielle dans une liste.

    algo_recherches.recherche_sequentielle(x, l, cmp=<function compare>)
    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
    
  2. É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.

  3. Implantez l’algorithme de recherche séquentielle dans une liste triée.

    algo_recherches.recherche_sequentielle_triee(x, l, cmp=<function compare>)
    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
    
  4. Implantez l’algorithme de recherche dichotomique dans une liste triée.

    algo_recherches.recherche_dichotomique(x, l, cmp=<function compare>)
    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

  1. L’expression suivante permet de créer la liste des entiers de 1 à 99

    list(range(0, 100))
    

    Écrivez cette expression sous la forme d’une chaîne de caractères, puis écrivez une expression de type str permettant de faire varier l’élément maximal.

    On pourra utiliser les chaînes formatées de python

    >>> n = 5
    >>> f"le nombre n vaut {n}"
    

    “le nombre n vaut 5”

Le module timeit

Vous allez maintenant utiliser une fonction qui permet de mesurer le temps d’exécution d’une instruction. Cette fonction se nomme timeit et elle est définie dans le module du même nom timeit.

Pour l’utiliser il suffit de taper la commande

from timeit import timeit

Vous allez utiliser cette fonction avec trois paramètres nommés stmt, setup et number :

  • le paramètre stmt (abbréviation de statement, terme anglais pouvant être traduit par instruction) est une chaîne de caractères représentant une instruction Python dont on veut mesurer le temps d’exécution ;

  • le paramètre setup est une chaîne de caractères représentant aussi du code Python à exécuter préalabement au code décrit par le paramètre précédent ;

  • le paramètre number est un nombre entier indiquant le nombre de fois que l’instruction décrite par stmt doit être exécutée.

Cette fonction renvoie le temps, exprimé en secondes, que l’instruction stmt a pris pour être exécutée number fois.

Par exemple, voici comment obtenir le temps mis pour calculer le carré d’un nombre (ici 12345) un million de fois

>>> timeit(stmt='a*a',
           setup='a=12345',
           number=1000000)
0.09580526201170869

La réponse obtenue dans ce cas est un peu moins d’un dixième de seconde (bien entendu ce nombre peut dépendre de la machine utilisée).

  1. En utilisant cette fonction, déterminez le temps que Python met pour calculer sur votre poste de travail le nombre \(\frac{1+\sqrt{5}}{2}\) dix millions de fois. Vous aurez besoin de mettre dans le paramètre setup l’importation de la fonction racine carrée.

Comparaison des temps d’exécution des trois fonctions de recherche.

Vous allez comparer les temps d’exécution des trois algorithmes de recherche.

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.

  1. Définissez une constante

    LONGUEURS_LISTES = (1, 2, …, 100)
    

    cette constante contient les longueurs des listes dans lesquelles nous allons effectuer les recherches.

    Définisssez également une constante

    NOMBRE_EVAL = 100
    

    Le paramètre number de la fonction timeit sera initialisé avec cette constante.

  2. É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)
    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).

  3. Construisez une liste de nombres

    temps1 = [ t1, t2, , t100 ]
    

    ti désigne le temps mis 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.

    Il vous faudra initialiser le paramètre setup de la méthode timeit avec l’instruction permettant de charger la méthode recherche_sequentielle : setup = "from algo_recherches import recherche_sequentielle"

  4. Construisez de même deux listes temps2 et temps3 pour les deux autres fonctions de recherche dans le cas d’une recherche fructueuse.

Représentation graphique

Vous allez maintenant visualiser les temps calculés. Pour cela vous allez utiliser certaines fonctionnalités du module matplotlib.

  1. Tapez la commande:

    from matplotlib import pyplot as plt
    

Avant de tracer les temps, 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', …

  1. Tracez la courbe obtenue pour les temps de la fonction recherche_sequentielle.

    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 de faire les trois commandes plot avant la commande show.

  1. 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.

    Temps de recherches par les trois méthodes
  2. Produisez un graphique avec les trois courbes de recherches pour des recherches infructueuses (ajoutez par exemple 0.5 aux nombres cherchés).

  3. Commentez les graphiques obtenus.