\chapterimage{x_files}
\chaptertext{Un peu  d'algo pour SI et  INFO sur un sujet  pas très bien
posé mais qui permet un bon survol de la programmtion MAPLE.}

\chapter{Un peu d'algo: X 2012}

\section*{\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{Caml}, il existe des primitives écrites en C.

Ici, nous allons construire les  fonctions évoquées dans le préambule du
sujet pour nous \og remettre dans le bain\fg{} onctueux de MAPLE...

\subsection*{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:

\begin{lstlisting}[caption={}]
> 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+$+


%$
\subsection*{taille}

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

\subsection*{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...


\subsection*{Exemple}

Nous utiliserons le tableau du sujet comme exemple de référence pour nos
tests:

\begin{lstlisting}[caption={}]
> tab11 := [3,2,5,8,1,34,21,6,9,14,8]:
\end{lstlisting}



\section*{Question 1}


Exceptionnellement,  je vous  donne une  proposition pour  vous rappeler
quelques éléments de syntaxe MAPLE sur les fonctions:

\begin{lstlisting}[caption={}]
> calculeIndicMaximum := proc(tab::list,a,b::nonnegint)
   local m,i,j;
   i:=a;
   m:=tab[a];
   for j from a+1 to b do
     if tab[j] > m then
        i:=j;
        m:=tab[j];
     fi;
   od;
   RETURN(i);
  end:
\end{lstlisting}




\section*{Question 3}

C'est  là  que  ça  commence  à être  pénible...  La  supposition  entre
parenthèses  ne  correspond  pas  à  une expérimentation.  En  tant  que
mathématicien(ne)s, nous  sommes plus à  l'aise avec la  manipulation de
fonctions et  non pas de procédures  avec des variables  globales et des
changements en place.
Nous allons donc créer une fonction:

\lstinline+partition := proc(tab,a,b,indicePivot)+ qui 
va renvoyer  le nouvel  indice évoqué dans  l'énoncé ainsi que  la liste
réordonnée, en deuxième opérande.


Par exemple, on obtiendra:

\begin{lstlisting}[caption={}]
> partition(tab11,1,11,4);
               6, [3, 2, 5, 1, 6, 8, 8, 34, 21, 9, 14]
\end{lstlisting}


Le  sujet n'évoque  pas le  traitement des  erreurs.  Montrons cependant
comment cela peut être traité avec MAPLE:

\begin{lstlisting}[caption={}]
if (indicePivot < a) then ERROR(`indice trop petit`)
\end{lstlisting}


\section*{Question 4}

L'algorithme est donné dans le  texte mais de manière étrange. Notez son
côté  récursif. Transformez-le un  peu pour  l'adapter à  notre fonction
\texttt{partition}.

Vous créerez également une  fonction \texttt{median(tab)} qui renvoie la
médiane d'un tableau.

\begin{DANGER}
Il y a  un problème dans l'énoncé,  au niveau de la huitième  ligne de la page 3...
\end{DANGER}

\begin{lstlisting}[caption={}]
> median(tab11[1..11]);
                                  8
\end{lstlisting}

\section*{Question 5}

Combien    de    comparaisons    effectue-t-on    avec    la    fonction
\texttt{partition} sur un tableau de taille $n$?

\section*{Question 6}


On   va   décomposer   le   problème.   Créez   d'abord   une   fonction
\texttt{decoupe5 := proc(tab)} qui découpe  une liste en paquets de 5 en
s'arrangeant avec les morceaux restant...

\begin{lstlisting}[caption={}]
> decoupe5(tab11[2..9]);
                    [[2, 5, 8, 1, 34], [21, 6, 9]]
> decoupe5(tab11[2..4]);
                             [[2, 5, 8]]
\end{lstlisting}





Pour  la   fonction  \texttt{choixPivot},  elle   encore  récursive,  on
utilisera la fonction \texttt{median} préalablement mise au point.




\includepdf[pages={1-6}]{X2012}



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