\chapter{Programmation\\orientée objet,\\programmation dynamique}

\section{Programmation orientée objet (POO)}

\begin{exointro}{\null}
On considère une classe \texttt{Personnage} représentant un personnage de jeu.

Le plateau du jeu est représenté par un repère orthonormé à trois axes. La position du joueur dans le plateau est repérée par ses attributs x, y et z.

\'Ecrire les méthodes \texttt{avance}, \texttt{droite} et \texttt{saute} permettant respectivement de faire avancer, aller à droite et sauter le personnage, c'est-à-dire d'augmenter de 1 respectivement x, y et z.

Implémenter de plus une autre méthode \texttt{coord} renvoyant les coordonnées sous forme d'un triplet.
\end{exointro}

\begin{problematique}
Comment modéliser des éléments du monde réel sous forme d'objets informatiques afin de les manipuler de manière simple ?
\end{problematique}

\subsection{Historique et définitions}

La \textit{programmation orientée objet} (en abrégé : POO) est un paradigme de programmation qui consiste à considérer un programme comme un ensemble d'objets en interaction.

Les \textit{objets} peuvent représenter un concept du monde réel (comme un meuble, une personne ou encore un livre par exemple).

Pour faire de la POO, on peut utiliser un \textit{langage à classes}, comme Python.

\Par

La POO trouve son origine en Norvège au début des années 1960. Elle fut élaborée par les informaticiens Ole-Johan Dahl et Kristen Nygaard.

Dans les années 1970, elle fut reprise par l'informaticien américain Alan Kay qui contribua à son essor. Cependant, il fallu attendre les années 1990 pour que ses principes soient clairement formalisés.

\nathanlive{video}{Retrouvez une présentation originale de la programmation orientée objet en vidéo avec Nathan Live.}
\label{video:ch4}

\subsection{Les classes sous Python}

\subsubsection{Introduction}

Nous allons considérer un objet \texttt{Individu} qui représente une personne.

Cette personne a plusieurs caractéristiques. Par exemple:
\begin{itemize}
\item sa date de naissance;
\item son genre;
\item sa taille;
\item sa masse;
\item etc.
\end{itemize}

qui vont représenter les \textit{variables} de la personne.

De plus, cette personne peut faire plusieurs choses:
\begin{itemize}
\item parler;
\item manger;
\item marcher;
\item etc.
\end{itemize}

qui vont correspondre à des \textit{fonctions} propres à elle-même.

\Par

Pour définir cette personne ainsi que les fonctions qui lui sont associées, on peut définir une \textit{classe}.

\subsubsection{Définitions et vocabulaire}

\begin{defin}
\index{Classe!Définition}
Une \textit{classe} est une entité informatique qui définit en son sein:
\begin{itemize}
\item  des variables membres (appelées \textit{attributs});
\item des fonctions membres (appelées \textit{méthodes}).
\end{itemize}
\end{defin}

\newpage

\begin{Exemple}
voici  un exemple en Python où l'on définit une classe \texttt{Personne} à l'aide de trois caractéristiques (année de naissance, taille en cm, masse en kg) et où l'on définit une fonction propre à la classe (grandir) qui\linebreak admet un paramètre numérique (exprimé en cm).

\Par

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

\Par

Ce programme affiche :

\Par\Par

{
\ttfamily
Luc pèse 69 kg.

Luc mesure à présent 186 cm après avoir grandi de 8 cm en\linebreak 1 an. Avant ça, il mesurait: 178 cm.
}
\end{Exemple}

\begin{defins}
\index{Classe!Attribut}
\index{Classe!Méthode}
Dans l'exemple précédent,
\begin{itemize}
\item \texttt{birthyear}, \texttt{tall} et \texttt{weight} sont appelées des \textit{attributs} de la classe \texttt{Personne};
\item \texttt{grandir} est appelée une \textit{méthode} de la classe \texttt{Personne}.
\end{itemize}
\end{defins}

\Par

On accède aux attributs d'une classe à l'aide de la syntaxe:

\begin{center}
\ttfamily
<nom de la classe>.<nom de l'attribut>
\end{center}

\Par

