TP2-PROG-03 : Approche pratique de la complexité : Recherche

complexite

TP2-PROG-03 : Approche pratique de la complexité : Recherche#

Objectifs pédagogiques#

  • être capable de comprendre plusieurs algorithmes différents pour le problème de la recherche d’un élément dans une liste triée comme :

    • recherche linéaire

    • recherche dichotomique

  • être capable de comprendre les programmes en Python qui implémentent ces algorithmes

  • mesurer la performance des algorithmes

  • déduire le comportement asymptotique et la complexité

Algorithmes de recherche#

Les quatre algorithmes de recherche étudiés répondent tous au même problème à résoudre : trouver un nombre aléatoire dans des nombres triés entre une borne inférieure borneInf et une borne supérieure borneSup

Afin de les comparer, nous calculons le nombre de comparaisons qu’il faut effectuer. Cette grandeur est nommée N tout au long du TP. C’est ce N que nous allons comparer.

Recherche linéaire#

L’algorithme est le plus simple :

  1. On choisi un nombre aléatoire qu’il faut rechercher: atrouve

  2. On initialise une variable nombre = borneInf :

    • si nombre == atrouve, alors on arrête

    • sinon, on passe au nombre suivant

    • tout cela est fait tant que nombre != borneSup

L’algorigramme est le suivant :

RechercheLineaire

# Recherche linéaire commentée
# Vincent Keller, 2023
# Importation de la bibliothèque random (nombres aléatoires)
import random
# Input borneInf
borneInf = 0
# Input borneSup
borneSup = 100
# variable atrouver : nombre aléatoire de type entier compris entre borneInf et borneSup (compris)
atrouver = random.randint(borneInf,borneSup)
# N est la variable qui contiendra le nombre de comparaisons
N = 0
# nombre est la variable qui contient l'itérateur entre borneInf et borneSup
nombre = 0
# trouve est une variable de type booléen.
trouve = False
# Boucle "tant que la variable trouve n'est pas égale à True)
while (trouve!=True):
    # Si le nombre est égal à celui à trouver (atrouver), alors la variable trouve devient True
    if (nombre==atrouver):
        trouve=True
    # on incrémente l'itérateur
    nombre = nombre + 1
    # On incrémente le nombre de comparaisons
    N = N + 1
# Output : affichage du nombre à trouver et du nombre de comparaisons
print("Nombre d'opérations pour trouver "+str(atrouver)+" : "+str(N))

Nombre d'opérations pour trouver 97 : 98

Recherche dichotomique#

L’algorithme est le suivant :

  1. On choisi un nombre aléatoire qu’il faut rechercher: atrouve

  2. On initialise une variable booléenne trouve = False

  3. On initialise une variable bmax = borneSup

  4. On initialise une variable bmin = borneInf

  5. Tant que trouve != True :

    • on calcule la moitié des nombres : moitie = int((bmax+bmin)/2)

    • si moitie == atrouve, alors on arrête : trouve = True

    • sinon si moitie > atrouver, alors bmax = moitie

    • sinon si moitie < atrouver, alors bmin = moitie

L’algorigramme est le suivant :

RechercheDichotomique

# Recherche dichotomique commentée
# Vincent Keller, 2023

# Importation de la bibliothèque random (nombres aléatoires)
import random
# Input borneInf
borneInf = 0
# Input borneSup
borneSup = 100
# variable atrouver : nombre aléatoire de type entier compris entre borneInf et borneSup (compris)
atrouver = random.randint(borneInf,borneSup)
# N est la variable qui contiendra le nombre de comparaisons
N = 0
# trouve est une variable de type booléen.
trouve = False
# déclaration de la variable bmax qui contient la borne supérieure temporaire après division par 2
# A l'initialisation, elle contient la borne supérieure globale borneSup
bmax = borneSup
# déclaration de la variable bmin qui contient la borne inférieure temporaire après division par 2
# A l'initialisation, elle contient la borne inférieure globale borneInf
bmin = borneInf
# Boucle "tant que la variable trouve n'est pas égale à True)
while (trouve!=True):
    # on calcule l'élément à la moitié des deux bornes temporaires
    moitie = int((bmax+bmin)/2)
    # si moitie est égal au nombre à trouver, on sort de la boucle
    if (moitie == atrouver) :
        trouve=True
    # sinon, si le nombre à trouver est situé avant de la moitié, alors la borne supérieure
    # temporaire devient moitie
    elif (moitie > atrouver) :
        bmax = moitie
    # sinon, si le nombre à trouver est situé au-delà de la moitié, alors la borne inférieure
    # temporaire devient moitie
    elif (moitie < atrouver) :
        bmin = moitie
    # On incrémente le nombre de comparaisons
    N = N + 1
