% !TeX encoding = UTF-8
% !TeX spellcheck = fr_FR

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Concours commun INP                                %
% https://www.concours-commun-inp.fr                 %
% CC BY-NC-SA, Novembre 2025                         %
% https://creativecommons.org/licenses/by-nc-sa/4.0/ %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Pour compiler : lualatex -shell-escape
\documentclass{ccinp}

\lfoot{\includegraphics[width=5em]{by-nc-sa.eu.png}}
\cfoot{\thepage}
\rfoot{9 novembre 2025}

\begin{document}


\title{Sélection de sujets posés lors de la session 2025}
\date{}



\maketitle
\thispagestyle{fancy}

\section*{Exercices de type A}
\exocommand{Course d'escargots (type A)}
On s'intéresse à l'organisation d'une course d'escargots.
Dans ce milieu les paris peuvent monter haut et les enjeux importants poussent parfois au dopage des escargots participant à ces courses.
Vous êtes chargé de proposer une méthode utilisant de l'apprentissage automatique pour mieux cibler les tests sur les escargots les plus susceptibles d'avoir été dopés.

Les seules informations disponibles concernant les escargots en amont de la course sont leur masse et la longueur de leur antennes.

Pour vous aider dans votre tâche, l'organisation en charge de la course met à votre disposition les données passées concernant les tests réalisés, contenant les informations suivantes:
\begin{itemize}
  \item Numéro du test
  \item Masse de l'escargot (g)
  \item Longueur des antennes (mm)
  \item Résultat du test
\end{itemize}
Sur la base de ces informations, il vous est demandé de proposer une approche permettant, en amont d'une course, de prédire pour chaque escargot s'il est ou non dopé.
\begin{enumerate}
  \item De quel type de problème d'apprentissage s'agit-il ?
  \item L'algorithme de classification hiérarchique ascendante serait-il pertinent pour résoudre ce problème ? Justifier brièvement votre réponse.
\end{enumerate}

La figure (A) présente de manière graphique la liste des tests passés fournie par l'organisation de la course. La figure (B) est une liste d'escargots qui participeront à la prochaine course.


\begin{minipage}[t]{0.59\linewidth}
\begin{center}
\includegraphics{escargot.png}
\smallbreak
\begin{center}
 \textit{A: La liste des tests passés et leur résultat. Les tests positifs sont marqué d'un + et ceux négatifs sont marqué d'un -. En abscisse la masse et en ordonnée la longueur des antennes.}
\end{center}
\end{center}

\end{minipage}
\begin{minipage}[t]{0.39\linewidth}
\begin{center}
\bigbreak
\bigbreak
\bigbreak
\bigbreak
\begin{tabular}{|c|c|c|}
  \hline
  n$^{\circ}$ candidat & Masse & Longueur\\
  \hline
  0 & 20 & 12 \\
  1 & 50 & 12 \\
  2 & 40 & 15 \\
  3 & 30 & 21 \\
  \hline
\end{tabular}
\smallbreak
\begin{center}
 \textit{B: Les escargots participant à la prochaine course.}
\end{center}
\end{center}
\end{minipage}

On souhaite réaliser les prédictions à l'aide de l'algorithme des $k$ plus proches voisins.
\begin{enumerate}[resume]
  \item Rappelez le principe de cet algorithme et détaillez la manière dont on pourrait l'appliquer dans le cas présent.
\end{enumerate}
\begin{enumerate}[resume]
  \item On fixe $k=3$ et on utilise la distance euclidienne. Quels sont les escargots pour lesquels ce modèle prédit un dopage possible ?
  \item Quelle est la complexité temporelle d'une prédiction de cet algorithme dans le cas général (le nombre de points $n$ et la valeur de $k$ ne sont pas supposés fixés) ?
  \item Est-ce possible d'espérer une complexité meilleure via l'usage d'une implémentation adaptée ?
\end{enumerate}
Par conscience professionnelle, vous vous demandez si le modèle utilisé est efficace et en particulier si vous avez correctement choisi la valeur de $k$.
Pour répondre à cette question, vous tentez de prédire le résultat du test des 10 premiers escargots d'une seconde liste, plus grande et fournie par l'organisation de la course, pour différentes valeurs de $k$.

Pour $k=3$ vous obtenez les prédictions suivantes:

\begin{center}
\begin{tabular}{|c|c|c|c|}
  \hline
  numéro du test & prédiction & résultat réel\\
  \hline
  0 & négatif & négatif \\
  1 & négatif & positif \\
  2 & négatif & négatif \\
  3 & positif & négatif \\
  4 & positif & positif \\
  5 & négatif & négatif \\
  6 & positif & négatif \\
  7 & négatif & négatif \\
  8 & positif & négatif \\
  9 & positif & positif \\
  \hline
\end{tabular}
\end{center}
\begin{enumerate}[resume]
  \item Dressez la matrice de confusion de ces prédictions. Commentez le résultat obtenu.
\end{enumerate}
À l'aide de nombreux calculs, vous obtenez le tableau suivant donnant le taux de prédictions correctes de votre modèle pour différentes valeur de $k$ sur les 10 premiers tests de la seconde liste.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
  \hline
  k & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
  \hline
  taux de prédictions correctes & 30\% & 40\% & 70\% & 40\% & 30\% & 10\% & 5\%\\
  \hline
\end{tabular}
\end{center}

Vous choisissez donc de conserver $k=3$.
\begin{enumerate}[resume]
  \item Est-ce raisonnable d'affirmer que votre modèle a un taux de prédictions correctes de $70\%$ ?
\end{enumerate}
\paragraph*{Proposition de corrigé}
\begin{enumerate}
  \item  Il s'agit d'un problème d'apprentissage supervisé, et plus précisément de classification binaire pour prédire la valeur du test de dopage.
  \item  Non, puisque la classification hiérarchique ascendante est un algorithme d'apprentissage non supervisé. 
  \item  Pour prédire la classe d'un point, on regarde la classe majoritaire parmi ses $k$ plus proches voisins.
        Ici, on tente de prédire le résultat du test (la classe) à partir de la proximité vis à vis des caractéristiques connues en amont: masse et longueur des antennes. Sans précisions supplémentaire on pourra choisir la distance euclidienne sur le couple des entrées.
        
  \item  Il faut appliquer l'algorithme des $k$ plus proches voisins. Un dessin permet de donner des réponses immédiates sans avoir besoin de réaliser des calculs. Les résultats prédits sont, dans l'ordre:

        \begin{tabular}{|c|c|c|c|}
          \hline
          numéro du candidat escargot & Masse (en g) & Longueur des antennes (en mm) & prédiction de dopage\\
          \hline
          0 & 20 & 12 & positive\\
          1 & 50 & 12 & négative\\
          2 & 40 & 15 & positive\\
          3 & 30 & 21 & négative\\
          \hline
        \end{tabular}
  \item  On doit trouver les $k$ plus proches voisins, il y a plusieurs manières de procéder, mais la plus simple est de calculer toutes les distances, puis de trier la liste des distances obtenues et de prendre les $k$ premières.
        La complexité du calcul des distances dans ce cas est en $O(n)$ et $O(dn)$ dans le cas général d'une distance euclidienne de dimension $d$.
        Le tri est en $O(n\log(n))$ via un algorithme adapté.
        Une prédiction est donc en $O(n\log(n))$.
  \item  On pourrait utiliser des arbres $d$-dimensionnels pour élaguer une partie de la recherche des voisins.
        Cela ne change rien au pire cas, mais peut améliorer la complexité dans certains cas. Si une file de priorité est proposée pour passer de $n\log(n)$ à $n\log(k)$ est proposée, on demande une autre structure plus spécifique au problème et on ne donne les points que si les arbres $d$-dimensionnels sont connus.
  \item  pour la matrice.

        On obtient la matrice suivante:

        \begin{tabular}{|c|c|c|}
          \hline
          & prédiction test positif & prédiction test négatif\\
          \hline
          test positif & 2 & 1\\
          \hline
          test négatif & 3 & 4\\
          \hline
        \end{tabular}

         pour le commentaire.

        On peut observer que le modèle semble bien plus fiable pour prédire qu'un test sera négatif (20\% de faux négatifs) que pour prédire qu'un test sera positif (60\% de faux positifs).

        Si on prédit que le test sera positif il faut donc rester très prudent, mais si le modèle prédit un test négatif, il est peu utile de tester quand même.
        
  \item  Non puisque la valeur $k$ a été choisie sur la base de ce taux d'erreur, qui est donc nécessairement biaisé puisque cette maximisation du taux gonfle celui-ci. On peut aussi accepter une réponse indiquant qu'une corrélation croisée devrait être réalisée et que se baser uniquement sur le taux de prédiction des 10 premiers n'est pas très fiable.
\end{enumerate}
\newpage

\exocommand{Grammaires (type A)}
\begin{enumerate}
\item Soit $\Sigma_0 = \{ \texttt{\textbf{a}}, \texttt{\textbf{b}}, ..., \texttt{\textbf{z}} \}$ l'ensemble des caractères alphanumériques minuscules. Quel est le langage engendré par la grammaire suivante de symbole initial $S$ et d'alphabet terminal $\Sigma_0$ ? \[S \rightarrow \varepsilon \, | \, AS \qquad A \rightarrow \sigma \text{ avec $\sigma \in \Sigma_0$} \]
\end{enumerate}

On considère un langage de programmation $\hat{\texttt{C}}$ (prononcé \textit{C chapeau}) qui peut être vu comme un sous ensemble de \texttt{C}. On rappelle qu'un \textit{identificateur} est un nom choisi par le programmeur qui peut être utilisé pour désigner une variable ou une fonction. 

En $\hat{\texttt{C}}$, un identificateur est une séquence de caractères de $\Sigma_1 = \{\texttt{\textbf{a}},... \texttt{\textbf{z}}, \texttt{\textbf{A}},..., \texttt{\textbf{Z}}, \texttt{\textbf{0}}, ..., \texttt{\textbf{9}},\texttt{\_} \}$ ne commençant pas par un chiffre. Exemples d'identificateurs : \texttt{\textbf{x}} \qquad \texttt{\textbf{Tea4Two}} \qquad \texttt{\textbf{\_foo\_bar}}

\begin{enumerate}[resume]
    \item Donner une grammaire de symbole initial $X$ qui engendre exactement le langage des mots qui sont des identificateurs valides en $\hat{\texttt{C}}$.
\end{enumerate}

Dans toute la suite, on suppose que $E$ est le symbole initial d'une grammaire permettant d'engendrer les expressions en $\hat{\texttt{C}}$. On considère à présent un non-terminal $I$ destiné à engendrer les instructions de $\hat{\texttt{C}}$. Ces dernières sont : soit une expression (éventuellement absente dans le cas d'une instruction vide) suivie du caractère '\texttt{\textbf{;}}', soit une instruction \texttt{\textbf{while}}, soit un \textit{bloc}. On obtient ainsi les règles suivantes : \begin{align*}
    (1) & \quad I \longrightarrow E \texttt{\textbf{;}} \\
    (2) & \quad I \longrightarrow \texttt{\textbf{;}} \\
    (3) & \quad I \longrightarrow \texttt{\textbf{while (}} \, E \, \texttt{\textbf{)}} \,\,\, I \\
    (4) & \quad I \longrightarrow B
\end{align*}

Le non-terminal $B$ est destiné à engendrer les blocs de $\hat{\texttt{C}}$, sachant qu'un bloc est une liste (éventuellement vide) d'instructions délimité par une accolade ouvrante et une accolade fermante. Exemple : \\ \texttt{\textbf{\{ while (a!=1)\{ \quad a= 3*a+1; \{\} ;; while (a\%2 ==0) a= a/2; \} \}  }}

\begin{enumerate}[resume]
    \item Montrer que tout mot engendré par $I$ se termine par un point-virgule ou une accolade fermante.
    \item Indiquer quelles règles ajouter aux règles (1) à (4) pour que le langage engendré par $B$ soit celui des blocs en $\hat{\texttt{C}}$.
    \item Le langage engendré par $I$ est-il rationnel ?
\end{enumerate}

Similairement à \texttt{C}, $\hat{\texttt{C}}$ a une instruction conditionnelle. Elle est définie syntaxiquement par l'ajout de la règle (5) à $I$ : le non-terminal $O$ désigne une branche sinon (\texttt{\textbf{else}}) : \begin{align*}
    (5) & \quad I \longrightarrow \texttt{\textbf{if (}} \, E \, \texttt{\textbf{)}} \,\,\, I \,\,\, O \\
    (6) & \quad O \longrightarrow \texttt{\textbf{else}} \,\,\, I \\
    (7) & \quad O \longrightarrow \, \varepsilon
\end{align*}

\begin{enumerate}[resume]
    \item Après avoir ajouté ces règles, la grammaire de symbole initial $I$ est-elle ambiguë ? Justifier votre réponse en considérant l'instruction suivante : \texttt{\textbf{if (x) if (y) a = a+1; else a = a+2;}}
\end{enumerate}

Similairement à \texttt{C}, la sémantique de $\hat{\texttt{C}}$ élimine les ambiguités des \texttt{\textbf{if}}/\texttt{\textbf{else}} en rattachant le \texttt{\textbf{else}} au \texttt{\textbf{if}} le plus proche parmi les \texttt{\textbf{if}} ambigus. Par exemple, \texttt{\textbf{if (e1) if (e2) e3; else e4;}} équivaut sémantiquement à \texttt{\textbf{if (e1) \{if (e2) e3; else e4;\}}}

\begin{enumerate}[resume]
    \item Donner une grammaire non-contextuelle non ambiguë rattachant le \texttt{\textbf{else}} au \texttt{\textbf{if}} le plus proche.
\end{enumerate}

\paragraph*{Proposition de corrigé}
\begin{enumerate}
\item  $S$ engendre $\Sigma_0^{\star}$.
\item  Voici une grammaire convenable (la sémantique de $P$ est "première lettre", celle de $M$ est "mot de $\Sigma_1^{\star}$" et celle de $S$ est "symbole de $\Sigma_1$") : \[X \rightarrow PM \quad P \rightarrow \texttt{\textbf{a}} | ... |  \texttt{\textbf{z}} | \texttt{\textbf{A}} | ... | \texttt{\textbf{Z}} | \texttt{\textbf{\_}} \quad M \rightarrow \varepsilon | SM \quad S \rightarrow P | \texttt{\textbf{0}} | ...| \texttt{\textbf{9}} \] 

\item Les règles (1), (2) et (4) terminent une dérivation à partir de $I$ par \texttt{\textbf{;}} ou \texttt{\textbf{\}}}. Donc inductivement sur la dérivation (ou par récurrence sur sa longueur), la règle (3) termine aussi une dérivation à partir de $I$ par ces symboles, ce qui conclut.
\item Une possibilité : \[B \rightarrow \texttt{\textbf{\{}} \, L \, \texttt{\textbf{\}}} \quad L \rightarrow I \,\, L \, | \, \varepsilon \]
\item  Le langage engendré par $I$ n'est pas régulier. En effet s'il l'était, son intersection avec $\{^{\star}\}^{\star}$ le serait. Or ce langage est le langage $\{ \{^n \}^n \, | \, n \in \mathbb{N}^{\star} \}$ qui n'est pas régulier.
\item Cette grammaire est ambiguë car le mot proposé par l'énoncé admet deux arbres de dérivation. Les deux commencent en utilisant la règle (5) puis l'un dérive le $O$ ainsi produit avec la règle (7) alors que l'autre le dérive avec la règle (6).




\item Le if-else est distingué du if sans else : dans le if-else, l'instruction du then peut être tout sauf un if-then. D'où les règles suivantes : \[I \rightarrow \texttt{\textbf{if (}} \, E \, \texttt{\textbf{)}} \, I \, | \, J \qquad J \rightarrow E \texttt{\textbf{;}} \, | \, \texttt{\textbf{;}} \, | \, \texttt{\textbf{while (}} \, E \, \texttt{\textbf{)}} \,\, I \, | \, B \, | \, \texttt{\textbf{if (}} \, E \, \texttt{\textbf{)}} \,\, J \,\, \texttt{\textbf{else}} \,\, I \]
\end{enumerate}

\section*{Exercices de type B}
\exocommand{wildcards (type B)}

\preambuleocaml

On définit un \textit{motif} comme étant un mot sur l'alphabet $\{\texttt{a}, \texttt{b}, \texttt{?}, \texttt{*} \}$ et un \textit{texte} comme étant un mot sur l'alphabet $\Sigma = \{\texttt{a}, \texttt{b}\}$. L'objectif de l'exercice est de déterminer si un texte \textit{respecte} un certain motif (on dit alors aussi que le motif \textit{capture} le texte) avec comme conventions que :
\begin{itemize}
    \item Le caractère \texttt{?} dans un motif signifie "n'importe quel caractère de $\Sigma$ est autorisé".
    \item Le caractère \texttt{*} dans un motif signifie "n'importe quel mot de $\Sigma^{\star}$ (y compris $\varepsilon$) est autorisé".
  \end{itemize}
  Autrement dit, un texte est capturé par un motif si c'est un mot qui appartient au langage décrit par le motif. Par exemple les textes \texttt{abba} et \texttt{aabaaaba} respectent le motif \texttt{a?ba*} (car ils commencent par \texttt{a}, puis contiennent une lettre, puis se poursuivent par le facteur \texttt{ba}, puis terminent par un nombre quelconque de lettres) alors que ce même motif ne capture pas le texte \texttt{abaab}.
  
  \medskip
  
  \begin{enumerate}
    \item Parmi les textes suivants, indiquer ceux qui respectent le motif $m_0 = \texttt{*ab$$*$$?a}$ : \begin{multicols}{3}
      \begin{enumerate}
        \item \texttt{aab}
        \item \texttt{abab}
        \item \texttt{abbbbaa}
        \item \texttt{babaa}
        \item \texttt{aaaba}
        \item \texttt{abbabba}
      \end{enumerate}
    \end{multicols}
  \end{enumerate}
  
  Ces textes sont stockés dans une liste \mio{textes} dans le code compagnon ; qui servira ainsi aux tests. Pour les questions 2 à 5, on représente textes et motifs par un type \mio{chaine} défini par :
  \begin{fancy-code}{ocaml}
    type chaine = char list
  \end{fancy-code}
  Remarquons que le mot vide $\varepsilon$ est ainsi représenté en OCaml par la liste vide \mio{[]}.
  
  \begin{enumerate}[resume]
    \item \'Ecrire une fonction \mio{chaine_of_string} qui convertit un objet de type \mio{string} en l'objet de type \mio{chaine} correspondant. Ainsi, \mio{chaine_of_string "aa*b"} s'évalue en la liste \mio{['a';'a';'*';'b']}. 
    \item Vu notre objectif, expliquer pourquoi il est inutile dans un motif d'avoir plusieurs $*$ consécutives.
    \item \'Ecrire une fonction \mio{purge : chaine -> chaine} qui supprime les étoiles consécutives inutiles du motif en entrée. Ainsi, \mio{purge ['a';'*';'*';'*';'b';'*']} s'évalue en \mio{['a';'*';'b';'*']}.
  \end{enumerate}
  
  \medskip
  
  On suppose dans la suite qu'on ne travaille qu'avec des motifs purgés, c'est-à-dire sans occurrences consécutives d'étoiles. Au besoin, les motifs seront modifiés via \mio{purge} pour s'en assurer.
  
  Pour savoir si un texte respecte un motif donné, on propose tout d'abord la stratégie récursive naïve suivante. On compare la première lettre $u$ du motif et la première lettre $v$ du texte : \begin{itemize}
    \item Si $u \in \{\texttt{a}, \texttt{b} \}$ et coïncide avec $v$ on vérifie que la fin du texte respecte la fin du motif.
    \item Si $u = \texttt{?}$, on vérifie que la fin du texte respecte la fin du motif.
    \item Si $u = \texttt{*}$, il y a deux possibilités pour que le texte respecte le motif : soit cette \texttt{*} représente $\varepsilon$ dans le texte, soit elle représente un mot auquel la lettre $v$ appartient. On vérifie que dans au moins un des deux cas, le morceau de texte restant respecte le morceau de motif restant.
  \end{itemize}
  
  Le code compagnon fournit une fonction (incomplète) \mio{respecte_naif : chaine -> chaine -> bool} prenant dans cet ordre un motif et un texte et destinée à renvoyer \mio{true} si et seulement si le texte respecte le motif en suivant la stratégie précédente.
  
  \medskip
  
  \begin{enumerate}[resume]
    \item Expliquer brièvement la correction des cas traités dans \mio{respecte_naif}.
    \item Compléter la fonction \mio{respecte_naif} et vérifier qu'elle se comporte comme attendu sur les exemples de la question 1.
  \end{enumerate}
  
  On admet que la fonction \mio{respecte_naif} a une complexité exponentielle en la taille de son entrée. Pour~améliorer cette complexité, on propose de déterminer si un texte $t = t_0...t_{|t|-1}$ respecte un motif $m = m_0...m_{|m|-1}$ par programmation dynamique. 
  
  Pour tout $i \in \llbracket 0, |m| \rrbracket$ et tout $j \in \llbracket 0, |t| \rrbracket$, on note $p(i,j)$ le booléen valant vrai si et seulement si le préfixe de longueur $j$ du texte respecte le préfixe de longueur $i$ du motif.
  
  \begin{enumerate}[resume]
    \item Pour $j \in \llbracket 0, |t| \rrbracket$, que vaut $p(0,j)$ ? Pour $i \in \llbracket 0, |m| \rrbracket$, que vaut $p(i,0)$ ?
  \end{enumerate}
  
  On admet la validité des relations suivantes : pour tout $i \in \llbracket 1, |m|\rrbracket$ et tout $j \in \llbracket 1, |t| \rrbracket$ on a : \begin{center}
    $p(i,j) = \begin{cases}
      p(i-1,j-1) & \text{\quad si $m_{i-1}$ vaut \texttt{?}} \\
      p(i-1,j-1) \wedge (m_{i-1} = t_{j-1}) & \text{\quad si $m_{i-1}$ vaut \texttt{a} ou \texttt{b}} \\
      p(i-1,j) \lor p(i,j-1) & \text{\quad si $m_{i-1}$ vaut \texttt{*}}
    \end{cases}$
  \end{center}
  
  \begin{enumerate}[resume]
    \item \'Ecrire une fonction \mio{respecte_dynamique : string -> string -> bool} prenant en entrée dans cet ordre un motif et un texte sous forme de chaînes de caractères et renvoyant \mio{true} si et seulement si le texte respecte le motif selon la stratégie dynamique. On demande d'adopter une approche de bas en haut (bottom-up). On rappelle l'existence de la fonction \mio{Array.make_matrix}.
    \item Déterminer les complexités temporelle et spatiale de \mio{respecte_dynamique}. Peut-on améliorer la complexité spatiale à moindres frais ? Justifier.
  \end{enumerate}

\paragraph*{Proposition de corrigé}
\begin{enumerate}
      \item Le motif $m_0$ permet de capturer les textes qui contiennent le facteur $ab$ puis qui contiennent une lettre et terminent par $a$. Les textes qui respectent $m_0$ sont c, d, f.
      
      
  \item On accumule les caractères de l'entrée en tête (pour des raisons de complexité) d'une liste initialement vide. On la renvoie renversée pour respecter l'ordre initial de l'entrée :
        \begin{fancy-code}{ocaml}
      let chaine_of_string (s:string) :chaine =
        let res = ref [] in
        for i = 0 to (String.length s) -1 do
          res := s.[i]::(!res)
        done;
        List.rev !res
      \end{fancy-code}
      
      \item La concaténation de $k$ mots quelconques est un mot quelconque. Réciproquement, un mot quelconque $m$ est la concaténation de $k$ mots, par exemple $m$ suivi de $k-1$ fois $\varepsilon$. On en déduit que pour tout $k \geq 1$, le motif $*$ et le motif $\underbrace{* ... *}_{k \text{ fois}}$ capturent les mêmes textes.
      
      
      \item On filtre simplement la chaîne sur ses deux premiers éléments : \begin{fancy-code}{ocaml}
      let rec purge (s:chaine) :chaine =
        match s with
        |[]  |[_] -> s
        |'*'::'*'::q -> purge ('*'::q)
        |a::q -> a::(purge q)
      \end{fancy-code}
    
  \item Le code fourni traite en fait les cas de base :
        \begin{itemize}
        \item Un texte vide respecte le motif vide (ligne 1).
        \item Si le motif est vide mais pas le texte, le texte ne peut pas respecter le motif (ligne 4).
        \item Si le texte est vide, le seul motif qui le capture est $*$ (puisque seules les successions de $*$ permettent de capturer $\varepsilon$ et que le motif est purgé), d'où les lignes 2 et 3.
      \end{itemize} 
  
      \item  
      
      Il ne reste plus qu'à suivre la stratégie proposée :
      \begin{fancy-code}{ocaml}
        let rec respecte_naif (motif:chaine) (texte:chaine) :bool =
          match motif, texte with
          |[], [] -> true
          |['*'], [] -> true
          |_, [] -> false
          |[], _ -> false
          |a::b, c::d when a = c || a = '?' -> respecte_naif b d
          |'*'::b, _::d -> (respecte_naif b texte) || (respecte_naif motif d)
          |_ -> false
        \end{fancy-code}
    
        Le dernier cas permet de traiter la situation où le motif commence par une lettre de $\{a,b\}$ mais qui ne coïncide pas avec la première lettre du texte. L'avant-dernier cas traduit l'énoncé. Premier cas : on ne consomme pas de lettre du texte, ce qui correspond au cas où $*$ représente $\varepsilon$ dans le motif. Second cas : l'$*$ du motif consomme la première lettre du texte ; et est susceptible de consommer les suivantes.
    
        On vérifie ensuite les réponses de la question 1 :
        \begin{fancy-code}{ocaml}
          let m0 = chaine_of_string "*ab*a?"
          let _ = List.map (respecte_naif m0) (List.map chaine_of_string textes)
        \end{fancy-code}
  
        
    
  \item On constate que répondre à ces questions revient à traduire les cas de base de la fonction \mio{respecte_naif} :
        \begin{itemize}
          \item $p(0,0)$ vaut vrai puisque $\varepsilon$ respecte $\varepsilon$.
          \item Pour tout $j \geq 1$, $p(0,j)$ vaut faux car un texte non vide ne peut pas respecter $\varepsilon$.
          \item Pour tout $i \geq 2$, $p(i,0)$ vaut faux car $\varepsilon$ ne peut pas respecter un motif de taille au moins deux ; ce dernier contenant au moins un symbole différent de $*$ puisqu'il est purgé.
          \item Enfin il reste le cas particulier de $p(1,0)$, qui vaut vrai si et seulement si la première lettre du motif est $*$ car c'est la seule possibilité pour que $\varepsilon$ le respecte.
        \end{itemize}
        \item  On souhaite calculer $p(|m|,|t|)$ puisque c'est le booléen valant vrai si et seulement si le préfixe de taille le texte du texte (donc le texte) respecte le préfixe de taille le motif du motif (donc le motif). 
        
        On calcule donc la matrice $(p(i,j))_{0 \leq i \leq |m|, 0 \leq j \leq |t|}$, de taille $(1+ |m|) \times (1 + |t|)$. Sa première ligne et sa première colonne se remplissent grâce à la question 6. Puis, on la remplit ligne à ligne (ce qui est possible vu les relations). Il ne reste plus qu'à extraire le bon coefficient :
        \begin{fancy-code}{ocaml}
    let respecte_dynamique (motif:string) (texte:string) :bool =
      let n = String.length motif in
      let m = String.length texte in
      let res = Array.make_matrix (n+1) (m+1) false in
      res.(0).(0) <- true;
      res.(1).(0) <- motif.[0] = '*';
      for i = 1 to n do
        for j = 1 to m do
          match motif.[i-1] with
          |'?' -> res.(i).(j) <- res.(i-1).(j-1)
          |'*' -> res.(i).(j) <- res.(i-1).(j) || res.(i).(j-1)
          |_ -> res.(i).(j) <- res.(i-1).(j-1) && motif.[i-1] = texte.[j-1]
        done;
      done; 
      res.(n).(m)
        \end{fancy-code}
  
        
        
        \item Calculer un coefficient de la matrice précédente se fait en temps constant. On en déduit que la complexité temporelle de \mio{respecte_dynamique} est en $O(|t||m|)$. C'est aussi le cas de la complexité spatiale.
        
        On peut la faire passer à un $O(|t|)$ en ne conservant que deux lignes de la matrice à tout moment et même à un $O(\min(|m|, |t|))$ car la relation de récurrence permet un remplissage ligne à ligne ou colonne par colonne : on peut donc choisir ce qui est le plus avantageux du point de vue spatial.
  
        
    \end{enumerate}
    \newpage
\exocommand{Saisie swype (type B)}

\preambulec

\begin{minipage}{.75\linewidth}
Certains claviers de smartphones autorisent une saisie par glissement
du doigt (\emph{swype} en anglais): l'utilisateur pose son doigt sur
la première lettre du mot et, sans soulever le doigt, le fait glisser
de sorte à ce qu'il passe successivement et dans l'ordre sur les
lettres du mot qu'il souhaite écrire, jusqu'à la dernière lettre de ce
mot. À ce moment-là, il peut soulever son doigt et un mot apparaît à
l'écran, qui appartient à la langue dans laquelle le clavier est
paramétré. Bien entendu, pendant le déplacement du doigt, ce dernier
est passé sur des caractères qui n'appartiennent pas au mot. Par
exemple, sur un clavier azerty réglé en français, pour écrire le mot
``pour'', il suffit de faire glisser horizontalement le doigt de la
lettre ``p'' à la lettre ``r''. On passe par les lettres ``p'', ``o'',
``i'', ``u'', ``y'', ``t'' et ``r'', dont certaines appartiennent au
mot ``pour'' et d'autres non, comme illustré dans la figure ci-contre.
\end{minipage}\qquad
\begin{minipage}{.15\linewidth}
  \includegraphics[height=6cm]{pour.png}
\end{minipage}

Le but de cet exercice est de trouver tous les mots d'un lexique
qui sont sous-mots d'une suite de lettres saisie et possèdent les
mêmes première et dernière lettre que cette suite.

Dans tout le sujet, on suppose que la langue de paramétrage du sujet
est le français, et on ne considère que des mots écrits avec des
lettres latines minuscules sans accents, à l'exclusion de tout autre
type de caractères (par exemple pas de tiret ou d'apostrophe dans les
mots considérés).

Le code fourni est mis dans trois fichiers:
\begin{itemize}
\item le fichier d'en-tête \mib{auxiliaire.h} contient les déclarations
  des types et fonctions, et la documentation associée: il faut le lire;
\item le fichier \mib{auxiliaire.c} contient les définitions des
  fonctions fournies; il est inutile de le regarder, mais il est
  nécessaire pour la compilation;
\item le fichier \mib{compagnon.c} qui contient une fonction \mic{main} et
  des fonctions à trou pour certaines questions; c'est dans ce
  fichier que vous devez écrire votre code.
\end{itemize}

Vous est par ailleurs fourni un fichier \mib{lexique.txt} contenant un
lexique (le code compagnon se sert de ce fichier pour remplir une
certaine structure de données décrite en partie~\ref{sec-recherche},
inutile pour vous de connaître le format de ce fichier).

\section{Fonctions auxiliaires}
Pour des raisons pratiques sur lesquelles nous reviendrons plus tard,
pendant l'exécution de l'algorithme principal, les mots sont stockés
à l'envers (de la dernière à la première lettre).

Un mot est représenté en \mib{C} par une chaîne de caractères, et nous
représenterons un ensemble de mots par une liste chaînée de type
\mic{liste} qui est un synonyme de \mic{struct maillon *}, types
définis dans \mib{auxiliaire.h} (sans nous soucier des éventuels doublons).

\subsection{Affichages}
\begin{enumerate}
\item Écrire une fonction
  \mic{void affiche_miroir(char *mot)} qui affiche une chaîne de
  caractères à l'envers (de la dernière à la première lettre).
\item Écrire une fonction
  \mic{void affiche_liste(liste lst)} qui affiche tous les mots de la
  liste \mic{lst} séparés par des retours à la ligne, chaque mot étant
  affiché à l'envers.
\end{enumerate}

\subsection{Gestion de listes de mots}
Notez que les maillons des listes contiennent chacun un mot (champ
\mic{mot}) et sa longueur (champ~\mic{n}).
\begin{enumerate}[resume]
\item Compléter la fonction \mic{void ajout_lettre(char c, liste lst)}
  qui ajoute le caractère \mic{c} à la fin de chaque chaîne de caractère
  de la liste  \mic{lst} (ce qui correspond donc à un ajout au début
  de chaque mot lors de l'affichage).
  On suppose (sans avoir à le vérifier) que la place
  mémoire allouée pour chaque champ \mic{mot} est suffisante pour cet
  ajout. La complexité de votre fonction doit être linéaire en la
  longueur de la liste (sans avoir à le justifier).
\item Justifier brièvement la complexité temporelle de votre fonction dans
  le pire des cas. Quelle aurait été la complexité
  d'une fonction ajoutant le caractère \mic{c} au début de chaque mot de
  la liste \mic{lst}?\label{q-envers}
\end{enumerate}


\section{Fonction principale : Recherche de mots}\label{sec-recherche}
Le fichier d'en-tête \mib{auxiliaire.h} vous fournit un type
\mic{lexique} et une fonction \mic{genere_lexique}
permettant d'obtenir une adresse d'une valeur de ce type (cette fonction utilise le
fichier \mib{lexique.txt} également fourni). Le type \mic{lexique}
représente un arbre lexicographique dont chaque n\oe ud interne
contient 26 fils rangés dans un tableau: le fils d'indice~\mic{0}
représente la lettre $a$, le fils d'indice~\mic{1} le lettre
$b$, etc. Chaque n\oe ud de cet arbre contient un marqueur (le
champ \mic{fin}) qui indique si la suite des lettres de la racine à ce
n\oe ud est un mot du lexique ou pas. Si un fils est
\mic{NULL}, cela signifie que le mot atteint suivi de la lettre
correspondant au fils n'est pas le préfixe d'un mot existant dans le
lexique. La figure 
ci-dessous donne l'arbre lexicographique obtenu pour le lexique
constitué des mots \mic{"aaa"}, \mic{"ab"} et \mic{"aba"}. À droite de
chaque n\oe ud de l'arbre est indiquée l'étiquette du chemin de la
racine vers ce n\oe ud.


\newcommand{\croix}[1]{%
  \path[draw,gray] (#1.north east) -- (#1.south west)
  (#1.north west) -- (#1.south east);
}

\begin{center}
  \scalebox{.8}{
\begin{tikzpicture}[node distance=2.5cm,auto,>=latex]
\begin{scope}
  \node [draw,minimum size=3em,text width=6.1cm] (a) {\mic{false}};
  \node [draw,minimum size=3em,anchor=north,text width=6.1cm] (b) at
  (a.south) {};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x0) at
  (b.west) {\;\;\!};
  \node at (x0.center) {$\bullet$};
  \foreach \x[count=\i from 0] in {1,2,...,26} {%
    \node[draw,inner sep=1pt,anchor=west,text height=3ex] (x\x) at
    (x\i.east) {\;\;\!};
    \croix{x\x}
  }

  \node [draw,inner sep=1pt,anchor=north west] (eta) at (a.north west) {\mic{fin}};
  \node [draw,inner sep=1pt,anchor=north west] (etb) at (b.north west)
        {\mic{s}};
\end{scope}
\begin{scope}[yshift=-3cm]
  \node [draw,minimum size=3em,text width=6.1cm] (a2) {\mic{false}};
  \node [draw,minimum size=3em,anchor=north,text width=6.1cm] (b2) at
  (a2.south) {};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x02) at
  (b2.west) {\;\;\!};
  \node at (x02.center) {$\bullet$};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x12) at
  (x02.east) {\;\;\!};
  \node at (x12.center) {$\bullet$};
  \foreach \x[count=\i from 1] in {2,3,...,26} {%
    \node[draw,inner sep=1pt,anchor=west,text height=3ex] (x\x2) at
    (x\i2.east) {\;\;\!};
    \croix{x\x2}
  }

  \node [draw,inner sep=1pt,anchor=north west] (eta2) at (a2.north west) {\mic{fin}};
  \node [draw,inner sep=1pt,anchor=north west] (etb2) at (b2.north west)
        {\mic{s}};
\end{scope}
\begin{scope}[yshift=-6cm]
  \node [draw,minimum size=3em,text width=6.1cm] (a3) {\mic{false}};
  \node [draw,minimum size=3em,anchor=north,text width=6.1cm] (b3) at
  (a3.south) {};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x03) at
  (b3.west) {\;\;\!};
  \node at (x03.center) {$\bullet$};
  \foreach \x[count=\i from 0] in {1,2,...,26} {%
    \node[draw,inner sep=1pt,anchor=west,text height=3ex] (x\x3) at
    (x\i3.east) {\;\;\!};
    \croix{x\x3}
  }

  \node [draw,inner sep=1pt,anchor=north west] (eta3) at (a3.north west) {\mic{fin}};
  \node [draw,inner sep=1pt,anchor=north west] (etb3) at (b3.north west)
        {\mic{s}};
\end{scope}
\begin{scope}[xshift=8cm,yshift=-6cm]
  \node [draw,minimum size=3em,text width=6.1cm] (a4) {\mic{true}};
  \node [draw,minimum size=3em,anchor=north,text width=6.1cm] (b4) at
  (a4.south) {};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x04) at
  (b4.west) {\;\;\!};
  \node at (x04.center) {$\bullet$};
  \foreach \x[count=\i from 0] in {1,2,...,26} {%
    \node[draw,inner sep=1pt,anchor=west,text height=3ex] (x\x4) at
    (x\i4.east) {\;\;\!};
    \croix{x\x4}
  }

  \node [draw,inner sep=1pt,anchor=north west] (eta4) at (a4.north west) {\mic{fin}};
  \node [draw,inner sep=1pt,anchor=north west] (etb4) at (b4.north west)
        {\mic{s}};
