\documentclass[a4paper,11pt]{article}

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

\title{Diviser pour régner}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Diviser pour régner} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{terminalediviserpourregner}{
  \begin{question}{q01}
    Quelles sont les \textbf{trois étapes} du paradigme diviser pour
régner ?
    \begin{choices}
    \wrongchoice{Initialiser, itérer, terminer}
    \correctchoice{Diviser, régner, combiner}
    \wrongchoice{Trier, fusionner, comparer}
    \wrongchoice{Identifier, calculer, vérifier}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q02}
    Quelle est la complexité au pire de la recherche dichotomique
sur un tableau trié de $n$ éléments ?
    \begin{choices}
    \correctchoice{$O(\log n)$}
    \wrongchoice{$O(n \log n)$}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(1)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q03}
    Quel est le principe du \textbf{tri fusion} ?
    \begin{choices}
    \wrongchoice{Chercher le plus petit élément, le placer en début, recommencer}
    \correctchoice{Couper le tableau en deux moitiés, trier chaque moitié récursivement, puis fusionner les deux moitiés triées}
    \wrongchoice{Insérer chaque élément à sa place dans la portion déjà triée}
    \wrongchoice{Comparer chaque paire d'éléments adjacents et les permuter si nécessaire}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q04}
    Quelle est la complexité du tri fusion sur un tableau de $n$
éléments ?
    \begin{choices}
    \correctchoice{$O(n \log n)$}
    \wrongchoice{$O(n^2)$}
    \wrongchoice{$O(2^n)$}
    \wrongchoice{$O(n)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q05}
    Quel est le \textbf{cas de base} du tri fusion ?
    \begin{choices}
    \wrongchoice{Un tableau de deux éléments}
    \wrongchoice{Un tableau trié}
    \wrongchoice{Un tableau de longueur paire}
    \correctchoice{Un tableau de zéro ou un élément}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q06}
    L'\textbf{exponentiation rapide} calcule $a^n$ en exploitant
quelle propriété mathématique ?
    \begin{choices}
    \wrongchoice{$a^n = a^{n-1} \cdot a$}
    \wrongchoice{$a^n = a + a + \cdots + a$ ($n$ fois)}
    \correctchoice{$a^n = (a^{n/2})^2$ si $n$ est pair, et $a^n = a \cdot (a^{(n-1)/2})^2$ si $n$ est impair}
    \wrongchoice{$a^n = n \cdot a$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q07}
    Le tri fusion est-il un tri \textbf{en place} ?
    \begin{choices}
    \wrongchoice{Oui, il modifie le tableau d'origine sans mémoire supplémentaire}
    \correctchoice{Non, il utilise une mémoire supplémentaire proportionnelle à $n$}
    \wrongchoice{Oui, mais seulement pour des listes de taille paire}
    \wrongchoice{Non, mais il utilise une mémoire constante}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q08}
    Quelle est la condition \textbf{indispensable} pour appliquer la
recherche dichotomique ?
    \begin{choices}
    \correctchoice{Le tableau doit être trié}
    \wrongchoice{Le tableau doit être de taille puissance de $2$}
    \wrongchoice{Le tableau doit avoir une taille connue à l'avance}
    \wrongchoice{Le tableau doit contenir uniquement des entiers}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q09}
    Pourquoi le paradigme diviser pour régner s'implémente-t-il
