\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{Diviser pour régner}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

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

% Q1 - Réponse en B
\begin{frame}[fragile]{Question 1 \textemdash{} Étapes du paradigme diviser pour régner}
    Quelles sont les \textbf{trois étapes} du paradigme diviser pour
régner ?\medskip
    \begin{itemize}
        \item[A.] Initialiser, itérer, terminer
        \item[\alert<2>{B.}] \alert<2>{Diviser, régner, combiner}
        \item[C.] Trier, fusionner, comparer
        \item[D.] Identifier, calculer, vérifier
    \end{itemize}
\end{frame}

% Q2 - Réponse en A
\begin{frame}[fragile]{Question 2 \textemdash{} Complexité de la recherche dichotomique}
    Quelle est la complexité au pire de la recherche dichotomique
sur un tableau trié de $n$ éléments ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$O(\log n)$}
        \item[B.] $O(n \log n)$
        \item[C.] $O(n)$
        \item[D.] $O(1)$
    \end{itemize}
\end{frame}

% Q3 - Réponse en B
\begin{frame}[fragile]{Question 3 \textemdash{} Principe du tri fusion}
    Quel est le principe du \textbf{tri fusion} ?\medskip
    \begin{itemize}
        \item[A.] Chercher le plus petit élément, le placer en début, recommencer
        \item[\alert<2>{B.}] \alert<2>{Couper le tableau en deux moitiés, trier chaque moitié récursivement, puis fusionner les deux moitiés triées}
        \item[C.] Insérer chaque élément à sa place dans la portion déjà triée
        \item[D.] Comparer chaque paire d'éléments adjacents et les permuter si nécessaire
    \end{itemize}
\end{frame}

% Q4 - Réponse en A
\begin{frame}[fragile]{Question 4 \textemdash{} Complexité du tri fusion}
    Quelle est la complexité du tri fusion sur un tableau de $n$
éléments ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$O(n \log n)$}
        \item[B.] $O(n^2)$
        \item[C.] $O(2^n)$
        \item[D.] $O(n)$
    \end{itemize}
\end{frame}

% Q5 - Réponse en D
\begin{frame}[fragile]{Question 5 \textemdash{} Cas de base du tri fusion}
    Quel est le \textbf{cas de base} du tri fusion ?\medskip
    \begin{itemize}
        \item[A.] Un tableau de deux éléments
        \item[B.] Un tableau trié
        \item[C.] Un tableau de longueur paire
        \item[\alert<2>{D.}] \alert<2>{Un tableau de zéro ou un élément}
    \end{itemize}
\end{frame}

% Q6 - Réponse en C
\begin{frame}[fragile]{Question 6 \textemdash{} Principe de l'exponentiation rapide}
    L'\textbf{exponentiation rapide} calcule $a^n$ en exploitant
quelle propriété mathématique ?\medskip
    \begin{itemize}
        \item[A.] $a^n = a^{n-1} \cdot a$
        \item[B.] $a^n = a + a + \cdots + a$ ($n$ fois)
        \item[\alert<2>{C.}] \alert<2>{$a^n = (a^{n/2})^2$ si $n$ est pair, et $a^n = a \cdot (a^{(n-1)/2})^2$ si $n$ est impair}
        \item[D.] $a^n = n \cdot a$
    \end{itemize}
\end{frame}

% Q7 - Réponse en B
\begin{frame}[fragile]{Question 7 \textemdash{} Tri fusion en place ?}
    Le tri fusion est-il un tri \textbf{en place} ?\medskip
    \begin{itemize}
        \item[A.] Oui, il modifie le tableau d'origine sans mémoire supplémentaire
        \item[\alert<2>{B.}] \alert<2>{Non, il utilise une mémoire supplémentaire proportionnelle à $n$}
        \item[C.] Oui, mais seulement pour des listes de taille paire
        \item[D.] Non, mais il utilise une mémoire constante
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile]{Question 8 \textemdash{} Pré-requis de la recherche dichotomique}
    Quelle est la condition \textbf{indispensable} pour appliquer la
recherche dichotomique ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le tableau doit être trié}
        \item[B.] Le tableau doit être de taille puissance de $2$
        \item[C.] Le tableau doit avoir une taille connue à l'avance
        \item[D.] Le tableau doit contenir uniquement des entiers
    \end{itemize}
\end{frame}

