\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Recherche linéaire}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Recherche linéaire} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{premiererecherchelineaire}{
  \begin{question}{q01}
    En quoi consiste la \textbf{recherche linéaire} (ou séquentielle) ?
    \begin{choices}
    \wrongchoice{Sauter directement à la position centrale puis comparer}
    \correctchoice{Parcourir la liste élément par élément et comparer chaque valeur à celle recherchée}
    \wrongchoice{Utiliser un dictionnaire pour aller directement à la valeur}
    \wrongchoice{Trier la liste puis chercher le premier élément}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q02}
    La recherche linéaire suppose-t-elle que la liste
soit \textbf{triée} ?
    \begin{choices}
    \wrongchoice{Uniquement si la liste contient des nombres}
    \correctchoice{Non, elle fonctionne sur n'importe quelle liste}
    \wrongchoice{Uniquement si la liste contient au moins 10 éléments}
    \wrongchoice{Oui, sinon elle ne fonctionne pas}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q03}
    Quel est le \textbf{nombre maximal de comparaisons} dans
une recherche linéaire dans une liste de longueur n ?
    \begin{choices}
    \wrongchoice{n²}
    \wrongchoice{log(n)}
    \correctchoice{n}
    \wrongchoice{n / 2}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q04}
    Dans une recherche linéaire bien programmée, quand
arrête-t-on de parcourir la liste ?
    \begin{choices}
    \wrongchoice{Au bout de log(n) comparaisons}
    \wrongchoice{Dès que l'élément n'est pas trouvé}
    \wrongchoice{Toujours après avoir parcouru toute la liste}
    \correctchoice{Dès que l'élément cherché est trouvé, ou en arrivant à la fin de la liste}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q05}
    Si l'élément cherché n'est \textbf{pas dans la liste},
que peut-on raisonnablement renvoyer ?
    \begin{choices}
    \wrongchoice{La dernière position de la liste (n - 1)}
    \wrongchoice{La position 0 (par défaut)}
    \wrongchoice{La longueur de la liste}
    \correctchoice{\texttt{None} ou \texttt{-1}, pour signaler l'absence}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q06}
    Quel code implémente correctement la recherche
linéaire et renvoie l'\textbf{indice} de la cible (ou
-1 si absente) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def chercher(liste, cible):
    for i in range(len(liste)):
        if liste[i] == cible:
            return i
        return -1
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(liste, cible):
    for x in liste:
        if x == cible:
            return x
    return -1
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def chercher(liste, cible):
    for i in range(len(liste)):
        if liste[i] == cible:
            return i
    return -1
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(liste, cible):
    while True:
        if liste[0] == cible:
            return 0
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q07}
    L'expression Python \texttt{42 in liste} réalise
implicitement quelle opération ?
    \begin{choices}
    \wrongchoice{Un tri}
    \wrongchoice{Une recherche dichotomique (rapide)}
    \correctchoice{Une recherche linéaire de gauche à droite, qui s'arrête dès qu'une correspondance est trouvée}
    \wrongchoice{Une vérification de type}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q08}
    Que doit renvoyer une recherche linéaire (qui
renvoie l'indice ou -1) sur une \textbf{liste vide} ?
    \begin{choices}
    \wrongchoice{Une exception}
    \wrongchoice{\texttt{None}}
    \correctchoice{-1 (élément absent)}
    \wrongchoice{0}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q09}
    Trouver le \textbf{minimum} d'une liste est aussi un
cas de recherche linéaire. Quelle est sa
complexité ?
    \begin{choices}
    \wrongchoice{O(n²) : double boucle nécessaire}
    \wrongchoice{O(1) : on prend juste le premier élément}
    \wrongchoice{O(log n) : recherche dichotomique}
    \correctchoice{O(n) : on doit comparer tous les éléments}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q10}
    On cherche \texttt{cible = 7} dans \texttt{liste = [3, 5, 7, 2, 7]}.
Combien de comparaisons effectue une recherche
linéaire \textbf{avec arrêt précoce} ?
    \begin{choices}
    \wrongchoice{5}
    \wrongchoice{1}
    \wrongchoice{2}
    \correctchoice{3}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q11}
    Quelle est la complexité dans le \textbf{meilleur cas}
de la recherche linéaire ?
    \begin{choices}
    \correctchoice{O(1)}
    \wrongchoice{O(n²)}
    \wrongchoice{O(log n)}
    \wrongchoice{O(n)}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q12}
    On veut juste savoir si l'élément est présent ou
