\thumb

\begin{qcm}{Vérification de connaissances}{10}
\label{04-qcm1}
Pour chacune des questions suivantes, plusieurs propositions de réponses sont faites dont une seule est correcte. Laquelle ?

\begin{questions}
\item On définit la classe \texttt{identite} de la manière suivante :

\begin{listing}{}{04-ex01.py}
\end{listing}

\Par

Si on tape :

\Par

{\ttfamily
\pychevrons hugo = identite('Hugo' , 'Dupont' , 1999)\\
\pychevrons print( hugo.age(2020) )
}

\Par

que s'affiche-t-il ?

\Par

\begin{tabularx}{\linewidth}{@{}XXXX@{}}
\choix 'Hugo' & 
\choix 'Dupont' &
\choix 1999 &
\choix 21
\end{tabularx}

\item On définit la classe \texttt{voiture} de la manière suivante :

\begin{listing}{}{04-ex02.py}
\end{listing}

\Par

Si on tape :

\Par

{\ttfamily
\pychevrons F430 = voiture('Ferrari' , 'Rouge' , 43)\\
\pychevrons print(F430.nc())
}

\Par

que s'affiche-t-il ?\resetchoix

\Par

\begin{tabularx}{\linewidth}{@{}XX@{}}
\choix 'Ferrari Rouge'
&
\choix Une erreur
\end{tabularx}

\newpage

\item Qu'affiche le programme suivant ?\resetchoix

\begin{listing}{}{04-ex03.py}\end{listing}

\Par

\begin{tabularx}{\linewidth}{@{}XXX@{}}
\choix Une erreur
&
\choix True
&
\choix False
\end{tabularx}

\end{questions}
\end{qcm}

\begin{corrige}
\begin{questions}
\item Réponse \choix[d]. En effet, la méthode calcule la différence entre la valeur de l'argument \texttt{a} et la valeur de \texttt{self.an}, qui correspond à l'année (sans doute de naissance) de Hugo. Il s'agit donc ici de $2020-1999=21$.

\item Réponse \choix[b]. En effet, dans la déclaration de la méthode \texttt{nc}, les\linebreak variables \texttt{nom} et \texttt{couleur} ne sont pas définies. Il aurait fallu écrire\linebreak \texttt{self.nom + self.couleur} pour que cela soit correct.

Rappelons que la déclaration d'une méthode peut faire appel:

\begin{itemize}
\item à des variables locales (qui doivent être initialisées avant utilisation et qui sont \og détruites \fg{} à la fin de la méthode);

\item à des attributs de l'objet lui-même qui  \og appartiennent \fg{} à l'objet, qui sont partagés entre toutes les méthodes, et qui subsistent en mémoire jusqu'à ce que l'objet lui-même soit détruit. Dans ce cas, il faut y faire référence en utilisant le paramètre \texttt{self}, qui est le premier argument de toute méthode.
\end{itemize}

\item Réponse \choix[b]. Ici, tout est correctement défini. Ainsi, la méthode\linebreak \texttt{is}\verb+_+\texttt{square} regarde si $a^2+b^2$ est bien égal à $c^2$, ce qui est le cas pour notre exemple. \og True \fg{}  est donc affiché.
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%

\begin{vf}{Vérification des connaissances}{10} % titre , temps
\label{04-vf2}
Les affirmations suivantes sont-elles vraies ou fausses ? Justifier la réponse.

\begin{questions}
\item \textit{La programmation dynamique.}
\begin{questions}
\item La mémoïsation est une forme itérative.

\item La programmation dynamique consiste à résoudre des problèmes, de celui qui a la taille la plus petite vers celui qui a la taille la plus grande.

\item Un problème d'optimisation où la variable peut être réelle peut être résolu en utilisant la programmation dynamique.

\item Le problème du rendu de monnaie est un problème classique qui ne peut être résolu que par programmation dynamique.
\end{questions}

\item \textit{La Programmation Orientée Objet (POO).}

\begin{questions}
\item Les variables d'une classe sont appelées des \textit{méthodes}.

\item Dans une classe, la définition d'une méthode \verb+_+\verb+_+\texttt{init}\verb+_+\verb+_+ n'est pas obligatoire.
\end{questions}
\end{questions}
\end{vf}

\begin{corrige}
\begin{questions}
\item \textit{La programmation dynamique.}

\begin{questions}
\item \textit{Faux}. La mémoïsation, ou Top Down, est une forme récursive.

\item \textit{Faux}. La technique décrite dans la question est celle du Bottom Up. La programmation dynamique, quant à elle, consiste à découper un problème en plusieurs sous-problèmes de tailles inférieures et en utilisant l'une des techniques Bottom Up ou Top Down pour les résoudre.

\item \textit{Faux}. La programmation dynamique ne sert que lorsque la variable est entière.

\item \textit{Faux}. Nous avons vu dans le cours qu'il existait d'autres façons que la programmation dynamique pour résoudre le problème du rendu de monnaie, comme l'approche gloutonne ou diviser pour régner. Cependant, la programmation dynamique a pour objectif d'optimiser le code. C'est donc cette technique qui est préférable aux autres car elle nécessite moins d'opérations de calcul et de traitement que les autres.
\end{questions}

\item \textit{La Programmation Orientée Objet (POO).}

\begin{questions}
\item \textit{Faux}. Une \textit{méthode} est une \textit{fonction} d'une classe. Les \textit{attributs} sont les variables de la classe.

\item \textit{Vrai}. On peut tout à fait définir une classe sans la méthode \verb+_+\verb+_+\texttt{init}\verb+_+\verb+_+. En voici un exemple :
\begin{listing}{}{04-ex04.txt}\end{listing}
\Par
qui renvoie \og 50 \fg.

Le constructeur \_\_\texttt{init}\_\_ est rendu obligatoire dès lors qu'un paramètre est passé lors de l'appel de la classe (par exemple,\linebreak \texttt{d = toto(7)}) ou qu'il est nécessaire d'initialiser certains attributs dès la création de l'objet.
\end{questions}

\end{questions}
\end{corrige}

\newpage

\sectionnn{Classes}


%%%%%%%%%%%%%%%%

\begin{exo}{La classe \og Piece \fg}{\null}{1}{5} 
\label{exo:04-piece}
Voici un programme en Python :

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex05.py}
\end{listing}

\Par

Expliquez en détail ce qu'il permet d'afficher.
\end{exo}

\begin{corrige}
La classe \texttt{Piece} est composée de deux méthodes.

\begin{itemize}
\item La méthode \texttt{alea} retourne simplement un nombre aléatoire de l'ensemble $\{0;1\}$.

\item La méthode \texttt{moyenne}, qui admet un attribut \texttt{n}, commence par définir une liste vide nommée \texttt{tirage}. Ensuite, une boucle itérative est créée, pour 100 itérations. Au cours de chacune d'elles, on insère dans la liste \texttt{tirage} le retour de la méthode \texttt{alea} (on insère donc \og 0 \fg{} ou \og 1 \fg{} $n$ fois).

Une fois la boucle finie, on retourne la valeur de \og \texttt{sum(tirage) / n} \fg, c'est-à-dire la somme des nombres contenus dans la liste \texttt{tirage} divisée par $n$ : il s'agit ici du calcul du nombre moyen de \og 1 \fg{} obtenus lors des $n$ choix aléatoires.
\end{itemize}

Ainsi, dans ce contexte, si on décide d'associer \og Pile \fg{} à \og 1 \fg{} lors du\linebreak lancer d'une pièce, le programme calcule le nombre moyen de \og Pile \fg{} sur 100 lancers.
\end{corrige}


