\documentclass{tpcaml}
% \includeversion{prof}
% \excludeversion{eleve}
\includeversion{eleve}
\excludeversion{prof}

\Newassociation{corrige}{Sol}{soltp3sup}
\renewcommand{\Sollabel}[1]{\textbf{\large Exercice #1}}
\Newassociation{corrigese}{Solse}{soltp3sup}
\renewcommand{\Solselabel}[1]{\textbf{\large Sujet d'étude #1}}
\Opensolutionfile{soltp3sup}

\title{TP 3 : diviser pour régner}
\begin{document}

\maketitle

\bigskip
Nous allons rencontrer dans ce TP des situations où la méthode dite
``diviser pour régner'' donne de bons résultats. Rappelons les
principes de cette méthode :
\begin{itemize}
\item \textbf{Diviser} l'objet de taille $N$ en $p$ \emph{sous-objets}
  de taille approximative $n/p$.
\item \textbf{Régner} sur chacun des sous-objets, autrement dit
  résoudre le problème sur chacun des $p$ sous-objets.
\item \textbf{Fusionner} les résultats pour obtenir une solution du
  problème pour l'objet initial.
\end{itemize}
Le plus souvent, on prend $p=2$, mais il pourra parfois être judicieux
de choisir $p$ autrement.
\bigskip
\begin{Ex}[Exponentiation rapide]
  On cherche un moyen de calculer efficacement $x^n$, où $x\in\Z$ (ou
  $\R$) et $n\in\N$.
  \begin{enumerate}
  \item Écrire un programme \texttt{expo\_naif} utilisant la relation :
    $x^0=1,\ \forall n\ge1,\,x^n=x\times x^{n-1}$.
  \item Appliquer la méthode ``diviser pour régner'' pour écrire un
    nouveau programme  \texttt{expo\_dpr}. En prouver la correction.
  \item Comparer les deux algorithmes.
  \item Quel est le nombre minimal de multiplications nécessaires pour
    calculer $x^{15}$ ?
  \item Soit $n=\ovl{b_pb_{p-1}\dots b_0}$ l'écriture décimale de $n$
    avec $b_i=0\text{ ou }1$ et $b_p=1$. Montrer que le nombre de
    multiplications effectuées par l'algorithme ``diviser pour
    régner'' est égal à $p+b_{p-1}+\dots+b_0$. Estimer cette quantité
    en fonction de $n$.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\bigskip
\begin{Ex}[Fibonacci encore et toujours]
  La \emph{suite de Fibonacci} est définie par les relations :
  $$F_0=0,\ F_1=1\quad{et}\quad \forall n\ge1,\ F_{n+1}=F_n+F_{n-1}$$
  \begin{enumerate}
  \item Écrire un programme \texttt{fibo\_naif} utilisant cette
    définition tel que \texttt{fibo\_naif n} renvoie $F_n$, et
    expliquer pourquoi cet algorithme est inefficace.
  \item On note $u_n=F_n$ et $v_n=F_{n+1}$. Remarquer que les deux
    suites $(u_n)$ et $(v_n)$ vérifient les relations de récurrence :
    $$u_0=0,\ v_0=1\text{ et }\forall n\ge0,\,
    \begin{systeme}
      u_{n+1}=v_n\\ v_{n+1}=u_n+v_n
    \end{systeme}$$
    Écrire un programme utilisant cette nouvelle relation. Quel est la
    complexité de ce programme ?
  \item Démontrer la relation : $\forall n,p\ge1,\ 
    F_{n+p}=F_nF_p+F_{n-1}F_{p-1}$. En déduire un algorithme de calcul
    de $F_n$ selon la méthode ``diviser pour régner'', et estimer sa
    complexité.
  \item Comparer les efficacités temporelles et spatiales de ces
    différents programmes.
  \end{enumerate}
  \begin{corrige}
    
  \end{corrige}
\end{Ex}
\newpage
\begin{Ex}[Multiplication de polynômes]
  Soit $P(x)=a_0+a_1x+\dots+a_px^p$ et $Q(x)=b_0+b_1x+\dots+b_qx^q$
  deux polynômes donnés par leurs coefficients (entiers, réels...)
  dont on veut calculer le produit $R(x)=c_0+c_1x+\dots+c_rx^r$. En
  développant le produit $P(x)Q(x)$, on obtient la relation :
  $$c_k=a_0b_k+a_1b_{k-1}+\dots+a_kb_0=\sum_{i+j=k}a_ib_j$$
  en convenant que $a_i=0$ si $i>p$ et $b_j=0$ si $j>q$.
  \begin{enumerate}
  \item Écrire un programme \texttt{produit\_naif} utilisant cette
    relation, et estimez-en le temps d'exécution.
  \item Un algorithme ``diviser pour régner'' a été présenté par
    \textsc{Knuth} en 1969 : en supposant les deux polynômes de degré
    au plus $2n-1$, on les décompose en deux polynômes de degré au
    plus $n-1$ en écrivant leur division euclidienne par $x^n$ :
    $$P(x)=P_0+x^nP_1,\ Q(x)=Q_0+x^nQ_1$$
    de sorte que
    $$R(x)=P_0Q_0+x^n((P_0+P_1)(Q_0+Q_1)-P_0Q_0-P_1Q_1)+x^{2n}P_1Q_1$$
    qui fait apparaître $3$ multiplications de polynômes de degré au
    plus $n-1$, et trois additions de polynômes de degrés au plus
    $2n-2$ (pourquoi ?).

    Construisez un programme \texttt{produit\_KNUTH} reproduisant cet
    algorithme.
  \item Essayez d'estimer l'efficacité de ce nouveau programme, et la
    comparer à l'algorithme naïf. Ce programme est-il toujours plus
    efficace ?
  \item Chercher un algorithme permettant de calculer
    $(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2)$ en cinq multiplications, et
    en déduire un algorithme de multiplication polynomiale
    asymptotiquement plus rapide que \texttt{produit\_KNUTH}.
  \item Testez tous ces programmes sur le calcul de $(1+X)^n$... en
    construisant un algorithme exploitant la méthode ``diviser pour
    régner'' pour cette exponentiation, bien sûr !
  \end{enumerate}
  \begin{corrige}
    
  \end{corrige}
\end{Ex}
\bigskip
\begin{Ex}[Tri fusion, tri rapide]
  On applique ici \emph{brut de décoffrage} le principe de ce TP au
  tri d'un tableau d'entier.
  \begin{enumerate}
  \item Concevoir un algorithme ``diviser pour régner'' triant un
    tableau d'entier.
  \item Écrire une fonction \texttt{fusion} fusionnant deux tableaux triés.
  \item En fait, il vaudrait mieux fusionner des morceaux d'un unique
    tableau. Revoir la fonction précédente.
  \item Enrober la fonction précédente dans une autre
    \texttt{tri\_fusion} triant un tableau d'entiers.
  \item Estimer l'efficacité de ce tri en supposant que le tableau est
    de taille $N=2^p$.
  \item Le tri rapide exploite lui aussi la méthode ``diviser pour
    régner'', mais avec un découpage différent : on sélectionne un
    \emph{pivot} dans le tableau, et on partage le tableau en deux
    sous-tableaux, l'un contenant tous les éléments inférieurs au
    pivot, l'autre contenant ceux qui sont supérieurs.

    Du coup, l'algorithme de fusion s'en trouve simplifié : il n'y a
    qu'a emprisonner le pivot entre les deux sous-tableaux triés.

    Écrire un programme \texttt{tri\_rapide} réalisant cette idée.
  \item Comparez les deux méthodes de tris vues dans cet exercice.
    Quels sont les avantages et inconvénients de chacun ?
  \end{enumerate}
  \begin{corrige}
    
  \end{corrige}
\end{Ex}
\Closesolutionfile{soltp3sup}
\newpage
\titre{Corrigé (partiel) du TP 3 : diviser pour régner}
\Readsolutionfile{soltp3sup}

\end{document}

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

\begin{Ex}
  
  \begin{corrige}
    
  \end{corrige}
\end{Ex}