\end{scope}
\begin{scope}[yshift=-9cm]
  \node [draw,minimum size=3em,text width=6.1cm] (a5) {\mic{true}};
  \node [draw,minimum size=3em,anchor=north,text width=6.1cm] (b5) at
  (a5.south) {};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x05) at
  (b5.west) {\;\;\!};
  \croix{x05}
  \foreach \x[count=\i from 0] in {1,2,...,26} {%
    \node[draw,inner sep=1pt,anchor=west,text height=3ex] (x\x5) at
    (x\i5.east) {\;\;\!};
    \croix{x\x5}
  }

  \node [draw,inner sep=1pt,anchor=north west] (eta5) at (a5.north west) {\mic{fin}};
  \node [draw,inner sep=1pt,anchor=north west] (etb5) at (b5.north west)
        {\mic{s}};
\end{scope}
\begin{scope}[xshift=8cm,yshift=-9cm]
  \node [draw,minimum size=3em,text width=6.1cm] (a6) {\mic{true}};
  \node [draw,minimum size=3em,anchor=north,text width=6.1cm] (b6) at
  (a6.south) {};
  \node [draw,inner sep=1pt,anchor=west,text height=3ex] (x06) at
  (b6.west) {\;\;\!};
  \croix{x06}
  \foreach \x[count=\i from 0] in {1,2,...,26} {%
    \node[draw,inner sep=1pt,anchor=west,text height=3ex] (x\x6) at
    (x\i6.east) {\;\;\!};
    \croix{x\x6}
  }

  \node [draw,inner sep=1pt,anchor=north west] (eta6) at (a6.north west) {\mic{fin}};
  \node [draw,inner sep=1pt,anchor=north west] (etb6) at (b6.north west)
        {\mic{s}};