%%%%%%%%%%%%%%%

\begin{exo}{\'Ecrire une classe}{\null}{1}{10} 
\textit{Pour chacune des questions suivantes, un constructeur initialisant les\linebreak mesures devra être présent dans chacune des classes.}
\enlargethispage*{3em}
\begin{questions}
\item \'Ecrire une classe nommée \texttt{Carre} admettant la mesure des côtés d'un carré en attribut, avec deux méthodes:
\begin{itemize}
\item une méthode \texttt{perimetre} permettant de retourner le périmètre du carré;
\item une méthode \texttt{aire} permettant de retourner son aire.
\end{itemize}


\item \'Ecrire une classe \texttt{Triangle} représentant un triangle et admettant la mesure des trois côtés comme attributs, avec deux méthodes :
\begin{itemize}
\item une méthode \texttt{aire} renvoyant l'aire du triangle à l'aide de la formule de Héron : 
\[
\mathcal{A}=\sqrt{p(p-a)(p-b)(p-c)},
\]
où $a$, $b$ et $c$ sont les longueurs des trois côtés et où $p=\dfrac{a+b+c}{2}$;
\item une méthode \texttt{rect} qui renvoie \texttt{True} si le triangle est rectangle, et \texttt{False} sinon.
\end{itemize}

\item Définir alors un carré de côté 5, puis afficher son aire et son périmètre. Définir ensuite un triangle de côtés 5.4, 9 et 7.2 pour afficher son aire et regarder s'il est rectangle.
\end{questions}
\end{exo}

\begin{corrige}
\enlargethispage*{4em}
\begin{questions}
\item ~\par\vspace*{-17pt}\nathanlive[13mm]{progmargin}{}
\begin{listing}{}{04-ex06.py}\end{listing}

\newpage

\item  Une classe possible est la suivante:

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex07.py}\end{listing}

\item Définissons dans une console le carré et le triangle demandés.

\Par

\hrulefill

{\ttfamily
\pychevrons C = Carre(5)\\
\pychevrons C.aire() , C.perimetre()\\
(25, 20)\\
\pychevrons T = Triangle(5.4 , 9 , 7.2)\\
\pychevrons (T.aire() , T.rect())\\
(19.44000000000001, True)
}

\hrulefill

\Par

On voit ainsi que le triangle défini est rectangle et que son aire vaut $19,44$.


\begin{Remarque}
on pourrait améliorer légèrement l'affichage dans le cas où le triangle est rectangle.
\end{Remarque}

\Par


En effet, dans ce cas précis, pour \mbox{calculer} l'aire du triangle, on peut utiliser la formule $\dfrac{b \times h}{2}$, où $b$ et $h$ sont respectivement une base du triangle et la hauteur relative à cette base.

Ainsi, dans la méthode \texttt{aire}, on pourrait écrire le code page ci-contre.

\begin{aretenir}
Quel que soit le contexte d'un programme, il ne faut pas s'éloigner de ses règles. Si le programme concerne des mathématiques alors il faut utiliser les propriétés mathématiques pour optimiser le code.
\end{aretenir}

\newpage

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex08.py}\end{listing}
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%
\newpage
\begin{exo}{Devinette et remplissage}{\null}{1}{10} 
On considère la classe \texttt{mystere} définie de la manière suivante:

\nathanlive{progmargin}{}%04-ex09.py
\begin{listing}{}{04-ex09.txt}\end{listing}

\begin{questions}
\item Que fait le programme suivant ?
\begin{listing}{}{04-ex10.py}\end{listing}

\item Ajoutez à cette classe une méthode  \texttt{ecc} qui crée et renvoie  une liste dont les éléments sont les cumuls de ceux de l'attribut \texttt{Liste} de la classe.

