\thumb

\sectionnn{Programmation fonctionnelle}

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

\begin{exo}{Réécriture}{\null}{1}{5} 
\label{exo:03-reecriture}
Réécrire de façon fonctionnelle le programme suivant:

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

\Par

\begin{Remarque}
la fonction \texttt{hash} renvoie la valeur de hachage d'un objet. Une fonction de hashage produit un condensé des données de l'objet. Ce condensé est de taille fixe, dont la valeur diffère suivant la fonction utilisée.
\end{Remarque} 
\end{exo}

\begin{corrige}
Voici une possibilité:

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

\end{corrige}

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

\begin{exo}{Fonction carré}{\null}{1}{5} 
\'Ecrire en Python de manière fonctionnelle une fonction \texttt{carre(n)} qui affiche sous forme de liste le carré des entiers de 0 à $n$ (compris).
\end{exo}

\begin{corrige}
Une possibilité est la suivante:

\begin{listing}{}{03-ex03.py}\end{listing}
\end{corrige}


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

\begin{exo}{Compteur d'occurrences}{\null}{2}{10} 
À l'aide de la fonction \texttt{reduce} du module \texttt{functools}, écrire en Python une fonction \texttt{compteur(liste,mot)} qui retourne le nombre d'occurrences de la chaîne \texttt{mot} dans la liste \texttt{liste}.
\end{exo}

\begin{corrige}
Une possibilité est la suivante:

\nathanlive{progmargin}{} 
\begin{listing}{}{03-ex04.py}\end{listing}

\Par

Dans cet exemple, le programme retourne \og 3 \fg; ce n'est pas un bug : le\linebreak premier \og Le \fg{} n'est pas compté (car il a une majuscule) mais dans le mot \og poulailler \fg, la chaîne \og le \fg{} apparaît une fois. Il y a donc bien trois\linebreak occurrences de \og le \fg{} dans la liste.
\end{corrige}


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

\begin{exo}{Taille d'une liste}{\null}{2}{10} 
Supposons que la fonction \texttt{len} n'existe pas.

\'Ecrire, en Python et en utilisant le paradigme de la programmation\linebreak fonctionnelle, une fonction récursive \texttt{taille(liste)} admettant une liste comme argument et retournant sa taille.
\end{exo}

\begin{corrige}
\enlargethispage*{4em}
Une première possibilité est la suivante:

\begin{listing}{Version  itérative}{03-ex05.py}
\end{listing}

\newpage

Une deuxième possibilité est, en utilisant la récursivité:

\begin{listing}{Version  fonctionnelle récursive}{03-ex06.py}
\end{listing}
\end{corrige}

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

\begin{exo}{Calcul d'une taille moyenne}{\null}{2}{15} 
On dispose d'une liste de dictionnaires \texttt{gens}:

\Par

{\ttfamily
gens = [\\
\hspace*{1cm} {’nom’: ’Pierre’ , ’taille’: 178},\\
\hspace*{1cm}  {’name’: ’Marie’ , ’taille’: 181},\\
\hspace*{1cm}  {’name’: ’Paul’ , ’taille’: 157}\\
]
}

\Par

\'Ecrire en Python de manière fonctionnelle une fonction \texttt{average(gens)}\linebreak admettant une liste de dictionnaires de la forme décrite précédemment et\linebreak retournant la taille moyenne des personnes figurant dans cette liste.


\textit{Aide :} on utilisera les fonctions :
\begin{center}
\texttt{reduce} et \texttt{filter(fonction,dictionnaire)},
\end{center}
cette dernière fonction renvoyant un dictionnaire contenant tous les éléments du dictionnaire d'origine pour lesquelles \texttt{fonction = True}.

On pourra aussi importer la fonction \texttt{add} du module \texttt{operator} de sorte que \texttt{reduce(add,liste)} retourne la somme des éléments de \texttt{liste}.
\end{exo}

\begin{corrige}
Voici une possibilité :

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

\Par\Par

Ce programme affiche \og 172 \fg, qui correspond à la taille moyenne des trois personnes du dictionnaire.
\newpage
\end{corrige}



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

\begin{exo}{Une fonction \og pipeline\_each \fg}{\null}{3}{10}
\label{exo:03-pipeline} 
On souhaite écrire en Python une fonction \texttt{pipeline}\verb+_+\texttt{each(liste,fonctions)} comme suit:
\begin{itemize}
\item son premier paramètre (\texttt{liste}) reçoit une liste de chaînes de caractères;
\item son second paramètre (\texttt{fonctions}) reçoit une liste d'une ou plusieurs\linebreak fonctions qui, chacune, reçoit une liste de chaînes en argument et y effectue un traitement.
\end{itemize}
La fonction \texttt{pipeline}\verb+_+\texttt{each(liste,fonctions)} doit appliquer, tour à tour, chacune des fonctions de la liste \texttt{fonctions} à la liste de chaînes de caractères \texttt{liste}. Puis elle doit renvoyer cette liste à l'issue des traitements successifs.
\Par

Compléter le programme suivant:

\nathanlive{progmargin}{}
\begin{listing}{}{03-ex08.py}\end{listing}

\Par

afin d'avoir en affichage :

{\ttfamily
['Le Monde Est À Nous;', ' Il Ne Faut Pas Le Détériorer;']
}
\end{exo}

\begin{corrige}
Une solution envisageable est la suivante.

\nathanlive{progmargin}{}
\begin{listing}{}{03-ex09.py}
\end{listing}
\end{corrige}


\sectionnn{Diviser pour régner}

\begin{exo}{Fonction \og maximum \fg{} d'une liste }{\null}{1}{15} 
\label{exo:fct-max-liste}
On dispose d'une liste \texttt{L} de nombres.

En utilisant la méthode du \og diviser pour régner \fg, implémenter une fonction \texttt{maximum(L,debut,fin)} retournant le maximum de \texttt{L}.
\end{exo}

\begin{corrige}
L'idée consiste à diviser en deux la liste \texttt{L} en deux parties et à trouver le maximum des deux parties. Le maximum global sera la plus grande des valeurs ainsi trouvées. On doit partager en deux jusqu'à obtenir des listes élémentaires (à 1 élément). On doit alors utiliser la récursivité.

Une fonction possible est alors la suivante :

\nathanlive{progmargin}{}
\begin{listing}{}{03-12.py}\end{listing}
\end{corrige}

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

\begin{exo}{Algorithme de Karatsuba}{\null}{3}{30} 
\label{prog:algo-karatsuba}
\index{Karatsuba (algorithme de)}
L'objectif de cet exercice est d'utiliser l'algorithme de Karatsuba afin de\linebreak trouver le produit de deux polynômes $P$ et $Q$.

On rappelle qu'un \textit{polynôme en $X$ de degré $n$} est une expression de la forme :
\[
P(X)=\sum_{k=0}^n a_k X^k.
\]

On représente alors en Python le polynôme $P$ par la liste \texttt{[a0,a1,..,an]} des coefficients $a_0$, $a_1$, ..., $a_n$.

\begin{questions}
\item \'Ecrire une fonction \texttt{standardise(P,Q)} qui retourne un couple de deux listes de dimension $\max\big(\deg(P);\deg(Q)\big)$, où $\deg(P)$ représente le\linebreak degré de $P$.

Par exemple, si $P(X)=3+2X$ et $Q(X)=5-7X+4X^2$ (soit en\linebreak Python : \texttt{P = [3,2]} et \texttt{Q = [5,-7,4]}), la fonction devra retourner:\linebreak \texttt{([3,2,0] , [5,-7,4])}.

\item \'Ecrire une fonction \texttt{add(P,Q)} qui retourne une liste dont les éléments sont les coefficients de la somme des deux polynômes $P$ et $Q$, puis une fonction \texttt{sous(P,Q)} qui retourne sous forme de liste le résultat de $P(X)-Q(X)$.

Par exemple, si $P(X)=3+2X$ et $Q(X)=5-7X+4X^2$ alors :
\begin{itemize}
\item \texttt{add(P,Q) = [8,-5,4]};
\item \texttt{sous(P,Q) = [-2,9,-4]}. 
\end{itemize}

\item L'algorithme de Karatsuba consiste à décomposer $P$ et $Q$ de la manière suivante:
\[
\begin{cases}
P(X) & = X^k P_1(X) + P_0(X),\quad \deg P_0 \leqslant k\\
Q(X) & = X^k Q_1(X) + Q_0(X),\quad \deg Q_0 \leqslant k
\end{cases}
\]
où $k = E\left(\dfrac{n}{2}\right)$ (partie entière de la moitié de \texttt{n}).

\begin{questions}
\item On suppose que:
\begin{align*} 
(PQ)(X) & = (P_0Q_0)(X)\\ 
& + \big( (P_0+P_1)(Q_0+Q_1) - P_0Q_0 - P_1Q_1\big)(X) X^k\\ 
& + (P_1Q_1)(X) X^{2k}.
\end{align*}

\'Ecrire une fonction \texttt{prodmonome(P,k)} qui renvoie sous forme de liste le produit du polynôme $P$ par $X^k$.

\item En déduire une fonction \texttt{prod(P,Q)} qui renvoie sous forme de liste le produit de deux polynômes $P$ et $Q$.\enlargethispage*{3em}

\item Tester cette fonction sur les polynômes:
\[
P(X)=5-2X^4+3X^3-X^2+2X-1 \text{ et }  Q(X)=-3+5X+2X^2.
\]
\end{questions}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Une fonction possible est la suivante:\enlargethispage*{5em}

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

\Par

\item Une fonction possible est la suivante:

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

\item 
\begin{questions}
\item Une fonction possible est la suivante:

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

\Par
En effet,
\[
P(X) X^k = X^k \sum_{i=0}^n a_i X^i = \sum_{i=0}^n a_i X^{i+k} = \sum_{i=k+1}^{n+k} a_{i-k-1} X^{i}. 
\]
Ainsi, $a_0$ n'est plus le coefficient de $X^0$ mais de $X^{0+k}$, $a_1$ est celui de $X^{1+k}$, etc.

\Par

\item  ~\par\vspace*{-7mm}\begin{listing}{}{03-ex13.py}\end{listing}

\item On définit dans cette question P et Q ainsi :

\begin{center}
\texttt{P , Q = [5,-2,3,-1,2,-1] , [-3,5,2]}
\end{center}

En appelant la fonction \texttt{prod}, on obtient la liste :
\begin{center}
\ttfamily [-15, 31, -9, 14, -5, 11, -1, -2, 0, 0, 0]
\end{center}
ce qui signifie que:
\[
PQ(X)=-15+31X-9X^2+14X^3-5X^4+11X^5-X^6-2X^7.
%ERR NON DETECTEE PQ(X)=-15+31X-9X^2+14X^3-5X^4+11X^5-X^6-12X^7.
\]
\end{questions}
\end{questions}

\nathanlive{prog}{Télécharger le programme complet.}%  \texttt{[03-ex14.py]}}
\end{corrige}

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

\begin{exo}{Le problème du sac à dos}{\null}{3}{30} 
\label{exo:sac-a-dos-1}
\index{Sac à dos (problème du)}
On dispose d'un sac à dos ne pouvant supporter qu'un poids $P$. On dispose de plus d'une collection de $n$ objets, chaque objet ayant un poids $p_i$ et une valeur $v_i$, $1 \leqslant i \leqslant n$, avec $p_1+p_2+\cdots+p_n>P$.

On souhaite mettre dans le sac le plus d'objets possible tout en maximisant la valeur totale des objets.

En utilisant une approche récursive \og diviser pour régner \fg, donner une\linebreak solution en Python qui affiche la valeur maximale.

Appliquer le programme au cas où l'ensemble des objets (poids,valeur) est :
\[
E = \{ (12,14) ; (1,2) ; (4,10) ; (1,1) ; (2,2) \}
\]
et où $P = 15$.
\end{exo}

\begin{corrige}
Pour résoudre un tel problème, il faut avant tout passer par une formalisation mathématique : une traduction algébrique.
\begin{itemize}
\item Notons $E = \{ (p_1,v_1) ; \cdots ; (p_n,v_n) \}$ l'ensemble des $n$ objets.
\item La solution attendue sera un $n$-uplet $(x_1;x_2;\ldots;x_n)$ où $x_i=0$ si l'on ne prend pas l'objet $i$ et $x_i=1$ dans le cas contraire.
\item Il faut alors que $\displaystyle\sum_{i=1}^n x_ip_i \leqslant P$ et $\displaystyle\sum_{i=1}^n x_iv_i$ maximale.
\end{itemize}

Nous avons vu dans le livre de Première NSI qu'une approche gloutonne était peu recommandée car dans certains cas, la solution donnée n'est pas optimale.

On nous demande ici une approche récursive de type \og diviser pour régner \fg. Il est alors important dans ce type d'exercices d'établir une formule de\linebreak récurrence. Le raisonnement prend nécessairement en compte le poids et la valeur d'un objet.

Notons $V(i,p)$ la valeur maximale des objets que l'on peut mettre dans un sac de capacité $p$ en ne prenant que les $i$ premiers objets. Ce qui nous intéresse est alors $V(n,P)$. On a alors:
\begin{itemize}
\item $V(0,p)=0$ car s'il n'y a pas d'objet, la valeur maximale est nécessairement 0;
\item Si $p_i > p$ alors $V(i,p)=V(i-1,p)$ car si le poids de l'objet $i$ est supérieure au poids maximal, on ne l'ajoute pas et la valeur maximale des objets reste inchangée par rapport à celle de l'étape précédente;
\item Enfin, si $p_i \leqslant p$ alors $V(i,p)=\max\big( V(i-1,p) ; V(i-1,p-p_i) + v_i \big)$ car il faut regarder la valeur obtenue en ajoutant la valeur de l'objet $i$ ($v_i$) à la valeur maximale correspondant à $i-1$ objets dans un sac de capacité $p-p_i$.
\end{itemize}


Ces relations de récurrence nous mènent alors à l'implémentation suivante :\enlargethispage*{5em}

\nathanlive{progmargin}{}
\begin{listing}{}{03-ex15.py}\end{listing}
\newpage

Cela donne avec notre exemple :

\hrulefill
{\ttfamily

\pychevrons E = [ (12,14) , (1,2) , (4,10) , (1,1) , (2,2) ]

\pychevrons P = 15

\pychevrons initSac(E,P)

18
}

\hrulefill

\og 18 \fg{}  est en effet la valeur maximale que l'on obtient en faisant $14 + 2 + 2$ (objets 1, 2 et 5).
\end{corrige}

\thumb
\AfficheCorrige