\end{scope}
\path[draw,->,>=latex] (x0.center) -- (eta2.north) node[right,near end] {$a$};
\path[draw,->,>=latex] (x02.center) -- (eta3.north) node[right,near end] {$a$};
\path[draw,->,>=latex] (x12.center) to[out=275,in=100,looseness=.4]
node[above,very near end] {$b$} (eta4.north);
\path[draw,->,>=latex] (x03.center) -- (eta5.north) node[right,near end] {$a$};
\path[draw,->,>=latex] (x04.center) -- (eta6.north) node[right,near
  end] {$a$};
\node[anchor=west] at (a.east) {\mic{""}};
\node[anchor=west] at (a2.east) {\mic{"a"}};
\node[anchor=west] at (a3.east) {\mic{"aa"}};
\node[anchor=west] at (a4.east) {\mic{"ab"}};
\node[anchor=west] at (a5.east) {\mic{"aaa"}};
\node[anchor=west] at (a6.east) {\mic{"aba"}};
\end{tikzpicture}}
\end{center}


Le fichier d'en-tête \mib{auxiliaire.h} vous fournit une fonction 
\mic{int num(char c)} qui à partir d'un caractère supposé être une
lettre minuscule sans accent fournit l'indice associé à cette lettre
dans l'alphabet.
  