% Q9 - Réponse en D
\begin{frame}[fragile]{Question 9 \textemdash{} Récursivité et diviser pour régner}
    Pourquoi le paradigme diviser pour régner s'implémente-t-il
naturellement par \textbf{récursivité} ?\medskip
    \begin{itemize}
        \item[A.] Parce que la récursivité est le seul moyen de coder une boucle en Python
        \item[B.] Parce que le paradigme nécessite la mémoïsation
        \item[C.] Parce que la récursivité est plus rapide que l'itération
        \item[\alert<2>{D.}] \alert<2>{Parce qu'on doit résoudre des sous-problèmes de même nature que le problème initial, ce qui s'exprime naturellement par un appel récursif}
    \end{itemize}
\end{frame}

% Q10 - Réponse en C
\begin{frame}[fragile]{Question 10 \textemdash{} Fusion de deux listes triées}
    Pour fusionner deux listes \textbf{déjà triées} de longueur $n$
chacune en une seule liste triée, quelle est la complexité
de l'opération ?\medskip
    \begin{itemize}
        \item[A.] $O(n^2)$
        \item[B.] $O(n \log n)$
        \item[\alert<2>{C.}] \alert<2>{$O(n)$}
        \item[D.] $O(1)$
    \end{itemize}
\end{frame}

% Q11 - Réponse en D
\begin{frame}[fragile]{Question 11 \textemdash{} Nombre de comparaisons en dichotomie}
    Combien de comparaisons effectue \textbf{au pire} une recherche
dichotomique sur un tableau de $1\ 000$ éléments ?\medskip
    \begin{itemize}
        \item[A.] $1$
        \item[B.] $500$
        \item[C.] $1\ 000$
        \item[\alert<2>{D.}] \alert<2>{Environ $10$}
    \end{itemize}
\end{frame}

% Q12 - Réponse en A
\begin{frame}[fragile]{Question 12 \textemdash{} Tri fusion sur un exemple}
    Si l'on applique le tri fusion à la liste $[5, 2, 8, 3, 9, 1]$,
quelle est la première étape ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Diviser la liste en $[5, 2, 8]$ et $[3, 9, 1]$}
        \item[B.] Trouver le plus petit élément ($1$) et le placer en début
        \item[C.] Trier la liste avec une fonction \texttt{sorted} intégrée
        \item[D.] Comparer $5$ et $2$, les permuter
    \end{itemize}
\end{frame}

% Q13 - Réponse en C
\begin{frame}[fragile]{Question 13 \textemdash{} Complexité de l'exponentiation rapide}
    Quelle est la complexité de l'exponentiation rapide pour
calculer $a^n$ ?\medskip
    \begin{itemize}
        \item[A.] $O(1)$
        \item[B.] $O(n)$
        \item[\alert<2>{C.}] \alert<2>{$O(\log n)$}
        \item[D.] $O(n^2)$
    \end{itemize}
\end{frame}

% Q14 - Réponse en C
\begin{frame}[fragile]{Question 14 \textemdash{} Récurrence du tri fusion}
    Soit $T(n)$ le nombre d'opérations du tri fusion sur un
tableau de $n$ éléments. Quelle relation de récurrence
vérifie $T(n)$ ?\medskip
    \begin{itemize}
        \item[A.] $T(n) = T(n/2) + 1$
        \item[B.] $T(n) = T(n-1) + 1$
        \item[\alert<2>{C.}] \alert<2>{$T(n) = 2 \cdot T(n/2) + n$}
        \item[D.] $T(n) = T(n-1) + T(n-2)$
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Stabilité du tri fusion}
    Le tri fusion est-il un tri \textbf{stable} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Oui, à condition d'utiliser \texttt{<=} plutôt que \texttt{<} dans la fonction de fusion}
        \item[B.] La notion de stabilité ne s'applique qu'aux tris itératifs
        \item[C.] Cela dépend de la taille de la liste
        \item[D.] Non, le tri fusion ne préserve pas l'ordre des éléments égaux
    \end{itemize}
\end{frame}

% Q16 - Réponse en A
\begin{frame}[fragile]{Question 16 \textemdash{} Tri fusion vs tri par insertion}
    Pour trier un tableau de $1\ 000\ 000$ éléments, le tri
fusion ($O(n \log n)$) est environ combien de fois plus
rapide que le tri par insertion ($O(n^2)$) ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Environ $50\ 000$ fois}
        \item[B.] $1\ 000\ 000$ fois
        \item[C.] $2$ fois
        \item[D.] $10$ fois
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile]{Question 17 \textemdash{} Optimisation par mémoïsation}
    Dans une implémentation \textbf{récursive} d'exponentiation
