\def\NomChapitre{Programmation dynamique}
\def\Type{TP}
\LeTitre{\Type}{\NomChapitre}


\section{Dictionnaires (TD)}

Rappel de la syntaxe des {\em
  \href{https://docs.python.org/3/tutorial/datastructures.html#dictionaries}{dictionnaire}}. 

Une liste \lstinline{L} est un ensemble ordonné d'éléments auxquels on accède via leur
indice : \lstinline{L[i]}. 

Un dictionnaire suit le même principe, mais au lieu
d'un indice, on utilise une clef que l'on définit soi-même : c'est un semble
de paires {\em clef : valeur}.
Un exemple en forme d'annuaire:
\smallskip

\begin{tabular}{|l|l|}\hline
\lstinline[]$mesNum = {'Ariane': 0620, 'Pierre': 0720}$
& Analogue de \lstinline[]$L = [2, 4, 1]$.\\\hline
\lstinline[]$mesNum['Ariane']$
& Analogue de \lstinline[]$L[i]$ pour une liste.\\
\lstinline[]$mesNum['Thesee'] = 0454$
& Rentre un nouveau couple clef: valeur.\\\hline
\lstinline[]$'Egee'  in mesNum$
& Teste la présence d'une clef.\\\hline
\end{tabular}

\begin{exo}
Le magasin \emph{Geek and sons} gère la \og liste\fg\ des articles disponibles, ainsi que leurs prix, à l'aide d'un dictionnaire nommé {\tt Produits}, dont les clés sont le nom des articles (type chaîne de caractère), et les valeurs associées sont les prix correspondants (type réel).

Par exemple:

 \lstinline[]$Produits ={'Sabre laser':229.0, 'Mitendo DS':127.30, 'Coussin Linux':74.50,...}$

\begin{enumerate}
\item Ecrire une fonction qui prend en entrée le nom d'un produit (sous forme d'une chaîne de caractère) et qui renvoie \lstinline{True} si le produit est disponible, \lstinline{False} sinon.
\item Trouver le produit dont le prix est le plus cher.
\item Ecrire une fonction \lstinline{fourchette(mini, maxi)}, qui renvoie la liste des noms des objets dont le prix est entre \lstinline{mini} et \lstinline{maxi}.
\item Le \emph{panier} est un concept omniprésent dans les sites marchands, \emph{Geeks and sons} n'échappe pas à la règle. En Python, le panier du client sera représenté par un dictionnaire dont les clés sont les noms des produits, et les valeurs la quantité que le consommateur veut acheter.
\begin{enumerate}
\item Donner une expression Python correspondant à l'achat de $3$ sabres lasers, de $2$ coussins Linux et de $1$ Mitendo DS.
\item Ecrire une fonction \lstinline{prix} qui prend en entrée un panier, et qui retourne le prix total correspondant.\\
{\it Remarque : on supposera que tous les articles du panier sont disponibles}.
\end{enumerate}
\end{enumerate}
% \begin{sol}
% {\bf 1)} 
% \begin{verbatim}
% def present(nom):
%     if nom in Produits:
%         return True
%     else:
%         return False
% \end{verbatim}

% {\bf 2)} 
% \begin{verbatim}
% def le_plus_cher():
%     max = -1
%     for prod, prix in Produits.items():
%         if prix > max:
%             max = prix
%             produit = prod
%     return prod
% \end{verbatim}

% {\bf 3)} 
% \begin{verbatim}
% def fourchette(mini, maxi):
%     res = []
%     for prod, prix in Produits.items():
%         if prix >= min and prix <= max:
%             res.append(prod)
%     return res
% \end{verbatim}

% {\bf 4a)} {\tt panier = {'Sabre laser':3, 'Coussin Linux':2, 'Mitendo DS':1}}

% {\bf 4b)} 
% \begin{verbatim}
% def prix(panier):
%     som = 0
%     for objet, nb in panier:
%         som = som + nb * Produits[objet]
%     return som
% \end{verbatim}


% \hrule\end{sol}
\end{exo}


