\documentclass[a4paper,11pt]{article}

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

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

\begin{document}

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

\bigskip

\element{terminalerecherchetextuelle}{
  \begin{question}{q01}
    En quoi consiste la \textbf{recherche textuelle} ?
    \begin{choices}
    \wrongchoice{Chercher un mot dans un dictionnaire trié}
    \wrongchoice{Compter le nombre de caractères dans un texte}
    \wrongchoice{Trier un texte par ordre alphabétique}
    \correctchoice{Trouver toutes les positions d'un motif (chaîne courte) dans un texte (chaîne longue)}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q02}
    Quel est le principe de l'\textbf{algorithme naïf} (force brute) ?
    \begin{choices}
    \wrongchoice{On utilise une table de hachage pour aller plus vite}
    \correctchoice{On teste chaque position de départ possible et on compare le motif caractère par caractère}
    \wrongchoice{On découpe le texte en deux et on cherche dans chaque moitié}
    \wrongchoice{On compare le motif uniquement à la fin du texte}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q03}
    Dans l'algorithme naïf, la boucle externe va de 0 à
quelle valeur (incluse) pour pouvoir aligner un motif
de longueur \texttt{m} dans un texte de longueur \texttt{n} ?
    \begin{choices}
    \wrongchoice{\texttt{n - 1}}
    \wrongchoice{\texttt{n - m - 1}}
    \wrongchoice{\texttt{n}}
    \correctchoice{\texttt{n - m}}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q04}
    Quelle est la complexité dans le \textbf{pire cas} de
l'algorithme naïf de recherche textuelle ?
    \begin{choices}
    \wrongchoice{O(n + m)}
    \correctchoice{O(n × m)}
    \wrongchoice{O(log n)}
    \wrongchoice{O(n)}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q05}
    Quelle est l'\textbf{idée centrale} de l'algorithme de
Boyer-Moore-Horspool ?
    \begin{choices}
    \wrongchoice{Comparer le motif de gauche à droite mais en sautant les voyelles}
    \wrongchoice{Utiliser la programmation dynamique avec mémoïsation}
    \wrongchoice{Pré-trier le texte pour faire une recherche dichotomique}
    \correctchoice{Comparer le motif de droite à gauche et sauter plusieurs positions en cas d'échec grâce à une table de décalages}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q06}
    Lequel des outils suivants utilise une variante de la
recherche textuelle (algorithme naïf ou Boyer-Moore) ?
    \begin{choices}
    \wrongchoice{La commande Unix \texttt{grep}}
    \correctchoice{Toutes les réponses précédentes}
    \wrongchoice{La fonction Ctrl+F d'un éditeur de texte}
    \wrongchoice{L'analyse de séquences ADN}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q07}
    Lorsqu'on programme \texttt{recherche(texte, motif)}, quel
est le retour le plus utile ?
    \begin{choices}
    \wrongchoice{Un booléen \texttt{True}/\texttt{False} indiquant la présence}
    \correctchoice{La liste des indices de début de chaque occurrence}
    \wrongchoice{Le texte modifié pour retirer le motif}
    \wrongchoice{La longueur du motif}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q08}
    Avec l'algorithme naïf, on cherche \texttt{motif = "ab"} dans
\texttt{texte = "babab"}. Quel est le résultat ?
    \begin{choices}
    \wrongchoice{[0, 2]}
    \correctchoice{[1, 3]}
    \wrongchoice{[]}
    \wrongchoice{[1, 2, 3]}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q09}
    Lequel de ces couples (texte, motif) constitue un
\textbf{pire cas} pour l'algorithme naïf ?
    \begin{choices}
    \wrongchoice{texte = \texttt{'hello'}, motif = \texttt{'hello'}}
    \correctchoice{texte = \texttt{'aaaaaaaaa'}, motif = \texttt{'aaab'}}
    \wrongchoice{texte = \texttt{'abracadabra'}, motif = \texttt{'xyz'}}
    \wrongchoice{texte = \texttt{'a'}, motif = \texttt{'ab'}}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q10}
    Dans Boyer-Moore-Horspool, par quel caractère du motif
commence-t-on la comparaison ?
    \begin{choices}
    \wrongchoice{Le premier (gauche)}
    \correctchoice{Le dernier (droite)}
    \wrongchoice{Un caractère choisi au hasard}
    \wrongchoice{Le caractère du milieu}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q11}
    Pour le motif \texttt{"dab"} (longueur 3), quelle est la table
