\chapterimage{x_files4}
\chaptertext{Armé(e) d'un maple 12 avant-avant-dernière génération, vous allez vous attaquer au sujet X/Cachan des
  MP-SI débarqué  à Palaiseau  en juin  dernier et  vous pourrez  alors attaquer
  seul(e) celui de 2010...mais vous n'êtes pas seul(e)...}

\chapter{X: info B}

%\section{L'aide mémoire de M. Stainer}
%\setindent{0cm}%

\section{L'algo à l'X}

L'épreuve  B d'informatique  dure deux  heures et  n'est corrigée  que pour  les
candidats admissibles.

%Voici un petit résumé du rapport de l'épreuve de 2012.

Le choix du langage de programmation est libre.

Environ 60\%  des candidats  choisissent Maple,  25\% OCaml, 6\%  C ou  C++, 4\%
Python et 3\% des langages divers.

Nous  illustrerons le  sujet de  2013 en  Maple car  cela nous  servira aussi  à
préparer l'épreuve de Math IΙde Centrale.

Voici quelques remarques que l'on retrouve dans les rapports d'année en année.

\begin{itemize}
\item Il  faut faire  attention aux  directives du sujet,  par exemple  s'il est
  indiqué que  l'indexation des tableaux commence  à zéro. Vous pouvez  faire un
  autre choix en l'indiquant clairement, mais cela embêtera le correcteur....
\item Il faut proscrire toutes les commandes de calcul formel.
\item Le code mis en \oe uvre doit être simple et clair dans sa forme autant que
  dans sa présentation: indentation, passage à la ligne...
\item N'hésitez pas à commenter votre code (avec \# en Maple).
\item Un  ancien correcteur n'aimait pas  la récursivité. Il faudra  attendre le
  rapport 2013 pour voir ce qu'il en est du nouveau. Nous en reparlerons.
\item Donnez des noms explicites aux fonctions intermédiaires que vous créez.
\item Attention à utiliser des fonctions qui retournent les valeurs demandées et
  non pas leur  affichage avec un petit message du  style \og \textit{La réponse
    est : 5}\fg{}.
\item N'oubliez pas d'initialiser vos variables.
\item N'oubliez pas que les  fonctions des questions précédentes servent souvent
  à créer celles des suivantes.
\item Pensez à  économiser la mémoire en évitant les  évaluations répétées d'une
  même expression.
\item Une erreur bizarre et fréquente: si votre indice de boucle est \texttt{i},
  ne  vous   attendez  pas  à   ce  qu'une  variable   \texttt{ti}  s'incrémente
  automatiquement avec \texttt{i}...
\item Autre  erreur fréquente et  un peu bête:  entre les indices  \texttt{a} et
  \texttt{b}, il y a \texttt{b-a+1} valeurs!...
\end{itemize}


Le sujet de 2013 étudie la recherche de points fixes de fonctions à valeurs dans
un ensemble fini.

Vous noterez que quatre questions parmi les quatorze ne demande pas de code mais
des  calculs  de  complexité   ou  des  démonstrations  mathématiques...mais  un
programme est lui-même une démonstration... 

Le sujet est un peu plus difficile que d'habitude mais on y retrouve toujours la
manipulation de  tableaux. Il y  a comme  d'habitude des questions  pouvant être
considérées hors programme mais le hors programme semble être au programme à l'X
et aux ENS...


\section{Le tutoriel de M. Stainer}

Voici  à  présent  un  rappel  des  principales  fonctions  Maple  proposées  par
M. \textsc{Stainer} qui seront surtout
utiles pour l'oral de Centrale et qu'il faudra donc conserver par devers vous.

%\includegraphics[height=\textheight,page=1]{stainer1}
\includepdf[openright=false,pages={1-6}]{stainer1}
\includepdf[pages={1-6}]{stainer2}

\includepdf[pages={1-8}]{stainer3}
\includepdf{stainer4}


\includepdf[pages={1-5}]{Info_SI_MP_2013}

\section{X/Cachan 2013}
\subsection*{\og Primitives\fg{}}

En  informatique, on  désigne par  primitive d'un  langage un  objet qui
n'est pas construit à partir du langage lui-même.
Par exemple en \textsc{OCaml}, il existe des primitives écrites en C.

Ici, nous allons construire les  fonctions évoquées dans le préambule du
sujet  en  Maple donc  ce  n'est  pas vraiment  des  primitives  mais cela  nous
permettra de nous \og remettre dans le bain\fg{} onctueux de MAPLE...

\subsubsection*{allouer}

La  fonction  \texttt{allouer(m,c)} renvoie  un  tableau  de taille  $m$
rempli  de $c$. Comme  il s'agit  de tableaux  d'une ligne,  nous allons
plutôt nous  tourner sur des  objets de type  \textit{liste}, facilement
manipulables  en MAPLE,  mais il  faut  bien faire  la différence  entre
les  listes qui  sont définies  dynamiquement et  les tableaux  qui sont
définis  statiquement. Le  jour du  concours, le  jury accepte  que vous
employiez  des listes  au lieu  de  tableaux \texttt{array}  si vous  le
précisez et le motivez.

\begin{lstlisting}
> allouer := proc(m::nonnegint,c)
    RETURN([c$m])
  end:
\end{lstlisting}

Il est  optionnel de préciser le  type des arguments  des fonctions mais
cela sert de garde-fou. Notez l'utilisation du \lstinline+$+


%$
\subsubsection*{taille}

Il existe une fonction qui compte le nombre d'opérandes d'une liste: \lstinline+nops+. 

% \subsubsection*{Partie entière}

% Il existe deux fonctions relatives à la partie entière d'un réel: \lstinline+floor+ et 
% \lstinline+ceil+. Votre niveau d'anglais vous permettra de comprendre ce
% qu'elles représentent...


\subsubsection*{Exemple}

Nous utiliserons le tableau du sujet comme exemple de référence pour nos
tests. Nous n'aurons donc pas besoin de la fonction \texttt{allouer}...

\begin{lstlisting}
> tab_ex := [1,3,5,7,9,1,3,5,7,9]:
\end{lstlisting}

\begin{DANGER}
  Maple commence à compter à 1 alors  que le sujet précise que le premier indice
  des tableaux est  0: vous pouvez donc \textbf{à l'écrit}  considérer que Maple
  commence  à  compter à  0  mais  sur vos  tests  sur  machine aujourd'hui,  ce
  \verb+@@@!!###!!+ Maple voudra que vous commenciez à 1....
\end{DANGER}


\subsubsection*{Passage par valeur / par adresse}

Au début du sujet, il est évoqué  le passage de paramètre, ce qui est grandement
hors programme et donc déroutant!

En gros, il existe deux types de passage des paramètres d'une fonction:
\begin{description}
\item[par valeur] (ou par copie): la fonction  ne dispose que d'une copie de son
  paramètre. C'est cette copie qu'elle  peut modifier mais le paramètre d'entrée
  peut rester, lui, immuable (non \og mutable\fg{} en franglais informatique).
\item[par adresse]: la fonction dispose de  l'adresse de son argument. Elle peut
  donc  modifier  le  contenu de  cette  adresse  et  à  la fin  de  l'exécution
  l'argument  se  trouve  irrémédiablement   modifié.  C'est  plus  rapide  mais
  dangereux car  cela crée un \textit{effet  de bord}. Le paramètre  d'entrée ne
  peut plus être 
   immuable (il doit être \og mutable\fg{}).
\end{description}

Voyons  ce que  cela donne  en Maple  avec une  liste (immuable)  ou un  tableau
(mutable).

On prend un paramètre  qui sera un tableau ou une liste  d'entiers et on modifie
son premier terme:

\begin{lstlisting}
> test := proc(t)
    t[1]:= t[1]+2;
    RETURN(t);
  end:
\end{lstlisting}

Avec un tableau:

\begin{lstlisting}
> tab := array([3,4,5,6]):
> test(tab):
> tab[1]
                               5
> test(tab):
> tab[1]
                               7
\end{lstlisting}

Le  paramètre  a  été  irrémédiablement   modifié  par  la  fonction.  De  plus,
\texttt{tab[1]} ne renvoie pas toujours la même chose!...

Avec une liste:

\begin{lstlisting}
> liste := [3,4,5,6]:
> test(liste):
Error, (in test) Illegal use of a formal parameter
\end{lstlisting}


Il faut donc faire le passage par valeur à la main.


\begin{lstlisting}
> test2 := proc(t)
    local u;
    u := t;
    u[1]:= t[1]+2;
    RETURN(u);
  end:
\end{lstlisting}

Alors:

\begin{lstlisting}
> liste := [3,4,5,6]:
> test2(liste);
                             [5, 4, 5, 6]
> liste;
                             [3, 4, 5, 6]
> test2(liste);
                             [5, 4, 5, 6]
\end{lstlisting}


OK, mais est-ce que ça change quelque chose pour les tableaux:

\begin{lstlisting}
> test2(tab):
> tab[1]
                               5
> test2(tab):
> tab[1]
                               7
\end{lstlisting}

Maple continue donc à  passer les arguments par adresse même  si nous avons créé
une variable locale pour faire à la main un passage par valeur.

Bref,  encore une  fois,  programmer avec  Maple  qui n'est  pas  un langage  de
programmation, c'est sportif...

Pour ne pas se perdre, je vous conseille  d'utiliser des listes et de créer à la
main des variables locales. 


\subsection*{Question 1}

On pensera  à utiliser \verb+RETURN+ qui  permet de sortir de  la procédure sans
aller au bout de la boucle.


Pour se fixer notre façon de travailler, voici ce que nous écrirons sur Maple:


\begin{lstlisting}
> admet_point_fixe := proc(t::list)
    local k;
    for k from 1 to nops(t) do
          if t[k] = k - 1 
          then RETURN(true)
          fi;
   od;
 RETURN(false);
 end:
\end{lstlisting}

et sur la copie:

\begin{lstlisting}
> admet_point_fixe := proc(t::list)
    local k;
    for k from 1 to taille(t) do
          # est-ce que k est un point fixe ?
          if t[k] = k 
          # on renvoie vrai et on arrête l'exécution
          then RETURN(vrai)
          fi;
   od;
 # si l'on n'est pas déjà sorti, c'est qu'il n'y a pas de point fixe
 RETURN(faux);
 end:
\end{lstlisting}


\begin{aparte}
Dans  de  vrais  langages  de  programmation,  cela  peut  être  plus  clair  et
concis. Par exemple en Haskell:

\haskell
\begin{lstlisting}
> any (\x -> mod (2*x + 1) 10 == x) [1..9]
True
\end{lstlisting}

Mais bon, cela réduirait  le contenu de ce sujet...En  prépa, on apprend aux
futurs ingénieur(e)s à programmer de manière inutilement compliquée avec des outils préhistoriques ;-)
\maple

Mais je  suis un  peu de  mauvaise foi  car Maple  intègre deux  procédures fort
utiles héritées des  principes de la programmation  fonctionnelle: \verb+map+ et
\verb+select+.

Par exemple, ici:

\begin{lstlisting}
> select(x -> (2*x+1) mod 10 = x, [k $ k = 1..9]);
                                 [9]
\end{lstlisting}


\end{aparte}



\subsection*{Question 2}

On reprend la fonction précédente mais en introduisant un compteur.


\subsection*{Question 3}

C'est l'occasion de voir un peu de  récursivité (une définition avec des ... est
une définition récursive: c'est donc l'énoncé qui nous y incite...).

Par exemple, $f^5(1)= f^4(f(1))$ i.e. \verb+itere(t,1,5) = itere(t,3,4)+.

Attention aux indices...

\subsection*{Question 4}

Il n'y a pas grand chose à faire si ce n'est du copier-coller....

\subsection*{Question 5}

Deux  petites questions  préliminaires: combien  de points  fixes peut  admettre une
fonction ayant un  attracteur principal? En combien d'itérations  au maximum cet
attracteur est-il atteint à partir d'un entier de $E_n$?

N'oubliez pas non plus de lire la dernière phrase de la question...


\subsection*{Question 6}

L'énoncé donne  une relation de récurrence...Décidément,  difficile d'échapper à
la récursion dans ce sujet, n'en déplaise à certains correcteurs...

Par sécurité, on pourrait introduire un message d'erreur s'il n'y a pas d'attracteur
principal avec \verb+ERROR(`Pas d'attracteur principal`)+.



\subsection*{Question 7}

On répond à ce genre de question en une ligne de manière claire et efficace avec
Haskell ou OCaml mais bon... 

La question est bizarrement posée car la fonction précédente est déjà au pire de
complexité linéaire et on ne  voit pas comment ne  pas calculer chaque
temps de convergence donc cela nous donne une complexité quadratique...

Bon, on  va supposer que  le rédacteur pense à  la complexité de  cette fonction
sans tenir compte de celle des autres.

Maple sait comparer deux nombres avec \verb+max+. 

\subsection*{Question 8}

C'est un peu le même principe que la fonction précédente.

\subsection*{Question 9}

Alors  là,  c'est   carrément  hors  programme  cette   histoire  de  complexité
logarithmique, à  croire que les rédacteurs  des sujets pour étudiants  de MP-SI
pensent qu'ils écrivent un sujet pour MP-INFO.

Des étudiants d'option INFO, quand  ils voient \og complexité logarithmique\fg{},
pensent d'abord à \og dichotomie\fg{} puis ensuite éventuellement cherchent ailleurs...


\subsection*{Question 10}

Rigolo le rappel sur du hors programme...En grec, $διχοτομια$ signifie \og
couper en deux\fg{}: qu'est-ce qui est coupé en deux dans \verb+point_fixe+?


\subsection*{Question 11}

Que pensez-vous de $f^k(x)$?

\subsection*{Fin}

Des questions d'arithmétique...

\section{X/Cachan 2010}

Voici encore  un sujet qui est  allé hors programme en  parlant d'algorithmes de
tri.

Nous allons encore 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}
> 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}
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}
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}
> 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}
> 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}
> 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}
> 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}
> 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}
\includepdf[pages={1-4}]{X2010}

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