Par exemple, si \texttt{Liste = [1,2,4,5]}, \texttt{ecc} doit retourner: 
\begin{center}
\texttt{[1, 3 ,7, 12]}.
\end{center}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item \texttt{L.Liste} est \textit{a priori} une liste (d'après la ligne : \texttt{self.Liste = [ ]}).

Ainsi, l'affichage sera une liste. Regardons maintenant de plus près la définition de la fonction \texttt{add}:

\begin{itemize}
\item avant tout, si l'argument \texttt{x} est supérieur ou égal au dernier élément de la liste ou si la liste est vide, on ajoute la valeur de \texttt{x} à la liste;

\item sinon, si \texttt{x} contient une valeur strictement plus petite que le premier élément de la liste, on place la valeur de \texttt{x} en tête de la liste;

\item dans les autres cas, on parcourt la liste et on teste si la valeur contenue dans \texttt{x} est comprise entre deux valeurs de la liste. Si tel est le cas, on insère cette valeur entre les deux autres valeurs.
\end{itemize}

On peut alors dire que la fonction \texttt{add} ajoute la valeur de l'argument tout en faisant en sorte que la liste soit rangée dans l'ordre croissant.

\Par\enlargethispage*{2em}

Ainsi, le programme proposé affichera :
\Par
\begin{center}
\texttt{[7, 10, 50, 78, 89]}
\end{center}

\item Voici une proposition pour la méthode \texttt{ecc}:

\begin{listing}{}{04-ex11.py}\end{listing}

\Par

Ici, on commence par créer une liste \texttt{E} dont le seul élément est le\linebreak premier de la liste \texttt{self.Liste}, puis on parcourt \texttt{self.Liste} à\linebreak partir du deuxième élément : pour chaque nombre d'index \texttt{i}, on lui ajoute \texttt{E[i-1]} et on stocke le résultat à la fin de la liste \texttt{E}, donc dans \texttt{E[i]}.

La boucle terminée, on retourne \texttt{E}, qui est la liste de tous les cumuls.

\begin{Remarque}
en statistiques, on appelle ces nombres les \textit{effectifs cumulés croissants}.
\end{Remarque}
\end{questions}

\nathanlive{prog}{Téléchargez le programme complet.} %04-ex12.py
\end{corrige}



%%%%%%%%%%%%%%%%%%%

\begin{exo}{La classe \og Complexe \fg}{\null}{1}{20} 
En mathématiques, dans un plan rapporté à un repère orthonormé $(O;\vec{u},\vec{v})$, tout point $M$ de coordonnées $(x;y)$ peut être représenté par ce que l'on nomme un \textit{nombre complexe}, qui peut s'écrire sous la forme:
\[
z = x + \text{i}y.
\]
%(voir figure page suivante).

On dit que $x$ est la \textit{partie réelle} de $z$ et $y$, sa \textit{partie imaginaire}.

\newpage

%\begin{figure}\begin{center}\includegraphics{03-ex-complexe}\figcaption{Représentation d'un nombre complexe dans un repère}\end{center}\end{figure}

En posant $z = x + \text{i}y$ et $z' = x' + \text{i}y$, on définit alors les opérations suivantes:
\begin{itemize}
\item $z + z' = (x+x') + \text{i}(y+y')$
\item $z-z' = (x-x')+\text{i}(y-y')$
\item $z \times z' = (xx'-yy') + \text{i}(xy' + x'y)$
\end{itemize}

De plus, on dit que $z=z'$ si $x=x'$ et $y=y'$.

\'Ecrire en Python une classe \texttt{complexe}:
\begin{itemize}
\item qui définit un nombre complexe (le constructeur devra initialiser un tuple de deux nombres : la partie réelle et la partie imaginaire;

\item ayant une méthode permettant d'afficher le nombre complexe sous forme d'un tuple de deux éléments;

\item permettant d'ajouter, soustraire, multiplier et comparer (en terme d'égalité) deux nombres complexes;

\item permettant de donner la distance de l'origine du repère au point représenté par le nombre complexe (on appelle cette distance le \textit{module}, qui est égal à $\sqrt{x^2+y^2}$.
\end{itemize}

Tester cette classe avec les nombres :
\[
z = -3 + 5\text{i}\qquad\text{et}\qquad z' = 7 + \text{i}.
\]
\end{exo}

\begin{corrige}
Voici une classe possible :

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex13.py}\end{listing}

\Par

En testant avec les nombres $z = -3 + 5\text{i}$ et $z' = 7 + \text{i}$, cela donne :

\Par

\hrulefill

{\ttfamily

\pychevrons z , v = complexe(-3,5) , complexe(7,1)

\pychevrons print("{} + {} = {}".format(z.nombre() , v.nombre() , 

\phantom{\pychevrons}(z+v).nombre() ) )

(-3, 5) + (7, 1) = (4, 6)

\pychevrons print("{} - {} = {}".format(z.nombre() , v.nombre() , 

\phantom{\pychevrons}(z-v).nombre() ) )

(-3, 5) - (7, 1) = (-10, 4)

\pychevrons print("{} * {} = {}".format(z.nombre() , v.nombre() , 

\phantom{\pychevrons}(z*v).nombre() ) )

(-3, 5) * (7, 1) = (-26, 32)

\pychevrons print("Le module de {} est {}".format( z.nombre() , 

\phantom{\pychevrons}z.module() ) )

Le module de (-3, 5) est 5.830951894845301

\pychevrons print("{} est-il égal à {} ? {}".format(z.nombre() , 

\phantom{\pychevrons}v.nombre() , z == v))

(-3, 5) est-il égal à (7, 1) ? False
}

\hrulefill
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2 étoiles


\begin{exo}{Une classe \og Polynôme \fg}{\null}{2}{20} 
\index{Classe!Polynôme}
\index{Karatsuba (algorithme de)}
\label{exo:polynomekaratsuba}
En s'inspirant du corrigé de l'exercice \ref{prog:algo-karatsuba} page \pageref{prog:algo-karatsuba} sur l'algorithme de\linebreak Karatsuba, écrire en Python une classe \texttt{Polynome} permettant de faire une addition, une soustraction, une division de deux polynômes.

On écrira de plus  une méthode \texttt{affiche} permettant d'afficher un polynôme.
\end{exo}

\begin{corrige}
Voyons étape par étape la construction d'une telle classe:

\begin{itemize}
\item Le constructeur.

\begin{listing}{}{04-ex14.txt}\end{listing}

\Par

On initialise ici une liste  : celle des coefficients informés en paramètre.

\item La méthode \texttt{affiche}.

\begin{listing}{}{04-ex15.txt}\end{listing}

\newpage

On commence par initialiser une chaîne de caractères \texttt{r} par le premier coefficient (transformé pour l'occasion en chaîne de caractères avec la fonction \texttt{str}) et en lui adjoignant un espace à la fin.

On parcourt ensuite tous les degrés possibles pour chaque terme du polynôme, donc de 1 jusqu'au degré maximal. Pour chaque degré différent de 1, on définit l'affichage de l'exposant par \og \verb+^+ \fg  suivi du degré. Pour le cas où l'exposant est 1, on n'affiche rien (car $X^1 = X$).

Si le coefficient est négatif, on ajoute à \texttt{r} ce coefficient (avec le signe \og $-$ \fg) suivi de \og X\verb+^+ degré \fg; si le coefficient est positif, il faut penser à ajouter un \og $+$ \fg{} avant le \og X \fg.


Nous avons choisi de clore cette méthode par un affichage de \texttt{r}, mais on aurait pu simplement retourner sa valeur.



\item La méthode \texttt{standardise}.

\begin{listing}{}{04-ex16.txt}\end{listing}

\Par

Dans cette méthode, on complète la liste des coefficients des deux polynômes la plus courte pour qu'elle ait une longueur égale à la plus grande : on ajoute donc à la liste la plus courte autant de \og 0 \fg{} que nécessaire (la différence entre les deux degrés des polynômes).

\item Somme et différence de deux polynômes.

\begin{listing}{}{04-ex17.txt}\end{listing}

\Par

Dans les deux méthodes, on standardise les deux polynômes afin de\linebreak pouvoir ajouter (ou soustraire) les éléments d'indice \texttt{i} des deux listes. Il est à noter ici la présence de l'astérisque devant les listes ainsi obtenues : cela permet de transformer les listes en énumérations convenables.
\newpage
En effet, \texttt{Polynome([1,2,3])} n'est pas la bonne syntaxe pour définir un polynôme; il faut donc transformer \texttt{[1,2,3]} en tuple \texttt{1,2,3}. On appelle cela l'\textit{unpacking}.

\item Produit de deux polynômes.

\begin{listing}{}{04-ex18.txt}\end{listing}

\Par

Afin de pouvoir utiliser l'algorithme de Karatsuba, nous devons définir une méthode \texttt{prodmonome} qui se charge de multiplier un polynôme par $X^k$, puis nous pouvons définir le produit en utilisant les formules de\linebreak l'algorithme.
\end{itemize}
 

Ainsi, avec $P(X)=1+2X+3X^2$ et $Q(X) = 4+5X+6X^2$, on obtient :

\hrulefill

{\ttfamily

\pychevrons P , Q = Polynome(1,2,3) , Polynome(4,5,6)

\pychevrons (P*Q).affiche()

4 + 13X + 28X\verb+^+2 + 27X\verb+^+3 + 18X\verb+^+4 
}

\hrulefill

\nathanlive{prog}{Télécharger la classe complète}%04-ex181.py
\end{corrige}


%%%%%%%%%%% 

\begin{exo}{La classe \og Temps \fg}{\null}{2}{25} 
\index{Classe!Temps}
En Python, écrire une classe \texttt{Temps} qui permet de définir un horaire au format $\rm hh:mm:ss$ et qui admet les méthodes suivantes:
\begin{itemize}
\item \texttt{affiche}, qui affiche l'horaire au format \og 12 h 37 min 45 s \fg;

\item \_\_\texttt{add}\_\_, qui ajoute deux horaires de la classe \texttt{Temps};

\item \_\_\texttt{sub}\_\_, qui calcule la différence entre deux horaires de la classe \texttt{Temps}.
\end{itemize}
\end{exo}

\begin{corrige}
Une définition de la classe \texttt{Temps} est donnée page suivante.
\Par

Avec cette définition, voici ce que l'on peut obtenir:\enlargethispage*{4em}

\hrulefill\\
\texttt{\pychevrons t1, t2 = Temps(8,45,37), Temps(15,31,18)}\\
\texttt{\pychevrons (t1+t2).affiche(), (t1-t2).affiche()}\\
\texttt{'24 h 16 min 55 s' , '6 h 45 min 41 s'}

\hrulefill

\newpage

\nathanlive{progmargin}{}%3-ex10.py
\begin{listing}{}{04-ex19.py}\end{listing}
\end{corrige}


%%%%%%%%%

\begin{exo}{La classe \og Fraction \fg}{\null}{2}{25} 
\index{Classe!Fraction}
En Python, écrire une classe \texttt{Fraction} qui vérifie les instructions page suivante.
\newpage

\hrulefill

{\ttfamily
\pychevrons x = Fraction(12,9)\\
\pychevrons x.num\\
12\\
\pychevrons x.denom\\
9\\
\pychevrons x = Fraction(12,9).simplify()\\
\pychevrons x.num , x.denom\\
4,3\\
\pychevrons y = Fraction(48,36)\\
\pychevrons x == y\\
True}

\hrulefill

\Par

\textit{Aides : }
\begin{itemize}
\item pour la simplification de fraction, on s'appuiera sur le résultat\linebreak mathématique suivant :
\[
\text{fraction : }\dfrac{a}{b} \longrightarrow \text{ fraction simplifiée : }\dfrac{a\div\PGCD(a;b)}{b\div\PGCD(a;b)}
\]

\item on pourra s'aider de l'exercice \ref{exo-calcul-pgcd-recursif} page \pageref{exo-calcul-pgcd-recursif} pour le calcul du PGCD;

\item pour redéfinir le test d'égalité, on pourra redéfinir de façon interne à la classe la méthode \verb+_+\verb+_+\texttt{eq}\verb+_+\verb+_+.
\end{itemize}
\end{exo}

\begin{corrige}
\enlargethispage*{5em}
%Voici une définition possible pour cette classe.

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex20.py}\end{listing}
\end{corrige}


%%%%%%%%%%% 

\begin{exo}{La classe \og Vecteur \fg}{\null}{2}{30} 
\index{Classe!Vecteur}
En Python, écrire une classe \texttt{Vecteur} admettant trois attributs (ses\linebreak coordonnées dans l'espace) comportant :
\begin{itemize}
\item une méthode permettant d'afficher les coordonnées du vecteur sous la forme $(x;y;z)$;

\item une méthode renvoyant le vecteur somme de deux vecteurs (en\linebreak redéfinissant \verb+_+\verb+_+\texttt{add}\verb+_+\verb+_+);

\item une méthode renvoyant la norme du vecteur;

\item une méthode renvoyant le produit scalaire de deux vecteurs;

\item une méthode permettant de vérifier si un vecteur est colinéaire à un autre (passé en attribut);


\item une méthode permettant de vérifier si un vecteur est orthogonal à un autre (passé en attribut).
\end{itemize}
\end{exo}

\begin{corrige}
Une définition de la classe \texttt{Vecteur} est la suivante.

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex21.py}\end{listing}


\Par

Avec cette classe, on peut par exemple obtenir :

\Par

\hrulefill

\texttt{\pychevrons u, v = Vecteur(-1,2,1) ,  Vecteur(3,5,-7)}\\
\texttt{\pychevrons u.affiche(), (u+v).affiche()}\\
\texttt{'(-1;2;1)' , '(2;7;-6)'}\\
\texttt{\pychevrons u.norme()}\\
\texttt{2.449489742783178}\\
\texttt{\pychevrons u.is}\verb+_+\texttt{ortho(v)}\\
\texttt{True}\\
\texttt{\pychevrons u.is}\verb+_+\texttt{colin(v)}\\
\texttt{False}

\hrulefill
\end{corrige}


%%%%%%%%%%%
\newpage
\begin{exo}{La classe \og SerieStat \fg }{\null}{2}{30} 
\enlargethispage*{\baselineskip}
\'Ecrire en Python une classe \texttt{SerieStat} remplissant le cahier des charges suivant:
\begin{itemize}
\item un objet de cette classe est un tableau statistique comportant les caractères étudiés ainsi que leur effectif. Il sera implémenté à travers un dictionnaire;

\item une méthode \texttt{affiche} qui affiche toutes les valeurs de la série;

\item une méthode \texttt{moyenne} permettra de calculer la moyenne de cette série;

\item une méthode \texttt{var} permettra de calculer la variance de la série;

\item une méthode \texttt{ecart} permettra de calculer son écart-type.
\end{itemize}
\end{exo}

\begin{corrige}
Pour les calculs, il est nécessaire de faire quelques rappels mathématiques.

$(x_i;n_i)$ désigne la série statistique à $N$ éléments.

\begin{itemize}
\begin{multicols}{2}
\item $\bar{x} = \dfrac{\displaystyle\sum_{i=1}^N x_i \times n_i}{\displaystyle\sum_{i=1}^N n_i}$ (moyenne)

\item $V = \dfrac{\displaystyle\sum_{i=1}^N (x_i - \bar{x})^2 \times n_i}{\displaystyle\sum_{i=1}^N n_i}$ (variance)
\end{multicols}

\item $\sigma = \sqrt{V}$ (écart-type)
\end{itemize}


\begin{Remarque}
la variance est donc la moyenne de la série initiale dans\linebreak laquelle nous avons remplacé $x_i$ par $(x_i-\bar{x})^2$... Cela va nous intéresser pour l'implémentation.
\end{Remarque}
\nathanlive{progmargin}{}
\begin{listing}{}{04-ex22.py}\end{listing}

\begin{methode}
\texttt{zip(C,E)} permet de créer une association entre les éléments \texttt{i} des listes \texttt{C} et \texttt{E}. Pour mettre ces associations sous forme de dictionnaire, nous avons utilisé la fonction \texttt{dict}.
\end{methode}

Nous pouvons regarder ce que cela donne à travers un exemple.

\newpage

\hrulefill
{\ttfamily

\pychevrons from random import randint\\
\pychevrons C = range(21)\\
\pychevrons E = [randint(0,20) for i in C]\\
\pychevrons serie = SerieStat(C,E)\\
\pychevrons serie.affiche()\\
S'affiche ici le dictionnaire\\
\pychevrons print('Moyenne : ',serie.moyenne())\\
Moyenne : 8.401041666666666\\
\pychevrons print('Variance : ',serie.var())\\
Variance :  33.21937391493056\\
\pychevrons print('Ecart-type : ',serie.ecart())\\
Ecart-type :  5.76362506717175
}

\hrulefill
\end{corrige}


%%%%%%%%%%%%%%%%%

\begin{exo}{Classes \og Mot \fg et \og Phrase \fg}{\null}{2}{30} 
On considère la classe \texttt{Mot} définie ainsi:

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex23.py}\end{listing}
\enlargethispage*{4em}
\begin{questions}
\item Indiquer ce que fait la fonction \texttt{fctA()} définie par :
\begin{listing}{}{04-ex24.txt}\end{listing}