On accède aux méthodes d'une classe à l'aide de la syntaxe:
\begin{center}
\ttfamily
\mbox{<nom classe>.<nom méthode>(<arguments potentiels>)}
\end{center}

\newpage

\subsubsection{Constructeur d'une classe}
\index{POO!Constructeur}
\index{Constructeur (d'une classe)}

\vspace*{-1em}
\begin{defin}
Le \textit{constructeur} d'une classe est une fonction:
\begin{itemize}
\item dont le nom est nécessairement \texttt{\_\_init\_\_};
\item admettant au moins un paramètre nommé \texttt{self} placé obligatoirement en premier s'il y en a plusieurs.
\end{itemize}
\end{defin}

Le paramètre \texttt{self} représente l'objet cible : c'est une variable qui contient une référence vers l'objet qui est en cours de création. Grâce à ce dernier, on va pouvoir accéder aux attributs et fonctionnalités de l'objet cible.

\subsubsection{Instanciation et variables d'instance}
\index{POO!Instanciation}
\index{Instanciation (POO)}
\index{Variables d'instances (classe)}

Une classe est une sorte de moule qui sert à fabriquer des objets. 

L'\textit{instanciation} est l'opération qui consiste à créer un objet. L'objet ainsi créé est alors appelé une \textit{instance} de la classe.

\begin{Exemple}
si on reprend la classe \texttt{Personne} de l'exemple précédent, en définissant :
\begin{center}
\texttt{luc = Personne(2002,178,69)}
\end{center}
nous avons défini une instance de la classe \texttt{Personne}.
\end{Exemple}

On peut ainsi définir plusieurs instances d'une même classe, chacune ayant des attributs qui lui sont propres.

\Par

Si on demande d'afficher la variable \texttt{luc}, on voit apparaître quelque chose de la forme:
\begin{center}
\ttfamily
<\_\_main\_\_.Personne object at 0x02CDDC50>
\end{center}

Cela signifie que \texttt{luc} est une référence vers l'objet créé, c'est-à-dire une indication sur son emplacement en mémoire. Ici, par exemple, l'objet \texttt{Personne} se trouve en mémoire à la position 
0x02CDDC50.

\Par

Un attribut de la classe est représenté par une variable appelée \textit{variable d'instance}, accessible à l'aide du paramètre \texttt{self}. L'idée, dans notre exemple, est que le constructeur initialise ces variables d'instances, qui seront alors stockées dans l'objet et en mémoire pour toute la durée de vie de l'objet. 

Il est important de faire la différence entre les deux types de variables qui se trouvent dans le code de ce constructeur :\enlargethispage*{3em}
\begin{itemize}
\item la variable \texttt{self.tall} (par exemple) représente la variable d'instance, c'est-à-dire celle associée à l'objet, qui existe à partir de la création de l'objet jusque sa destruction;
\item la variable \texttt{tall} représente le paramètre reçu par le constructeur et n'existe que dans le corps de ce dernier.
\end{itemize}
Le paramètre \texttt{self} permet donc d'accéder aux variables d'instance, c'est-à-dire aux attributs de l'objet cible, depuis le constructeur.

\subsubsection{Méthodes d'une classe}
\index{Méthode (d'une classe)}
\index{POO!Méthode}

\begin{defin}
Une \textit{méthode} d'une classe est une fonction définie au sein de la classe et admettant au moins le paramètre \texttt{self} (obligatoirement en premier s'il y a plusieurs paramètres).
\end{defin}

Le paramètre \texttt{self} représente l'objet cible sur lequel la méthode est appelée. Il permet notamment d'avoir accès aux variables d'instance de l'objet.

Dans l'exemple précédent, \texttt{grandir(self,h)} est une méthode admettant deux paramètres, dont le second est un nombre. Cette méthode redéfinit la variable d'instance \texttt{self.tall} en lui ajoutant la valeur passée en second paramètre.

\Par

Une méthode est appelée en spécifiant l'objet cible (ici, \texttt{luc}) suivi de la méthode en utilisant l'opérateur d'appel : le point. Cela donne ici:
\begin{center}
luc.grandir(8)
\end{center}



\subsubsection{Redéfinition des opérations}

Maintenant que l'on sait définir un objet à l'aide d'une classe, on peut s'intéresser aux opérations que l'on peut faire sur ces objets. 

Par exemple, si on souhaite définir un objet \texttt{vector} représentant un vecteur du plan, il serait utile de pouvoir définir la somme de deux de ces vecteurs, qui est aussi un objet de classe \texttt{vector} (car la somme de deux vecteurs du plan est aussi un vecteur du plan).

Python permet de définir une telle opération de la manière suivante:


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

\Par

En mode console, cela donne par exemple :

\Par

{\ttfamily
\pychevrons u , v = vector(-2,8) , vector(3,-5)

\pychevrons w = u + v

\pychevrons print("w(\{\},\{\})".format(w.x,w.y))

w(1,3)
}

\Par

Cette capacité du langage Python s'appelle la \textit{surcharge d'opérateur}. 

% suppression pour gagner des pages.....
%Le tableau suivant présente les différents opérateurs qu'il est possible de\linebreak surcharger, avec le nom de la méthode à utiliser.

%\Par


%\begin{figure}\begin{center}\renewcommand{\arraystretch}{2}\begin{tabular}{|Zc|>{\ttfamily}Zc|>{\ttfamily}Zc|}\tabulartitle\hlineOpérateur	& Notation &	Méthode à définir\\\hlineSigne positif	&+	& \_\_pos\_\_\\\hlineSigne négatif	& - &	\_\_neg\_\_\\\hlineAddition&	+	&\_\_add\_\_\\\hlineSoustraction&	-	&\_\_sub\_\_\\\hlineMultiplication&	*&	\_\_mul\_\_\\\hlineDivision&	/&	\_\_truediv\_\_\\\hlineExponentiation&	**&	\_\_pow\_\_\\\hlineDivision entière&	//&	\_\_floordiv\_\_\\\hlineReste de la division entière&	\%&	\_\_mod\_\_\\\hlineÉgal&	==&	\_\_eq\_\_\\\hlineDifférent&	!=&	\_\_ne\_\_\\\hlineStrictement plus petit&	<&	\_\_lt\_\_\\\hlinePlus petit ou égal&	<=&	\_\_le\_\_\\\hlineStrictement plus grand&	>&	\_\_gt\_\_\\\hlinePlus grand ou égal&	>=&	\_\_ge\_\_\\\hline« non » logique	&not&	\_\_not\_\_\\\hline« et » logique&	and&	\_\_and\_\_\\\hline« ou » logique	&or&	\_\_or\_\_\\\hline\end{tabular}\tabcaption{Liste des différents opérateurs}\end{center}\end{figure}

\newpage

\subsubsection{Encapsulation}

La classe \texttt{vector} définie précédemment aurait pu être définie autrement :

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

\Par

On est passé de deux variables d'instance à une seule, mais cette différence ne doit pas être perçue par l'utilisateur.trice : la manière  dont on gère les valeurs passées en paramètres au sein de la classe ne doit pas être vue \og de l'extérieur \fg. Ce principe fondamental de la POO est appelé \textit{encapsulation}.

\Par

\textit{Voir QCM \ref{04-qcm1} page \pageref{04-qcm1} et exercices \ref{exo:04-piece} à \ref{exo:04-autre-classe-polynome} pages \pageref{exo:04-piece} à \pageref{exo:04-autre-classe-polynome}.}



\begin{solintro}
Une définition possible de la classe \texttt{Personnage} est la suivante:
\begin{listing}{}{04-04.py}\end{listing}

\Par

En utilisant le code, voici ce que donne un exemple d'utilisation :

\hrulefill

{\ttfamily

\pychevrons Lara = Personnnage(0,0,0)\\
\pychevrons Lara.avance()\\
\pychevrons Lara.saute()\\
\pychevrons Lara.coord()\\
(1,0,1)
}
\end{solintro}

\section{Programmation dynamique}
\index{Programmation dynamique}

\begin{exointro}{\null}
Étant donné un système de monnaie $S$ comportant des pièces de valeurs\linebreak différentes, écrire un programme qui affiche le nombre \textit{minimal} de pièces à utiliser pour rendre une somme donnée, ainsi que leur énumération.
\end{exointro}

\subsection{Introduction}

Il s'agit d'un problème d'optimisation, puisqu'on veut utiliser un nombre de pièces et de billets minimal. A travers l'étude de ce problème d'algorithmique classique, nous allons voir qu'il existe de multiples possibilités d'y répondre. La programmation dynamique est la plus efficace.

\subsection{Approche gloutonne}

C'est l'approche que font bon nombre de commerçants quand il rendent la\linebreak monnaie à leurs clients.

Elle consiste à prendre le billet ou la pièce de valeur maximale en dessous de la somme à restituer, puis à recommencer ce geste par rapport à la différence. Cela donne l'algorithme suivant :

\begin{algorithme}{}
V $\leftarrow$ valeur à atteindre
Tant que V n'est pas nulle:
\quad Choisir le billet ou la pièce de plus grande valeur $v_i$
\quad telle que $v_i \leqslant$ V
\quad V $\leftarrow$ V - $v_i$
Fin du Tant que
\end{algorithme}

\begin{Exemple}
comment rendre la somme de 14 \euro{} dans un système monétaire européen simplifié constitué uniquement de pièces de 1, 2, 5 et 10 \euro{} ?
\end{Exemple}
On a alors $S =  \{1; 2; 5; 10\}$.

\Par

Pour rendre 14 \euro{}, la plus grande valeur possible à déduire est 10 \euro, ce qui donne $14-10 = 4$.

La plus grande valeur possible à déduire de 4 \euro{} est $2\times2$~\euro{}, ce qui donne\linebreak $4-2\times2 = 0$.

\newpage

La solution renvoyée par notre algorithme est donc le quadruplet $(0; 2; 0; 1)$, soit un total de 3 pièces. Les autres possibilités sont :

\begin{itemize}
\item $(0; 2; 2; 0)$, soit 4 pièces,
\item $(0; 7; 0; 0)$, soit 7 pièces,
\item $(14; 0; 0; 0)$, soit 14 pièces.
\end{itemize}

L'algorithme glouton a ici donné  la solution optimale. Mais cela ne serait pas forcément le cas pour d'autres systèmes.

Imaginons en effet un système composé uniquement de pièces de 1, 7 et 9 \euro, c'est-à-dire que $S = \{1; 7; 9\}$.

L'algorithme glouton nous amène à la solution $(5;0;1)$, soit un rendu de 6 pièces. Alors que la solution optimale est $(0; 2; 0)$, soit seulement 2 pièces.

\Par

\textit{Conclusion} : l'algorithme glouton a le mérite d'être simple, mais il ne rend pas toujours la solution optimale. Il ne convient donc pas à la résolution de notre problème.

\subsection{Approche récursive \og diviser pour régner \fg}
\index{Diviser pour régner}

Notons à présent $S = \{v_1; v_2; \ldots ; v_n\}$, $v_i$ étant les valeurs des $n$ pièces ou billets composant notre système monétaire $S$,  et $V$ la somme à rendre.

Nous allons calculer le nombre minimal de pièces à rendre que nous noterons \texttt{minimum}. Il servira ensuite à déterminer le $n$-uplet optimal recherché. La méthode précédente suggère de prendre une approche récursive.

\begin{itemize}
\item Si $V=0$, on retourne \og 0 \fg... Logique !

\item Sinon, on fixe la valeur de la variable \texttt{minimum} (qui représentera au final le plus petit nombre de pièces) délibérément à une valeur assez grande (de toute\linebreak évidence, le nombre de pièces est inférieur à la somme totale, donc fixer \texttt{minimum} à \texttt{V+1} nous assure que les valeurs de \texttt{minimum} qui seront calculées par la suite seront inférieures).

\item On parcourt le système monétaire \texttt{S} et pour chaque valeur \texttt{S[i]}, on teste si elle est inférieure ou égale à \texttt{V}; si tel est le cas, on prend en compte la valeur \texttt{S[i]} et on ajoute le nombre minimum de pièces ou billets nécessaires pour atteindre la valeur \texttt{V - S[i]}. Si la valeur obtenue est plus petite que \texttt{minimum} alors cela signifie que l'on a trouvé une combinaison plus optimale que les précédentes et on change la valeur de la variable \texttt{minimum} pour la valeur de \texttt{n}.

\item Une fois que l'on a parcouru le système monétaire, on retourne la valeur de \texttt{minimum}, qui correspond au plus petit nombre possible de pièces et de billets.
\end{itemize}
\enlargethispage*{5em}
le script page ci-contre est de type \og diviser pour régner \fg, puisque nous avons ramené le calcul du nombre recherché pour le montant $V$ au même calcul pour des montants inférieurs ($V-\text{piece1},\ V-\text{piece2},\ \text{etc.})$. Nous avons divisé le problème initial, puis appliqué un traitement récursif.  Notons cependant que pour cela, de nombreux calculs redondants ont été effectués. Cet algorithme n'est donc pas optimisé.

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


\subsection{Approche dynamique Top Down}
\index{Top Down}
\index{Programmation dynamique!Top Down}

Nous allons améliorer l'algorithme précédent en mémorisant dans une liste nommée \texttt{L} les calculs effectués à chaque étape. \texttt{L} est une liste unidimensionnelle de ($V+1$) éléments qui va contenir le nombre de pièces minimal \texttt{L[v]} que l'on doit utiliser pour rendre la monnaie, pour chaque montant \texttt{v} compris dans $[0;V]$. Cette liste est construite de manière récursive à partir du montant initial $V$. De cette manière, les redondances de l'algorithme précédent disparaissent et l'algorithme est optimisé. 

C'est ce qu'on appelle l'approche dynamique \textit{Top Down} (de haut en bas).

\begin{defin}[Top Down]
La forme récursive \textit{Top Down} est une technique d'optimisation ayant pour but de diminuer le temps d'exécution d'une fonction récursive en mémorisant (dans une liste par exemple) les valeurs retournées par cette fonction après avoir\linebreak vérifié qu'elles n'existaient pas encore dans la liste.
\end{defin}
Cette technique est aussi appelée \textit{mémoïsation}.\index{Mémoïsation}

\enlargethispage*{4em}

\nathanlive{progmargin}{}%04-06.py
\begin{listing}{}{04-06-1.txt}\end{listing}
\Par
\begin{center}
\textit{(Suite du programme page suivante)}
\end{center}
\newpage
\begin{listing}{}{04-06-2.txt}\end{listing}

\subsection{Approche dynamique Bottom Up}
\index{Bottom Up}
\index{Programmation dynamique!Bottom Up}

Dans cette approche, nous conservons notre liste \texttt{L} qui va être, cette fois, construite de manière itérative, en partant de 0 pour aller jusqu'à $V$. Il n'y a plus d'appel\linebreak récursif comme c'était le cas pour la fonction \texttt{NombreTopDown}.

Cette technique de programmation dynamique est appelée \textit{Bottom Up} (de bas en haut).

\vspace*{-3mm}
\begin{defin}[Bottom Up]
La forme itérative \textit{Bottom Up} est une technique consistant à résoudre des\linebreak problèmes en partant de celui qui a la taille la plus petite et en allant vers celui qui a la taille la plus grande, tout en stockant les résultats de chacun d'eux dans une liste (par exemple).
\end{defin}

Les techniques d'optimisation \og Bottom Up \fg et \og Top Down \fg sont à la base de la programmation dynamique, ce qui nous amène à la définition suivante :

\vspace*{-2mm}
\begin{defin}[programmation dynamique]
La \textit{programmation dynamique} est une méthode de résolution de problèmes\linebreak d'optimisation en scindant le problème en plusieurs sous-problèmes et en\linebreak utilisant l'une des méthodes « Top Down » ou « Bottom Up ».

\Par

Ainsi, la programmation dynamique est un paradigme de programmation complémentaire à « diviser pour régner », ce dernier se révélant inefficace dans certains cas.
\end{defin}

Voici le fonctionnement du programme final.\enlargethispage*{5em}

\begin{itemize}
\item On commence par initialiser deux listes \texttt{L} et \texttt{valeurs}, toutes les deux étant de dimension \texttt{V+1}, \texttt{V} étant la valeur à décomposer, les indices variant de 0 à \texttt{V}.

\texttt{L} est une liste où \texttt{L[x]} contiendra le nombre minimum de pièces et billets qui compose la valeur \texttt{x} (comprise entre 0 et \texttt{V}) tandis que \texttt{valeurs[x]} contiendra l'indice \texttt{i} pour lequel \texttt{S[i]} $\leqslant$ \texttt{x} et pour lequel \texttt{1+L[x-S[i]]} est plus petit ou égal au nombre minimum de pièces et billets nécessaires pour la décomposition de la somme souhaitée.
\newpage
\item On remplit donc \texttt{L} avec la boucle : \texttt{for x in range(1,V+1)}.

\item Dans cette boucle, on commence par initialiser le minimum à \texttt{V+1}; nous sommes ainsi assuré.e.s que le minimum est plus petit que cette valeur.

\item On parcourt ensuite tous les indices \texttt{i} de 0 à \texttt{len(S)}, et on effectue le test \texttt{if (S[i]<=x) and (1+L[x-S[i]]<minimum)} pour déterminer la valeur du nouveau minimum car si ces conditions sont remplies, le minimum devient \texttt{1+L[x-S[i]]}. Dans ce cas, on précise que l'indice à garder est celui sur \linebreak lequel on est : on le stocke dans la variable \texttt{v} pour plus tard.

\item Une fois à l'extérieur du test conditionnel, pour la valeur d'argent \texttt{x} sur laquelle on est, nous stockons le minimum obtenu dans \texttt{L[x]} ainsi que l'indice \texttt{v} obtenu dans \texttt{valeurs[x]}.

\item À la sortie de la boucle itérative sur \texttt{x}, les listes \texttt{L} et \texttt{valeurs} sont ainsi remplies respectivement du minimum de pièces et billets qui composent chaque indice jusqu'à \texttt{V}.

On initialise alors la variable \texttt{x} à \texttt{V} et une liste vide \texttt{R}, qui contiendra le rendu de monnaie, donc la décomposition.

\item Pour remplir la liste \texttt{R}, il suffit de soustraire à \texttt{x} la valeur que l'on y insère, et cette valeur correspond à \texttt{S[valeurs[x]]}.

\item On finit par retourner \texttt{L[V]}, à savoir le nombre minimum de pièces et billets nécessaires pour décomposer \texttt{V}, ainsi que la liste \texttt{R} nouvellement obtenue.
\end{itemize}


Le programme qui suit affiche \texttt{(2, [7, 7])}, qui représente bien la solution à notre problème :

\begin{itemize}
\item la solution optimale est composée de 2 pièces ;
\item l'énumération des pièces à utiliser pour un montant de 14 \euro{} est : (7 \euro{}, 7 \euro).
\end{itemize}

\textit{Voir exercice \ref{04-vf2} page \pageref{04-vf2} et exercices \ref{exo:04-coefbinom} à \ref{exo:04-sacados} pages \pageref{exo:04-coefbinom} à \pageref{exo:04-sacados}. }

\begin{solintro}
\nathanlive[11mm]{progmargin}{}%04-07.py
\begin{listing}{}{04-07-1.txt}\end{listing}
\Break
\begin{listing}{}{04-07-2.txt}\end{listing}
\end{solintro}


\begin{aretenir}[principaux types de programmation]
\begin{tabular}{|Z{m{28mm}}|Z{m{42mm}}|Z{m{25mm}}|}
\tabulartitle\hline
\centering\arraybackslash
Désignation &
\centering\arraybackslash
Description &
\centering\arraybackslash 
Compléments \\
\hline
Programmation\newline impérative & Suites d'instructions\newline exécutées par la machine. & Programmation intuitive.\\
\hline
Programmation fonctionnelle & \'Evite les effets de bords. & Pas de variables\newline globales.\\
\hline
Diviser pour régner & Découpe un problème en\newline plusieurs sous-problèmes. & Utilisation de la\newline récursivité.\\
\hline
Programmation Orientée Objet\newline(POO) & Considère un programme comme une collection\newline d'objets en interaction. & Utilisation de\newline classes.\\
\hline
Programmation\newline dynamique & Optimise un programme en temps et en mémoire. & Utilisation de la forme récursive \textit{Top Down} ou de la forme itérative \textit{Bottom Up}.\\
\hline
\end{tabular}
\end{aretenir}


\newpage

