\documentclass[a4paper,11pt]{article}

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

\title{Programmation dynamique}
\date{Numérique et sciences informatiques}

\begin{document}

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

\bigskip

\element{terminaleprogrammationdynamique}{
  \begin{question}{q01}
    Quel est le principe fondamental de la
programmation dynamique ?
    \begin{choices}
    \wrongchoice{Diviser le problème en deux moitiés et résoudre chacune indépendamment}
    \wrongchoice{Faire à chaque étape le choix qui semble localement le meilleur}
    \wrongchoice{Modifier le programme à mesure qu'il s'exécute}
    \correctchoice{Mémoriser les solutions des sous-problèmes pour ne pas avoir à les recalculer}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q02}
    Qu'est-ce que la \textbf{mémoïsation} ?
    \begin{choices}
    \wrongchoice{La comparaison de deux algorithmes pour choisir le plus rapide}
    \wrongchoice{La conversion automatique d'une fonction récursive en boucle itérative}
    \wrongchoice{La compression d'un programme en mémoire pour gagner de la place}
    \correctchoice{Le stockage des résultats déjà calculés dans un cache pour les réutiliser}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q03}
    Qu'appelle-t-on \textbf{tabulation} en programmation
dynamique ?
    \begin{choices}
    \wrongchoice{Le découpage d'un problème en sous-problèmes égaux}
    \wrongchoice{La création d'une table HTML pour afficher les résultats}
    \wrongchoice{Une optimisation des comparaisons utilisée dans un algorithme de tri}
    \correctchoice{La construction d'un tableau de résultats, en partant des plus petits sous-problèmes pour aller vers les plus grands}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q04}
    Quelle est la complexité de la suite de Fibonacci
calculée avec mémoïsation ?
    \begin{choices}
    \wrongchoice{$O(n^2)$}
    \wrongchoice{$O(\log n)$}
    \wrongchoice{$O(2^n)$}
    \correctchoice{$O(n)$}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q05}
    Que signifie « le problème a des sous-problèmes
\textbf{recouvrants} » ?
    \begin{choices}
    \wrongchoice{Les sous-problèmes ont tous la même solution}
    \wrongchoice{Les sous-problèmes sont triés par taille décroissante}
    \wrongchoice{Les sous-problèmes sont indépendants les uns des autres}
    \correctchoice{Plusieurs sous-problèmes peuvent apparaître plus d'une fois dans la décomposition récursive}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q06}
    Que signifie « le problème possède une
\textbf{sous-structure optimale} » ?
    \begin{choices}
    \wrongchoice{La taille des sous-problèmes diminue de manière logarithmique}
    \correctchoice{La solution optimale du problème global est constituée des solutions optimales aux sous-problèmes}
    \wrongchoice{Le problème peut être résolu en parallèle sur plusieurs processeurs}
    \wrongchoice{Les sous-problèmes ont tous la même taille}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q07}
    Quelle est la différence principale entre un
\textbf{algorithme glouton} et un algorithme de
\textbf{programmation dynamique} ?
    \begin{choices}
    \correctchoice{L'algorithme glouton fait un choix local optimal sans revenir en arrière, tandis que la programmation dynamique explore toutes les possibilités via les sous-problèmes}
    \wrongchoice{L'algorithme glouton est récursif, alors que la programmation dynamique est itérative}
    \wrongchoice{La programmation dynamique est utilisée uniquement pour les jeux vidéo}
    \wrongchoice{L'algorithme glouton ne fonctionne que sur les graphes}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q08}
    Quelle structure Python convient le mieux pour
mémoïser une fonction prenant un seul paramètre
entier positif ?
    \begin{choices}
    \correctchoice{Une liste indexée par la valeur du paramètre}
    \wrongchoice{Un fichier sur le disque}
    \wrongchoice{Un dictionnaire avec les paramètres comme clés}
    \wrongchoice{Une variable globale unique}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q09}
    Le terme « programmation dynamique » a été
introduit en $1953$ par :
    \begin{choices}
    \wrongchoice{Tim Berners-Lee}
    \wrongchoice{Alan Turing}
    \wrongchoice{Donald Knuth}
    \correctchoice{Richard Bellman}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q10}
    Lequel des problèmes suivants se résout
typiquement par programmation dynamique ?
    \begin{choices}
    \wrongchoice{Tester si un nombre est premier}
    \wrongchoice{Inverser une chaîne de caractères}
    \wrongchoice{Trier un tableau}
    \correctchoice{Calculer le plus court chemin dans un graphe pondéré}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q11}
    On écrit la fonction suivante :

\begin{lstlisting}
memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
\end{lstlisting}

Combien d'appels effectifs (qui calculent
réellement, sans utiliser le cache) sont
effectués pour \texttt{fib(10)} ?
    \begin{choices}
    \wrongchoice{Exactement un}
    \correctchoice{Environ onze}
    \wrongchoice{Plus de mille}
    \wrongchoice{Environ cent}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q12}
    Quelle est la version \textbf{tabulée} (itérative) de
la suite de Fibonacci ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def fib(n):
    return round((1.618 ** n) / 2.236)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def fib(n):
    t = [0, 1]
    for i in range(2, n + 1):
        t.append(t[i-1] + t[i-2])
    return t[n]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def fib(n):
    return n * (n - 1) / 2
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q13}
    Le problème du \textbf{sac à dos $0/1$} consiste à