rapide, est-il utile d'ajouter de la \textbf{mémoïsation} ?\medskip
    \begin{itemize}
        \item[A.] Oui, cela accélère le calcul
        \item[\alert<2>{B.}] \alert<2>{Non, l'exponentiation rapide ne fait pas d'appels redondants}
        \item[C.] Oui, mais seulement pour des exposants pairs
        \item[D.] Cela rendrait l'algorithme plus lent
    \end{itemize}
\end{frame}

% Q18 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 18 \textemdash{} Détection d'une erreur dans la dichotomie}
    Dans la fonction suivante :

\begin{lstlisting}
def recherche(x, tab):
    gauche, droite = 0, len(tab) - 1
    while gauche < droite:        # ← ICI
        milieu = (gauche + droite) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1
\end{lstlisting}

Quel est le bug ?\medskip
    \begin{itemize}
        \item[A.] Il manque l'initialisation de \texttt{milieu} avant la boucle
        \item[B.] La condition de boucle devrait être \texttt{gauche <= droite} (avec \texttt{<=} au lieu de \texttt{<})
        \item[C.] Le calcul de \texttt{milieu} est incorrect
        \item[D.] La fonction devrait être récursive pour fonctionner
    \end{itemize}
\end{frame}

% Q18 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 18 \textemdash{} Détection d'une erreur dans la dichotomie}
    Dans la fonction suivante :

\begin{lstlisting}
def recherche(x, tab):
    gauche, droite = 0, len(tab) - 1
    while gauche < droite:        # ← ICI
        milieu = (gauche + droite) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1
\end{lstlisting}

Quel est le bug ?\medskip
    \begin{itemize}
        \item[A.] Il manque l'initialisation de \texttt{milieu} avant la boucle
        \item[\alert{B.}] \alert{La condition de boucle devrait être \texttt{gauche <= droite} (avec \texttt{<=} au lieu de \texttt{<})}
        \item[C.] Le calcul de \texttt{milieu} est incorrect
        \item[D.] La fonction devrait être récursive pour fonctionner
    \end{itemize}
\end{frame}

% Q19 - Réponse en B
\begin{frame}[fragile]{Question 19 \textemdash{} Tri rapide vs tri fusion}
    Quelle est la principale différence entre le \textbf{tri rapide}
(\textit{quicksort}) et le tri fusion ?\medskip
    \begin{itemize}
        \item[A.] Le tri rapide est toujours plus rapide que le tri fusion
        \item[\alert<2>{B.}] \alert<2>{Le tri rapide est en place mais sa complexité au pire est $O(n^2)$, alors que le tri fusion est $O(n \log n)$ garanti mais pas en place}
        \item[C.] Le tri rapide est plus simple à comprendre
        \item[D.] Le tri rapide ne fonctionne que sur les entiers
    \end{itemize}
\end{frame}

% Q20 - Réponse en C
\begin{frame}[fragile]{Question 20 \textemdash{} Découpage déséquilibré}
    Que se passe-t-il si le découpage en sous-problèmes est très