# Output : affichage du nombre à trouver et du nombre de comparaisons
print("Nombre d'opérations pour trouver "+str(atrouver)+" : "+str(N))

Nombre d'opérations pour trouver 44 : 6

Exercice 1 : Trace#

Sur une feuille de papier, construisez la trace des deux algorithmes en établissant le tableau de toutes les valeurs des variables avec les valeurs suivantes : borneInf = 0, borneSup = 16, atrouver = 7

Exercice 2 : Enregistrement des codes#

  • copiez-collez les 2 programmes dans un dossier TP2 sur votre volume personnel

Vous devriez vous retrouver avec deux fichiers :

  • recherche_lineaire.py

  • recherche_dichotomique.py

Exercice 3 : Complexité d’un algorithme#

Rappel : la complexité d’un algorithme se déduit de l’équation qui décrit le nombre d’opérations (ou d’instructions N (durnat ce TP, N représente le nombre de comparaisons) en fonction de la taille du problème b. Dans cet exercice nous allons trouver la fonction f de l’équation N = f(b)

  • Choisissez un algorithme de recherche parmi les 2 codes

  • observez la variable qui fait varier la taille du problème. Cela sera la variable b

  • Modifiez votre code pour qu’il mesure des valeurs de N entre borneInf = 0 et une borne supérieure variable b

    • de 100 à 10000

  • Dans un classeur Excel, reportez les valeurs de N en fonction de b

  • Décrivez la complexité de l’algorithme

Attention : pour pouvoir copier-coller les valeurs dans Excel, vous devriez afficher les valeurs de Ǹ en fonction de b, utilisez la fonction suivante :

print(b,"\t",N)

Exercice 4 : Moyenne caractéristique#

Afin d’obtenir des grandeurs caractéristiques, il est utile d’obtenir différentes valeurs dont on prendra la moyenne.

  • Pour chaque algorithme, écrivez une boucle qui calcule une moyenne de 10 nombres aléatoires à trouver

  • Testez pour chacun des 2 algorithmes

Par exemple :

import random
borneInf = 0
borneSup = 100
somme = 0
# initialiser l'itérateur i à 0
i = 0
# Exécuter 10 fois le même algorithme de recherche
while i < 10:
    atrouver = random.randint(borneInf,borneSup)
    N = 0
    nombre = 0
    trouve = False
    while (trouve!=True):
        if (nombre==atrouver):
            trouve=True
        nombre = nombre + 1
        N = N + 1
    somme = somme + N
    # Ajouter l'incrémentation de l'itérateur i !
    i = i + 1
print("Nombre moyen pour la recherche linéaire : "+str(somme/10))

Nombre moyen pour la recherche linéaire : 55.3

Exercice 5 : Comparaison des algorithmes#

Modifiez les 2 implémentations des algorithmes de recherche. Il est maintenant possible de les comparer avec les mêmes bornes borneInf, borneSup et le nombre aléatoire à trouver atrouver

  • Modifiez votre code afin de mesurer les valeurs de N entre borneInf = 0 et différentes valeurs de borneSup :

    • 100 à 100000 avec un pas de 200

  • Dans un graphique Excel, notez toutes les valeurs sur 5 colonnes : borneSup, et les 2 N retournés pour chaque algorithme

    • N_lin est la variable contenant le nombre de comparaisons pour la recherche linéaire

    • N_dic est la variable contenant le nombre de comparaisons pour la recherche dichotomique

Exercice 6 : Comportement asymptotique de la complexité des algorithmes#

Le comportement asymptotique représente le comportement de la fonction mathématique décrivant la complexité d’un algorithme. Dans le pire des cas, c’est celui qui est décrit par la notation Big O ou \(\mathcal{O}\).

Par exemple : \(\mathcal{O}(n)\) est un comportement linéaire, \(\mathcal{O}(n^2)\) est quadratique, \(\mathcal{O}(n\log{}n)\) est linéarithmique, etc..

  • A l’aide de votre graphique Excel, êtes-vous capable d’estimer une fonction qui passerait par les points mesurés ?

  • Si oui, lesquelles ?

  • Sinon pourquoi ?

Exercice 7 (pour aller plus loin) : 2 nouveaux algorithmes#

Il existe deux autres algorithmes pour le problème de la recherche d’un élément dans une liste :

  1. La recherche aléatoire avec remise

  2. La recherche aléatoire sans remise

Suivez le même processus avec ces deux nouveaux algorithmes

Recherche aléatoire avec remise#

L’algorithme est le suivant :

  1. On choisi un nombre aléatoire qu’il faut rechercher: atrouve

  2. On choisi un nombre aléatoire : nombre

  3. tant que nombre != atrouve :

    • si nombre == atrouve, alors on arrête

    • sinon, choisi un nouveau nombre aléatoire : nombre

On note que cet algorithme peut faire ressortir plusieurs fois le même nombre aléatoire. C’est pourqoi il s’appelle recherche aléatoire avec remise.

L’algorigramme est le suivant :

RechercheAleatoireAvecRemise

# Recherche aléatoire avec remise dans une liste triée commentée 
# Vincent Keller, 2023
# Importation de la bibliothèque random (nombres aléatoires)
import random
# Input borneInf
borneInf = 0
# Input borneSup
borneSup = 100
# variable atrouver : nombre aléatoire de type entier compris entre borneInf et borneSup (compris)
atrouver = random.randint(borneInf,borneSup)
# N est la variable qui contiendra le nombre de comparaisons
N = 0
# trouve est une variable de type booléen.
trouve = False
# Boucle "tant que la variable trouve n'est pas égale à True)
while (trouve!=True):
    # On tire un nombre que l'on assigne à la variable aleatoire
    aleatoire = random.randint(borneInf,borneSup)
    # Si le nombre à trouver est égal au nombre aléatoire tiré, alors on sort de la boucle
    if (aleatoire == atrouver) :
        trouve=True
    # On incrémente le nombre de comparaisons
    N = N + 1
# Output : affichage du nombre à trouver et du nombre de comparaisons
print("Nombre d'opérations pour trouver "+str(atrouver)+" : "+str(N))

Nombre d'opérations pour trouver 97 : 170

Recherche aléatoire sans remise#

L’algorithme est proche du précédent mais l’algorithme ne tire pas deux fois le même nombre

# Recherche aléatoire sans remise commentée
# On ne tire jamais le même nombre aléatoire à chaque itération
# Vincent Keller, 2023

# Importation de la bibliothèque random (nombres aléatoires)
import random

# Définition d'une fonction qui retourne un nombre aléatoire qui n'a jamais été tiré
# Argument 1 : already : liste qui contient tous les nombres aléatoires déjà tirés
# Argument 2 : bmin : borne inférieure pour la fonction randint
# Argument 3 : bmax : borne supérieure pour la fonction randint
# Return     : un nombre aléatoire jamais tiré auparavant
# ATTENTION : CETTE FONCTION EST PARTICULIEREMENT COMPLEXE, VOUS N'AVEZ PAS BESOIN D'EN COMPRENDRE
# TOUTES LES SUBTILITES
def random_non_tire(already,bmin,bmax):
    ret = 0
    nontire = False
    while nontire != True :
        aleat = random.randint(bmin,bmax)
        tire = False
        for i in range(len(already)):
            if already[i] == aleat :
                tire = True
        if tire == False:
            nontire = True
    return aleat


# Input borneInf
borneInf = 0
# Input borneSup
borneSup = 100
# variable atrouver : nombre aléatoire de type entier compris entre borneInf et borneSup (compris)
atrouver = random.randint(borneInf,borneSup)
# N est la variable qui contiendra le nombre de comparaisons
N = 0
# trouve est une variable de type booléen.
trouve = False
# deja_tire est une liste qui contient tous les nombres aléatoires déjà tirés
# Initialisation à une liste vide
deja_tire = []
# Boucle "tant que la variable trouve n'est pas égale à True)
while (trouve!=True):    
    # On tire un nombre jamais tiré que l'on assigne à la variable aleatoire
    aleatoire = random_non_tire(deja_tire,borneInf,borneSup)
    # Si le nombre à trouver est égal au nombre aléatoire tiré, alors on sort de la boucle
    if (aleatoire == atrouver) :
        trouve=True
    # On incrémente le nombre de comparaisons
    N = N + 1
    # on ajoute le nombre à la liste des aléatoires déjà tirés
    deja_tire.append(aleatoire)
# Output : affichage du nombre à trouver et du nombre de comparaisons
print("Nombre d'opérations pour trouver "+str(atrouver)+" : "+str(N))

Nombre d'opérations pour trouver 83 : 57
Contents