\documentclass[a4paper,11pt]{article}

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

\title{Algorithmes gloutons}
\date{Numérique et sciences informatiques}

\begin{document}

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

\bigskip

\element{premierealgorithmesgloutons}{
  \begin{question}{q01}
    Quel est le principe d'un \textbf{algorithme glouton} ?
    \begin{choices}
    \wrongchoice{Il choisit toujours au hasard parmi les options disponibles}
    \wrongchoice{Il essaie chaque possibilité, abandonne quand la solution échoue, puis revient en arrière pour explorer une autre voie}
    \correctchoice{À chaque étape, il fait le choix qui semble localement le meilleur, sans jamais revenir en arrière}
    \wrongchoice{Il essaie toutes les solutions possibles, puis garde la meilleure}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q02}
    Lequel des problèmes suivants est résolu
naturellement par un algorithme glouton, dans le
système monétaire de l'euro ?
    \begin{choices}
    \wrongchoice{Calculer la racine carrée d'un nombre}
    \wrongchoice{Trier une liste d'entiers}
    \correctchoice{Le rendu de monnaie, qui consiste à donner le minimum de pièces pour atteindre un montant}
    \wrongchoice{Vérifier si une chaîne de caractères est un palindrome}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q03}
    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 ?
    \begin{choices}
    \wrongchoice{L'algorithme glouton ne termine pas}
    \correctchoice{$4 + 1 + 1 = 6$, soit trois pièces}
    \wrongchoice{$3 + 3 = 6$, soit deux pièces}
    \wrongchoice{$1 + 1 + 1 + 1 + 1 + 1 = 6$, soit six pièces}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q04}
    Lequel des énoncés suivants est \textbf{vrai} pour les
algorithmes gloutons ?
    \begin{choices}
    \correctchoice{Ils sont en général rapides, mais ne garantissent pas l'optimum global}
    \wrongchoice{Ils essaient toutes les solutions avant de choisir la meilleure}
    \wrongchoice{Ils ont toujours une complexité exponentielle}
    \wrongchoice{Ils ne fonctionnent que sur les listes triées}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q05}
    Pour résoudre un problème d'optimisation par un
algorithme glouton, quelle question doit-on se
poser en premier ?
    \begin{choices}
    \wrongchoice{Quelle est la taille du problème ?}
    \correctchoice{Quel critère local utiliser pour décider à chaque étape ?}
    \wrongchoice{Combien de cœurs possède le processeur ?}
    \wrongchoice{Quel est le langage de programmation utilisé ?}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q06}
    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 ?
    \begin{choices}
    \wrongchoice{Choisir l'activité qui commence le plus tôt}
    \wrongchoice{Choisir une activité au hasard}
    \correctchoice{Choisir l'activité qui finit le plus tôt parmi celles compatibles avec les choix précédents}
    \wrongchoice{Choisir l'activité qui dure le plus longtemps}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q07}
    Quelle propriété distingue un algorithme glouton
des autres stratégies algorithmiques ?
    \begin{choices}
    \wrongchoice{Il essaie toutes les solutions possibles avant de répondre}
    \wrongchoice{Il ne fonctionne que sur des listes triées}
    \wrongchoice{Il fait toujours un choix aléatoire à chaque étape}
    \correctchoice{Il ne revient jamais sur ses décisions : un choix fait reste définitif}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q08}
    Quelle est typiquement la \textbf{complexité} d'un
algorithme glouton ?
    \begin{choices}
    \wrongchoice{$O(n!)$, factorielle}
    \correctchoice{Polynomiale, le plus souvent linéaire ou quasi-linéaire, c'est-à-dire $O(n)$ ou $O(n \log n)$}
    \wrongchoice{Exponentielle}
    \wrongchoice{Indéfinie selon les cas}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q09}
    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)} ?
    \begin{choices}
    \wrongchoice{Elle compte le nombre de pièces}
    \correctchoice{Elle trie les pièces par ordre décroissant, pour traiter d'abord les plus grandes}
    \wrongchoice{Elle mélange les pièces de manière aléatoire}
    \wrongchoice{Elle trie les pièces par ordre croissant}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q10}
    Une caractéristique fondamentale d'un algorithme
