\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{Programmation dynamique}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

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

% Q1 - Réponse en D
\begin{frame}[fragile]{Question 1 \textemdash{} Idée centrale de la programmation dynamique}
    Quel est le principe fondamental de la
programmation dynamique ?\medskip
    \begin{itemize}
        \item[A.] Diviser le problème en deux moitiés et résoudre chacune indépendamment
        \item[B.] Faire à chaque étape le choix qui semble localement le meilleur
        \item[C.] Modifier le programme à mesure qu'il s'exécute
        \item[\alert<2>{D.}] \alert<2>{Mémoriser les solutions des sous-problèmes pour ne pas avoir à les recalculer}
    \end{itemize}
\end{frame}

% Q2 - Réponse en D
\begin{frame}[fragile]{Question 2 \textemdash{} Mémoïsation}
    Qu'est-ce que la \textbf{mémoïsation} ?\medskip
    \begin{itemize}
        \item[A.] La comparaison de deux algorithmes pour choisir le plus rapide
        \item[B.] La conversion automatique d'une fonction récursive en boucle itérative
        \item[C.] La compression d'un programme en mémoire pour gagner de la place
        \item[\alert<2>{D.}] \alert<2>{Le stockage des résultats déjà calculés dans un cache pour les réutiliser}
    \end{itemize}
\end{frame}

% Q3 - Réponse en D
\begin{frame}[fragile]{Question 3 \textemdash{} Tabulation}
    Qu'appelle-t-on \textbf{tabulation} en programmation
dynamique ?\medskip
    \begin{itemize}
        \item[A.] Le découpage d'un problème en sous-problèmes égaux
        \item[B.] La création d'une table HTML pour afficher les résultats
        \item[C.] Une optimisation des comparaisons utilisée dans un algorithme de tri
        \item[\alert<2>{D.}] \alert<2>{La construction d'un tableau de résultats, en partant des plus petits sous-problèmes pour aller vers les plus grands}
    \end{itemize}
\end{frame}

% Q4 - Réponse en D
\begin{frame}[fragile]{Question 4 \textemdash{} Suite de Fibonacci en programmation dynamique}
    Quelle est la complexité de la suite de Fibonacci
calculée avec mémoïsation ?\medskip
    \begin{itemize}
        \item[A.] $O(n^2)$
        \item[B.] $O(\log n)$
        \item[C.] $O(2^n)$
        \item[\alert<2>{D.}] \alert<2>{$O(n)$}
    \end{itemize}
\end{frame}

% Q5 - Réponse en D
\begin{frame}[fragile]{Question 5 \textemdash{} Sous-problèmes recouvrants}
    Que signifie « le problème a des sous-problèmes
\textbf{recouvrants} » ?\medskip
    \begin{itemize}
        \item[A.] Les sous-problèmes ont tous la même solution
        \item[B.] Les sous-problèmes sont triés par taille décroissante
        \item[C.] Les sous-problèmes sont indépendants les uns des autres
        \item[\alert<2>{D.}] \alert<2>{Plusieurs sous-problèmes peuvent apparaître plus d'une fois dans la décomposition récursive}
    \end{itemize}
\end{frame}

% Q6 - Réponse en B
\begin{frame}[fragile]{Question 6 \textemdash{} Sous-structure optimale}
    Que signifie « le problème possède une
\textbf{sous-structure optimale} » ?\medskip
    \begin{itemize}
        \item[A.] La taille des sous-problèmes diminue de manière logarithmique
        \item[\alert<2>{B.}] \alert<2>{La solution optimale du problème global est constituée des solutions optimales aux sous-problèmes}
        \item[C.] Le problème peut être résolu en parallèle sur plusieurs processeurs
        \item[D.] Les sous-problèmes ont tous la même taille
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Programmation dynamique et algorithme glouton}
    Quelle est la différence principale entre un
\textbf{algorithme glouton} et un algorithme de
\textbf{programmation dynamique} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{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}
        \item[B.] L'algorithme glouton est récursif, alors que la programmation dynamique est itérative
        \item[C.] La programmation dynamique est utilisée uniquement pour les jeux vidéo
        \item[D.] L'algorithme glouton ne fonctionne que sur les graphes
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile]{Question 8 \textemdash{} Structure de mémoïsation}
    Quelle structure Python convient le mieux pour
mémoïser une fonction prenant un seul paramètre
entier positif ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une liste indexée par la valeur du paramètre}
        \item[B.] Un fichier sur le disque
        \item[C.] Un dictionnaire avec les paramètres comme clés
        \item[D.] Une variable globale unique
    \end{itemize}