\item Indiquer ce que fait la fonction \texttt{fctB()} définie par :
\begin{listing}{}{04-ex25.txt}\end{listing}
\end{questions}

On souhaite écrire une classe \texttt{Phrase}. Toutes les questions suivantes porteront sur cette classe.

\begin{questions}
\setcounter{enumi}{2}
\item \'Ecrire un constructeur qui définit une liste \texttt{self.mots} remplie de tous les mots de la phrase passée en paramètre, chacun des mots devant être de classe \texttt{Mot}.

\item \'Ecrire deux méthodes \texttt{doReverse} et \texttt{value} telles que la fonction \texttt{fctC()} suivante :
\begin{listing}{}{04-ex26.txt}\end{listing}
\Par
affiche : 
\begin{center}
\og mortels sont hommes les Tous \fg
\end{center}

\item \'Ecrire une méthode \texttt{doShuffle} afin que la fonction suivante:
\begin{listing}{}{04-ex27.txt}\end{listing}
\Par
affiche les mots de la phrase \og Tous les hommes sont mortels \fg{} dans un ordre aléatoire.

\item On définit la méthode \texttt{motAt} de la manière suivante:
\begin{listing}{}{04-ex28.txt}\end{listing}
\Par
Que fait la fonction \texttt{fctE()} suivante ?
\begin{listing}{}{04-ex29.txt}\end{listing}

\item On définit la méthode \texttt{insert} de la manière suivante:
\begin{listing}{}{04-ex30.txt}\end{listing}
\Par
Que fait la fonction \texttt{fctF()} suivante ?
\begin{listing}{}{04-ex31.txt}\end{listing}