\section{La suite de Fibonacci} 

On définit la suite $(u_n)$ par
\[u_0=0\qquad u_1=1 \qquad \forall n \in\N\backslash\{0,1\}\quad 
u_n=u_{n-1}+u_{n-2}\]
C'est la \og{} suite de Fibonacci \fg{}, une suite d'entiers qui a été utilisée
au XIIIe siècle pour décrire la croissance d'une population de lapins (on
compte les couples à chaque génération, sans décès).

Vous remarquerez que c'est une suite récurrente linéaire : vous connaissez des
techniques pour calculer directement le $n$-ième terme. Mais ces techniques,
appliquées à l'informatique, font utiliser des \lstinline{float} et donc
potentiellement perdre en précision (en fait, avec le théorème des
accroissements finis on réussit à
maîtriser l'erreur... mais ce n'est pas le sujet ici\footnote{Un test en Python sur une machine 64 bits donne un résultat qui n'est plus entier dès $n=4$, et dont la valeur entière la plus proche n'est pas la valeur correcte pour $n=71$.}).

Vous aurez éventuellement besoin d'augmenter le niveau de récursion autorisé
par Python : 

\begin{center}
\begin{minipage}{.8\linewidth}
\begin{lstlisting}
import sys
sys.setrecursionlimit(10000)
\end{lstlisting}
\end{minipage}
\end{center}

\subsection{Version récursive naïve}

\begin{exo}\label{fibonaif}
~\\\vspace{-1cm}
\begin{enumerate}
\item Écrire une fonction récursive qui calcule le $n$-ième terme de la suite de
Fibonacci. 
\item Tester la rapidité (un $n$ raisonnable pourra être
  obtenu par dichotomie -- à la main). Que constate-t-on ?
\item Tracer le nombre d'appels récursifs en fonction de $n$, à l'aide d'un
  compteur. Conjecturer la complexité en fonction de $n$.
\item Déterminer, par une preuve rigoureuse, la complexité de
  l'algorithme. On comptera le nombre d'appel récursif. 
\end{enumerate}
\end{exo}

\subsection{De bas en haut : méthode ascendante}

\begin{exo}\label{fiboiter}
Écrire un algorithme itératif (\cad{} une boucle) qui calcule $u_n$ 
\og{} du bas vers le haut \fg{}, donc en partant de $u_0$ et $u_1$.
%
Donner la complexité de cet algorithme. On comptera le nombre d'additions.
\end{exo}


\subsection{Méthode descendante : versions avec mémoïsation}

On revient à des algorithmes récursifs, en essayant d'améliorer la complexité.


\begin{exo}[Formule de récurrence usuelle]\label{fibomemo}
Améliorer l'algorithme récursif naïf en stockant les $u_k$ déjà calculés (et
donc 
en vérifiant, à chaque étape, si on a ou non déjà calculé le $u_n$ que l'on
cherche). Donner la complexité du nouvel algorithme (on pourra commencer par
tracer la courbe du compteur en fonction de $n$) en comptant le nombre
d'additions.
\end{exo}


