\documentclass{tp-caml}

\tp{
  title={Révisions},
  number=7ème,
  date=Lundi 25 mars 2013,
  class=MP
}

\begin{document}

\begin{corpus}

\section{Tris}

\begin{exo}
Écrire une fonction de tri fusion sur les listes.
\end{exo}

\begin{exo}
Que fait la fonction ci-dessous ? Que renvoie-t-elle ?
\end{exo}

\begin{verbatim}
partition (tableau idDebut idFin pivot)
  Si idDebut > idFin
    Renvoyer idFin
  Sinon
    Si tableau[idDebut] < pivot
      partition(tableau, idDebut+1, idFin, pivot)
    Sinon
      échange(tableau, idDebut, idFin)
      partition(tableau, idDebut, idFin-1, pivot)
\end{verbatim}

\begin{exo}
Écrire une fonction de tri rapide sur les tableaux. Cette fonction
modifiera le tableau en place et ne renverra rien. Attention, vous ne
devez jamais dupliquer le tableau !
\end{exo}

\section{Nombres}

\begin{exo}
Écrire les fonctions qui prennent deux arguments $a$ et $b$ et
renvoient $a\wedge b$, $a\vee b$ (pgcd et ppcm).
\end{exo}

\begin{exo}
Écrire une fonction qui prend en argument deux entiers $a$ et $b$ et
retourne deux entiers $u$ et $v$ tels que $a\times u+b\times v=a\wedge b$.
\end{exo}

\begin{exo}
Écrire une fonction qui prend en argument un entier $n$ et retourne
une liste [$a_0, …, a_k$] telle que $\sum_{i=0}^k a_i\times 2^i = n$.
\end{exo}

\begin{exo}
Écrire la fonction inverse qui prend en argument une liste [$a_0,…,a_k$]
et renvoie le nombre $n=\sum_{i=0}^k a_i\times 2^i$.
\end{exo}

\section{Arbres}

On définit le type suivant :

\begin{caml}
type 'a arbre = F of 'a | N of 'a * 'a arbre * 'a arbre;;
\end{caml}

\begin{exo}
Écrire une fonction qui teste si un arbre est un arbre binaire de
recherche.
\end{exo}

\begin{exo}
Écrire une fonction qui prend un arbre binaire étiqueté (pas
nécessairement une ABR) par des entiers et renvoie la valeur maximale
de la somme des éléments d'une de ses branches.
\end{exo}

\begin{exo}
Écrire une fonction qui prend en argument un arbre binaire étiqueté
par des caractères et renvoie son ordre préfixe. Faire de même pour
l'ordre infixe.
\end{exo}

\section{Quelques erreurs classiques}

\begin{exo}
Yorel Reivax tente de coder la fonction max3, qui retourne le maximum
de 3 éléments.
\begin{caml}
let max3 a b c = max max a b c;;
\end{caml}

Caml retourne max3 : \textit{(’a -> ’a -> ’a) -> ’a -> ’a -> ’a = <fun>},
pourquoi ?  Déterminer un appel de max3 qui ne retourne pas
d’erreur.
\end{exo}

\begin{exo}
Yorel Reivax tombe sur l'erreur :\\
\textit{This expression has type truc,
but is used with type truc.}
Que pouvez-vous lui dire ?
\end{exo}

\end{corpus}


\end{document}



