L'énoncé
Répondre aux questions suivantes
Tu as obtenu le score de
Question 1
Que fait l'algorithme de recherche d'occurrence ?
Il recherche le mot "occurrence" dans une liste.
Il teste la présence d'un élément dans un tableau.
On résout une équation selon le principe d'occurrence.
Question 2
Par quel moyen vérifie-t-on la présence d'un élément ?
Par balayage
On cherche par balayage la présence d'une valeur dans un tableau.
Par dichotomie
Par la méthode des moindres carrés
Question 3
Que signifie un algorithme par balayage ?
On nettoie la liste : en d'autres termes, on doit la trier avant d'effectuer le test.
On vérifie successivement toutes les valeurs.
On vérifie successivement toutes les valeurs que l'on compare à la valeur recherchée et l'on s'arrête dès lors que cette valeur apparait.
On divise la liste en plein de branches, comme les poils d'un balais.
Question 4
Quand l'algorithme s'arrête-il ?
Toujours après avoir parcouru toute la liste.
Lorsque le nombre apparait pour la deuxième fois.
Lorsque le nombre apparait pour la première fois.
On vérifie successivement toutes les valeurs que l'on compare à la valeur recherchée et l'on s'arrête dès lors que cette valeur apparait.
Question 5
Quel autre problème utilise la méthode du balayage ?
La résolution de l'équation $f(x) = 0$
On peut résoudre par balayage l'équation $f(x) = 0$ où $f$ est une fonction continue et strictement monotone.
Lors du tri d'une liste
Lors de la recherche par dichotomie
Question 6
L'algorithme affiche forcément un résultat.
Vrai
Faux
En effet, si le nombre $a$ n'appartient pas à la liste, alors l'algorithme n'affiche rien.
Question 7
Pourquoi impose-t-on la condition if $i<n$ ?
Pour éviter de sortir de la liste
Car cela correspond au cas où la liste ne contient que la valeur $a$.
Car cela correspond au cas où la liste ne contient pas la valeur $a$.
En effet, lors de la dernière itération si $a$ n'appartient pas à la liste, $i$ prend la valeur $n$. La condition $i < n$ n'est donc plus rempli et on n'affiche aucun résultat : c'est normal $a$ n'appartient pas à la liste.
Question 8
Quelle variable joue le rôle de variant dans l'algorithme ?
$n$
C'est la taille de la liste donc $n$ ne varie pas.
$i$
$i$ correspond à l'indice successif des éléments de la liste $L$.
$a$
C'est la valeur cherchée, qui ne varie donc pas.
Question 9
Quel est le pire des cas ?
Lorsque le soleil explosera.
Lorsque la liste ne contient que des $a$.
Lorsque l'algorithme parcourt toute la liste.
Cela nécessite le plus grand nombre d'itérations.
Question 10
Quelle est la complexité de l'algorithme ?
Linéaire
Dans le pire des cas, il y a $2n + 1$ opérations élémentaires: c'est la définition d'une complexité élémentaire.
Quadratique
Assez facile
On cherche par balayage la présence d'une valeur dans un tableau grâce à l'algorithme.