\documentclass{tp-caml}

\tp{
  title=Listes,
  number=Second,
  date=Vendredi 21 janvier 2011,
  class=HX4 \& HX1
}

\begin{document}

\begin{corpus}

\section{Utilisation du filtrage}
\subsection{filtrage simple}

\begin{exo}
Programmez les fonctions :
\begin{prototype}
	tete : 'a list -> 'a
	queue : 'a list -> 'a list
\end{prototype}
qui doivent renvoyer l'élément de tête et la queue de la liste ou
échouer avec une exception (utiliser le mot clé \emph{failwith}).
\end{exo}
\begin{solc}
let tete = function
  | [] ->  failwith "liste vide"
  | a::q -> a
  
let queue = function 
  | [] -> failwith "liste vide"
  | a::q -> q
\end{solc}


\subsection{filtrage et récursivité}
Programmez les fonctions :

\begin{exo}
\begin{prototype}
	taille : 'a list -> int
\end{prototype} 
renvoyant la taille d'une liste (c'est à dire le nombre d'éléments de
la liste).
\end{exo}
\begin{solc}
let rec taille = function
  | [] -> 0
  | a::q -> 1+taille q
\end{solc}

\begin{exo}
\begin{prototype}
	appartient : 'a -> 'a list -> bool	
\end{prototype} 
renvoyant \emph{true} si $x$ apparait dans la liste
\end{exo}
\begin{solc}
let rec appartient x = function
  | [] -> false
  | a::q -> a=x || appartient x q
\end{solc}
\begin{exo}
\begin{prototype}
	applique :  ('a -> 'b) -> 'a list -> 'b list
\end{prototype} 
qui étant données une fonction $f$ et une liste [$a_1$;...;$a_n$] doit
renvoyer [$f a_1$;...;$f a_n$].
\end{exo}
\begin{solc}
let rec applique f = function
  | [] -> []
  | a::q -> f a::applique f q