\end{frame}

% Q9 - Réponse en D
\begin{frame}[fragile]{Question 9 \textemdash{} Origine du terme}
    Le terme « programmation dynamique » a été
introduit en $1953$ par :\medskip
    \begin{itemize}
        \item[A.] Tim Berners-Lee
        \item[B.] Alan Turing
        \item[C.] Donald Knuth
        \item[\alert<2>{D.}] \alert<2>{Richard Bellman}
    \end{itemize}
\end{frame}

% Q10 - Réponse en D
\begin{frame}[fragile]{Question 10 \textemdash{} Exemple classique de programmation dynamique}
    Lequel des problèmes suivants se résout
typiquement par programmation dynamique ?\medskip
    \begin{itemize}
        \item[A.] Tester si un nombre est premier
        \item[B.] Inverser une chaîne de caractères
        \item[C.] Trier un tableau
        \item[\alert<2>{D.}] \alert<2>{Calculer le plus court chemin dans un graphe pondéré}
    \end{itemize}
\end{frame}

% Q11 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Mémoïsation manuelle de Fibonacci}
    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)} ?\medskip
    \begin{itemize}
        \item[A.] Exactement un
        \item[B.] Environ onze
        \item[C.] Plus de mille
        \item[D.] Environ cent
    \end{itemize}
\end{frame}

% Q11 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Mémoïsation manuelle de Fibonacci}
    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)} ?\medskip
    \begin{itemize}
        \item[A.] Exactement un
        \item[\alert{B.}] \alert{Environ onze}
        \item[C.] Plus de mille
        \item[D.] Environ cent
    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Tabulation pour Fibonacci}
    Quelle est la version \textbf{tabulée} (itérative) de
la suite de Fibonacci ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def fib(n):
    return round((1.618 ** n) / 2.236)
\end{lstlisting}

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

        \item[C.]~\\
\begin{lstlisting}
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def fib(n):
    return n * (n - 1) / 2
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Tabulation pour Fibonacci}
    Quelle est la version \textbf{tabulée} (itérative) de
la suite de Fibonacci ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def fib(n):
    return round((1.618 ** n) / 2.236)
\end{lstlisting}

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

        \item[C.]~\\
\begin{lstlisting}
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def fib(n):
    return n * (n - 1) / 2
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q13 - Réponse en D
\begin{frame}[fragile]{Question 13 \textemdash{} Problème du sac à dos}
    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 ?\medskip
    \begin{itemize}
        \item[A.] $O(n!)$
        \item[B.] $O(n)$
        \item[C.] $O(2^n)$
        \item[\alert<2>{D.}] \alert<2>{$O(n \cdot W)$}
    \end{itemize}
\end{frame}

% Q14 - Réponse en B
\begin{frame}[fragile]{Question 14 \textemdash{} Sac à dos : comparer les deux approches}
    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 ?\medskip
    \begin{itemize}
        \item[A.] L'algorithme glouton est plus rapide mais moins précis
        \item[\alert<2>{B.}] \alert<2>{Non, l'algorithme glouton peut manquer l'optimum dans le cas $0/1$}
        \item[C.] Oui, c'est l'algorithme correct pour ce problème
        \item[D.] Cela dépend du langage de programmation utilisé
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Approche descendante et approche ascendante}
    Quelle est la différence entre l'approche
\textbf{descendante} et l'approche \textbf{ascendante} en
programmation dynamique ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{L'approche descendante est récursive avec mémoïsation, l'approche ascendante est itérative avec tabulation}
        \item[B.] L'approche descendante concerne les graphes, l'approche ascendante concerne les listes
        \item[C.] L'approche descendante est toujours plus rapide
        \item[D.] Aucune, ces termes sont synonymes
    \end{itemize}
\end{frame}

% Q16 - Réponse en C
\begin{frame}[fragile]{Question 16 \textemdash{} Le décorateur \texttt{lru\_cache} en Python}
    En Python, quel décorateur de la bibliothèque
\texttt{functools} automatise la mémoïsation d'une
fonction ?\medskip
    \begin{itemize}
        \item[A.] \texttt{@dynamic}
        \item[B.] \texttt{@cache\_me}
        \item[\alert<2>{C.}] \alert<2>{\texttt{@lru\_cache}}
        \item[D.] \texttt{@memoize}
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile]{Question 17 \textemdash{} Rendu de monnaie en programmation dynamique}
    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) :\medskip
    \begin{itemize}
        \item[A.] La somme totale rendue
        \item[\alert<2>{B.}] \alert<2>{Le nombre minimal de pièces nécessaires pour atteindre la somme}
        \item[C.] La pièce la plus grande utilisée
        \item[D.] Une séquence ordonnée de pièces
    \end{itemize}
