\chapterimage{tri}
\chaptertext{Nous  travaillerons  aujourd'hui  sur  les  deux  dernières
  épreuves de 2 heures de  l'X/ENS Cachan. Comme il s'agit d'une épreuve
  écrite, on s'attachera à  rédiger des solutions sur papier, présentées
  de manière claire, après avoir travaillé sur brouillon-papier et brouillon-écran.}

\chapter{Permutations, tris et polynômes}


\section{Sujet 2011 - Permutations}

On ne s'occupera aujourd'hui que  des premières questions destinées à se
familiariser avec  ce genre d'épreuve  et dégager quelques  réflexes qui
aideront à traiter le second sujet.


Si  on  rédige   en  Maple,  on  peut  utiliser   pour  représenter  les
permutations  (puis les  polynômes),  des listes  ou  des tableau  (type
\texttt{array}).

Les plus commodes à utiliser  sont les listes. Nous introduisons ici les
primitives \lstinline+allouer+ et \lstinline+taille+ souvent introduites
dans  les sujets  même si  la première  est inutile  avec les  listes de
Maple. Elles faciliteront cependant la tâche du correcteur.


\begin{lstlisting}
> allouer := proc(m)
    RETURN([0 $ m])
  end:
> taille := proc(t)
    RETURN(nops(t))
  end:
\end{lstlisting}
 


\subsection{Ordre d'une permutation}

\begin{enumerate}
\item Diverses solutions sont possibles:  réfléchir à ce qui empêche une
  \textit{application}  d'être  une  permutation.  En  Maple,  les  deux
  éléments de  $\BR_2$ sont \lstinline+true+  et \lstinline+false+. Mais
  avant tout, comment représenter une permutation à l'aide d'une liste?

\item Normalement, il ne faut pas oublier de tester si la composition est possible avant de
  l'effectuer mais l'énoncé nous dispense de le faire...
\item Si \lstinline+u+ est votre inverse, que vaut \lstinline+u[t[i]]+?
\item No comment...
\item On pourra introduire la liste correspondant à l'identité.
\end{enumerate}


\section{Sujet 2010 - Échangeurs de polynômes}


Nous allons travailler sur des  listes plutôt qu'avec des tableaux. On a
souvent besoin  de considérer la  \textit{tête} d'une liste qui  est son
premier élément et la \textit{queue} d'une liste qui est la liste privée
de son premier élément. 

Nous pouvons donc introduire deux primitives:

\begin{lstlisting}[caption={}]
> Tete := proc(L)
   RETURN(L[1])
  end:
> Queue := proc(L)
   RETURN(L[2..-1])
  end:
\end{lstlisting}


Pour  la   beauté  du  geste,   vous  essaierez  d'éviter   les  boucles
\textit{pour}  ou  \textit{tant  que}  pour  répondre  aux  5  premières
questions au moins.

\begin{enumerate}
\item Il est plus léger ici d'utiliser l'algorithme de \bsc{Hörner} pour
  évaluer un polynôme. Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications.




On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}


Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions. En fait il y a au maximum $2\times$degré
de P opérations (voire moins avec les zéros).

Proposez ici  une version récursive utilisant la  liste des coefficients
et nos primitives \lstinline+Tete+ et \lstinline+Queue+.


\item Encore une  fois, une version récursive est  rapide à écrire. Vous
  aurez peut-être besoin de  distinguer trois conditions. Utilisez alors
  la structure conditionnelle:

  \begin{lstlisting}[caption={}]
if ... then ...
elif ... then ...
else ...
fi
  \end{lstlisting}
\item Une version récursive est  attendue. Vous aurez sûrement besoin de
  concaténer deux listes ou d'ajouter un élément à une liste.

Pour ajouter un 0 en bout de liste par exemple, on peut faire:

\begin{lstlisting}[caption={}]
liste := [op(liste),0]
\end{lstlisting}


\item Une  structure conditionnelle \lstinline+if...elif...else...fi+ traduit
  l'énoncé. On pourra utiliser  la commande \lstinline+signum(n)+ qui renvoie
  1 si $n>0$, $-1$ si $n<0$ et 0 sinon.