Soit deux mots finis $u$ et $v$ sur un alphabet donné, tels que $v$
est de longueur au moins~2.
On dit que $u$ est un sous-mot \emph{final} de $v$ si c'est un
sous-mot de $v$ et que $u$ et $v$ se terminent par la même lettre.
On dit que $u$ est un sous-mot \emph{admissible} de $v$ si c'est un
sous-mot final de $v$ et que $u$ et $v$ commencent par la même lettre.

Pour un mot $v$ fixé de longueur au moins~2, on cherche à déterminer
les mots d'un lexique qui sont des sous-mots admissibles de $v$. On
note (P) ce problème.

\begin{enumerate}[resume]
\item Justifier brièvement que le nombre de sous-mots distincts d'un
  mot donné est au plus exponentiel en la longueur du mot. Pourquoi
  cela peut-il être moins?
\end{enumerate}

Nous allons utiliser une technique de retour sur trace
(\emph{backtracking}) pour résoudre le problème~(P) :
l'idée est de parcourir le mot $v$ et l'arbre représentant le lexique
en même temps: pour chaque lettre de $v$, à l'exclusion des première
et dernière, on teste la possibilité de conserver ou non cette
lettre. Chaque choix fait aboutit alors à un 
ensemble de mots possibles, et on considère l'union de ces deux
ensembles. Pour simplifier, on autorise les doublons.