\end{solc}
\begin{exo}
\begin{prototype}
	pour_tout : ('a -> bool) -> 'a list -> bool
\end{prototype} 
qui prend un prédicat (c'est à dire une fonction renvoyant un booléen)
et doit renvoyer true si tous les éléments de la liste vérifient le
prédicat ($f(e)=\mbox{true}$ pour tout élément $e$ de la liste).
\end{exo}
\begin{solc}
let rec  pour_tout pred = function 
  | [] -> true
  | a::q -> pred a && pour_tout q
\end{solc}
\section{it\_list}
La fonction 
\begin{prototype}
	it_list : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
\end{prototype}
prend en argument une fonction $f$, un élément $a_0$ et une liste $[b_1;b_2;...;b_n]$. Elle renvoie $a_n$ où $a_i = f ~ a_{i-1} ~ b_i$. 
\begin{exo}
Explicitez $f$ et $a_0$ tels que $a_n = \sum_{i=1}^{n} b_i$. En déduire une fonction 
\begin{prototype}
	somme : int list -> int
\end{prototype} 
utilisant it\_list, qui doit renvoyer la somme des éléments d'une liste.
\end{exo}
	
\begin{solc}
let somme l = 
  let add x y = x+y in
  it_list add 0 l
\end{solc}

\begin{exo}
De la même manière, programmez, d'abord, en utilisant it\_list, puis, sans,
\begin{prototype}
	retourne : 'a list -> 'a list
\end{prototype} 
qui prend en argument $[a_1;...;a_n]$ et qui renvoie $[a_n;...;a_1]$.
\end{exo}

\begin{solc}
let retourne l = 
  let f ac el = el::ac in
  it_list f [] l
\end{solc}

\begin{exo}
Programmez votre version de la fonction it\_list.
\end{exo}

\begin{solc}
let rec it_list f a0 = function
  | [] -> a0
  | b::q -> it_list f (f a0 b) q 
\end{solc}

\section{Tris}
\subsection{tri par insertion}
\begin{exo}
Écrivez une fonction 
\begin{prototype}
	insere : 'a -> 'a list -> 'a list
\end{prototype}
qui étant donnés un élément $x$ et une liste triée $[a_1;...;a_n]$ avec $a_1\leq a_2\leq...\leq a_n$ doit renvoyer $[a_1;...;a_i;x;a_{i+1};...;a_n]$ avec $a_i \leq x \leq a_{i+1}$. 
En déduire une fonction 
\begin{prototype}
	tri : 'a list -> 'a list
\end{prototype} 
qui doit renvoyer la liste triée. On pourra utiliser it\_list ou faire une fonction à deux arguments: le premier est un bout de liste déjà trié, le second est ce qu'il reste à trier.
\end{exo}

\begin{solc}
let rec insere x = function
  | [] -> [x]
  | a::q ->
    if a < x 
    then a:: insere x q
    else x::a::q
    
let rec complete_tri l = function
  | [] -> l
  | a::q -> complete_tri (insere a l) q
;;
let tri l = complete_tri [] l

let tri2 l = it_list (fun ac el -> insere el ac) [] l
\end{solc}
\subsection{tri fusion}
\begin{exo}
Écrivez les fonctions :
\begin{prototype}
	partition : 'a list -> 'a list * 'a list
\end{prototype}
qui, d'une liste, fabrique une bi-partition la plus équilibrée possible;
\begin{prototype}
	reunit : 'a list * 'a list -> 'a list
\end{prototype}
qui fabrique une liste triée à partir de deux listes triées.
En déduire la fonction :
\begin{prototype}
	tri_fusion : 'a list -> 'a list
\end{prototype}
\end{exo}
\begin{solc}
let rec partition = function
  | [] -> ([],[])
  | a::q -> 
    let (g,d) = partition q in
    (a::d,g)

let rec reunit = function 
  | (a::q,x::t) -> 
    if x > a 
    then a::reunit (q,x::t)
    else x::reunit (a::q,t)
  | (a,b) -> a@b

let rec tri_fusion = function
  | [] -> []
  | [a] -> [a]
  | l -> 
    let (p1,p2) = partition l in
    reunit (tri_fusion p1,tri_fusion p2)
\end{solc}

\begin{exo}
En utilisant 
\begin{prototype}
	random__int : int -> int
\end{prototype}
générez des listes aléatoires et vérifiez que vos tris trient bien.
\end{exo}
\begin{solc}
let rec aleatoire =  function
  | 0 -> []
  | n -> random__int 100::aleatoire (n-1)

let a  = aleatoire 100
let b = tri_fusion a
let c = tri a
let  d = c = b
\end{solc}

\begin{exod}
Quel est le meilleur des deux algorithmes ? Essayez d'évaluer le nombre d'opérations que va effectuer chacun des algorithmes. Mettez le sous la forme $O(f(n))$, pour de bons $f$.
\end{exod}
\begin{sol}
Pour le premier algorithme on fait $n$ fois : insérer un élément dans une liste. Dans le pire des cas on a donc : 
$$\sum_{i=1}^n i = O(n^2)$$

Pour le second, on a que, quand $2^k \leq n \leq 2^{k+1}$, on peut minorer et majorer par les temps mis pour $2^k$ et pour $2^{k+1}$. Quand $n=2^k$ on montre alors par récurrence que $T(k) = 2^k + 2*T(k-1)+2^k$ donc $\dfrac{T(k)}{2^k} = 1+\dfrac{T(k-1)}{2^{k-1}}$. On a donc $ T(k) = k*2^k$ et donc l'algorithme est en $O(n * ln(n))$. Par ailleurs, on ne peut pas avoir une meilleure complexité.

Bien évidemment, le premier algorithme est plus lent, en pire cas, que le second.
\end{sol}

\subsection{Tri par sélection}
\begin{exo}
Le tri par sélection fonctionne de la manière suivante : on extrait le minimum de la liste que l'on veut trier, on trie la liste restante, on ajoute le minimum au début du reste trié.
\end{exo}
\begin{solc}
let rec extrait_min = function
  | [] -> failwith "liste vide"
  | [a] -> (a,[])
  | a::q -> 
    let (mini,reste) = extrait_min q in
    if a < mini 
    then (a,q)
    else (mini,reste)

let rec tri_insertion = function
  | [] -> []
  | l -> 
    let (mini,reste) = extrait_min l in
    mini::(tri_insertion reste)
\end{solc}

\begin{section}{Quelques exercices difficiles}

\begin{exod}
\textbf{Type ENS : Back to the future}

Après avoir voyagé dans le futur puis être revenu à votre époque, vous disposez d'un tableau qui vous dit ce que vaut, chaque mois, le cours de l'or. Comme vous voulez à tout prix vous enrichir, mais en faisant le moins d'efforts possible, vous décidez de regarder quel est le profit maximal que vous puissiez faire. Le cours de l'or est présenté sous la forme d'une liste d'entiers et vous devez donner le gain maximal réalisable. Vous ne pouvez faire qu'un achat/vente car sinon vous modifieriez trop le cours du temps et donc cela changerait les cours (vous pourriez y perdre) mais cela risquerait aussi de modifier le continuum espace/temps lui même!
\end{exod}
\begin{sol}
On remarque que le gain maximal réalisé en un point est donné par la différence entre la valeur de ce point et du minimum sur la partie de la liste avant cet élément. Il suffit donc de maintenir le minimum rencontré et à chaque fois de voir combien on gagne en vendant.
\begin{caml}
let backtothefuture = function
  | [] -> failwith "pas d'infos"
  | a::q -> 
    let rec foo min_vu = function
      | [] -> 0
      | a::q -> max (a-min_vu) (foo (min a min_vu) q)
    in
    foo a q
\end{caml}
\end{sol}

\begin{exod}
\textbf{Type ENS : Majorité}

Vous possédez les résultats d'une élection, présenté sous forme de liste. Par flemme, vous ne voulez faire qu'un dépouillement, c'est à dire qu'un parcours de liste. En plus, vous ne disposez que d'une petite mémoire. Vous ne voyez aucune technique pour trouver le candidat qui a le plus de voix ... Vous vous contentez donc d'assurer de donner le bon nom (celui qui a le plus de voix), seulement s'il obtient une stricte majorité. Comment faire ?
\end{exod}
\begin{sol}
Si on était vraiment cette personne on devrait, dès que l'on a deux bulletins pour des candidats différents, les déchirer et les bulletins qui nous reste en main à la fin ne peuvent être que ceux de celui qui a la majorité stricte, si majorité stricte il existe.
\begin{caml}  
let majorite =  function
  | [] -> failwith "impossible"
  | a::q ->
    let rec foo candidat vote = function 
      | [] -> candidat
      | a::q ->
        let nvote = vote + ( if a = candidat then 1 else -1 ) in
        if nvote < 0 
        then foo a 1 q
        else foo candidat nvote q
    in
    foo a 1 q
\end{caml}
\end{sol}

\begin{exod}
\textbf{Jeu : Snake}

Vous connaissez tous le jeu du snake, présent sur la plupart des téléphones portables. On va le programmer.
Tout d'abord il faut récupérer l'interface graphique sur le site du TP. Ensuite vous devez écrire une fonction 
\begin{prototype}
	enleve_queue : 'a list -> 'a list
\end{prototype}
qui retire le dernier élément d'une liste.

Ensuite vous devez compléter la fonction maj. L'interface donnée se charge du graphisme et de la gestion du clavier. Cette fonction maj doit faire évoluer le serpent, gérer si la pomme est avalée, si la tête du serpent croise le corps, si le serpent sort du périmètre ... toutes les règles que vous souhaitez.
\end{exod}	
\begin{solc}
(* Un snake minimaliste *)
and regulier y = 
  if y < 0 || y >= 30 then failwith "en dehors"

and maj serpent pomme grandir ax ay =
  
  let (tetex,tetey) = tete(serpent) in
  regulier (tetex+ax) ;
  regulier (tetey+ay) ;
  let ntete = (tetex+ax,tetey+ay) in
  let nserpent = ntete::(if grandir > 0 then serpent else enleve_queue serpent) in
  if appartient ntete serpent then failwith "superposition" ;
  let (npomme,ngrandir) = (if pomme = ntete then ((random__int 30,random__int 30),grandir+3) else (pomme,max (grandir-1) 0)) in
    (nserpent,npomme,ngrandir)
\end{solc}


\begin{exod}
\textbf{Équilibrage}

Étant donné quatre listes d'entiers $[a_1,...,a_n]$, $[b_1,...,b_m]$, $[c_1,...,c_p]$, $[d_1,...,d_q]$, pouvez vous dire s'il existe $i,j,k,l$ tels que $a_i+b_j+c_k+d_l=0$. 
\end{exod}
\begin{sol}
Pour avoir une bonne solution (en $O(n^2)$ et non en $O(n^2 ln(n))$) il faut un outil que nous verrons prochainement : les tables de hachages. Sans : 
On crée la liste des sommes de un élément de a et d'un de b d'un côté et celle de l'inverse des sommes d'un élément de c et un de d. On cherche alors une intersection entre ces deux listes. Pour trouver les intersections on trie et on fait un code similaire à reunit.
\begin{caml}
let somme l l' = 
  let rec foo acc = function
    | (_,[]) -> acc
    | ([],_) -> acc
    | ([a],x::t) -> foo (a+x::acc) ([a],t)
    | (x::t,q) -> foo (foo acc ([x],q)) (t,q)
  in
  tri_fusion (foo [] (l,l'))

let equilibre a b c d = 
  let rec inter = function 
    | ([],_) -> false
    | (_,[]) -> false
    | (a::q,x::t) -> 
      if a=x then true
      else 
        if a < x 
        then inter (q,x::t)
        else inter (a::q,t)
  in
  let rec nega = function
    | [] -> []
    | a::q -> -a::nega q
  in
  inter (somme a b , somme (nega c) (nega d))
\end{caml} 
\end{sol}

\end{section}
\end{corpus}


\end{document}



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