\item On définit la méthode \texttt{remove} de la manière suivante:
\begin{listing}{}{04-ex32.txt}\end{listing}
\Par
Que fait la fonction \texttt{fctG()} suivante ?
\begin{listing}{}{04-ex33.txt}\end{listing}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\enlargethispage*{3em}
\item L'instruction \og \texttt{m = Mot("Socrate")} \fg{} définit dans un premier temps un objet \texttt{Mot} comme étant la chaîne de caractères \og Socrate \fg. 

Ensuite, \og \texttt{m.doReverse()} \fg{} fait appel à la méthode \texttt{doReverse} de la classe \texttt{Mot} qui, comme son nom l'indique, transforme la chaîne de caractères en inversant les lettres. 

Enfin, \og \texttt{print(m.value())} \fg{} affiche ce qui est contenu dans \texttt{self.m} de la classe \texttt{Mot}, donc affiche ici : \og etarcoS \fg{} (le mot écrit à l'envers).

\item Comme dans la fonction précédente, on commence par définir un\linebreak objet de classe \og Mot \fg, puis on fait appel à la méthode \texttt{doShuffle} qui retourne une anagramme du mot.

La fonction \texttt{fctB()} affiche donc une anagramme de \og Socrate \fg.

\item Un constructeur possible est le suivant :

\begin{listing}{}{04-ex34.txt}\end{listing}

\Par

On commence par définir une liste \texttt{L} composée de tous les mots de la phrase passée en paramètre avec la méthode \texttt{split} : à ce stade, les mots se sont que des chaînes de caractères. Or, nous souhaitons que chaque mot soit de classe \texttt{Mot}. On parcourt alors cette liste et, à partir de chaque item, on définit un objet de classe \texttt{Mot} que l'on insère dans une liste \texttt{self.mots} (\og self \fg{} est indispensable pour lier cette nouvelle liste à l'objet de classe \texttt{Phrase} ainsi défini).

\item Une proposition de méthodes est la suivante:
\begin{listing}{}{04-ex35.txt}\end{listing}
\Par
Dans la méthode \texttt{doReverse}, nous n'avons fait qu'inverser l'ordre des items de la liste \texttt{self.mots} avec l'opération \texttt{[::-1]}, et dans la\linebreak méthode \texttt{value}, nous avons initialisé une chaîne de caractères \texttt{result} comme étant vide, puis parcouru chaque item de la liste \texttt{self.mots} pour concaténer à \texttt{result} la chaîne de caractères correspondant à l'item (\texttt{m.value()}) en y ajoutant un espace afin qu'au final, \texttt{result}\linebreak représente la phrase.

\item Ici, nous pouvons utiliser à nouveau la fonction \texttt{shuffle} du module \texttt{random}, ce qui donne:
\begin{listing}{}{04-ex36.txt}\end{listing}

\item Dans la fonction \texttt{fctE()}, on commence par définir une phrase, puis un mot \texttt{m} comme étant l'objet \texttt{Mot} en position 3 dans la phrase définie. Ici, il s'agit donc de \og sont \fg{} (attention : le premier mot est à la position 0, comme dans toute liste). Ensuite, on applique la méthode \texttt{doReverse} de la classe \texttt{Mot} au mot ainsi trouvé, ce qui a pour effet de mettre ses lettres dans le sens inverse.

On affiche ensuite la phrase ainsi obtenue, ce qui donne :

\Par

\begin{center}
Tous les hommes tnos mortels
\end{center}

\item Dans la fonction \texttt{fctE()}, on commence par définir une phrase, puis on fait appel à la méthode \texttt{insert} qui insère le mot \og ne \fg{} dans la phrase en position 3, c'est-à-dire après le 3\ieme{} mot de la phrase. On fait de même en position 5, c'est-à-dire après le 5\ieme{} mot : on y insère le mot \og pas \fg. Et enfin, on affiche la phrase ainsi obtenue, ce qui donne:

\Par

\begin{center}
Tous les hommes ne sont pas mortels
\end{center}

\item On commence par prendre le mot en position 4 dans la phrase, donc \og 
mortels \fg. On mélange ensuite les lettres dans ce mot en faisant appel à la méthode \texttt{doShuffle} de la classe \texttt{Mot}. Ensuite, on fait appel à la méthode \texttt{remove} de la classe \texttt{Phrase} en passant en paramètre le nombre 2 : on supprime alors le mot \og hommes \fg. Enfin, on insère en position 2 le contenu de la variable \texttt{m}, c'est-à-dire l'anagramme de \og mortels \fg{} obtenu précédemment. On affiche alors le résultat, ce qui donne par exemple:

\Par

\begin{center}
Tous les elmsort sont elmsort
\end{center}
\vspace*{-4mm}
\begin{Remarque}
le dernier mot n'est plus \og mortels \fg; en effet, nous avons définit \texttt{m} comme l'objet en position 4 dans l'objet \texttt{p}. Dès lors que l'on écrit \texttt{m.doShuffle}, cet objet est modifié dans l'objet \texttt{p}. Ainsi, à ce stade, l'objet \og mortels \fg{} n'existe plus mais il est remplacé par une anagramme de la chaîne de caractères qu'il représente.
\end{Remarque}
\nathanlive{prog}{Télécharger le programme complet.}% 04-ex361.py
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%

\begin{exo}{Une autre classe \og polynôme \fg}{\null}{3}{30} 
\label{exo:04-autre-classe-polynome}
\index{Classe!Polynôme}
Dans cet exercice, on se propose de construire une classe nommée \texttt{polynome} représentant un polynôme, c'est-à-dire une expression de la forme:
\[
a_0 + a_1X + a_2X^2 + \cdots + a_n X^n.
\]
Dans cet exemple, $n$ est appelé le \textit{degré} du polynôme, et $(a_0,a_1,\ldots,a_n)$ sont ses coefficients.

Les termes $a_k X^k$ (pour $0 \leqslant k \leqslant n$) de l'expression sont appelés des\linebreak \textit{monômes}.

On souhaite pouvoir ajouter, soustraire et multiplier deux polynômes à l'aide de la classe \texttt{polynome}.

Pour faciliter le travail, nous allons devoir créer une deuxième classe nommée \texttt{monome} permettant de définir un monôme avec son coefficient et son degré.

\begin{questions}
\item \textit{La classe \texttt{monome}}.
\begin{itemize}
\item \'Ecrire le constructeur de la classe \texttt{monome} qui permet d'initialiser les variables d'instance \texttt{coef} et \texttt{deg}.

Par exemple, \texttt{monome(5,2)} devra représenter le monôme $5X^2$.

\item \'Ecrire une méthode \texttt{affiche} qui retourne un affichage correct du\linebreak monôme. On devra notamment éviter les affichages :
\begin{itemize}
\item[$\to$] \og 1X\verb+^+1\fg, lui préférant \og X \fg,
\item[$\to$] \og 3X\verb+^+0 \fg, lui préférant \og 3 \fg,
\item[$\to$]  ou encore \og 0X\verb+^+2 \fg, auquel cas on ne doit rien afficher.
\end{itemize}

\item \'Ecrire ensuite trois méthodes \_\_\texttt{add}\_\_, \_\_\texttt{sub}\_\_  et \_\_\texttt{mul}\_\_ permettant respectivement d'ajouter deux monômes de même degré, de soustraire deux monômes de même degré et de multiplier deux monômes entre eux.

Pour rappel,  
\begin{itemize}
\item[$\to$] $5X^2 + 3X^2 = (5+3)X^2$,
\item[$\to$] $(5X^2) \times (3X^4) = (5\times3)X^{2+4}$.
\end{itemize}
\end{itemize}

