\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{Recherche textuelle}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en D
\begin{frame}[fragile]{Question 1 \textemdash{} Position du problème}
    En quoi consiste la \textbf{recherche textuelle} ?\medskip
    \begin{itemize}
        \item[A.] Chercher un mot dans un dictionnaire trié
        \item[B.] Compter le nombre de caractères dans un texte
        \item[C.] Trier un texte par ordre alphabétique
        \item[\alert<2>{D.}] \alert<2>{Trouver toutes les positions d'un motif (chaîne courte) dans un texte (chaîne longue)}
    \end{itemize}
\end{frame}

% Q2 - Réponse en B
\begin{frame}[fragile]{Question 2 \textemdash{} Principe de l'algorithme naïf}
    Quel est le principe de l'\textbf{algorithme naïf} (force brute) ?\medskip
    \begin{itemize}
        \item[A.] On utilise une table de hachage pour aller plus vite
        \item[\alert<2>{B.}] \alert<2>{On teste chaque position de départ possible et on compare le motif caractère par caractère}
        \item[C.] On découpe le texte en deux et on cherche dans chaque moitié
        \item[D.] On compare le motif uniquement à la fin du texte
    \end{itemize}
\end{frame}

% Q3 - Réponse en D
\begin{frame}[fragile]{Question 3 \textemdash{} Borne de la boucle}
    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} ?\medskip
    \begin{itemize}
        \item[A.] \texttt{n - 1}
        \item[B.] \texttt{n - m - 1}
        \item[C.] \texttt{n}
        \item[\alert<2>{D.}] \alert<2>{\texttt{n - m}}
    \end{itemize}
\end{frame}

% Q4 - Réponse en B
\begin{frame}[fragile]{Question 4 \textemdash{} Complexité du naïf}
    Quelle est la complexité dans le \textbf{pire cas} de
l'algorithme naïf de recherche textuelle ?\medskip
    \begin{itemize}
        \item[A.] O(n + m)
        \item[\alert<2>{B.}] \alert<2>{O(n × m)}
        \item[C.] O(log n)
        \item[D.] O(n)
    \end{itemize}
\end{frame}

% Q5 - Réponse en D
\begin{frame}[fragile]{Question 5 \textemdash{} Idée clé de Boyer-Moore}
    Quelle est l'\textbf{idée centrale} de l'algorithme de
Boyer-Moore-Horspool ?\medskip
    \begin{itemize}
        \item[A.] Comparer le motif de gauche à droite mais en sautant les voyelles
        \item[B.] Utiliser la programmation dynamique avec mémoïsation
        \item[C.] Pré-trier le texte pour faire une recherche dichotomique
        \item[\alert<2>{D.}] \alert<2>{Comparer le motif de droite à gauche et sauter plusieurs positions en cas d'échec grâce à une table de décalages}
    \end{itemize}
\end{frame}

% Q6 - Réponse en B
\begin{frame}[fragile]{Question 6 \textemdash{} Applications concrètes}
    Lequel des outils suivants utilise une variante de la
recherche textuelle (algorithme naïf ou Boyer-Moore) ?\medskip
    \begin{itemize}
        \item[A.] La commande Unix \texttt{grep}
        \item[\alert<2>{B.}] \alert<2>{Toutes les réponses précédentes}
        \item[C.] La fonction Ctrl+F d'un éditeur de texte
        \item[D.] L'analyse de séquences ADN
    \end{itemize}
\end{frame}

% Q7 - Réponse en B
\begin{frame}[fragile]{Question 7 \textemdash{} Que renvoie l'algorithme ?}
    Lorsqu'on programme \texttt{recherche(texte, motif)}, quel
est le retour le plus utile ?\medskip
    \begin{itemize}
        \item[A.] Un booléen \texttt{True}/\texttt{False} indiquant la présence
        \item[\alert<2>{B.}] \alert<2>{La liste des indices de début de chaque occurrence}
        \item[C.] Le texte modifié pour retirer le motif
        \item[D.] La longueur du motif
    \end{itemize}
\end{frame}

% Q8 - Réponse en B
\begin{frame}[fragile]{Question 8 \textemdash{} Trace de l'algorithme naïf}
    Avec l'algorithme naïf, on cherche \texttt{motif = "ab"} dans
\texttt{texte = "babab"}. Quel est le résultat ?\medskip
    \begin{itemize}
        \item[A.] [0, 2]
        \item[\alert<2>{B.}] \alert<2>{[1, 3]}
        \item[C.] []
        \item[D.] [1, 2, 3]
    \end{itemize}
\end{frame}

% Q9 - Réponse en B
\begin{frame}[fragile]{Question 9 \textemdash{} Pire cas du naïf}
    Lequel de ces couples (texte, motif) constitue un
\textbf{pire cas} pour l'algorithme naïf ?\medskip
    \begin{itemize}
        \item[A.] texte = \texttt{'hello'}, motif = \texttt{'hello'}
        \item[\alert<2>{B.}] \alert<2>{texte = \texttt{'aaaaaaaaa'}, motif = \texttt{'aaab'}}
        \item[C.] texte = \texttt{'abracadabra'}, motif = \texttt{'xyz'}
        \item[D.] texte = \texttt{'a'}, motif = \texttt{'ab'}
    \end{itemize}
\end{frame}

% Q10 - Réponse en B
\begin{frame}[fragile]{Question 10 \textemdash{} Direction de comparaison}
    Dans Boyer-Moore-Horspool, par quel caractère du motif
commence-t-on la comparaison ?\medskip
    \begin{itemize}
        \item[A.] Le premier (gauche)
        \item[\alert<2>{B.}] \alert<2>{Le dernier (droite)}
        \item[C.] Un caractère choisi au hasard
        \item[D.] Le caractère du milieu
    \end{itemize}
\end{frame}

% Q11 - Réponse en B
\begin{frame}[fragile]{Question 11 \textemdash{} Construction de la table}
    Pour le motif \texttt{"dab"} (longueur 3), quelle est la table
de décalages de Boyer-Moore-Horspool ?\medskip
    \begin{itemize}
        \item[A.] {'d': 3, 'a': 3, 'b': 3}
        \item[\alert<2>{B.}] \alert<2>{{'d': 2, 'a': 1}}
        \item[C.] {'d': 0, 'a': 1, 'b': 2}
        \item[D.] {'d': 2, 'a': 1, 'b': 0}
    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile]{Question 12 \textemdash{} Caractère absent du motif}
    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 ?\medskip
    \begin{itemize}
        \item[A.] 1
        \item[\alert<2>{B.}] \alert<2>{3 (la longueur du motif)}
        \item[C.] 0
        \item[D.] 2
    \end{itemize}
\end{frame}

% Q13 - Réponse en C
\begin{frame}[fragile]{Question 13 \textemdash{} Caractère répété}
    Pour le motif \texttt{"maman"} (longueur 5), quelle est la
table de décalages ?\medskip
    \begin{itemize}
        \item[A.] {'m': 0, 'a': 3}
        \item[B.] {'m': 4, 'a': 1}
        \item[\alert<2>{C.}] \alert<2>{{'m': 2, 'a': 1}}
        \item[D.] {'m': 2, 'a': 3, 'n': 0}
    \end{itemize}
\end{frame}

% Q14 - Réponse en A
\begin{frame}[fragile]{Question 14 \textemdash{} Pourquoi exclure le dernier caractère ?}
    Pourquoi exclut-on le dernier caractère du motif lors
du pré-traitement ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Parce qu'il donnerait un décalage de 0, ce qui ferait boucler l'algorithme}
        \item[B.] Pour économiser de la mémoire
        \item[C.] Parce qu'il est toujours absent du motif
        \item[D.] Parce que Python ne permet pas d'indexer la dernière position
    \end{itemize}
\end{frame}

% Q15 - Réponse en D
\begin{frame}[fragile]{Question 15 \textemdash{} Trace de Boyer-Moore}
    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 ?\medskip
    \begin{itemize}
        \item[A.] 11 (la longueur du texte)
        \item[B.] 2
        \item[C.] 1
        \item[\alert<2>{D.}] \alert<2>{3 (la longueur du motif)}
    \end{itemize}
\end{frame}

% Q16 - Réponse en C
\begin{frame}[fragile]{Question 16 \textemdash{} Complexité dans le pire cas}
    Quelle est la complexité de Boyer-Moore-Horspool dans
le \textbf{pire cas} ?\medskip
    \begin{itemize}
        \item[A.] O(n)
        \item[B.] O(log n)
        \item[\alert<2>{C.}] \alert<2>{O(n × m)}
        \item[D.] O(n + m)
    \end{itemize}
\end{frame}

% Q17 - Réponse en A
\begin{frame}[fragile]{Question 17 \textemdash{} Meilleur cas sous-linéaire}
    Quelle est la complexité dans le \textbf{meilleur cas} de
Boyer-Moore-Horspool ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{O(n / m)}
        \item[B.] O(n)
        \item[C.] O(m)
        \item[D.] O(1)
    \end{itemize}
\end{frame}

% Q18 - Réponse en B
\begin{frame}[fragile]{Question 18 \textemdash{} Quand BM n'apporte rien}
    Dans quel cas Boyer-Moore-Horspool n'apporte-t-il
\textbf{aucun gain} par rapport à l'algorithme naïf ?\medskip
    \begin{itemize}
        \item[A.] Quand l'alphabet est large
        \item[\alert<2>{B.}] \alert<2>{Quand le texte et le motif ne contiennent presque que des caractères identiques (par exemple uniquement des \texttt{'a'})}
        \item[C.] Quand le motif est très court
        \item[D.] Quand le texte est très long
    \end{itemize}
\end{frame}

% Q19 - Réponse en B
\begin{frame}[fragile]{Question 19 \textemdash{} Cas particuliers}
    Que doit renvoyer \texttt{recherche\_naif("abc", "")} (motif
vide) selon la convention de Python ?\medskip
    \begin{itemize}
        \item[A.] []
        \item[\alert<2>{B.}] \alert<2>{[0, 1, 2, 3]}
        \item[C.] [0]
        \item[D.] Une erreur (\texttt{ValueError})
    \end{itemize}
\end{frame}

% Q20 - Réponse en D
\begin{frame}[fragile]{Question 20 \textemdash{} Mécanisme de \texttt{grep}}
    La commande Unix \texttt{grep} (et ses variantes \texttt{egrep},
\texttt{fgrep}) utilise principalement quel type d'algorithme
pour la recherche de motifs simples ?\medskip
    \begin{itemize}
        \item[A.] Algorithme naïf O(n × m)
        \item[B.] Programmation dynamique
        \item[C.] Recherche dichotomique sur le texte
        \item[\alert<2>{D.}] \alert<2>{Variantes de Boyer-Moore (avec \texttt{fgrep} ou les motifs sans expression régulière)}
    \end{itemize}
\end{frame}

% Q21 - Réponse en D
\begin{frame}[fragile]{Question 21 \textemdash{} Nombre d'alignements de BM}
    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 ?\medskip
    \begin{itemize}
        \item[A.] 11
        \item[B.] 2
        \item[C.] 9 (comme l'algorithme naïf)
        \item[\alert<2>{D.}] \alert<2>{4}
    \end{itemize}
\end{frame}

% Q22 - Réponse en B
\begin{frame}[fragile]{Question 22 \textemdash{} Table d'un motif complexe}
    Quelle est la table de décalages de
Boyer-Moore-Horspool pour le motif \texttt{"abracadabra"}
(longueur 11) ?\medskip
    \begin{itemize}
        \item[A.] {'a': 1, 'b': 2, 'r': 3, 'c': 4, 'd': 5}
        \item[\alert<2>{B.}] \alert<2>{{'a': 3, 'b': 2, 'r': 1, 'c': 6, 'd': 4}}
        \item[C.] {'a': 0, 'b': 1, 'r': 2, 'c': 3, 'd': 4}
        \item[D.] {'a': 3, 'b': 2, 'r': 1, 'c': 6, 'd': 4, 'a': 0}
    \end{itemize}
\end{frame}

% Q23 - Réponse en A
\begin{frame}[fragile]{Question 23 \textemdash{} Choix d'algorithme}
    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} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{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)$}
        \item[B.] Algorithme naïf, suffisant pour la plupart des cas
        \item[C.] Recherche dichotomique
        \item[D.] Boyer-Moore-Horspool, simple à implémenter mais limité par l'alphabet réduit
    \end{itemize}
\end{frame}

% Q24 - Réponse en D
\begin{frame}[fragile]{Question 24 \textemdash{} Bug subtil}
    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 ?\medskip
    \begin{itemize}
        \item[A.] L'algorithme entre dans une boucle infinie
        \item[B.] L'algorithme est plus rapide (gain négligeable)
        \item[C.] L'algorithme renvoie des positions incorrectes
        \item[\alert<2>{D.}] \alert<2>{L'algorithme rate les motifs situés à la toute fin du texte}
    \end{itemize}
\end{frame}

% Q25 - Réponse en D
\begin{frame}[fragile]{Question 25 \textemdash{} Comparaison synthétique}
    Parmi les affirmations suivantes sur les algorithmes
de recherche textuelle vus en NSI, laquelle est
\textbf{fausse} ?\medskip
    \begin{itemize}
        \item[A.] L'algorithme naïf a une complexité O(n × m) dans le pire cas
        \item[B.] Boyer-Moore-Horspool peut atteindre O(n / m) dans le meilleur cas
        \item[C.] Pour de nombreux motifs simultanés, on préfère Aho-Corasick à Boyer-Moore
        \item[\alert<2>{D.}] \alert<2>{Boyer-Moore-Horspool est toujours plus rapide que l'algorithme naïf}
    \end{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Code de l'algorithme naïf}
    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 ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def recherche_naif(texte, motif):
    for i in range(len(texte)):
        if texte[i] == motif:
            return i
    return -1
\end{lstlisting}

        \item[B.]~\\
\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}

        \item[C.]~\\
\begin{lstlisting}
def recherche_naif(texte, motif):
    return [i for i, c in enumerate(texte) if c == motif[0]]
\end{lstlisting}

        \item[D.]~\\
\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{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Code de l'algorithme naïf}
    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 ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def recherche_naif(texte, motif):
    for i in range(len(texte)):
        if texte[i] == motif:
            return i
    return -1
\end{lstlisting}

        \item[\alert{B.}]~\\
\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}

        \item[C.]~\\
\begin{lstlisting}
def recherche_naif(texte, motif):
    return [i for i, c in enumerate(texte) if c == motif[0]]
\end{lstlisting}

        \item[D.]~\\
\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{itemize}
\end{frame}

% Q27 - Réponse en D
\begin{frame}[fragile]{Question 27 \textemdash{} Saut maximal en pratique}
    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 ?\medskip
    \begin{itemize}
        \item[A.] 1 position
        \item[B.] 0 position (on doit tester à nouveau au même endroit)
        \item[C.] 4 positions (la moitié de la longueur du motif)
        \item[\alert<2>{D.}] \alert<2>{8 positions (la longueur du motif)}
    \end{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
