\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{Algorithmes gloutons}
\subtitle{QCM}
\author{Première}
\date{\today}

\begin{document}

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

% Q1 - Réponse en C
\begin{frame}[fragile]{Question 1 \textemdash{} Définition d'un algorithme glouton}
    Quel est le principe d'un \textbf{algorithme glouton} ?\medskip
    \begin{itemize}
        \item[A.] Il choisit toujours au hasard parmi les options disponibles
        \item[B.] Il essaie chaque possibilité, abandonne quand la solution échoue, puis revient en arrière pour explorer une autre voie
        \item[\alert<2>{C.}] \alert<2>{À chaque étape, il fait le choix qui semble localement le meilleur, sans jamais revenir en arrière}
        \item[D.] Il essaie toutes les solutions possibles, puis garde la meilleure
    \end{itemize}
\end{frame}

% Q2 - Réponse en C
\begin{frame}[fragile]{Question 2 \textemdash{} Exemple classique}
    Lequel des problèmes suivants est résolu
naturellement par un algorithme glouton, dans le
système monétaire de l'euro ?\medskip
    \begin{itemize}
        \item[A.] Calculer la racine carrée d'un nombre
        \item[B.] Trier une liste d'entiers
        \item[\alert<2>{C.}] \alert<2>{Le rendu de monnaie, qui consiste à donner le minimum de pièces pour atteindre un montant}
        \item[D.] Vérifier si une chaîne de caractères est un palindrome
    \end{itemize}
\end{frame}

% Q3 - Réponse en B
\begin{frame}[fragile]{Question 3 \textemdash{} Contre-exemple du rendu de monnaie}
    Avec le système hypothétique de pièces
$\{1, 3, 4\}$, on veut rendre $6$. Que donne
l'algorithme glouton qui prend la plus grande
pièce possible à chaque étape ?\medskip
    \begin{itemize}
        \item[A.] L'algorithme glouton ne termine pas
        \item[\alert<2>{B.}] \alert<2>{$4 + 1 + 1 = 6$, soit trois pièces}
        \item[C.] $3 + 3 = 6$, soit deux pièces
        \item[D.] $1 + 1 + 1 + 1 + 1 + 1 = 6$, soit six pièces
    \end{itemize}
\end{frame}

% Q4 - Réponse en A
\begin{frame}[fragile]{Question 4 \textemdash{} Caractéristiques d'un algorithme glouton}
    Lequel des énoncés suivants est \textbf{vrai} pour les
algorithmes gloutons ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Ils sont en général rapides, mais ne garantissent pas l'optimum global}
        \item[B.] Ils essaient toutes les solutions avant de choisir la meilleure
        \item[C.] Ils ont toujours une complexité exponentielle
        \item[D.] Ils ne fonctionnent que sur les listes triées
    \end{itemize}
\end{frame}

% Q5 - Réponse en B
\begin{frame}[fragile]{Question 5 \textemdash{} Critère de choix glouton}
    Pour résoudre un problème d'optimisation par un
algorithme glouton, quelle question doit-on se
poser en premier ?\medskip
    \begin{itemize}
        \item[A.] Quelle est la taille du problème ?
        \item[\alert<2>{B.}] \alert<2>{Quel critère local utiliser pour décider à chaque étape ?}
        \item[C.] Combien de cœurs possède le processeur ?
        \item[D.] Quel est le langage de programmation utilisé ?
    \end{itemize}
\end{frame}

% Q6 - Réponse en C
\begin{frame}[fragile]{Question 6 \textemdash{} Sélection d'activités}
    On dispose de $n$ activités, chacune définie par
une heure de début et une heure de fin. On
souhaite sélectionner le plus grand nombre
possible d'activités sans chevauchement. Quel
critère glouton donne la solution optimale ?\medskip
    \begin{itemize}
        \item[A.] Choisir l'activité qui commence le plus tôt
        \item[B.] Choisir une activité au hasard
        \item[\alert<2>{C.}] \alert<2>{Choisir l'activité qui finit le plus tôt parmi celles compatibles avec les choix précédents}
        \item[D.] Choisir l'activité qui dure le plus longtemps
    \end{itemize}
\end{frame}

% Q7 - Réponse en D
\begin{frame}[fragile]{Question 7 \textemdash{} Pas de retour en arrière}
    Quelle propriété distingue un algorithme glouton
des autres stratégies algorithmiques ?\medskip
    \begin{itemize}
        \item[A.] Il essaie toutes les solutions possibles avant de répondre
        \item[B.] Il ne fonctionne que sur des listes triées
        \item[C.] Il fait toujours un choix aléatoire à chaque étape
        \item[\alert<2>{D.}] \alert<2>{Il ne revient jamais sur ses décisions : un choix fait reste définitif}
    \end{itemize}
\end{frame}

% Q8 - Réponse en B
\begin{frame}[fragile]{Question 8 \textemdash{} Complexité d'un algorithme glouton}
    Quelle est typiquement la \textbf{complexité} d'un
algorithme glouton ?\medskip
    \begin{itemize}
        \item[A.] $O(n!)$, factorielle
        \item[\alert<2>{B.}] \alert<2>{Polynomiale, le plus souvent linéaire ou quasi-linéaire, c'est-à-dire $O(n)$ ou $O(n \log n)$}
        \item[C.] Exponentielle
        \item[D.] Indéfinie selon les cas
    \end{itemize}
\end{frame}

% Q9 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 9 \textemdash{} Algorithme glouton de rendu de monnaie en Python}
    Voici le squelette d'un algorithme glouton de
rendu de monnaie :

\begin{lstlisting}
def rendu(montant, pieces):
    pieces = sorted(pieces, reverse=True)
    resultat = []
    for p in pieces:
        while montant >= p:
            resultat.append(p)
            montant -= p
    return resultat
\end{lstlisting}

Que fait l'instruction
\texttt{pieces = sorted(pieces, reverse=True)} ?\medskip
    \begin{itemize}
        \item[A.] Elle compte le nombre de pièces
        \item[B.] Elle trie les pièces par ordre décroissant, pour traiter d'abord les plus grandes
        \item[C.] Elle mélange les pièces de manière aléatoire
        \item[D.] Elle trie les pièces par ordre croissant
    \end{itemize}
\end{frame}

% Q9 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 9 \textemdash{} Algorithme glouton de rendu de monnaie en Python}
    Voici le squelette d'un algorithme glouton de
rendu de monnaie :

\begin{lstlisting}
def rendu(montant, pieces):
    pieces = sorted(pieces, reverse=True)
    resultat = []
    for p in pieces:
        while montant >= p:
            resultat.append(p)
            montant -= p
    return resultat
\end{lstlisting}

Que fait l'instruction
\texttt{pieces = sorted(pieces, reverse=True)} ?\medskip
    \begin{itemize}
        \item[A.] Elle compte le nombre de pièces
        \item[\alert{B.}] \alert{Elle trie les pièces par ordre décroissant, pour traiter d'abord les plus grandes}
        \item[C.] Elle mélange les pièces de manière aléatoire
        \item[D.] Elle trie les pièces par ordre croissant
    \end{itemize}
\end{frame}

% Q10 - Réponse en A
\begin{frame}[fragile]{Question 10 \textemdash{} Choix irrévocable}
    Une caractéristique fondamentale d'un algorithme
glouton est que ses choix sont :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Irrévocables : une fois une décision prise, l'algorithme ne revient jamais dessus}
        \item[B.] Optimaux globalement par construction
        \item[C.] Aléatoires à chaque appel
        \item[D.] Réversibles à tout moment
    \end{itemize}
\end{frame}

% Q11 - Réponse en B
\begin{frame}[fragile]{Question 11 \textemdash{} Sac à dos fractionnaire}
    Pour le \textbf{sac à dos fractionnaire} (où l'on peut
couper les objets en fragments), quel critère
glouton donne l'optimum ?\medskip
    \begin{itemize}
        \item[A.] Prendre tous les objets disponibles
        \item[\alert<2>{B.}] \alert<2>{Prendre les objets par ordre décroissant de valeur par unité de poids, c'est-à-dire \texttt{valeur / poids}}
        \item[C.] Prendre les objets par ordre décroissant de poids
        \item[D.] Prendre les objets par ordre décroissant de valeur totale
    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile]{Question 12 \textemdash{} Sac à dos 0/1 et algorithme glouton}
    Pour le \textbf{sac à dos $0/1$}, où chaque objet est
pris entièrement ou pas du tout, pourquoi
l'algorithme glouton fondé sur le ratio
valeur/poids ne donne-t-il pas toujours
l'optimum ?\medskip
    \begin{itemize}
        \item[A.] Parce que les objets ne sont pas triés
        \item[\alert<2>{B.}] \alert<2>{Parce qu'on ne peut pas couper les objets, et qu'un choix glouton initial peut occuper tout le sac sans laisser de place à une combinaison meilleure}
        \item[C.] Parce que l'algorithme glouton est trop lent
        \item[D.] Parce que l'algorithme manque toujours de mémoire
    \end{itemize}
\end{frame}

% Q13 - Réponse en A
\begin{frame}[fragile]{Question 13 \textemdash{} Sélection d'activités}
    Le problème de la \textbf{sélection d'activités}
consiste à planifier le maximum d'activités
possible dans une journée, sachant qu'on ne peut
en faire qu'une à la fois. Quelle stratégie
gloutonne donne l'optimum ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Choisir à chaque étape l'activité dont l'heure de fin est la plus précoce parmi celles encore compatibles}
        \item[B.] Choisir l'activité dont l'heure de début est la plus précoce
        \item[C.] Choisir une activité au hasard
        \item[D.] Choisir à chaque étape l'activité la plus courte
    \end{itemize}
\end{frame}

% Q14 - Réponse en B
\begin{frame}[fragile]{Question 14 \textemdash{} Sac à dos fractionnaire}
    Dans le \textbf{sac à dos fractionnaire} (où l'on
peut prendre une fraction d'un objet), quel
critère glouton donne l'optimum ?\medskip
    \begin{itemize}
        \item[A.] Prendre les objets les plus lourds d'abord
        \item[\alert<2>{B.}] \alert<2>{Prendre les objets par ordre décroissant de ratio valeur/poids, puis remplir le reste de la capacité avec une fraction de l'objet suivant}
        \item[C.] Prendre les objets dans l'ordre alphabétique
        \item[D.] Prendre les objets par ordre décroissant de valeur
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Trace du rendu de monnaie}
    Avec la stratégie gloutonne (« prendre la plus
grande pièce ne dépassant pas le reste à
rendre ») et les pièces $\{1, 2, 5, 10\}$, quel
est le rendu pour la valeur $18$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$10 + 5 + 2 + 1 = 18$, soit quatre pièces}
        \item[B.] $5 + 5 + 5 + 2 + 1 = 18$, soit cinq pièces
        \item[C.] La pièce de $1$ répétée dix-huit fois
        \item[D.] $10 + 10 = 20$
    \end{itemize}
\end{frame}

% Q16 - Réponse en A
\begin{frame}[fragile]{Question 16 \textemdash{} Propriété de choix glouton}
    Pour qu'un algorithme glouton donne l'optimum
global, le problème doit posséder la \textbf{propriété
de choix glouton}. Que signifie-t-elle ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Il existe un choix local optimal qui peut être étendu en une solution globalement optimale}
        \item[B.] Tous les choix locaux mènent à l'optimum global
        \item[C.] Le problème a une solution unique
        \item[D.] L'algorithme termine en un nombre fini d'étapes
    \end{itemize}
\end{frame}

% Q17 - Réponse en A
\begin{frame}[fragile]{Question 17 \textemdash{} Tri par critère personnalisé}
    Pour trier en Python une liste d'objets par leur
ratio \texttt{valeur / poids} décroissant (par exemple
en préparation d'un sac à dos fractionnaire),
quelle écriture utilise-t-on ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{\texttt{objets.sort(key=lambda o: o.valeur / o.poids, reverse=True)}}
        \item[B.] \texttt{objets.sort()}
        \item[C.] \texttt{objets = max(objets)}
        \item[D.] \texttt{objets.sort(by='ratio')}
    \end{itemize}
\end{frame}

% Q18 - Réponse en D
\begin{frame}[fragile]{Question 18 \textemdash{} Méthode pour concevoir un algorithme glouton}
    Quelles étapes sont conseillées pour concevoir
un algorithme glouton sur un nouveau problème ?\medskip
    \begin{itemize}
        \item[A.] Choisir le premier critère qui paraît simple, sans le tester
        \item[B.] Coder en Python, lancer en production, et espérer que cela fonctionne
        \item[C.] Demander directement la solution à l'enseignant
        \item[\alert<2>{D.}] \alert<2>{D'abord identifier le critère de choix local, puis tester sur de nombreux exemples (en comparant si possible à une recherche exhaustive), et enfin chercher activement un contre-exemple}
    \end{itemize}
\end{frame}

% Q19 - Réponse en B
\begin{frame}[fragile]{Question 19 \textemdash{} Algorithme glouton et recherche exhaustive}
    Quel est l'avantage essentiel d'un algorithme
glouton sur une \textbf{recherche exhaustive} ?\medskip
    \begin{itemize}
        \item[A.] Il garantit toujours l'optimum
        \item[\alert<2>{B.}] \alert<2>{Il est bien plus rapide : sa complexité est polynomiale plutôt qu'exponentielle}
        \item[C.] Il est plus simple à expliquer en classe
        \item[D.] Il consomme moins de mémoire
    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile]{Question 20 \textemdash{} Algorithme glouton comme approximation}
    Lorsque l'algorithme glouton ne donne pas
l'optimum, peut-on quand même l'utiliser ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Oui, comme algorithme d'approximation rapide donnant une solution proche de l'optimum}
        \item[B.] Seulement si on retire la contrainte d'optimalité
        \item[C.] Oui, mais seulement avec un ordinateur quantique
        \item[D.] Non, jamais
    \end{itemize}
\end{frame}

% Q21 - Réponse en C
\begin{frame}[fragile]{Question 21 \textemdash{} Construire un contre-exemple}
    On vous propose un problème et un algorithme
glouton. Comment démontrer que cet algorithme ne
donne \textbf{pas} toujours l'optimum ?\medskip
    \begin{itemize}
        \item[A.] Vérifier que l'algorithme termine
        \item[B.] Démontrer que l'algorithme est lent
        \item[\alert<2>{C.}] \alert<2>{Trouver un exemple concret où l'algorithme glouton donne une solution strictement moins bonne que l'optimum}
        \item[D.] Compiler le programme dans plusieurs langages différents
    \end{itemize}
\end{frame}

% Q22 - Réponse en C
\begin{frame}[fragile]{Question 22 \textemdash{} Algorithme glouton et terminaison}
    Pourquoi un algorithme glouton \textbf{termine-t-il
toujours} en un nombre fini d'étapes ?\medskip
    \begin{itemize}
        \item[A.] Parce qu'il utilise une boucle \texttt{while}
        \item[B.] Parce que la mémoire de l'ordinateur est limitée
        \item[\alert<2>{C.}] \alert<2>{Parce qu'à chaque étape, soit l'algorithme prend un élément qui ne sera plus considéré ensuite, soit il s'arrête}
        \item[D.] Parce que tous les algorithmes terminent en informatique
    \end{itemize}
\end{frame}

% Q23 - Réponse en D
\begin{frame}[fragile]{Question 23 \textemdash{} Vérifier expérimentalement l'optimalité}
    On a écrit un algorithme glouton pour un
nouveau problème d'optimisation. Sans pouvoir
faire de démonstration formelle, comment se
donner une \textbf{bonne confiance} dans le fait
qu'il donne l'optimum sur les cas pratiques ?\medskip
    \begin{itemize}
        \item[A.] Augmenter la taille du problème pour voir
si cela aide

        \item[B.] Lui faire confiance s'il a été trouvé sur
Internet

        \item[C.] Lancer le programme une seule fois sur un
exemple et conclure

        \item[\alert<2>{D.}] \alert<2>{Comparer ses résultats à ceux d'une recherche
exhaustive sur de nombreux cas de petite
taille (où la recherche exhaustive reste
praticable), et chercher activement des
contre-exemples
}
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile]{Question 24 \textemdash{} Quelle approche essayer en premier ?}
    Face à un nouveau problème d'optimisation, quelle
approche essayer en \textbf{premier} ?\medskip
    \begin{itemize}
        \item[A.] Aucune méthode particulière, en essayant plusieurs idées au hasard
        \item[B.] Une recherche exhaustive systématique, pour être certain d'obtenir l'optimum
        \item[\alert<2>{C.}] \alert<2>{Un algorithme glouton simple : il est rapide à coder et à tester ; si l'optimalité est démontrée ou empiriquement bonne, on s'arrête là, sinon on cherche une autre approche}
        \item[D.] Une approche aléatoire, sans stratégie particulière
    \end{itemize}
\end{frame}

% Q25 - Réponse en D
\begin{frame}[fragile]{Question 25 \textemdash{} Conclusion sur les algorithmes gloutons}
    Lequel des énoncés suivants résume le mieux les
algorithmes gloutons ?\medskip
    \begin{itemize}
        \item[A.] Ils sont rapides et fonctionnent toujours
        \item[B.] Ils sont obsolètes et n'ont plus aucun intérêt aujourd'hui
        \item[C.] Ils utilisent l'intelligence artificielle
        \item[\alert<2>{D.}] \alert<2>{Ils sont rapides et simples ; ils donnent l'optimum sur certains problèmes, et constituent souvent une bonne approximation sur d'autres}
    \end{itemize}
\end{frame}

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

\end{document}