\end{frame}

% Q18 - Réponse en D
\begin{frame}[fragile]{Question 18 \textemdash{} Programmation dynamique et diviser pour régner}
    En quoi la programmation dynamique se
distingue-t-elle du paradigme « diviser pour
régner » classique ?\medskip
    \begin{itemize}
        \item[A.] Le paradigme « diviser pour régner » utilise toujours la récursivité, contrairement à la programmation dynamique
        \item[B.] La programmation dynamique ne s'applique qu'aux problèmes portant sur des entiers
        \item[C.] La programmation dynamique est plus simple à coder
        \item[\alert<2>{D.}] \alert<2>{En programmation dynamique, les sous-problèmes se recouvrent ; en « diviser pour régner », ils sont disjoints}
    \end{itemize}
\end{frame}

% Q19 - Réponse en B
\begin{frame}[fragile]{Question 19 \textemdash{} Compromis mémoire et temps}
    La programmation dynamique illustre un
compromis classique en algorithmique. Lequel ?\medskip
    \begin{itemize}
        \item[A.] Moins de mémoire consommée et moins de temps de calcul
        \item[\alert<2>{B.}] \alert<2>{Plus de mémoire consommée, en échange de beaucoup moins de temps de calcul}
        \item[C.] Aucun changement par rapport à l'algorithme naïf
        \item[D.] Plus de temps de calcul mais moins de mémoire consommée
    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 20 \textemdash{} Lecture d'une programmation dynamique ascendante}
    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}\medskip
    \begin{itemize}
        \item[A.] La factorielle $n!$
        \item[B.] La $n$-ième valeur de la suite de Fibonacci
        \item[C.] $2^n$
        \item[D.] La somme $1 + 2 + \cdots + n$
    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 20 \textemdash{} Lecture d'une programmation dynamique ascendante}
    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}\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{La factorielle $n!$}
        \item[B.] La $n$-ième valeur de la suite de Fibonacci
        \item[C.] $2^n$
        \item[D.] La somme $1 + 2 + \cdots + n$
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile]{Question 21 \textemdash{} Plus longue sous-séquence commune}
    Pour calculer la plus longue sous-séquence
commune à deux chaînes de longueurs $m$ et $n$,
la programmation dynamique a une complexité
de :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$O(m \cdot n)$}
        \item[B.] $O(m^2 + n^2)$
        \item[C.] $O(m + n)$
        \item[D.] $O(2^{m+n})$
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 22 \textemdash{} Piège du paramètre par défaut mutable}
    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 ?\medskip
    \begin{itemize}
        \item[A.] Il est partagé entre tous les appels successifs de la fonction, conservant les valeurs entre exécutions différentes
        \item[B.] Il rend la fonction trop lente, car le dictionnaire est recréé à chaque appel
        \item[C.] Il ralentit globalement Python
        \item[D.] Il provoque une erreur de récursion
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 22 \textemdash{} Piège du paramètre par défaut mutable}
    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 ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{Il est partagé entre tous les appels successifs de la fonction, conservant les valeurs entre exécutions différentes}
        \item[B.] Il rend la fonction trop lente, car le dictionnaire est recréé à chaque appel
        \item[C.] Il ralentit globalement Python
        \item[D.] Il provoque une erreur de récursion
    \end{itemize}
\end{frame}

% Q23 - Réponse en C
\begin{frame}[fragile]{Question 23 \textemdash{} Reconstruire la solution}
    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 ?\medskip
    \begin{itemize}
        \item[A.] On ne peut pas, la programmation dynamique ne donne que la valeur optimale
        \item[B.] On lance plusieurs programmations dynamiques avec différents paramètres pour identifier les choix
        \item[\alert<2>{C.}] \alert<2>{On la reconstruit en parcourant la table à rebours, à partir de la valeur finale}
        \item[D.] On stocke aussi la solution dans la table
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 24 \textemdash{} Optimisation de l'espace}
    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 ?\medskip
    \begin{itemize}
        \item[A.] $O(n)$
        \item[B.] $O(n^2)$
        \item[C.] $O(1)$
        \item[D.] $O(\log n)$
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 24 \textemdash{} Optimisation de l'espace}
    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 ?\medskip
    \begin{itemize}
        \item[A.] $O(n)$
        \item[B.] $O(n^2)$
        \item[\alert{C.}] \alert{$O(1)$}
        \item[D.] $O(\log n)$
    \end{itemize}
\end{frame}