choisir un sous-ensemble d'objets à mettre dans
un sac de capacité fixée pour maximiser leur
valeur totale. Quelle est sa complexité en
programmation dynamique avec un sac de
capacité $W$ et $n$ objets ?
    \begin{choices}
    \wrongchoice{$O(n!)$}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(2^n)$}
    \correctchoice{$O(n \cdot W)$}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q14}
    Pour le problème du sac à dos $0/1$,
l'algorithme glouton qui prend les objets par
ordre décroissant du ratio « valeur / poids »
donne-t-il toujours la solution optimale ?
    \begin{choices}
    \wrongchoice{L'algorithme glouton est plus rapide mais moins précis}
    \correctchoice{Non, l'algorithme glouton peut manquer l'optimum dans le cas $0/1$}
    \wrongchoice{Oui, c'est l'algorithme correct pour ce problème}
    \wrongchoice{Cela dépend du langage de programmation utilisé}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q15}
    Quelle est la différence entre l'approche
\textbf{descendante} et l'approche \textbf{ascendante} en
programmation dynamique ?
    \begin{choices}
    \correctchoice{L'approche descendante est récursive avec mémoïsation, l'approche ascendante est itérative avec tabulation}
    \wrongchoice{L'approche descendante concerne les graphes, l'approche ascendante concerne les listes}
    \wrongchoice{L'approche descendante est toujours plus rapide}
    \wrongchoice{Aucune, ces termes sont synonymes}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q16}
    En Python, quel décorateur de la bibliothèque
\texttt{functools} automatise la mémoïsation d'une
fonction ?
    \begin{choices}
    \wrongchoice{\texttt{@dynamic}}
    \wrongchoice{\texttt{@cache\_me}}
    \correctchoice{\texttt{@lru\_cache}}
    \wrongchoice{\texttt{@memoize}}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q17}
    Pour le \textbf{rendu de monnaie} avec un système de
pièces arbitraire, la programmation dynamique
calcule, en $O(n \cdot s)$ (où $s$ est la somme
à rendre et $n$ le nombre de pièces) :
    \begin{choices}
    \wrongchoice{La somme totale rendue}
    \correctchoice{Le nombre minimal de pièces nécessaires pour atteindre la somme}
    \wrongchoice{La pièce la plus grande utilisée}
    \wrongchoice{Une séquence ordonnée de pièces}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q18}
    En quoi la programmation dynamique se
distingue-t-elle du paradigme « diviser pour
régner » classique ?
    \begin{choices}
    \wrongchoice{Le paradigme « diviser pour régner » utilise toujours la récursivité, contrairement à la programmation dynamique}
    \wrongchoice{La programmation dynamique ne s'applique qu'aux problèmes portant sur des entiers}
    \wrongchoice{La programmation dynamique est plus simple à coder}
    \correctchoice{En programmation dynamique, les sous-problèmes se recouvrent ; en « diviser pour régner », ils sont disjoints}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q19}
    La programmation dynamique illustre un
compromis classique en algorithmique. Lequel ?
    \begin{choices}
    \wrongchoice{Moins de mémoire consommée et moins de temps de calcul}
    \correctchoice{Plus de mémoire consommée, en échange de beaucoup moins de temps de calcul}
    \wrongchoice{Aucun changement par rapport à l'algorithme naïf}
    \wrongchoice{Plus de temps de calcul mais moins de mémoire consommée}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q20}
    Que calcule la fonction Python suivante ?