\begin{exo}[Autre formule de récurrence]
On admet les formules :
$\forall n \in \N^*\quad \left\{\begin{array}{rcl}
u_{2n+1}&=& u_{n+1}^2+u_n^2\\
u_{2n}&=& 2u_nu_{n-1}+u_n^2
\end{array}\right.$

Écrire un algorithme récursif avec mémoïsation qui utilise ces
formules. Quelle est sa complexité ? (sans preuve : on pourra se contenter de
faire un calcul dans le cas où $n$ est d'une forme sympathique).
\end{exo}



\newpage



\section{Rendu de monnaie}
On cherche à rendre une somme $v$ de monnaie à l'aide de différents types de
pièces et de billets. 

Les types de pièces et billets sont appelés « système de monnaie », représenté
par un $n$-uplet 
$S=(s_1,\dots,s_n)$ rangé par ordre croissant ($s_1 < \dots < s_n$). 

Une infinité de pièces de chaque type est disponible : elles ne s'épuisent
jamais. 

Le résultat sera, dans un premier temps, la liste
décroissante des pièces rendues.

\begin{ex}
Le système de monnaie de l'euro (tronqué des billets les plus élevés) est 
$S = \{1,2,5,10,20,50\}$. Quelques exemples de rendus :
\begin{enumerate}
\item Pour atteindre $63$ avec $S$, on rendra
  par exemple $1$ billet de $50$, $1$ billet de $10$, $1$ pièce de $2$ et $1$
  pièce de $1$, ce qui peut se noter
\[(50,10,2,1)\qquad 63=1+2+10+50\]
\item Pour rendre $7$, il y $6$ possibilités :
\[(1, 1, 1, 1, 1, 1, 1),\ 
(2, 1, 1, 1, 1, 1),\ 
(2, 2, 1, 1, 1),\ 
(2, 2, 2, 1),\ 
(5, 1, 1),\ 
(5, 2)
\]
%\[(7,0,0),\ (5,1,0),\ (3,2,0),\ (1,3,0),\ (2,0,1),\ (0,1,1)\]
\end{enumerate}
\end{ex}

\begin{deftn}[solution]
Une solution pour rendre la somme $v$ avec le système $S=(s_1,\dots,s_n)$ est
une liste $\ell$ d'éléments de $S$ tels que 
\[\sum_{i=1}^k \ell_i = v\]
\end{deftn}

\begin{deftn}[solution optimale]
Une solution est appelée « optimale » si elle rend le minimum de pièces : la
longueur $k$ de la liste $\ell$ doit être minimale parmi toutes les solutions
possibles.
\end{deftn}

\begin{ex}
\begin{enumerate}
\item 
Avec $S$ comme ci-dessus, $\ell =(5, 2)$ est optimale pour rendre $v=7$.
\item 
Avec $S=\{1,3,4\}$ et $v=6$, la solution optimale sera $\ell=(3,3)$.
\end{enumerate}
\end{ex}

\subsection{Rappels : l'algorithme glouton}
La méthode « usuelle » pour rendre la monnaie est celle de l'algorithme
glouton : tant qu'il reste quelque chose à rendre, choisir la plus grosse
pièce disponible (sans rendre trop). C'est un algorithme très simple et
rapide. 

On appelle canonique un système $S$ de pièces pour lequel cet
algorithme donne une solution optimale quelle que soit la valeur à rendre :
c'est le cas de la plupart des système de monnaie en circulation. 

\medskip

Plus généralement, qu'est-ce qu'un algorithme glouton ?
Lorsqu'il y a un choix à faire lors d'une étape d'un algorithme
 (ici, choisir quelle pièce rendre, mais on peut imaginer choisir une
 conférence à placer dans une salle (Activité 8 an dernier), ou choisir 
 une arête à
 un embranchement lorsqu'on cherche un plus court chemin dans un graphe), 
on utilise un critère simple à calculer (ici, la plus grande pièce inférieure
à la valeur restant à rendre). Pour le problème du choix de l'activité, on
choisissait la conférence qui se terminait le plus tôt. 

\medskip

Ces algorithmes ne donnent pas forcément la solution optimale, ni même une
solution, selon le problème traité. Mais ils ont souvent une bonne
complexité. 


\begin{ex}
~\\\vspace{-1cm}
\begin{enumerate}
\item Les solutions données dans les exemples 1.1 ($63=1+2+10+50$)
et 2.1 ($7 = 5+2$), sont des solutions  gloutonnes. 
\item Dans l'exemple 2.2,
  avec $S=\{1,3,4\}$ et $v=6$, la solution gloutonne sera $(4,1,1)$,
  donc ne sera pas une solution optimale : $(3,3)$ est optimale.
% \item S'il n'y a plus de pièces de $1$ dans le système usuel,
%   $S=(2,5,10,20,50)$, et, pour rendre $v=63$, l'algorithme glouton 
\end{enumerate}
\end{ex}


\begin{exo}[algorithme glouton]\label{TDdynExoGlout}
Dans cet exercice, on se donne un ensemble de pièces \lstinline{S} avec lequel
on cherche à rendre une somme $v$.
\begin{enumerate}
\item Écrire une fonction \lstinline{maximum(L,borne)} qui retourne le maximum
  des éléments de la liste \lstinline{L} inférieurs ou égaux à
  \lstinline{borne}. 
\item Écrire en python un algorithme \lstinline{renduGlouton(v, S)} qui
  prend en entrée une valeur entière \lstinline{v} et un tuple \lstinline{S},
  et retourne une liste \lstinline{L} d'éléments de $S$ de longueur $k$ telle
  que 
\[v = \sum_{i=0}^{k-1}  L[i]\]
On utilisera un algorithme glouton, de préférence récursif. Testez sur les
exemples donnés ci-dessus.
\item Êtes-vous certain que votre programme se termine ? Trouver un exemple de
  $S$ et $v$ tel que l'algorithme glouton n'arrive pas à rendre la monnaie,
  alors que le problème de rendu de monnaie a une solution. Corriger votre
  algorithme au besoin.
\item (facultatif) Proposer une version itérative de  l'algorithme
  ci-dessus.
\item (facultatif) Proposer une version de l'algorithme qui retourne, au lieu de la liste
 \lstinline{L},
 un dictionnaire \lstinline{d} dont les clefs sont des pièces de
 \lstinline{S}, et les valeurs \lstinline{d[s]} le nombre de pièce $s$
 rendues, \cad{} tel que 
\[v=\sum_{s\in d.keys()} d[s]\times s \]
\end{enumerate}
\end{exo}



\subsection{Version dynamique}

Cherchons désormais une solution optimale au problème de rendu de monnaie.

Il s'agit dans le cas général d'un problème NP-complet (en particulier, on
pense qu'il n'existe pas d'algorithme de complexité polynomiale en $n$
permettant de le résoudre).

\medskip

L'algorithme proposé ici pour chercher la solution optimale teste toutes les
décompositions possibles de $v$.

\medskip

Le principe consiste à parcourir les valeurs possibles $s$ des pièces
utilisables -- donc inférieures à $v$ -- et à rappeler la fonction pour rendre
la valeur $v-s$. 

Pour ne pas tester deux fois le même rendu (pour rendre $7$,
$5$ puis $2$ ou $2$ puis $5$), $s$ devra aussi être inférieur ou égal à la plus
petite pièce déjà utilisée.

% Structure de données : on utilisera un dictionnaire comme dans l'exercice
% \ref{TDdynExoGlout}. 

Pour une version animé et interactive du parcours de l'arbre des appels
récursifs par l'algorithme, on peut consulter la page suivante :

\url{http://mpechaud.fr/scripts/recursivite/recursivite.html#rendu}

\begin{exo}[Version dynamique]
~\\\vspace{-1cm}
\begin{enumerate}
\item Écrire en python un algorithme \lstinline{rendusAf(v, S, L=[])} qui
  prend en entrée une valeur entière \lstinline{v}, un tuple \lstinline{S}, et
  la liste \lstinline{L} du rendu, et affiche tous les rendus possibles pour
  la somme $v$ sous forme de listes \lstinline{L} comme à l'exercice
  \ref{TDdynExoGlout}.

\item Écrire en python un algorithme \lstinline{rendus(v, S, L=[], resultat=[])} qui prend en
  entrée une valeur entière \lstinline{v}, le tuple \lstinline{S}, la liste
  \lstinline{L} comme ci-dessus, et une liste \lstinline{resultat} qui
  contiendra le resultat, et
  retourne la liste de tous les rendus possibles pour la somme $v$ comme
  ci-dessus. %, sous forme d'une
% liste de dictionnaires \lstinline{d} de clefs contenues dans
% \lstinline{S} 
% tels que  
% \[v=\sum_{s\in d.keys()} d[s]\times s \]
On veillera à éviter de calculer plusieurs fois la décomposition d'une même
somme $w$.
\end{enumerate}
\end{exo}

% TO DO : pas encapspulé, pas d'ordre dans la liste de pièces rendues d'abord,
% puis un ordre, 
% puis mémo.
% Puis avec fonction pour ne garder que le rendu min à chaque étape :
% recherche sous contrainte de minimisation (retrouver terme exact)




% \begin{ex}
% Le système de monnaie de l'euro (tronqué des billets les plus élevés) est 
% $S = \{1,2,5,10,20,50\}$. Quelques exemples de rendus :
% \begin{enumerate}
% \item Pour atteindre $63$ avec $S$, on rendra
%   par exemple $1$ billet de $50$, $1$ billet de $10$, $1$ pièce de $2$ et $1$
%   pièce de $1$, ce qui peut se noter
% \[(1, 1, 0, 1, 0, 1)\qquad 63=1+2+10+50\]
% \item Pour rendre $7$, il y $6$ possibilités :
% \[(7,0,0),\ (5,1,0),\ (3,2,0),\ (1,3,0),\ (2,0,1),\ (0,1,1)\]
% \end{enumerate}
% \end{ex}

% \begin{deftn}[solution]
% Une solution pour rendre la somme $v$ avec le système $S=(s_1,\dots,s_n)$ est
% un $n$-uplet $(x_1,\dots,x_n)$ d'entiers tel que 
% \[x_1 s_1 + \dots x_n s_n = \sum_{i=1}^n x_i s_i = v\]
% \end{deftn}

% \begin{deftn}[solution optimale]
% Une solution est appelée « optimale » si elle rend le minimum de pièces.

% Notons 
% $\cS = \left\{(x_1,\dots,x_n)\in \N^n \mid \sum_{i=1}^n x_is_i=v\right\}$ 
% l'ensemble des solutions. 
% Alors $x=(x_1,\dots,x_n) \in \cS$ est optimale 
% si $\sum_{i=1}^n x_i$ est minimale :
% \[ \sum_{i=1}^n x_i = \min \left\{\sum_{i=1}^n x_i \mid\ x\in\cS \right\}\]
% \end{deftn}

% \begin{ex}
% \begin{enumerate}
% \item 
% Avec $S$ comme ci-dessus, $x=(0,1,1)$ est optimale pour rendre $v=7$.
% \item 
% Avec $S=\{1,3,4\}$ et $v=6$, la solution optimale sera $x=(0,2,0)$.
% \end{enumerate}
% \end{ex}

% \subsection{Rappels : l'algorithme glouton}
% La méthode « usuelle » pour rendre la monnaie est celle de l'algorithme
% glouton : tant qu'il reste quelque chose à rendre, choisir la plus grosse
% pièce qu'on peut rendre (sans rendre trop). C'est un algorithme très simple et
% rapide, et on appelle canonique un système $S$ de pièces pour lequel cet
% algorithme donne une solution optimale quelle que soit la valeur à rendre
% (c'est le cas de la plupart des système de monnaie en circulation). 

% Plus généralement, qu'est-ce qu'un algorithme glouton: 
% Lorsqu'il y a un choix à faire lors d'une étape d'un algorithme
%  (ici, choisir quelle pièce rendre), 
% on utilise un critère simple à calculer (ici, la plus grande pièce inférieure
% à la valeur restant à rendre). Pour le problème du choix de l'activité, on
% choisissait la conférence qui se terminait le plus tôt. 

% Ces algorithmes ne donnent pas forcément la solution optimale, ni même une
% solution, selon le problème traité. 


% \begin{ex}
% \begin{enumerate}
% \item Les solutions données dans les exemples 1.1 et 2.1, sont des solutions
%   gloutonnes. 
% \item Dans l'exemple 2.2,
%   avec $S=\{1,3,4\}$ et $v=6$, la solution gloutonne sera $x=(2,0,1)$,
%   donc ne sera pas optimale : $2+1 = 3 > 2$. 
% % \item S'il n'y a plus de pièces de $1$ dans le système usuel,
% %   $S=(2,5,10,20,50)$, et, pour rendre $v=63$, l'algorithme glouton 
% \end{enumerate}
% \end{ex}


% \begin{exo}[algorithme glouton]\label{TDdynExoGlout}
% Dans cet exercice, on se donne un ensemble de pièces \lstinline{S} avec lequel
% on cherche à rendre une somme $v$.
% \begin{enumerate}
% \item Écrire une fonction \lstinline{maximum(L,borne)} qui retourne le maximum
%   des éléments de la liste \lstinline{L} inférieurs ou égaux à
%   \lstinline{borne}. 
% \item Écrire en python un algorithme \lstinline{renduGlouton(v, S)} qui
%   prend en entrée une valeur entière \lstinline{v} et un tuple \lstinline{S},
%   et retourne  
% une liste \lstinline{L} de longueur \lstinline{len(S)} telle que
% \[v = \sum_{i=0}^{n-1} S[i] \times L[i] \qquad \text{où } 
% n=\text{\lstinline{len(L)}}\]
% On utilisera un algorithme glouton, de préférence récursif. Testez sur les
% exemples donnés ci-dessus.
% \item Êtes-vous certain que votre programme se termine ? Trouver un exemple de
%   $S$ et $v$ tel que l'algorithme glouton n'arrive pas à rendre la monnaie,
%   alors que le problème de rendu de monnaie a une solution. Corriger votre
%   algorithme au besoin.
% \item Proposer une version de l'algorithme qui retourne 
%  un dictionnaire \lstinline{d} de clefs contenues dans \lstinline{S}, au lieu de la liste
%  \lstinline{L}, tel que 
% \[v=\sum_{s\in d.keys()} d[s]\times s \]
% \item (bonus) Proposer une version itérative de l'un des deux algorithmes
%   ci-dessus.
% \end{enumerate}
% \end{exo}



% \subsection{Version dynamique}

% Cherchons désormais une solution optimale au problème de rendu de monnaie.

% Il s'agit dans le cas général d'un problème NP-complet (en particulier, on
% pense qu'il n'existe pas d'algorithme de complexité polynomiale en $n$
% permettant de le résoudre).

% Vous allez coder un algorithme qui teste toutes les décompositions possibles
% de $v$.

% Le principe consiste à parcourir les valeurs possibles $s$ des pièces
% utilisables -- donc inférieures à $v$ -- et à rappeler la fonction pour rendre
% la valeur $v-s$. 

% Pour ne pas tester deux fois le même rendu (pour rendre $7$,
% $5$ puis $2$ ou $2$ puis $5$), $s$ devra aussi être inférieur ou égal à la plus
% petite pièce utilisée.

% Structure de données : on utilisera un dictionnaire comme dans l'exercice
% \ref{TDdynExoGlout}. 

% \begin{exo}[Version dynamique]
% ~\\\vspace{-1cm}
% \begin{enumerate}
% \item 
%   Écrire en python un algorithme \lstinline{rendusAf(v, S)} qui prend en
% entrée  
% une valeur entière \lstinline{v} et un tuple \lstinline{S}, et affiche
%  tous les rendus possibles pour la somme $v$, sous forme de dictionnaires
%  \lstinline{d} comme à l'exercice \ref{TDdynExoGlout} :

% \[v=\sum_{s\in d.keys()} d[s]\times s \]
% \item
%   Écrire en python un algorithme \lstinline{rendus(v, S)} qui prend en
% entrée  
% une valeur entière \lstinline{v} et un tuple \lstinline{S}, et retourne 
% la liste de tous les rendus possibles pour la somme $v$ comme ci-dessus. %,  sous forme d'une
% % liste de dictionnaires \lstinline{d} de clefs contenues dans
% % \lstinline{S} 
% % tels que  
% % \[v=\sum_{s\in d.keys()} d[s]\times s \]
% On veillera à éviter de calculer plusieurs fois la décomposition d'une même
% somme $w$.
% \end{enumerate}
% \end{exo}


%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: FeuilleProgrammationDynamique1_2022
%%% End:
