Un algorithme de recherche dichotomique dans une liste triée de taille $n$ nécessite, dans le pire des cas, exactement $k$ comparaisons.
Combien cet algorithme va-t-il utiliser, dans le pire des cas, de comparaisons sur une liste de taille $2n$ ?

Réponses :

A- $k$

B- $k+1$

C- $2k$

D- $2k+1$

On considère la fonction suivante :

def f(x,L):
    g = 0
    d = len(L)-1
    while g < d:
        m = (g+d)//2
        if x <= L[m]:
            d = m
        else:
            g = m + 1
    return g

Cette fonction implémente :

Réponses :

A- le tri par insertion

B- le tri par sélection

C- la recherche dichotomique

D- la recherche du plus proche voisin

En utilisant une recherche dichotomique, combien faut-il de comparaisons pour trouver une valeur dans un tableau trié de 1000 nombres ?

Réponses :

A- 3

B- 10

C- 1000

D- 1024

Quelle précondition suppose l'algorithme de recherche dichotomique dans un tableau ?

Réponses :

A- que le tableau soit à éléments positifs

B- que le tableau soit trié

C- que l'élément cherché dans le tableau soit positif

D- que l'élément cherché figure effectivement dans le tableau

La fonction ci-dessous permet d’effectuer une recherche par dichotomie de l’index m de l’élément x dans un tableau L de valeurs distinctes et triées.

def dicho(x,L):
    g = 0
    d = len(L)-1
    while g <= d:
        m = (g+d)//2
        if L[m] == x:
            return m
        elif L[m] < x:
            g = m+1
        else:
            d = m-1
    return None

Combien de fois la cinquième ligne du code de la fonction m = (g+d)//2 sera-t-elle exécutée dans l'appel dicho(32, [4, 5, 7, 25, 32, 50, 51, 60]) ?

Réponses :

A- 1 fois

B- 2 fois

C- 3 fois

D- 4 fois

Auteur : Christophe JOUBERT

Avec un algorithme de recherche dichotomique, combien d'étapes sont nécessaires pour déterminer que 45 n'est pas présent dans la liste suivante : [1, 7, 12, 16, 18, 20, 24, 28, 35, 43, 69] ?

Réponses :

A- 2

B- 3

C- 4

D- 5

Autrice : Sylvie Genre

On souhaite écrire une fonction recherche_dichotomique(t, v), qui renvoie une position de la valeur v dans le tableau t, supposé trié, et None si v ne s'y trouve pas.
Parmi les 4 fonctions ci-dessous, laquelle est correcte ?

Réponses :

A-

def recherche_dichotomique(t, v) :
     g = 0
     d = len(t) - 1
     while g <= d :
          m = (g + d) // 2
          if t[m] < v :
               g = m + 1
          elif t[m] > v :
               d = m - 1
          else :
               return m
     return None

B-

def recherche_dichotomique(t, v) :
     g = 0
     d = len(t) - 1
     while g <= d :
          m = (g + d) // 2
          if t[m] > v :
               g = m + 1
          elif t[m] < v :
               d = m - 1
          else :
               return m
     return None

C-

def recherche_dichotomique(t, v) :
     g = 0
     d = len(t)
     while g <= d :
          m = (g + d) // 2
          if t[m] < v :
               g = m + 1
          elif t[m] > v :
               d = m - 1
          else :
               return m
     return None

D-

def recherche_dichotomique(t, v) :
     g = 0
     d = len(t) - 1
     while g < d :
          m = (g + d) // 2
          if t[m] < v :
               g = m + 1
          elif t[m] > v :
               d = m - 1
          else :
               return m
     return None

Auteur : Antony OLIVIER

Par quel moyen usuel peut-on démontrer la terminaison d'une boucle ?

Réponses :

A- une assertion

B- un invariant

C- un variant

D- la complexité

Dans la fonction suivante, les valeurs des variables x et y sont des entiers naturels :

def f(x, y) :
    s = x
    t = y
    while t > 0 :
        s = s + 1
        t = t - 1
    return s

Quelle affirmation est fausse ?

Réponses :

A- La propriété s + t = x + y est un invariant de boucle.

B- La variable s + t est un variant de boucle.

C- La propriété t est supérieur ou égal à 0 est un invariant de la boucle while.

D- La variable t est un variant de la boucle while.