\item  Voici une  petite  question  qui cache  un  chapitre de  l'option
  informatique consacrée aux tris!...
Le sujet est  vaste... Pour votre culture, nous  aborderons tout de même
deux tris possibles  et leur complexité: le tri par  insertion et le tri
fusion.
\begin{description}
\item[Tri par  insertion] C'est  le tri qui  correspond à un  joueur qui
  classe ses cartes.

Nous privilégierons une version récursive bien sûr.


Commencez par créer  une procédure récursive qui insère  un élément dans
une liste. Comme vous avez lu tout le sujet, vous savez qu'à la question
suivante, il sera  utile de trier une liste  avec deux relations d'ordre
différentes. 

Vous allez donc créer une procédure \lstinline+insere := proc(Ordre,P,Liste)+
qui insère le polynôme \lstinline+P+  dans la liste de polynômes \lstinline+Liste+
selon  l'ordre  croissant correspondant  à  \lstinline+Ordre+  (qui sera  par
exemple \lstinline+Compare_neg+ dans cette question).

Pour obtenir la liste triée, il suffit  de trier un à un les éléments de
la liste  avec une  procédure récursive \lstinline+tri  := proc(Ordre,Liste)+
qui utilise \lstinline+insere+.



Par exemple, vous devriez obtenir:

\begin{lstlisting}[caption={}]
> tri(Compare_neg,[[1],[0,-1],[0,1]]);

                        [[0, 1], [0, -1], [1]]
\end{lstlisting}

qui correspond à la sixième figure proposée dans le sujet.

Combien d'opérations élémentaires  la procédure va-t-elle effectuer dans
le pire des cas?



\item[Tri fusion]


On utilise la méthode diviser  pour régner: on \og coupe\fg{} le tableau
à trier en deux, on trie chaque tableau et on fusionne les deux tableaux
obtenus, de manière récursive.

Il faut donc commencer par créer une procédure 

{

\centering \lstinline+divise := proc(Ordre,L)+

}
 

qui  divise la liste  \lstinline+L+ en  deux listes  de longueurs  égales ou
 presque, selon la parité de la taille.

Il faudra ensuite créer une procédure récursive 

{

\centering \lstinline+fusionne := proc(Ordre,L1,L2)+

}

qui prend deux listes triées et en fait une seule liste triée.

On  utilise  ensuite  ces  deux  procédures  pour  créer  une  procédure
récursive 

{

\centering \lstinline+tri_f := proc(Ordre,Liste)+ 

}

qui trie la liste \lstinline+L+.

Pour  la   \textit{complexité},  on  peut  supposer   que  la  division
s'effectue à temps  constant et que la fusion de  deux listes triées est
de l'ordre de la taille $n$ du tableau.

Soit $K_n$ la complexité du tri d'une liste de taille $n$.

On obtient donc que $K_n$ est de l'ordre de $2K_{\lfloor n/2\rfloor}+n$.

Il  s'agit donc  d'étudier la  suite de  terme  général $u_n=2u_{\lfloor
  n/2\rfloor}+n$ avec $u_0=u_1=0$.

Montrez que $u_n$ est croissante.

En introduisant la suite définie par $x_k=u_{2^k}$, montrez que:

$$n\lfloor  \log_2(n)\rfloor  \leqslant  u_n  \leqslant  2n\left(\lfloor
  \log_2(n)\rfloor +1\right)$$
\end{description}



\item  Tout est  expliqué... Après  ce  gros effort  de récursion,  vous
  pouvez utiliser une boucle \textit{pour}. Utilisez à bon escient \lstinline+RETURN+
  qui  permet  de sortir  de  la  procédure, ce  qui  est  adapté à  ces
  procédure de  vérification pour  économiser du temps:  on en  sort dès
  qu'on tombe sur un os.

  \begin{lstlisting}[caption={}]
> verifier_permute([2,3,1],[[0,1],[0,-1],[1]]);

                                 true
  \end{lstlisting}