\begin{lstlisting}
def f(n):
    T = [0] * (n + 1)
    T[0] = 1
    for i in range(1, n + 1):
        T[i] = T[i-1] * i
    return T[n]
\end{lstlisting}
    \begin{choices}
    \correctchoice{La factorielle $n!$}
    \wrongchoice{La $n$-ième valeur de la suite de Fibonacci}
    \wrongchoice{$2^n$}
    \wrongchoice{La somme $1 + 2 + \cdots + n$}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q21}
    Pour calculer la plus longue sous-séquence
commune à deux chaînes de longueurs $m$ et $n$,
la programmation dynamique a une complexité
de :
    \begin{choices}
    \correctchoice{$O(m \cdot n)$}
    \wrongchoice{$O(m^2 + n^2)$}
    \wrongchoice{$O(m + n)$}
    \wrongchoice{$O(2^{m+n})$}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q22}
    Dans une mémoïsation manuelle, on écrit :

\begin{lstlisting}
def f(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = f(n-1, memo) + f(n-2, memo)
    return memo[n]
\end{lstlisting}

Quel problème pose le \texttt{memo=\{\}} placé en
paramètre par défaut ?
    \begin{choices}
    \correctchoice{Il est partagé entre tous les appels successifs de la fonction, conservant les valeurs entre exécutions différentes}
    \wrongchoice{Il rend la fonction trop lente, car le dictionnaire est recréé à chaque appel}
    \wrongchoice{Il ralentit globalement Python}
    \wrongchoice{Il provoque une erreur de récursion}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q23}
    En programmation dynamique, on calcule souvent
une \textbf{valeur optimale} (par exemple le coût
minimal). Comment retrouve-t-on la \textbf{solution
effective}, c'est-à-dire la séquence de
décisions qui mène à cet optimum ?
    \begin{choices}
    \wrongchoice{On ne peut pas, la programmation dynamique ne donne que la valeur optimale}
    \wrongchoice{On lance plusieurs programmations dynamiques avec différents paramètres pour identifier les choix}
    \correctchoice{On la reconstruit en parcourant la table à rebours, à partir de la valeur finale}
    \wrongchoice{On stocke aussi la solution dans la table}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q24}
    Pour calculer la suite de Fibonacci en $O(n)$
en temps avec une mémoire réduite, on peut
écrire :

\begin{lstlisting}
a, b = 0, 1
for _ in range(n):
    a, b = b, a + b
\end{lstlisting}

Quelle est la complexité \textbf{en mémoire} de
cette version ?
    \begin{choices}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(n^2)$}
    \correctchoice{$O(1)$}
    \wrongchoice{$O(\log n)$}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q25}
    Pour qu'un problème se résolve efficacement par
programmation dynamique, il doit posséder :
    \begin{choices}
    \wrongchoice{Une décomposition logarithmique du problème}
    \wrongchoice{Un seul cas de base et une seule récurrence}
    \wrongchoice{Une fonction objectif uniquement minimale}
    \correctchoice{La sous-structure optimale et des sous-problèmes recouvrants}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q26}
    On veut compter le nombre de chemins
monotones (n'allant qu'à droite ou en bas)
d'un coin d'une grille rectangulaire de $m$
lignes et $n$ colonnes au coin opposé. Quelle
est la récurrence appropriée et la complexité
par programmation dynamique ?
    \begin{choices}
    \correctchoice{$C(i, j) = C(i-1, j) + C(i, j-1)$ avec
$C(0, j) = C(i, 0) = 1$, complexité
$O(m \cdot n)$
}
    \wrongchoice{$C(i, j) = C(i-1, j-1) + 1$, complexité
$O(m \cdot n)$
}
    \wrongchoice{$C(i, j) = C(i-1, j) \cdot C(i, j-1)$,
complexité $O(m + n)$
}
    \wrongchoice{$C(i, j) = i + j$, calcul direct en
$O(1)$
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q27}
    La \textbf{distance d'édition} (ou distance de
Levenshtein) entre deux chaînes mesure le
nombre minimal d'opérations
(insertion, suppression, substitution) pour
transformer l'une en l'autre. Quel est le
schéma de programmation dynamique pour la
calculer ?
    \begin{choices}
    \wrongchoice{$D(i, j) = \max(i, j)$, calcul en $O(1)$
}
    \correctchoice{$D(i, j) = D(i-1, j-1)$ si les deux
derniers caractères sont égaux ; sinon,
$D(i, j) = 1 + \min(D(i-1, j),
D(i, j-1), D(i-1, j-1))$. Complexité
$O(m \cdot n)$
}
    \wrongchoice{On compare uniquement les premiers
caractères des deux chaînes. Complexité
$O(1)$
}
    \wrongchoice{$D(i, j) = D(i-1, j-1) + 1$ dans tous les
cas. Complexité $O(\min(m, n))$
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q28}
    Avec les pièces $\{1, 3, 4\}$ et la somme à