% Q25 - Réponse en D
\begin{frame}[fragile]{Question 25 \textemdash{} Reconnaître un problème de programmation dynamique}
    Pour qu'un problème se résolve efficacement par
programmation dynamique, il doit posséder :\medskip
    \begin{itemize}
        \item[A.] Une décomposition logarithmique du problème
        \item[B.] Un seul cas de base et une seule récurrence
        \item[C.] Une fonction objectif uniquement minimale
        \item[\alert<2>{D.}] \alert<2>{La sous-structure optimale et des sous-problèmes recouvrants}
    \end{itemize}
\end{frame}

% Q26 - Réponse en A
\begin{frame}[fragile]{Question 26 \textemdash{} Chemins dans une grille}
    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 ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$C(i, j) = C(i-1, j) + C(i, j-1)$ avec
$C(0, j) = C(i, 0) = 1$, complexité
$O(m \cdot n)$
}
        \item[B.] $C(i, j) = C(i-1, j-1) + 1$, complexité
$O(m \cdot n)$

        \item[C.] $C(i, j) = C(i-1, j) \cdot C(i, j-1)$,
complexité $O(m + n)$

        \item[D.] $C(i, j) = i + j$, calcul direct en
$O(1)$

    \end{itemize}
\end{frame}

% Q27 - Réponse en B
\begin{frame}[fragile]{Question 27 \textemdash{} Distance d'édition}
    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 ?\medskip
    \begin{itemize}
        \item[A.] $D(i, j) = \max(i, j)$, calcul en $O(1)$

        \item[\alert<2>{B.}] \alert<2>{$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)$
}
        \item[C.] On compare uniquement les premiers
caractères des deux chaînes. Complexité
$O(1)$

        \item[D.] $D(i, j) = D(i-1, j-1) + 1$ dans tous les
cas. Complexité $O(\min(m, n))$

    \end{itemize}
\end{frame}

% Q28 - Réponse en D
\begin{frame}[fragile]{Question 28 \textemdash{} Trace sur le rendu de monnaie}
    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) ?\medskip
    \begin{itemize}
        \item[A.] La programmation dynamique trouve $1$
pièce, l'algorithme glouton en trouve $2$

        \item[B.] La programmation dynamique et l'algorithme
glouton trouvent tous deux $3$ pièces

        \item[C.] Les deux échouent car aucune combinaison
ne donne $6$

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

% Q29 - Réponse en B
\begin{frame}[fragile]{Question 29 \textemdash{} Trace du sac à dos}
    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 ?\medskip
    \begin{itemize}
        \item[A.] $12$ (en prenant les trois objets)

        \item[\alert<2>{B.}] \alert<2>{$7$ (en prenant $O_1$ et $O_2$, poids
total $5$, valeur totale $7$)
}
        \item[C.] $5$ (en prenant uniquement $O_3$)

        \item[D.] $9$ (en prenant $O_2$ et $O_3$)

    \end{itemize}
\end{frame}

% Q30 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 30 \textemdash{} Code du sac à dos en programmation dynamique}
    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} ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    total = 0
    for i in range(len(poids)):
        total += valeurs[i]
    return total
\end{lstlisting}

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

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

        \item[D.]~\\
\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    return max(valeurs)
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q30 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 30 \textemdash{} Code du sac à dos en programmation dynamique}
    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} ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    total = 0
    for i in range(len(poids)):
        total += valeurs[i]
    return total
\end{lstlisting}

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

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

        \item[D.]~\\
\begin{lstlisting}
def sac_a_dos(poids, valeurs, W):
    return max(valeurs)
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q31 - Réponse en D
\begin{frame}[fragile]{Question 31 \textemdash{} Mesurer le gain de la mémoïsation}
    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 ?\medskip
    \begin{itemize}
        \item[A.] Les deux versions ont la même complexité
asymptotique

        \item[B.] La version mémoïsée est environ deux fois
plus rapide

        \item[C.] La version mémoïsée est plus lente à
cause du surcoût du cache

        \item[\alert<2>{D.}] \alert<2>{La version mémoïsée est environ
$10^{10}$ fois plus rapide
}
    \end{itemize}
\end{frame}

% Q32 - Réponse en A
\begin{frame}[fragile]{Question 32 \textemdash{} Optimisation de l'espace pour le sac à dos}
    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 ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{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
}
        \item[B.] On utilise un dictionnaire au lieu d'un
tableau

        \item[C.] On ne peut pas réduire l'espace en
dessous de $O(n \cdot W)$

        \item[D.] On compresse les valeurs avec un
algorithme de compression

    \end{itemize}
\end{frame}

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

\end{document}
