Algorithme de recherche dichotomique

Algorithme de recherche dichotomique

Exercice 1: 

1.1 Recopier et compléter sous Python la fonction suivante en respectant les spécifications:

tab est un tableau d’entiers trié dans l’ordre croissant

x est  nombre entier

La fonction doit renvoyer True si tab contient x et False sinon

def dichotomie(tab, x):

    debut = 0

    fin = len(tab) - 1

    while debut <= fin:

        m = ...

        if x == tab[m]:

            return ...

        if x > tab[m]:

            debut = m + 1

        else:

            fin = ...

    return ...

1.2 Tester le code pour les deux cas suivants:

 tab = [18, 19, 23, 24, 28, 29, 31, 33] et x=28  puis pour le même tab et x=27

1.3 Proposer une modification pour que la fonction renvoie l'emplacement de x dans tab s'il est présent et None sinon

1.4  Ce code ne peut traiter que des tableaux triés, la recherche échoue si on passe à la fonction un tableau tab qui n'est pas trié, on vous demande maintenant d'écrire une fonction verif_tri(tab) qui prend en paramètre un tableau tab et qui renvoie True si tab est trié (False sinon). Vous modifierez le code de la fonction dichotomie pour utiliser la valeur renvoyée par verif_tri(tab) dans la fonction et n'autoriser la recherche de la position de x dans tab que s'il est trié.

Exercice 2: analyse du programme et complexité

2.1 Comment peut-on être sûr que la fonction dichotomie se termine quand x n'est pas dans tab?

2.2 Combien d'étapes sont nécessaires pour se rendre compte que x=27 n'est pas dans la liste tab? Combien d'étapes seraient nécessaires pour se rendre compte que 27 n'est pas dans la liste tab si on doublait le nombre de données dans tab? Exemple si tab = [ 14, 15, 16, 17, 18, 19, 23, 24, 28, 29, 31, 33, 34, 35, 36, 40]

2.3 Est-ce que le nombre d'étapes est le même que pour x=27 si on recherche x=13 dans tab, le nombre d'étapes est-il dépendant de la position éventuelle de x ?  

Est-ce que le nombre d'étapes est le même que pour x=13 si on recherche x=41?

On rappelle que la complexité en temps est une estimation du temps que mets l'algorithme pour donner son résultat en fonction du nombre de données n qui doit traiter. La complexité ne note O, voici quelques complexités:

O(1): veut dire que le temps que mets l'algorithme pour donner son résultat est constant quelque soit le nombre de données n à traiter.

O(n) veut dire que le temps que mets l'algorithme pour donner son résultat est proportionnel aux nombres de données n à traiter.

=> n fois 2 entraîne un temps d'exécution fois 2

O(n2) veut dire que le temps que mets l'algorithme pour donner son résultat est proportionnel au carré du nombre de données n traités

=> si n est doublé ça entraîne un temps d'exécution fois 4

O(log2(n)) veut dire que le temps que mets l'algorithme pour donner son résultat est proportionnel au logarithme de base 2 du nombre de données n à traiter

2.4  Montrer que l'algorithme de recherche dichotomique à un complexité logarithmique.

Créé avec HelpNDoc Personal Edition: Avantages d'un outil de création d'aide