rendre $s = 6$, quel est le \textbf{nombre minimal}
de pièces calculé par programmation dynamique
(et l'écart avec la méthode gloutonne qui
prend toujours la plus grosse pièce
possible) ?
    \begin{choices}
    \wrongchoice{La programmation dynamique trouve $1$
pièce, l'algorithme glouton en trouve $2$
}
    \wrongchoice{La programmation dynamique et l'algorithme
glouton trouvent tous deux $3$ pièces
}
    \wrongchoice{Les deux échouent car aucune combinaison
ne donne $6$
}
    \correctchoice{La programmation dynamique trouve $2$
pièces (la combinaison $3 + 3$), tandis
que l'algorithme glouton en utilise $3$
(la combinaison $4 + 1 + 1$)
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q29}
    On dispose d'un sac de capacité $W = 5$ et de
trois objets : $O_1$ (poids $2$, valeur $3$),
$O_2$ (poids $3$, valeur $4$), $O_3$ (poids
$4$, valeur $5$). Quelle est la valeur
optimale obtenue par programmation
dynamique ?
    \begin{choices}
    \wrongchoice{$12$ (en prenant les trois objets)
}
    \correctchoice{$7$ (en prenant $O_1$ et $O_2$, poids
total $5$, valeur totale $7$)
}
    \wrongchoice{$5$ (en prenant uniquement $O_3$)
}
    \wrongchoice{$9$ (en prenant $O_2$ et $O_3$)
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q30}
    Quel code Python implémente correctement la
programmation dynamique ascendante (par
tabulation) pour le sac à dos $0/1$ avec $n$
objets de poids \texttt{poids[i]} et valeurs
\texttt{valeurs[i]} et un sac de capacité \texttt{W} ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    total = 0
    for i in range(len(poids)):
        total += valeurs[i]
    return total
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    n = len(poids)
    V = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            if poids[i-1] <= w:
                V[i][w] = max(V[i-1][w],
                              V[i-1][w-poids[i-1]] + valeurs[i-1])
            else:
                V[i][w] = V[i-1][w]
    return V[n][W]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    # Tri par ratio valeur/poids décroissant
    ordre = sorted(range(len(poids)),
                   key=lambda i: -valeurs[i]/poids[i])
    total = 0
    capa = W
    for i in ordre:
        if poids[i] <= capa:
            total += valeurs[i]
            capa -= poids[i]
    return total
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    return max(valeurs)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q31}
    On compare le calcul de \texttt{fibonacci(40)} avec
la version récursive naïve et avec la
version mémoïsée. Quel est l'ordre de
grandeur du rapport entre les deux
complexités ?
    \begin{choices}
    \wrongchoice{Les deux versions ont la même complexité
asymptotique
}
    \wrongchoice{La version mémoïsée est environ deux fois
plus rapide
}
    \wrongchoice{La version mémoïsée est plus lente à
cause du surcoût du cache
}
    \correctchoice{La version mémoïsée est environ
$10^{10}$ fois plus rapide
}
    \end{choices}
  \end{question}
}

\element{terminaleprogrammationdynamique}{
  \begin{question}{q32}
    Le sac à dos en programmation dynamique
utilise par défaut un tableau $V$ de taille
$(n+1) \times (W+1)$, soit un espace
$O(n \cdot W)$. Comment réduire cet
espace à $O(W)$ tout en gardant la même
complexité en temps ?
    \begin{choices}
    \correctchoice{On observe que pour calculer la ligne
$V[i]$, on n'a besoin que de la ligne
$V[i-1]$. On peut donc se contenter de
deux lignes (la précédente et la
courante), voire d'une seule en
parcourant les capacités de droite à
gauche
}
    \wrongchoice{On utilise un dictionnaire au lieu d'un
tableau
}
    \wrongchoice{On ne peut pas réduire l'espace en
dessous de $O(n \cdot W)$
}
    \wrongchoice{On compresse les valeurs avec un
algorithme de compression
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminaleprogrammationdynamique}
  \insertgroup{terminaleprogrammationdynamique}
}

\end{document}
