Cours Algorithmique, recherche par dichotomie
lesbonsprofs.com
Image
Cours Algorithmique, recherche par dichotomie
1
Video Algorithmique ; Recherche d'une occurrence par dichotomie
2
Exercice QCM - Recherche d'un élément dans une liste par dichotomie
QCM
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

L'énoncé

Cocher la ou les bonnes réponses.

Tu as obtenu le score de

Question 1

Comment fonctionne un algorithme par dichotomie ?

En balayant chaque élément de la liste et en le comparant à l'élément recherché

En divisant successivement la liste en deux, et en ne gardant qu'une des deux moitiés.

Question 2

En utilisant la fonction de la vidéo précédente, que renvoie dicho(a,T) avec :

a = 6

T = [1,3,3,6,7,12]

True

False

3

4

Question 3

Cet algorithme l'algorithme suivant ne fonctionne pas. Quelles lignes pose problème ? (essayez de ne pas regarder l'algorithme de la vidéo)

def dichoto(a,T):
    g = 0
    d = len(T)
    while g < d :
        k = (g+d)/2
        if a < T[k] :
            d = k
        else :
            g = k
    if a == T[g] :
        return g
    else :
        return False

k = (g+d)/2

while g < d :

d = len(T)

  • k = (g+d)/2

    Ici, le problème est qu'une division non entière est réalisée. k=(g+d)/2 peut donner un nombre à virgule, de type flottant, et ça n'aurait donc pas de sens d'écrire T[k]. Il faut donc mettre une double barre // pour ne conserver que la partie entière du résultat de la division (autrement dit, le quotient de la division euclidienne)

  • while g < d :

    Ici, il faut remplacer le d par d-1 : en effet, il avec cette fausse ligne, on ne sort de la boucle qu'une fois que g=d, ce qui est donc une liste à un seul élément. Il n'y a pas besoin d'aller jusque là, on peut s'arrêter à une liste à 2 éléments comme indiqué dans la vidéo (cf l'exemple qui finit par

Question 4

L = [1,2,3,4,5]

Que renvoie la ligne de code suivante ?

L[2]

1

2

3

4

5

Question 5

Quelle est la dernière valeur prise par c ici ?

n = 42
c = 0
while c < n:
    c = c + 1

41

42

Question 6

Que renvoie l'algorithme de dichotomie pour ces entrées ?

T = [13, 1, 42, 7, 0]
a = 1

1

2

True

False

Il y a un problème avec les entrées

La liste T n'est pas triée ! L'algorithme de dichotomie ne fonctionne qu'avec des listes triées dans l'ordre croissant. Cela peut se faire manuellement, ou à l'aide de la fonction sort de Python.

Question 7

Quel est le variant de boucle dans cet algorithme ?

def dichoto(a,T):
    g = 0
    d = len(T)
    while g < d-1 :
        k = (g+d)//2
        if a < T[k] :
            d = k
        else :
            g = k
    if a == T[g] :
        return g
    else :
        return False

a

T

d

g

k

d-g

Question 8

On suppose que T est bien triée, et on reste sur le même algorithme :

def dichoto(a,T):
    g = 0
    d = len(T)
    while g < d-1 :
        k = (g+d)//2
        if a < T[k] :
            d = k
        else :
            g = k
    if a == T[g] :
        return g
    else :
        return False

Au fur et à mesure d'itérations, d-g :

diverge

converge vers 1

ça dépend de a et T

Question 9

Dans quelle autre situation utilise-t-on la dichotomie ?

Lors de la recherche du zéro d'une fonction

En géométrie

Pour les formules de trigonométrie

Question 10

Quelle est la méthode la plus efficace (rapide) selon vous ?

Recherche d'une occurrence d'un élément dans une liste par balayage (c'est à dire examiner les éléments de la liste un à un et les comparer à l'élément recherché)

Recherche d'une occurrence d'un élément dans une liste par dichotomie (expliquée dans cette vidéo)