non (sans avoir besoin de l'indice). Quelle
version est la plus pythonique ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def present(liste, cible):
    return liste.index(cible)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def present(liste, cible):
    return cible in liste
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def present(liste, cible):
    for x in liste:
        if x == cible:
            return True
    return False
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def present(liste, cible):
    return cible == liste
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q13}
    Pour trouver \textbf{toutes} les positions où la cible
apparaît dans la liste, quelle adaptation de la
recherche linéaire utilise-t-on ?
    \begin{choices}
    \wrongchoice{On trie la liste avant de chercher}
    \correctchoice{On parcourt toute la liste et on enregistre tous les indices où l'élément correspond}
    \wrongchoice{On utilise une recherche dichotomique}
    \wrongchoice{On s'arrête à la première occurrence et on l'enregistre}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q14}
    Pour rechercher un élément dans une \textbf{liste triée}
de 1 000 000 d'éléments, combien de comparaisons
au pire avec chacune des deux méthodes ?
    \begin{choices}
    \correctchoice{Linéaire : 1 000 000 ; dichotomique : ~ 20}
    \wrongchoice{Linéaire : 1 000 000 ; dichotomique : 1 000}
    \wrongchoice{Linéaire : 1 000 ; dichotomique : 1 000 000}
    \wrongchoice{Les deux sont identiques}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q15}
    Un élève écrit
\begin{lstlisting}
def chercher(liste, cible):
    for i in range(len(liste)):
        if liste[i] == cible:
            trouve = True
        else:
            trouve = False
    return trouve