glouton est que ses choix sont :
    \begin{choices}
    \correctchoice{Irrévocables : une fois une décision prise, l'algorithme ne revient jamais dessus}
    \wrongchoice{Optimaux globalement par construction}
    \wrongchoice{Aléatoires à chaque appel}
    \wrongchoice{Réversibles à tout moment}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q11}
    Pour le \textbf{sac à dos fractionnaire} (où l'on peut
couper les objets en fragments), quel critère
glouton donne l'optimum ?
    \begin{choices}
    \wrongchoice{Prendre tous les objets disponibles}
    \correctchoice{Prendre les objets par ordre décroissant de valeur par unité de poids, c'est-à-dire \texttt{valeur / poids}}
    \wrongchoice{Prendre les objets par ordre décroissant de poids}
    \wrongchoice{Prendre les objets par ordre décroissant de valeur totale}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q12}
    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 ?
    \begin{choices}
    \wrongchoice{Parce que les objets ne sont pas triés}
    \correctchoice{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}
    \wrongchoice{Parce que l'algorithme glouton est trop lent}
    \wrongchoice{Parce que l'algorithme manque toujours de mémoire}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q13}
    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 ?
    \begin{choices}
    \correctchoice{Choisir à chaque étape l'activité dont l'heure de fin est la plus précoce parmi celles encore compatibles}
    \wrongchoice{Choisir l'activité dont l'heure de début est la plus précoce}
    \wrongchoice{Choisir une activité au hasard}
    \wrongchoice{Choisir à chaque étape l'activité la plus courte}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q14}
    Dans le \textbf{sac à dos fractionnaire} (où l'on
peut prendre une fraction d'un objet), quel
critère glouton donne l'optimum ?
    \begin{choices}
    \wrongchoice{Prendre les objets les plus lourds d'abord}
    \correctchoice{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}
    \wrongchoice{Prendre les objets dans l'ordre alphabétique}
    \wrongchoice{Prendre les objets par ordre décroissant de valeur}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q15}
    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$ ?
    \begin{choices}
    \correctchoice{$10 + 5 + 2 + 1 = 18$, soit quatre pièces}
    \wrongchoice{$5 + 5 + 5 + 2 + 1 = 18$, soit cinq pièces}
    \wrongchoice{La pièce de $1$ répétée dix-huit fois}
    \wrongchoice{$10 + 10 = 20$}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q16}
    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 ?
    \begin{choices}
    \correctchoice{Il existe un choix local optimal qui peut être étendu en une solution globalement optimale}
    \wrongchoice{Tous les choix locaux mènent à l'optimum global}
    \wrongchoice{Le problème a une solution unique}
    \wrongchoice{L'algorithme termine en un nombre fini d'étapes}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q17}
    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 ?
    \begin{choices}
    \correctchoice{\texttt{objets.sort(key=lambda o: o.valeur / o.poids, reverse=True)}}
    \wrongchoice{\texttt{objets.sort()}}
    \wrongchoice{\texttt{objets = max(objets)}}
    \wrongchoice{\texttt{objets.sort(by='ratio')}}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q18}
    Quelles étapes sont conseillées pour concevoir
un algorithme glouton sur un nouveau problème ?
    \begin{choices}
    \wrongchoice{Choisir le premier critère qui paraît simple, sans le tester}
    \wrongchoice{Coder en Python, lancer en production, et espérer que cela fonctionne}
    \wrongchoice{Demander directement la solution à l'enseignant}
    \correctchoice{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{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q19}
    Quel est l'avantage essentiel d'un algorithme
glouton sur une \textbf{recherche exhaustive} ?
    \begin{choices}
    \wrongchoice{Il garantit toujours l'optimum}
    \correctchoice{Il est bien plus rapide : sa complexité est polynomiale plutôt qu'exponentielle}
    \wrongchoice{Il est plus simple à expliquer en classe}
    \wrongchoice{Il consomme moins de mémoire}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q20}
    Lorsque l'algorithme glouton ne donne pas
l'optimum, peut-on quand même l'utiliser ?
    \begin{choices}
    \correctchoice{Oui, comme algorithme d'approximation rapide donnant une solution proche de l'optimum}
    \wrongchoice{Seulement si on retire la contrainte d'optimalité}
    \wrongchoice{Oui, mais seulement avec un ordinateur quantique}
    \wrongchoice{Non, jamais}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q21}
    On vous propose un problème et un algorithme
glouton. Comment démontrer que cet algorithme ne
donne \textbf{pas} toujours l'optimum ?
    \begin{choices}
    \wrongchoice{Vérifier que l'algorithme termine}
    \wrongchoice{Démontrer que l'algorithme est lent}
    \correctchoice{Trouver un exemple concret où l'algorithme glouton donne une solution strictement moins bonne que l'optimum}
    \wrongchoice{Compiler le programme dans plusieurs langages différents}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q22}
    Pourquoi un algorithme glouton \textbf{termine-t-il
toujours} en un nombre fini d'étapes ?
    \begin{choices}
    \wrongchoice{Parce qu'il utilise une boucle \texttt{while}}
    \wrongchoice{Parce que la mémoire de l'ordinateur est limitée}
    \correctchoice{Parce qu'à chaque étape, soit l'algorithme prend un élément qui ne sera plus considéré ensuite, soit il s'arrête}
    \wrongchoice{Parce que tous les algorithmes terminent en informatique}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q23}
    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 ?
    \begin{choices}
    \wrongchoice{Augmenter la taille du problème pour voir
si cela aide
}
    \wrongchoice{Lui faire confiance s'il a été trouvé sur
Internet
}
    \wrongchoice{Lancer le programme une seule fois sur un
exemple et conclure
}
    \correctchoice{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{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q24}
    Face à un nouveau problème d'optimisation, quelle
approche essayer en \textbf{premier} ?
    \begin{choices}
    \wrongchoice{Aucune méthode particulière, en essayant plusieurs idées au hasard}
    \wrongchoice{Une recherche exhaustive systématique, pour être certain d'obtenir l'optimum}
    \correctchoice{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}
    \wrongchoice{Une approche aléatoire, sans stratégie particulière}
    \end{choices}
  \end{question}
}

\element{premierealgorithmesgloutons}{
  \begin{question}{q25}
    Lequel des énoncés suivants résume le mieux les
algorithmes gloutons ?
    \begin{choices}
    \wrongchoice{Ils sont rapides et fonctionnent toujours}
    \wrongchoice{Ils sont obsolètes et n'ont plus aucun intérêt aujourd'hui}
    \wrongchoice{Ils utilisent l'intelligence artificielle}
    \correctchoice{Ils sont rapides et simples ; ils donnent l'optimum sur certains problèmes, et constituent souvent une bonne approximation sur d'autres}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premierealgorithmesgloutons}
  \insertgroup{premierealgorithmesgloutons}
}

\end{document}