naturellement par \textbf{récursivité} ?
    \begin{choices}
    \wrongchoice{Parce que la récursivité est le seul moyen de coder une boucle en Python}
    \wrongchoice{Parce que le paradigme nécessite la mémoïsation}
    \wrongchoice{Parce que la récursivité est plus rapide que l'itération}
    \correctchoice{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{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q10}
    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 ?
    \begin{choices}
    \wrongchoice{$O(n^2)$}
    \wrongchoice{$O(n \log n)$}
    \correctchoice{$O(n)$}
    \wrongchoice{$O(1)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q11}
    Combien de comparaisons effectue \textbf{au pire} une recherche
dichotomique sur un tableau de $1\ 000$ éléments ?
    \begin{choices}
    \wrongchoice{$1$}
    \wrongchoice{$500$}
    \wrongchoice{$1\ 000$}
    \correctchoice{Environ $10$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q12}
    Si l'on applique le tri fusion à la liste $[5, 2, 8, 3, 9, 1]$,
quelle est la première étape ?
    \begin{choices}
    \correctchoice{Diviser la liste en $[5, 2, 8]$ et $[3, 9, 1]$}
    \wrongchoice{Trouver le plus petit élément ($1$) et le placer en début}
    \wrongchoice{Trier la liste avec une fonction \texttt{sorted} intégrée}
    \wrongchoice{Comparer $5$ et $2$, les permuter}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q13}
    Quelle est la complexité de l'exponentiation rapide pour
calculer $a^n$ ?
    \begin{choices}
    \wrongchoice{$O(1)$}
    \wrongchoice{$O(n)$}
    \correctchoice{$O(\log n)$}
    \wrongchoice{$O(n^2)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q14}
    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)$ ?
    \begin{choices}
    \wrongchoice{$T(n) = T(n/2) + 1$}
    \wrongchoice{$T(n) = T(n-1) + 1$}
    \correctchoice{$T(n) = 2 \cdot T(n/2) + n$}
    \wrongchoice{$T(n) = T(n-1) + T(n-2)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q15}
    Le tri fusion est-il un tri \textbf{stable} ?
    \begin{choices}
    \correctchoice{Oui, à condition d'utiliser \texttt{<=} plutôt que \texttt{<} dans la fonction de fusion}
    \wrongchoice{La notion de stabilité ne s'applique qu'aux tris itératifs}
    \wrongchoice{Cela dépend de la taille de la liste}
    \wrongchoice{Non, le tri fusion ne préserve pas l'ordre des éléments égaux}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q16}
    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)$) ?
    \begin{choices}
    \correctchoice{Environ $50\ 000$ fois}
    \wrongchoice{$1\ 000\ 000$ fois}
    \wrongchoice{$2$ fois}
    \wrongchoice{$10$ fois}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q17}
    Dans une implémentation \textbf{récursive} d'exponentiation
rapide, est-il utile d'ajouter de la \textbf{mémoïsation} ?
    \begin{choices}
    \wrongchoice{Oui, cela accélère le calcul}
    \correctchoice{Non, l'exponentiation rapide ne fait pas d'appels redondants}
    \wrongchoice{Oui, mais seulement pour des exposants pairs}
    \wrongchoice{Cela rendrait l'algorithme plus lent}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q18}
    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 ?
    \begin{choices}
    \wrongchoice{Il manque l'initialisation de \texttt{milieu} avant la boucle}
    \correctchoice{La condition de boucle devrait être \texttt{gauche <= droite} (avec \texttt{<=} au lieu de \texttt{<})}
    \wrongchoice{Le calcul de \texttt{milieu} est incorrect}
    \wrongchoice{La fonction devrait être récursive pour fonctionner}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q19}
    Quelle est la principale différence entre le \textbf{tri rapide}
(\textit{quicksort}) et le tri fusion ?
    \begin{choices}
    \wrongchoice{Le tri rapide est toujours plus rapide que le tri fusion}
    \correctchoice{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}
    \wrongchoice{Le tri rapide est plus simple à comprendre}
    \wrongchoice{Le tri rapide ne fonctionne que sur les entiers}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q20}
    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) ?
    \begin{choices}
    \wrongchoice{La complexité reste $O(n)$}
    \wrongchoice{La complexité reste en $O(n \log n)$}
    \correctchoice{La complexité dégénère à $O(n^2)$}
    \wrongchoice{L'algorithme ne termine pas}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q21}
    Soit la récurrence $T(n) = 4 \cdot T(n/2) + n$. Quelle est la
complexité asymptotique de $T(n)$ ?
    \begin{choices}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(n^4)$}
    \wrongchoice{$O(n \log n)$}
    \correctchoice{$O(n^2)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q22}
    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 ?
    \begin{choices}
    \wrongchoice{$500$}
    \correctchoice{Environ $10$}
    \wrongchoice{$1$}
    \wrongchoice{$1\ 000$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q23}
    Pour calculer $a^n \mod m$ avec de très grands entiers