\end{lstlisting}
Quel est le bug ?
    \begin{choices}
    \wrongchoice{\texttt{return} doit être à l'intérieur de la boucle}
    \correctchoice{À chaque itération, \texttt{trouve} est réinitialisé. Seul le résultat de la dernière comparaison est renvoyé.}
    \wrongchoice{La fonction est trop lente}
    \wrongchoice{La variable \texttt{trouve} n'est pas définie hors de la boucle}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q16}
    Quelle est la différence pratique entre une
recherche linéaire écrite avec \texttt{for} et avec
\texttt{while} ?
    \begin{choices}
    \wrongchoice{\texttt{while} ne fonctionne pas sur les listes}
    \correctchoice{\texttt{for} est plus lisible quand on parcourt tous les indices ; \texttt{while} est plus naturel pour combiner deux conditions d'arrêt (par exemple \texttt{i < n and not trouve})}
    \wrongchoice{\texttt{for} est plus rapide}
    \wrongchoice{Les deux sont strictement équivalents en Python}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q17}
    Pourquoi la recherche d'une \textbf{clé} dans un
dictionnaire Python est-elle en O(1) (alors que
\texttt{in liste} est en O(n)) ?
    \begin{choices}
    \correctchoice{Parce que les dictionnaires utilisent une table de hachage : la position d'une clé est calculée directement par une fonction de hachage}
    \wrongchoice{Parce que les dictionnaires sont triés}
    \wrongchoice{Parce qu'ils contiennent moins de données}
    \wrongchoice{Parce que Python est un langage rapide}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q18}
    Si l'on sait qu'un élément est \textbf{plus souvent
cherché} que les autres, comment optimiser une
série de recherches linéaires successives ?
    \begin{choices}
    \wrongchoice{Trier la liste par ordre croissant}
    \wrongchoice{Doubler la taille de la liste}
    \correctchoice{Placer les éléments les plus fréquents au début de la liste}
    \wrongchoice{Convertir la liste en chaîne}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q19}
    Soit
\texttt{eleves = [("Alice", 17), ("Bob", 16), ("Eve", 18)]}.
Comment trouver l'âge d'Alice ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
eleves["Alice"]
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
for nom, age in eleves:
    if nom == "Alice":
        return age
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
eleves.index(("Alice"))
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
eleves.find("Alice")
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q20}
    L'expression \texttt{"a" in "abracadabra"} :
    \begin{choices}
    \wrongchoice{Lève une exception}
    \wrongchoice{Renvoie \texttt{False}}
    \wrongchoice{Renvoie le nombre d'occurrences}
    \correctchoice{Renvoie \texttt{True}}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q21}
    \begin{lstlisting}
def trouver(liste, cible):
    indice = -1
    for i in range(len(liste)):
        if liste[i] == cible:
            indice = i
    return indice
\end{lstlisting}
Quel est le comportement de cette fonction si la
cible apparaît plusieurs fois ?
    \begin{choices}
    \wrongchoice{Elle renvoie -1}
    \correctchoice{Elle renvoie l'indice de la dernière occurrence}
    \wrongchoice{Elle entre dans une boucle infinie}
    \wrongchoice{Elle renvoie l'indice de la première occurrence}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q22}
    Pour rechercher un élément dans une liste de
100 éléments, \textbf{non triée}, qu'on ne consultera
qu'une seule fois, quelle stratégie est la plus
efficace \textbf{globalement} ?
    \begin{choices}
    \correctchoice{Recherche linéaire directement}
    \wrongchoice{Convertir en dictionnaire}
    \wrongchoice{Faire la recherche en parallèle sur 4 cœurs}
    \wrongchoice{Trier puis dichotomie}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q23}
    \begin{lstlisting}
def chercher(liste, cible):
    i = 0
    while liste[i] != cible:
        i += 1
    return i
\end{lstlisting}
Quel problème pose ce code ?
    \begin{choices}
    \wrongchoice{Aucun, le code est correct}
    \wrongchoice{La fonction ne renvoie jamais rien}
    \correctchoice{Si l'élément est absent, la boucle dépasse la fin de la liste et lève \texttt{IndexError}}
    \wrongchoice{Le code modifie la liste}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q24}
    Sur ma machine, une recherche linéaire dans une
liste de 1 million d'éléments prend ~ 30 ms. Que
prendra une recherche dans une liste de 1
milliard d'éléments (si la mémoire le permet) ?
    \begin{choices}
    \wrongchoice{Environ 60 ms (juste deux fois plus)}
    \correctchoice{Environ 30 secondes (1000 fois plus, car n est multiplié par 1000)}
    \wrongchoice{Environ 30 secondes au carré}
    \wrongchoice{Toujours environ 30 ms (constante)}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur la recherche
linéaire, laquelle est \textbf{fausse} ?
    \begin{choices}
    \wrongchoice{En Python, l'opérateur \texttt{in} sur une liste fait une recherche linéaire}
    \wrongchoice{Elle fonctionne sur des listes triées comme non triées}
    \wrongchoice{Sa complexité au pire est O(n)}
    \correctchoice{Elle est toujours plus rapide que la dichotomique}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q26}
    On veut \textbf{compter} combien de fois la cible
apparaît dans la liste (et non simplement la
trouver). Quelle adaptation de la recherche
linéaire faut-il faire ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def compter(liste, cible):
    for x in liste:
        if x == cible:
            return 1
    return 0
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def compter(liste, cible):
    return len(liste) if cible in liste else 0
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def compter(liste, cible):
    n = 0
    for x in liste:
        if x == cible:
            n += 1
    return n
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def compter(liste, cible):
    return liste.index(cible)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q27}
    On cherche le \textbf{premier} élément d'une liste de
nombres qui soit \textbf{strictement supérieur} à
\texttt{100} (et son indice). Quel code applique
correctement la recherche linéaire à ce cas ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def premier_grand(liste):
    liste.sort()
    return liste[-1]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def premier_grand(liste):
    return max(liste) > 100
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def premier_grand(liste):
    for x in liste:
        if x > 100:
            return x
        return None
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def premier_grand(liste):
    for i, x in enumerate(liste):
        if x > 100:
            return (i, x)
    return None
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchelineaire}{
  \begin{question}{q28}
    On dispose d'une matrice carrée représentée par
une liste de listes (par exemple
\texttt{m = [[3, 7, 1], [8, 2, 5], [4, 9, 6]]}). On
cherche le couple \texttt{(ligne, colonne)} de la
première occurrence de la valeur \texttt{5}. Quel code
est correct ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def chercher(m, cible):
    if cible in m:
        return m.index(cible)
    return None
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(m, cible):
    for ligne in m:
        for x in ligne:
            if x == cible:
                return x
    return None
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(m, cible):
    for i in range(len(m)):
        if m[i] == cible:
            return i
    return None
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def chercher(m, cible):
    for i in range(len(m)):
        for j in range(len(m[i])):
            if m[i][j] == cible:
                return (i, j)
    return None
\end{lstlisting}
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premiererecherchelineaire}
  \insertgroup{premiererecherchelineaire}
}

\end{document}