\item \textit{La classe \texttt{polynome}}.
\begin{itemize}
\item \'Ecrire le constructeur de la classe \texttt{polynome} qui permet d'initialiser une variable d'instance \texttt{ListeMonomes}, liste de tous les monômes composant le polynôme, du monôme de plus bas degré à celui de plus haut degré.

Par exemple, \texttt{polynome(3,-2,0,1)} devra représenter le polynôme $3 - 2X + 0X^2 + X^3$.

\textit{Aide :} le constructeur devra être de la forme \_\_\texttt{init\_\_(self,*args)}, dans lequel \texttt{args} sera la liste de tous les coefficients.

\item \'Ecrire une méthode \texttt{affiche} retournant une chaîne de caractères correspondant à l'affichage du polynôme. On veillera à éviter l'affichage \og $+1+X+\cdots$ \fg{} (par exemple), lui préférant \og $1+X+\cdots$ \fg{} (car le premier signe n'est pas nécessaire à l'affichage si le premier coefficient est positif).

\item \'Ecrire une méthode \texttt{standardise} qui retourne deux polynômes ayant le même nombre de monômes.

Par exemple, \texttt{P.standardise(Q)} devra retourner \texttt{P} et \texttt{Q} de sorte que \texttt{P.ListeMonomes} et \texttt{Q.ListeMonomes} sont deux listes de même\linebreak longueur.

\item \'Ecrire alors trois méthodes \_\_\texttt{add}\_\_, \_\_\texttt{sub}\_\_  et \_\_\texttt{mul}\_\_ permettant respectivement d'ajouter, de soustraire et de multiplier deux polynômes entre eux.

\textit{Aide :} pour le produit de deux polynômes, il faudra penser à la distributivité (produit de monômes) et à la réduction (somme de monômes).
\end{itemize}

\item \textit{Test de la classe.}

Tester la classe \texttt{polynome} avec les deux polynômes suivants:
\[
P(X) = 1+2X+3X^2\qquad\text{et}\qquad Q(X)=-2+5X+7X^3
\]
en les ajoutant, soustrayant et multipliant.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item \textit{La classe \texttt{monome}}.
\begin{itemize}
\item Le constructeur.
\begin{listing}{}{04-ex37.txt}\end{listing}
\Par
On initialise les deux variables d'instance demandées : \texttt{coef} (le coefficient du monôme) et \texttt{deg} (pour le degré du monôme).
\enlargethispage*{3em}

\item La méthode \texttt{affiche}.

\begin{listing}{}{04-ex38.txt}\end{listing}

\newpage