(cryptographie), la méthode efficace est :
    \begin{choices}
    \correctchoice{Appliquer l'exponentiation rapide en réduisant modulo $m$ à chaque multiplication}
    \wrongchoice{Calculer $a^n$ entièrement, puis prendre le modulo}
    \wrongchoice{Utiliser une recherche dichotomique sur les diviseurs de $m$}
    \wrongchoice{Utiliser le tri fusion sur les chiffres décimaux}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q24}
    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é ?
    \begin{choices}
    \wrongchoice{$O(n^3)$}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(3^n)$}
    \correctchoice{$O(n \log_3 n)$}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q25}
    Parmi les algorithmes suivants, lequel \textbf{n'est pas} un
algorithme diviser pour régner ?
    \begin{choices}
    \correctchoice{Le tri par insertion}
    \wrongchoice{L'exponentiation rapide}
    \wrongchoice{La recherche dichotomique}
    \wrongchoice{Le tri fusion}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q26}
    Quel code Python implémente correctement
l'exponentiation rapide récursive de $a$ à la
puissance $n$ (avec $n \geq 0$) ?
    \begin{choices}
    \wrongchoice{\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}
}
    \wrongchoice{\begin{lstlisting}
def puissance(a, n):
    if n == 0:
        return 1
    return a * puissance(a, n - 1)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def puissance(a, n):
    return a ** n
\end{lstlisting}
}
    \correctchoice{\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{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q27}
    Dans le tri rapide, l'opération de
\textbf{partitionnement} autour d'un pivot consiste à :
    \begin{choices}
    \correctchoice{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é
}
    \wrongchoice{Diviser le tableau en deux parties de taille égale
}
    \wrongchoice{Compter le nombre d'inversions dans le tableau
}
    \wrongchoice{Trier la liste avant de choisir un pivot
}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q28}
    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 ?
    \begin{choices}
    \correctchoice{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)$)
}
    \wrongchoice{Parce que la recherche dichotomique n'est pas un
algorithme diviser pour régner
}
    \wrongchoice{Parce que la recherche dichotomique fonctionne
uniquement sur des tableaux de taille puissance de
deux
}
    \wrongchoice{Parce que les comparaisons sont gratuites en Python
}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q29}
    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) ?
    \begin{choices}
    \wrongchoice{\texttt{[2, 3, 5, 8]} et \texttt{[]}
}
    \wrongchoice{\texttt{[5]}, \texttt{[2]}, \texttt{[8]}, \texttt{[3]}
}
    \wrongchoice{\texttt{[5, 2]} et \texttt{[8, 3]}
}
    \correctchoice{\texttt{[2, 5]} et \texttt{[3, 8]}
}
    \end{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q30}
    Quelle fonction Python implémente
correctement la \textbf{fusion} de deux listes
déjà triées en une seule liste triée ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def fusion(a, b):
    return a + b
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def fusion(a, b):
    return sorted(a + b)
\end{lstlisting}
}
    \wrongchoice{\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}
}
    \correctchoice{\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{choices}
  \end{question}
}

\element{terminalediviserpourregner}{
  \begin{question}{q31}
    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) ?
    \begin{choices}
    \wrongchoice{\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}
}
    \correctchoice{\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}
}
    \wrongchoice{\begin{lstlisting}
def partitionner(tab, debut, fin):
    return tab[fin]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def partitionner(tab, debut, fin):
    tab.sort()
    return len(tab) // 2
\end{lstlisting}
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalediviserpourregner}
  \insertgroup{terminalediviserpourregner}
}

\end{document}