de décalages de Boyer-Moore-Horspool ?
    \begin{choices}
    \wrongchoice{{'d': 3, 'a': 3, 'b': 3}}
    \correctchoice{{'d': 2, 'a': 1}}
    \wrongchoice{{'d': 0, 'a': 1, 'b': 2}}
    \wrongchoice{{'d': 2, 'a': 1, 'b': 0}}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q12}
    Avec le motif \texttt{"dab"} (longueur 3), le caractère du
texte aligné avec la fin du motif est \texttt{'z'}. Quel
décalage applique-t-on ?
    \begin{choices}
    \wrongchoice{1}
    \correctchoice{3 (la longueur du motif)}
    \wrongchoice{0}
    \wrongchoice{2}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q13}
    Pour le motif \texttt{"maman"} (longueur 5), quelle est la
table de décalages ?
    \begin{choices}
    \wrongchoice{{'m': 0, 'a': 3}}
    \wrongchoice{{'m': 4, 'a': 1}}
    \correctchoice{{'m': 2, 'a': 1}}
    \wrongchoice{{'m': 2, 'a': 3, 'n': 0}}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q14}
    Pourquoi exclut-on le dernier caractère du motif lors
du pré-traitement ?
    \begin{choices}
    \correctchoice{Parce qu'il donnerait un décalage de 0, ce qui ferait boucler l'algorithme}
    \wrongchoice{Pour économiser de la mémoire}
    \wrongchoice{Parce qu'il est toujours absent du motif}
    \wrongchoice{Parce que Python ne permet pas d'indexer la dernière position}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q15}
    On cherche \texttt{motif = "dab"} dans \texttt{texte = "abracadabra"}.
Au premier alignement (i=0), on compare \texttt{texte[2]}
(\texttt{'r'}) avec \texttt{motif[2]} (\texttt{'b'}). Échec. Sachant que
\texttt{'r'} n'est pas dans le motif, de combien décale-t-on ?
    \begin{choices}
    \wrongchoice{11 (la longueur du texte)}
    \wrongchoice{2}
    \wrongchoice{1}
    \correctchoice{3 (la longueur du motif)}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q16}
    Quelle est la complexité de Boyer-Moore-Horspool dans
le \textbf{pire cas} ?
    \begin{choices}
    \wrongchoice{O(n)}
    \wrongchoice{O(log n)}
    \correctchoice{O(n × m)}
    \wrongchoice{O(n + m)}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q17}
    Quelle est la complexité dans le \textbf{meilleur cas} de
Boyer-Moore-Horspool ?
    \begin{choices}
    \correctchoice{O(n / m)}
    \wrongchoice{O(n)}
    \wrongchoice{O(m)}
    \wrongchoice{O(1)}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q18}
    Dans quel cas Boyer-Moore-Horspool n'apporte-t-il
\textbf{aucun gain} par rapport à l'algorithme naïf ?
    \begin{choices}
    \wrongchoice{Quand l'alphabet est large}
    \correctchoice{Quand le texte et le motif ne contiennent presque que des caractères identiques (par exemple uniquement des \texttt{'a'})}
    \wrongchoice{Quand le motif est très court}
    \wrongchoice{Quand le texte est très long}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q19}
    Que doit renvoyer \texttt{recherche\_naif("abc", "")} (motif
vide) selon la convention de Python ?
    \begin{choices}
    \wrongchoice{[]}
    \correctchoice{[0, 1, 2, 3]}
    \wrongchoice{[0]}
    \wrongchoice{Une erreur (\texttt{ValueError})}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q20}
    La commande Unix \texttt{grep} (et ses variantes \texttt{egrep},
\texttt{fgrep}) utilise principalement quel type d'algorithme
pour la recherche de motifs simples ?
    \begin{choices}
    \wrongchoice{Algorithme naïf O(n × m)}
    \wrongchoice{Programmation dynamique}
    \wrongchoice{Recherche dichotomique sur le texte}
    \correctchoice{Variantes de Boyer-Moore (avec \texttt{fgrep} ou les motifs sans expression régulière)}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q21}
    On cherche \texttt{motif = "dab"} (longueur 3) dans