On commence par initialiser une chaîne de caractères vide \texttt{aff} (qui contiendra l'affichage souhaité). Pour que l'affichage soit correct, on fait d'abord la différence entre un monôme de degré 0, 1 et supérieur. Ensuite, on regarde le coefficient : s'il est strictement négatif, on\linebreak l'affiche avec son signe; s'il est positif mais différent de 1, on ajoute le signe \og $+$ \fg{} avant le coefficient et s'il est égal à 1, on affiche un \og $+$ \fg{} sans le coefficient.

\Par

Remarquez qu'il n'y a pas la condition \og \texttt{self.coef == 0} \fg{} car dans ce cas, il ne faut rien afficher, donc on laisse la variable \texttt{aff} vide.


\Par

\item Les opérations (addition, soustraction, multiplication).
\Par
Pour l'addition et la soustraction, on commence par vérifier que les degrés des deux monômes sont égaux car on souhaite que ces méthodes portent sur deux monômes de mêmes degrés.

On définit alors le résultat comme le monôme dont le coefficient est la somme ou la différence des coefficients des deux monômes ajoutés ou soustraits, et dont le degré est le degré des monômes (on rappelle que l'on a : $aX^p + bX^p = (a + b)X^{p}$). 

Quant au produit, il est définit par le monôme dont le coefficient est le produit des coefficients des monômes et dont le degré est la somme des degrés des monômes ($aX^p \times bX^q = (a \times b) X^{p+q}$).

\begin{listing}{}{04-ex39.txt}\end{listing}
\end{itemize}

\item \textit{La classe \texttt{polynome}}.

\begin{itemize}
\item Le constructeur.

\begin{listing}{}{04-ex40.txt}\end{listing}

\Par

Nous avons utilisé ici une syntaxe concise pour construire la liste\linebreak demandée : cette liste est composée de tous les monômes\linebreak (\texttt{monome( args[d] , d )}) pour tout degré \texttt{d} compris entre 0 et la longueur de la liste \texttt{args} (longueur qui correspond au degré du\linebreak polynôme).

\item La méthode \texttt{affiche}.

\begin{listing}{}{04-ex41.txt}\end{listing}

\Par

La variable \texttt{r} est une chaîne de caractère correspondant à l'affichage désiré. Quant à \texttt{prems}, c'est un booléen qui ne sert qu'à supprimer le signe \og $+$ \fg{} devant le premier coefficient s'il est positif.

\item La méthode \texttt{standardise}.

\begin{listing}{}{04-ex42.txt}\end{listing}

\Par

L'idée consiste ici à comparer la longueur des listes \linebreak\texttt{self.ListeMonomes} et \texttt{other.ListeMonomes}, prendre le maximum de ces deux longueurs et de compléter la liste la plus courte par des\linebreak monômes de coefficients 0.

Ensuite, on crée deux listes de coefficients \texttt{P} et \texttt{Q} pour pouvoir définir deux polynômes à partir de ces deux listes et les retourner.

\item La somme de deux polynômes.

\begin{listing}{}{04-ex43.txt}\end{listing}

\Par

On commence pas standardiser les polynômes afin de pouvoir effectuer les sommes des différents monômes et mettre les résultats dans une liste \texttt{R}.

On retourne ensuite un polynôme construit à partir des coefficients des monômes de la liste \texttt{R}.

\item La différence de deux polynômes.

\begin{listing}{}{04-ex44.txt}\end{listing}

\Par

Le principe est le même que pour la somme.


\item Le produit de deux polynômes.

On commence par parcourir tous les monômes du premier polynôme et pour chacun d'eux, on parcourt tous ceux du second polynôme afin de les multiplier; on construit ainsi une liste \texttt{R} composée de tous les\linebreak produits des monômes (résultat du développement en utilisant la\linebreak distributivité).

\begin{listing}{}{04-ex45-1.txt}\end{listing}
\begin{center}
\textit{(Suite du script page suivante)}
\end{center}

\newpage

\begin{listing}{}{04-ex45-2.txt}\end{listing}

\Par

On crée ensuite une boucle de variable \texttt{degre} (qui varie de 0 à la somme des degrés des polynômes, car le produit de deux polynômes de degré $n$ et $m$ est un polynôme de degré $n+m$). Pour chacun des degrés, on initialise la variable \texttt{result} comme étant un monôme de coefficient 0 et de degré \texttt{degre}, puis on lui ajoute tous les monômes de même degré; la liste:
\begin{center}
\texttt{[ monome for monome in R if monome.deg == degre ]}
\end{center}
est composée uniquement des monômes dont le degré est égal à la valeur de la variable \texttt{degre}  courante.

Une fois la boucle en \texttt{m} finie, nous avons ajouté tous les monômes de degré \texttt{degre}; nous pouvons alors ajouter ce résultat à la liste \texttt{R}\_\texttt{final}, qui contiendra (au final) tous les monômes composant le produit des polynômes.

On retourne alors le polynôme construit à partir de cette liste (en ne prenant que les coefficients des monômes).
\end{itemize}

\item Avec $P(X) = 1 + 2X + 3X^2$ et $Q(X) = -2 + 5X + 7X^2$, on obtient :

\hrulefill

{\ttfamily
\pychevrons P, Q = polynome(1, 2, 3), polynome(-2, 5, 7)\\
\pychevrons A, S, M = P + Q, P - Q, P * Q\\
\pychevrons print( '(P+Q)(X)={}, (P-Q)(X)={}, (P*Q)(X)={}'.format(\\\phantom{\pychevrons} A.affiche(),S.affiche(),M.affiche() ) )\\
(P+Q)(X)=-1+7X+3X\verb+^+2+7X\verb+^+3,\\
(P-Q)(X)=3-3X+3X\verb+^+2-7X\verb+^+3,\\
(P*Q)(X)=-2+X+4X\verb+^+2+22X\verb+^+3+14X\verb+^+4+21X\verb+^+5
}

\hrulefill
\end{questions}
\Par
\nathanlive{prog}{Téléchargez le programme complet.}%04-ex46.py
%\begin{Remarque}
%deux classes représentant un même objet peuvent ne pas être construites de la même manière. C'est le cas pour la classe \texttt{polynome} que nous venons de voir et celle que nous avons vu dans l'exercice \ref{exo:polynomekaratsuba}. Selon l'angle sous lequel on souhaite voir l'objet, on peut construire une classe plus compliquée à manipuler que celle d'une autre personne. En l'occurrence, il y a fort à parier que la classe de cet exercice paraisse plus simple et plus claire que l'autre pour la plupart d'entre nous.
%\Par
%La POO clarifie la programmation en construisant des classes simples (comme Monome) utilisées par des classes plus complexes (comme Polynome) à la manière de Légos(R) qui viendraient s'emboîter pour construire le programme complet.
%\end{Remarque}
\end{corrige}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\sectionnn{Programmation dynamique}

\begin{exo}{Coefficients binomiaux}{\null}{1}{15} 
\label{exo:04-coefbinom}
Pour tout entier naturel $n$ et pour tout entier naturel $k \leqslant n$, on note $\dbinom{n}{k}$ le nombre d'ensembles de $k$ éléments pris parmi $n$. Une propriété mathématique affirme l'égalité suivante:
\[
\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k} .
\]
De plus, pour tout entier naturel $n$, $\dbinom{n}{0}=\dbinom{n}{n}=1$.

\Par

En utilisant une programmation dynamique, écrire en Python un programme affichant le coefficient binomial $\dbinom{n}{k}$ pour un $n$ et un $k$ donné.

Pour cela, on pourra s'aider du \textit{triangle de Pascal} suivant, permettant de\linebreak visualiser tous les coefficients binomiaux.

\Par\enlargethispage*{\baselineskip}

\begin{center}
\begin{tabular}{|>{\centering\arraybackslash}M{1cm}|*7{Zc|}}
\tabulartitle\hline
\diagbox[width=14mm,height=5mm]{$n$}{\raisebox{1mm}{$k$}} & 0 & 1 & 2 & 3  &4 & 5 & 6\\
\hline
0 & 1 & & & & & & \\
\hline
1 & 1 & 1 & & & & & \\
\hline
2 & 1 & 2 & 1 & & & & \\
\hline
3 & 1 & \multicolumn{2}{c|}{\cellcolor{LR}3 {\color{DR}$\xrightarrow{+}$} 3} & 1 & & & \\
\hline
4 & 1 & 4 &\cellcolor{LR} 6\psline[linecolor=DR]{->}(0.1,0.5)(0.1,0.1) & 4 & 1 & & \\
\hline
5 & 1 & 5 & 10 & 10 & 5 & 1 & \\
\hline
6 & 1 & 6 & 15 & 20 & 15 & 6 & 1\\
\hline
\end{tabular}

\textit{Début du triangle de Pascal}
\end{center}
\end{exo}

\begin{corrige}
Pour tout entier naturel $n$, $\dbinom{n}{0}=\dbinom{n}{n}=1$.

Donc $\dbinom{0}{0}=1$, $\dbinom{1}{0}=1$ et $\dbinom{1}{1}=1$.

\Par

Pour l'implémentation, on commence par initialiser un tableau rempli de 0.

Ensuite, on insère les coefficients binomiaux ligne par ligne à l'aide d'une boucle itérative (en $i$):
\begin{itemize}
\item si $i=0$, c'est-à-dire si nous sommes sur la 1\iere{} ligne, on fixe le coefficient à 1;
\item sinon, on parcourt toutes les colonnes de la ligne $i$ : si c'est la 1\iere{} ($p=0$), on fixe le coefficient à 1 et sinon, on calcule le coefficient à l'aide de la formule de récurrence.
\end{itemize}
\nathanlive{progmargin}{}
\begin{listing}{}{04-ex47.py}
\end{listing}
\end{corrige}

%%%%%%%%%%%%%%%%%%

\begin{exo}{Suite de Fibonacci : le retour}{\null}{2}{15}
\label{prog-dyn-suite-fibo} \enlargethispage*{4em}
\index{Fibonacci (suite de)}
Nous avons vu dans la correction de l'exercice \ref{prog-gen-suite-fibo} page \pageref{prog-gen-suite-fibo} que le programme sur la page suivante permettait de calculer tous les termes de la suite de\linebreak Fibonacci $(F_n)$ de $F_0$ à $F_{20}$.

\begin{listing}{}{04-ex48.py}\end{listing}
\Par
Adaptez ce programme à l'aide de la programmation dynamique et de la\linebreak mémoïsation afin de le rendre plus efficace.
\end{exo}

\begin{corrige}
\begin{methode}
La mémoïsation consiste à optimiser un code en mémorisant les différents termes calculés.
\Par
Nous allons donc placer chaque terme calculé dans un tableau afin de pouvoir y faire appel quand on en a besoin. 
\end{methode}

En effet, dans le programme donné, pour calculer $F_{20}$ (par exemple), il faut calculer $F_{19}$ et $F_{18}$. Or, pour calculer $F_{19}$, il faut calculer $F_{18}$ et $F_{17}$. Ainsi, à ce stade, $F_{18}$ est calculé deux fois. 	Et ce n'est rien comparé aux termes d'indices petits, qui sont appelés bien plus souvent pour les termes d'indices supérieurs.

De plus, la complexité de la fonction \texttt{fibo(n)} est ici exponentielle; en effet, elle est égale à $O\big(\varphi^n\big)$, où $\varphi=\dfrac{1+\sqrt5}{2}$ est le \textit{nombre d'or}.

\Par

Cela donne le programme page suivante.

\newpage



\nathanlive{progmargin}{}
\begin{listing}{}{04-ex49.py}\end{listing}

\Par

La fonction \texttt{fibo} ne permet pas de trouver directement le terme de rang $n$. Elle doit être appelée sur chaque terme, depuis le premier jusqu'à $n$, comme ce qui est fait dans l'énoncé, pour compléter progressivement \texttt{F}.

On complète donc \texttt{F} à la demande, seulement si nécessaire, depuis son dernier terme jusqu'au terme de rang $n$ souhaité.


Dans ce dernier programme, la complexité de la fonction \texttt{fibo(n)} est rendue linéaire.
\end{corrige}

%%%%%%%%%%%%%%%%%%

\begin{exo}{Modélisation d'une suite numérique}{\null}{2}{20} 
On considère la suite numérique $(u_n)$ définie par ses deux premiers termes $u_0=1$, $u_1=2$ et par la relation de récurrence suivante:
\[
\forall\; n\in\N,\quad u_{n+2}=\dfrac{u_n}{u_{n+1}}.
\]
\'Ecrire un programme Python permettant de calculer $u_n$ pour un entier $n$ donné en utilisant la programmation dynamique (version Bottom Up et Top Down).
\end{exo}

\begin{corrige}
Une version Bottom Up du programme dynamique est la suivante :
\nathanlive{progmargin}{}
\begin{listing}{Bottom Up}{04-08.py}
\end{listing}

\Par\enlargethispage*{5em}

Une version optimisée (en espace mémoire) est la suivante:

\nathanlive{progmargin}{}%04-09.py
\begin{listing}{Bottom Up (optimisée en espace mémoire)}{04-09.py}\end{listing}
%\begin{listing}{Bottom Up (optimisée en espace mémoire)}%{04-09-1.txt}\end{listing}
%\newpage
%\begin{listing}{}{04-09-2.txt}\end{listing}

\newpage

Une version Top Down est la suivante :

\nathanlive{progmargin}{}
\begin{listing}{Top Down}{04-10.py}\end{listing}

Une manière plus simple peut aussi être envisagée :

\nathanlive{progmargin}{}
\begin{listing}{Top Down}{04-11.py}\end{listing}
\end{corrige}

%%%%%%%%%%%%%%%%%%

\begin{exo}{Somme dans une suite numérique}{\null}{3}{30} 
On définit une suite $(u_n)$ par son premier terme $u_0=1$ et par la relation de récurrence:
\[
\forall n\in\N,\quad u_{n+1}=\dfrac{1}{n+1}\sum_{k=0}^n (k+1) u_k.
\]
\begin{questions}
\item Calculer $u_1$, $u_2$ et $u_3$.
\item Proposer deux programmes permettant de calculer $u_n$ pour tout entier naturel $n$ en utilisant le paradigme de la programmation dynamique\linebreak (version Bottom Up et Top Down).
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Bien que mathématique, et non informatique, cette question permet de comprendre le mode de génération des termes de la suite définie.
\begin{itemize}
\item $\displaystyle u_1 = u_{0+1}=\dfrac{1}{0+1}\sum_{k=0}^0 (k+1)u_k = u_0 = 1$;

\item $\displaystyle u_2 = u_{1+1} = \dfrac{1}{1+1}\sum_{k=0}^1 (k+1) u_k = \dfrac{1}{2}( 1u_0 + 2u_1 ) =  \dfrac{3}{2}$;

\item $\displaystyle\begin{aligned}[t]
u_3 & = u_{2+1}\\
&  = \dfrac{1}{2+1}\displaystyle\sum_{k=0}^2 (k+1) u_k \\
& = \dfrac{1}{3}( 1u_0 + 2u_1 + 3u_2 ) \\
& =  \dfrac{1}{3} \times \left(3+\dfrac{9}{2}\right) = \dfrac{5}{2}.
%ERR NON DETECTEE = \frac{7}{2}.
\end{aligned}$
\end{itemize}

\item La difficulté de ce genre de calcul réside dans la sommation. Il faut\linebreak penser à la stocker au même titre que les termes de la suite.


\nathanlive{progmargin}{}
\begin{listing}{Bottom Up}{04-ex50.py}\end{listing}

\Par

L'idée ici est donc de stocker non pas un terme mais un couple constitué du terme $u_k$ et de la somme $u_0+2u_1+\cdots+(k+1)u_k$ pour pouvoir calculer par la suite $u_{k+1}$.

\Par

\nathanlive{progmargin}{}
\begin{listing}{Top Down}{04-ex51.py}\end{listing}
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Le retour du problème du sac à dos}{\null}{3}{30} 
\label{exo:04-sacados}
\index{Sac à dos (problème du)}
Nous avons vu dans l'exercice \ref{exo:sac-a-dos-1} page \pageref{exo:sac-a-dos-1} ce en quoi consiste le problème du sac à dos. Nous en avons d'ailleurs donné une solution récursive de type \og diviser pour régner \fg.

\begin{questions}
\item Proposer une approche dynamique de type Bottom Up et Top Down de ce problème qui affiche uniquement la valeur maximale des objets.

Vérifier les programmes avec l'exemple où le poids maximal est $P = 10$ et où la collection d'objets est $E = \{ (5,7) ; (3,1) ; (3,4) ; (3,2) \}$.

\item Compléter l'approche Bottom Up (par exemple) afin d'afficher la\linebreak combinaison des objets retenus.

% suppression pour gagner une page
%\item Que dire de la complexité de l'approche Bottom Up par rapport à celle de l'approche récursive initiale ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Rappelons avant tout la fonction récursive initiale du problème : 

\begin{listing}{}{04-ex52.py}\end{listing}

\begin{itemize}
\item \textit{Approche dynamique de type \og Top Down \fg}.

\Par

Pour améliorer cette fonction récursive, il nous faut mémoriser les\linebreak solutions aux sous-problèmes (mémoïsation). Nous allons donc\linebreak stocker les valeurs de \texttt{V[i][p]}, avec $0 \leqslant i \leqslant n$ et $0 \leqslant p \leqslant P$, où $P$ est le poids maximal autorisé, dans une liste nommée par exemple \texttt{temp}.

La solution est très proche de l'initiale.

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex53.py}\end{listing}

\Par

Ce qui donne pour notre exemple:

\hrulefill
{\ttfamily

\pychevrons E, P = [ (5,7) , (3,1) , (3,4) , (3,2) ] , 10

\pychevrons initSac(E,P)

11
}

\hrulefill

\Par 

Cela signifie que la valeur maximale des objets que l'on peut mettre dans le sac est égale à 11 ($7 + 4$, avec un poids de $5+3=8$).

\item \textit{Approche dynamique de type \og Bottom Up \fg}.
\Par
\enlargethispage*{5em}

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex54.py}\end{listing}