\begin{enumerate}[resume]
        
\item  On suppose que la longueur d'un mot du lexique est majorée par
        la constante \mic{LG_MAX} donnée dans \mib{auxiliaire.h} \jury{et on rappelle qu'il est possible d'obtenir l'adresse de la case d'indice \mic{i} d'un tableau \mic{t} avec la syntaxe \mic{&t[i]} (note du jury: rappel non présent dans l'énoncé original que le jury a souhaité rajouter à la publication)}.

        Compléter la  fonction \mic{liste *sous_mots_possibles(lexique *lex, char *mot, bool obligatoire)} qui prend en argument un arbre représentant un lexique, une chaîne de caractères
        et un marqueur spécifiant s'il faut garder la première lettre de la
        chaîne et renvoie une liste contenant tous les mots du lexique qui
        sont des sous-mots finaux de~\mic{mot} si \mic{obligatoire} vaut
        \mic{false} et qui sont des sous-mots admissibles de~\mic{mot} si
        \mic{obligatoire} vaut \mic{true}.\label{q-swype}:
  \begin{enumerate}
    \item cas où le mot est vide (section \mib{A COMPLETER (a)}) : si
      la racine du lexique correspond à une fin de mot, alors
      \mic{res} doit être une liste contenant un unique maillon dont
      le champ \mic{mot} permet de stocker une chaîne de caractère de
      longueur \mic{LG_MAX} et est une chaîne de caractères vide;
    \item cas où on garde la première lettre du mot courant (section
      \mib{A COMPLETER (b)}) : \mic{lst1} doit contenir les sous-mots de
      \mic{mot} qui contiennent sa première lettre et appartiennent au
      lexique, stockés à l'envers (pour les raisons de complexité vues
      en question~\ref{q-envers});
    \item cas où on ne garde pas la première lettre du mot courant (section
      \mib{A COMPLETER (c)}) : \mic{lst2} doit contenir les sous-mots de
      $v_2\cdots v_k$ où \mic{mot}=$v_1\cdots v_k$ (c'est-à-dire
      les sous-mots de \mic{mot} privé de sa première lettre) et
      appartenant au lexique, stockés à l’envers (pour les raisons
      de complexité vues en question~\ref{q-envers}).
  \end{enumerate}