\item On peut  utiliser ici une triple boucle  \textit{pour} indexée sur
  les coefficients $a$, $b$ et $c$.

Attention! $<$ est une relation d'ordre binaire en Maple ce qui interdit
l'utilisation directe de \lstinline+a<b<c<d+. On passera par:
{

\centering \lstinline+(x<y) and (y<z)+ 


}

Pour traduire la double inégalité $x<y<z$.

\begin{lstlisting}[caption={}]
> est_echangeur_aux([2,4,1,3],2);

                                 true

> est_echangeur_aux([2,4,1,3],1);

                                false
\end{lstlisting}

\item Pas de difficulté particulière:

  \begin{lstlisting}[caption={}]
> est_echangeur([2,4,1,3]);

                                false
  \end{lstlisting}


\item  L'utilisation  de  \lstinline+sum+  dans une  récursion  est  peu
  fructueuse en Maple. On préférera une double boucle.


  \begin{lstlisting}[caption={}]
> nombre_echangeurs(4);

                                  22
  \end{lstlisting}

\item On traduit simplement l'énoncé.





\item C'est la question compliquée...

\begin{lstlisting}
> enumerer_echangeurs(4); 
[
[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],
[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[3,1,2,4],[3,2,1,4],[3,2,4,1],
[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],
[4,3,2,1]
]
\end{lstlisting}

\end{enumerate}

\section{Un petit oral de Centrale pour la route...}

% Pour  vous récompenser,  un petit  exercice corrigé  pour  vous rappeler
% quelques  outils   Maple  sur  les   courbes.  On  notera   la  fonction
% \lstinline+interp+ qui donne le polynôme interpolateur de \bsc{Lagrange}
% d'une  fonction (pendant  vos loisirs,  vous pouvez  créer  votre propre
% \lstinline+interp+...). 


\begin{exercice}[Centrale, PC 2010]

    \begin{enumerate}
        \item Soit $n\in\llbracket 0,10\rrbracket $. 
           Montrer en utilisant Maple qu'il existe $P_n∈ℝ[X]$
            tel que $$∀t∈ℝ,\quad \sin(nt)=P_n(\cos t)\sin t$$
        \item Soit $n∈ℕ$. Montrer qu'il existe un unique $P_n∈ℝ[X]$
            tel que $$∀t∈ℝ,\quad \sin(nt)=P_n(\cos t)\sin t$$
        \item Montrer que $∀n∈ℕ,\quad P_{n+2}=2XP_{n+1}-P_n$
        \item Écrire une procédure permettant de calculer $P_n$.

{

\centering{--- Optionnel ---}

}

        \item  Montrer que l'application
            $\displaystyle(P,Q)\mapsto ∫_{-1}^1 P(t)Q(t)\sqrt{1-t^2} \dd t$
            définit un produit scalaire sur $ℝ[X]$.
        \item Montrer que la famille $(P_n)_{n∈ℕ}$ est une famille
            orthogonale de $ℝ[X]$.
    \end{enumerate}

  \end{exercice}
  


Je  vous   donne  la  partie   Maple.  Vous  noterez   l'utilisation  de
\lstinline+subs+   pour  les  changements   de  variable,   de  l'option
\lstinline+remember+     pour     les     tableaux     récursifs,     et
\lstinline+evalb(test)+ qui évalue si un test est vrai ou faux.




\begin{lstlisting}[caption={}]
# a)
for n from 0 to 10 do
    Q := expand(sin(n * t) / sin(t)):
    P[n] := subs(cos(t)=x, Q);
    od;

# c)
tchebychev := proc(n)
    option remember;
    if n=0 then
        RETURN 0
    elif n=1 then
        RETURN 1
    else
        RETURN expand(2*x*tchebychev(n-1) - tchebychev(n-2));
    fi;
    end:

for n from 0 to 10 do
    evalb(tchebychev(n) = P[n]);
    od;

tchebychev(35);
\end{lstlisting}

\includepdf[pages={1-3}]{X2011}
\includepdf[pages={1-4}]{X2010}

%%% Local Variables: 
%%% TeX-master: "PolyMapleMPstar"
%%% End: 