\textbf{déséquilibré} (par exemple, une moitié contenant $1$
élément et l'autre $n-1$ éléments) ?\medskip
    \begin{itemize}
        \item[A.] La complexité reste $O(n)$
        \item[B.] La complexité reste en $O(n \log n)$
        \item[\alert<2>{C.}] \alert<2>{La complexité dégénère à $O(n^2)$}
        \item[D.] L'algorithme ne termine pas
    \end{itemize}
\end{frame}

% Q21 - Réponse en D
\begin{frame}[fragile]{Question 21 \textemdash{} Application du théorème maître}
    Soit la récurrence $T(n) = 4 \cdot T(n/2) + n$. Quelle est la
complexité asymptotique de $T(n)$ ?\medskip
    \begin{itemize}
        \item[A.] $O(n)$
        \item[B.] $O(n^4)$
        \item[C.] $O(n \log n)$
        \item[\alert<2>{D.}] \alert<2>{$O(n^2)$}
    \end{itemize}
\end{frame}

% Q22 - Réponse en B
\begin{frame}[fragile]{Question 22 \textemdash{} Profondeur de la pile en tri fusion}
    Pour trier un tableau de $1\ 000$ éléments par tri fusion
récursif, quelle est la \textbf{profondeur maximale} de la pile
d'appels ?\medskip
    \begin{itemize}
        \item[A.] $500$
        \item[\alert<2>{B.}] \alert<2>{Environ $10$}
        \item[C.] $1$
        \item[D.] $1\ 000$
    \end{itemize}
\end{frame}

% Q23 - Réponse en A
\begin{frame}[fragile]{Question 23 \textemdash{} Exponentiation modulaire}
    Pour calculer $a^n \mod m$ avec de très grands entiers
(cryptographie), la méthode efficace est :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Appliquer l'exponentiation rapide en réduisant modulo $m$ à chaque multiplication}
        \item[B.] Calculer $a^n$ entièrement, puis prendre le modulo
        \item[C.] Utiliser une recherche dichotomique sur les diviseurs de $m$
        \item[D.] Utiliser le tri fusion sur les chiffres décimaux
    \end{itemize}
\end{frame}

% Q24 - Réponse en D
\begin{frame}[fragile]{Question 24 \textemdash{} Analyse d'un nouvel algorithme DPR}
    On invente un algorithme qui, pour un tableau de $n$
éléments, le découpe en \textbf{trois tiers}, traite chaque tiers
récursivement, puis fait un travail $O(n)$ pour combiner.
Quelle est sa complexité ?\medskip
    \begin{itemize}
        \item[A.] $O(n^3)$
        \item[B.] $O(n)$
        \item[C.] $O(3^n)$
        \item[\alert<2>{D.}] \alert<2>{$O(n \log_3 n)$}
    \end{itemize}
\end{frame}

% Q25 - Réponse en A
\begin{frame}[fragile]{Question 25 \textemdash{} Reconnaître un algorithme DPR}
    Parmi les algorithmes suivants, lequel \textbf{n'est pas} un
algorithme diviser pour régner ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le tri par insertion}
        \item[B.] L'exponentiation rapide
        \item[C.] La recherche dichotomique
        \item[D.] Le tri fusion
    \end{itemize}
\end{frame}

% Q26 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Code de l'exponentiation rapide}
    Quel code Python implémente correctement
l'exponentiation rapide récursive de $a$ à la
puissance $n$ (avec $n \geq 0$) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return puissance(a, n // 2) * puissance(a, n // 2)
    return a * puissance(a, n // 2) * puissance(a, n // 2)
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    return a * puissance(a, n - 1)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def puissance(a, n):
    return a ** n
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    demi = puissance(a, n // 2)
    if n % 2 == 0:
        return demi * demi
    return a * demi * demi
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q26 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Code de l'exponentiation rapide}
    Quel code Python implémente correctement
l'exponentiation rapide récursive de $a$ à la
puissance $n$ (avec $n \geq 0$) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return puissance(a, n // 2) * puissance(a, n // 2)
    return a * puissance(a, n // 2) * puissance(a, n // 2)
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    return a * puissance(a, n - 1)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def puissance(a, n):
    return a ** n
\end{lstlisting}

        \item[\alert{D.}]~\\
\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    demi = puissance(a, n // 2)
    if n % 2 == 0:
        return demi * demi
    return a * demi * demi
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q27 - Réponse en A
\begin{frame}[fragile]{Question 27 \textemdash{} Partition du tri rapide}
    Dans le tri rapide, l'opération de
\textbf{partitionnement} autour d'un pivot consiste à :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Réorganiser le tableau de sorte que tous les
éléments inférieurs au pivot soient à sa
gauche, et tous les éléments supérieurs à sa
droite ; le pivot lui-même est alors à sa position
finale dans le tableau trié
}
        \item[B.] Diviser le tableau en deux parties de taille égale

        \item[C.] Compter le nombre d'inversions dans le tableau

        \item[D.] Trier la liste avant de choisir un pivot

    \end{itemize}
\end{frame}

% Q28 - Réponse en A
\begin{frame}[fragile]{Question 28 \textemdash{} DPR sans combinaison coûteuse}
    La recherche dichotomique satisfait la récurrence
$T(n) = T(n/2) + O(1)$. Pourquoi obtient-on
$O(\log n)$ et non $O(n \log n)$ comme dans le tri
fusion ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Parce qu'il n'y a qu'un seul sous-problème à
chaque appel (au lieu de deux), et que la
combinaison se fait en temps constant $O(1)$
(au lieu de $O(n)$)
}
        \item[B.] Parce que la recherche dichotomique n'est pas un
algorithme diviser pour régner

        \item[C.] Parce que la recherche dichotomique fonctionne
uniquement sur des tableaux de taille puissance de
deux

        \item[D.] Parce que les comparaisons sont gratuites en Python

    \end{itemize}
\end{frame}

% Q29 - Réponse en D
\begin{frame}[fragile]{Question 29 \textemdash{} Trace du tri fusion}
    On applique le tri fusion à la liste
\texttt{[5, 2, 8, 3]}. Quelles sont les listes
passées à la fusion finale (la dernière
étape, qui produit la liste triée
complète) ?\medskip
    \begin{itemize}
        \item[A.] \texttt{[2, 3, 5, 8]} et \texttt{[]}

        \item[B.] \texttt{[5]}, \texttt{[2]}, \texttt{[8]}, \texttt{[3]}

        \item[C.] \texttt{[5, 2]} et \texttt{[8, 3]}

        \item[\alert<2>{D.}] \alert<2>{\texttt{[2, 5]} et \texttt{[3, 8]}
}
    \end{itemize}
\end{frame}

% Q30 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 30 \textemdash{} Code de la fonction de fusion}
    Quelle fonction Python implémente
correctement la \textbf{fusion} de deux listes
déjà triées en une seule liste triée ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def fusion(a, b):
    return a + b
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def fusion(a, b):
    return sorted(a + b)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def fusion(a, b):
    resultat = []
    for x in a:
        for y in b:
            if x <= y:
                resultat.append(x)
            else:
                resultat.append(y)
    return resultat
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def fusion(a, b):
    i, j = 0, 0
    resultat = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultat.append(a[i])
            i += 1
        else:
            resultat.append(b[j])
            j += 1
    resultat.extend(a[i:])
    resultat.extend(b[j:])
    return resultat
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q30 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 30 \textemdash{} Code de la fonction de fusion}
    Quelle fonction Python implémente
correctement la \textbf{fusion} de deux listes
déjà triées en une seule liste triée ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def fusion(a, b):
    return a + b
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def fusion(a, b):
    return sorted(a + b)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def fusion(a, b):
    resultat = []
    for x in a:
        for y in b:
            if x <= y:
                resultat.append(x)
            else:
                resultat.append(y)
    return resultat
\end{lstlisting}

        \item[\alert{D.}]~\\
\begin{lstlisting}
def fusion(a, b):
    i, j = 0, 0
    resultat = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultat.append(a[i])
            i += 1
        else:
            resultat.append(b[j])
            j += 1
    resultat.extend(a[i:])
    resultat.extend(b[j:])
    return resultat
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q31 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 31 \textemdash{} Code du partitionnement}
    Dans le tri rapide, l'étape de
\textbf{partitionnement} réorganise un tableau
autour d'un pivot. Quel code Python
implémente correctement cette étape (avec
le pivot pris comme dernier élément du
sous-tableau, schéma de Lomuto) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    gauche = [x for x in tab if x <= tab[fin]]
    droite = [x for x in tab if x > tab[fin]]
    return gauche + droite
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    pivot = tab[fin]
    i = debut - 1
    for j in range(debut, fin):
        if tab[j] <= pivot:
            i += 1
            tab[i], tab[j] = tab[j], tab[i]
    tab[i + 1], tab[fin] = tab[fin], tab[i + 1]
    return i + 1
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    return tab[fin]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    tab.sort()
    return len(tab) // 2
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q31 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 31 \textemdash{} Code du partitionnement}
    Dans le tri rapide, l'étape de
\textbf{partitionnement} réorganise un tableau
autour d'un pivot. Quel code Python
implémente correctement cette étape (avec
le pivot pris comme dernier élément du
sous-tableau, schéma de Lomuto) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    gauche = [x for x in tab if x <= tab[fin]]
    droite = [x for x in tab if x > tab[fin]]
    return gauche + droite
\end{lstlisting}

        \item[\alert{B.}]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    pivot = tab[fin]
    i = debut - 1
    for j in range(debut, fin):
        if tab[j] <= pivot:
            i += 1
            tab[i], tab[j] = tab[j], tab[i]
    tab[i + 1], tab[fin] = tab[fin], tab[i + 1]
    return i + 1
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    return tab[fin]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def partitionner(tab, debut, fin):
    tab.sort()
    return len(tab) // 2
\end{lstlisting}

    \end{itemize}
\end{frame}

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

\end{document}