\item Prouver la correction totale de l'algorithme précédent.
\end{enumerate}

\paragraph*{Proposition de corrigé}
\begin{enumerate}
\item $~~$
  \begin{ccode}
void affiche_miroir(char *mot){  // Q1
  for(int i=strlen(mot)-1; i>=0; i=i-1){
    printf("%c", mot[i]);
  }
}
  \end{ccode}
\item $~~$
  \begin{ccode}
void affiche_liste(liste lst){ // Q2
  while(lst != NULL){
    affiche_miroir(lst->mot);
    printf("\n");
    lst = lst->suite;
  }
}
  \end{ccode}
\item $~~$
  \begin{ccode}
void ajout_lettre(char c, liste lst){  // Q3
  for(liste m=lst; m != NULL; m=m->suite){
    m->mot[m->n] = c;
    m->mot[m->n+1] = '\0';
    m->n = m->n + 1;
  }
}
  \end{ccode}
\item
  Chaque itération se fait en temps constant, il y a autant d'itérations que de mots dans la liste, la complexité temporelle est donc linéaire en la longueur de la liste.

  Si l'ajout se fait en début de mot, il faut décaler les autres
  lettres, chaque itération se ferait en temps linéaire en la longueur
  du suffixe, qui est majorée par la longueur du plus long mot. Si
  tous les mots ont même longueur, ce temps est atteint à chaque
  itération. Le nombre d'itérations n'est pas modifié. La complexité
  est donc linéaire en le produit de la longueur de la liste et de la
  longueur du plus long mot de cette liste. On peut aussi sans la
  dernière hypothèse simplificatrice majorer par la somme des
  longueurs des mots.
\item
Soit un mot $v$ de longueur $n$ indicé à partir de~0. Choisir un
sous-mot de $v$, c'est choisir une fonction $\llbracket
0,n-1\rrbracket \to \{V, F\}$. Il y a donc $2^n$ choix possibles. Ces
choix n'aboutissent pas toujours à des mots distincts si les lettres
de $v$ ne sont pas deux à deux distinctes. Par exemple si $v=a^n$, $v$
possède $n+1$ sous-mots distincts. 
\item $~~$
\begin{fancy-code-l}{c}
liste sous_mots_possibles(lexique *lex, char *mot, bool obligatoire){  // Q6
  if(lex == NULL){
    return NULL;
  }
  if(*mot == '\0'){
    if(!lex->fin){ //on n'est pas sur un mot du lexique
      return NULL;
    } else {
      liste res = NULL;
      // A COMPLETER (a) - debut
      res = malloc(sizeof(struct maillon));
      res->mot = malloc((LG_MAX+1)*sizeof(char));
      res->mot[0] = '\0';
      res->n = 0;
      res->suite = NULL;
      // A COMPLETER (a) - fin
      return res;
    }
  }
  liste lst1 = NULL;
  // A COMPLETER (b) - debut
  int nc = num(mot[0]);
  lst1 = sous_mots_possibles(lex->s[nc], &mot[1], false);
  ajout_lettre(mot[0], lst1);
  // A COMPLETER (b) - fin
  liste lst2 = NULL;
  obligatoire = obligatoire || mot[1] == '\0'; //dernière lettre obligatoire
  if(!obligatoire){ //lettre pas obligatoire : on la saute
    // A COMPLETER (c) - debut
    lst2 = sous_mots_possibles(lex, &mot[1], false);
    // A COMPLETER (c) - fin
  }
  return union_listes(lst1, lst2);
}
\end{fancy-code-l}
\item Par récurrence sur la longueur du sous-mot. 

On suppose \mic{lex} non vide, sinon la terminaison et la correction
sont immédiates.
  
\underline{cas de base} si \mic{mot} est le mot vide:
\begin{itemize}
\item si la racine de \mic{lex} n'est pas finale, alors l'appel se
  termine avec la bonne valeur en ligne~7;
\item sinon un maillon est créé contenant le mot vide (lignes~11 à~15)
  et l'appel se termine avec la bonne valeur en ligne~17.
\end{itemize}

\underline{hérédité} Supposons que tout appel à
\mic{sous_motes_possibles} se termine et soit correct, pour toute chaîne
de caractères \mic{mot} de longueur $n$ pour un certain $n\geq
0$. Soit une chaîne de caractères \mic{mot} de longueur $n+1$ (qu'on
suppose inférieure à \mic{LG_MAX}). L'ensemble des sous-mots de
\mic{mot} s'écrit comme une partition entre:
\begin{itemize}
\item l'ensemble de ses sous-mots qui contiennent la première lettre
  de~\mic{mot}: obtenu en temps fini avec les lignes~23 et~24 par
  hypothèse de récurrence;
\item l'ensemble de ses sous-mots qui ne contiennent pas la première
  lettre de~\mic{mot} si elle n'est pas obligatoire: obtenu en temps
  fini avec les lignes~26 et~30 par hypothèse de récurrence.
\end{itemize}
Le retour à la ligne~33 donne donc bien le résultat attendu en temps
fini.
\end{enumerate}
\end{document}