\texttt{texte = "abracadabra"} (longueur 11) avec
Boyer-Moore-Horspool. Combien d'alignements distincts
du motif sont effectués (i.e. valeurs successives de
\texttt{i}) avant la fin de l'algorithme ?
    \begin{choices}
    \wrongchoice{11}
    \wrongchoice{2}
    \wrongchoice{9 (comme l'algorithme naïf)}
    \correctchoice{4}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q22}
    Quelle est la table de décalages de
Boyer-Moore-Horspool pour le motif \texttt{"abracadabra"}
(longueur 11) ?
    \begin{choices}
    \wrongchoice{{'a': 1, 'b': 2, 'r': 3, 'c': 4, 'd': 5}}
    \correctchoice{{'a': 3, 'b': 2, 'r': 1, 'c': 6, 'd': 4}}
    \wrongchoice{{'a': 0, 'b': 1, 'r': 2, 'c': 3, 'd': 4}}
    \wrongchoice{{'a': 3, 'b': 2, 'r': 1, 'c': 6, 'd': 4, 'a': 0}}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q23}
    On veut chercher un motif de longueur 100 dans un
texte ADN (alphabet \texttt{\{A, C, G, T\}}) de 10⁹
nucléotides. Quel algorithme est le \textbf{plus pertinent} ?
    \begin{choices}
    \correctchoice{Un algorithme spécialisé (Knuth-Morris-Pratt, Aho-Corasick, ou une indexation par transformée de Burrows-Wheeler) garantissant une complexité en $O(n + m)$}
    \wrongchoice{Algorithme naïf, suffisant pour la plupart des cas}
    \wrongchoice{Recherche dichotomique}
    \wrongchoice{Boyer-Moore-Horspool, simple à implémenter mais limité par l'alphabet réduit}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q24}
    Un élève écrit la boucle externe de Boyer-Moore comme
\texttt{while i < n - m:} au lieu de \texttt{while i <= n - m:}.
Quel est l'effet ?
    \begin{choices}
    \wrongchoice{L'algorithme entre dans une boucle infinie}
    \wrongchoice{L'algorithme est plus rapide (gain négligeable)}
    \wrongchoice{L'algorithme renvoie des positions incorrectes}
    \correctchoice{L'algorithme rate les motifs situés à la toute fin du texte}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur les algorithmes
de recherche textuelle vus en NSI, laquelle est
\textbf{fausse} ?
    \begin{choices}
    \wrongchoice{L'algorithme naïf a une complexité O(n × m) dans le pire cas}
    \wrongchoice{Boyer-Moore-Horspool peut atteindre O(n / m) dans le meilleur cas}
    \wrongchoice{Pour de nombreux motifs simultanés, on préfère Aho-Corasick à Boyer-Moore}
    \correctchoice{Boyer-Moore-Horspool est toujours plus rapide que l'algorithme naïf}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q26}
    Quelle fonction Python implémente correctement
l'algorithme naïf de recherche textuelle, en
renvoyant la liste des indices de début de chaque
occurrence ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def recherche_naif(texte, motif):
    for i in range(len(texte)):
        if texte[i] == motif:
            return i
    return -1
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def recherche_naif(texte, motif):
    positions = []
    n, m = len(texte), len(motif)
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i + j] == motif[j]:
            j += 1
        if j == m:
            positions.append(i)
    return positions
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def recherche_naif(texte, motif):
    return [i for i, c in enumerate(texte) if c == motif[0]]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def recherche_naif(texte, motif):
    positions = []
    for i in range(len(texte)):
        if texte[i:i + len(motif)] == motif:
            positions.append(i)
    return positions
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalerecherchetextuelle}{
  \begin{question}{q27}
    Avec le motif \texttt{motif = "exercice"} (longueur 8) et
le texte \texttt{"l'élève fait son devoir"}, on aligne le
motif au tout début. Le caractère du texte aligné
avec la fin du motif est \texttt{'a'} (de « fait »).
Sachant que \texttt{'a'} n'apparaît pas dans \texttt{"exercice"},
de combien décale-t-on ?
    \begin{choices}
    \wrongchoice{1 position}
    \wrongchoice{0 position (on doit tester à nouveau au même endroit)}
    \wrongchoice{4 positions (la moitié de la longueur du motif)}
    \correctchoice{8 positions (la longueur du motif)}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalerecherchetextuelle}
  \insertgroup{terminalerecherchetextuelle}
}

\end{document}