\newpage
Avec cette approche, il n'y a plus de récursivité mais une itération.

On garde à peu près la même structure pour la fonction \texttt{sac}.

\Par

On obtient bien entendu le même résultat, à savoir \og 11 \fg.
\end{itemize}

\item Comme nous pouvons le voir ici, ces solutions n'affichent que la valeur optimale. Le problème du sac à dos étant d'obtenir la combinaison des objets retenus, il nous faut compléter ces solutions.

Si on complète l'approche Bottom up, cela donne le programme suivant:\enlargethispage*{\baselineskip}

\nathanlive{progmargin}{}
\begin{listing}{}{04-ex55.py} \end{listing}

% suppression pour gagner une page
%\Par

%Ici, on ajoute une liste \texttt{garde} qui stocke le numéro des objets que l'on met dans le sac.


%\item Dans l'approche récursive initiale, la complexité est en $O\big(2^n\big)$. En effet, deux appels récursifs sont fait pour $n$ objets.

%\Par


%Dans l'approche Bottom Up, elle est en $O(n \times P)$ car il y a deux boucles imbriquées portant sur $n$ et $P$, et qu'il y a le même nombre d'opérations élémentaires dans chacune d'elles.

%\begin{attention}
%Il ne faut pas conclure que la complexité est linéaire par rapport à $P$. En effet, la variable \texttt{P} est de taille $\log_2(P)$ et on peut alors écrire que le poids maximal est $P = 2^{\log_2(\texttt{P})}$. La complexité du programme dynamique est alors exponentielle par rapport à la taille de \texttt{P}. 

%Cependant, elle reste meilleure que celle du programme initial.
%\end{attention}
\end{questions}
\end{corrige}















\thumb
\AfficheCorrige
