\documentclass[documents]{monexamen}
%\documentclass[documents]{monexamen}
%\setlength{\parindent}{0pt}

\usepackage{graphicx}
\usepackage{a4wide,amssymb,frenchle}
\usepackage[latin1]{inputenc} %% entr\'ee 8 bits iso-latin1
\usepackage[T1]{fontenc}      %% encodage 8 bits des fontes utilis\'ees

\newcommand{\f}{\ensuremath{\uparrow}}


\begin{document}

\entete{\'{E}cole Sup\'{e}rieure en Sciences
Informatiques}
{ }{04}{05}{Mathématiques  Discrètes\\ du 24 Janvier 2005}{Durée : 2 heures}% \
%{Probabilit\'{e}s}{02}{03}{du 1er Avril  2003 }
\\
\addtolength{\evensidemargin}{-1cm}
\addtolength{\oddsidemargin}{-1cm}
\reversemarginpar{ 

\begin{tabular}{l|l}
1 &  \ \  \\\hline
2 &   \\\hline
3 &   \\\hline
4 &   \\\hline
5 &    \\

\end{tabular}
}
\\


Tous documents autorisés. Toutes vos réponses doivent être prouvées. Si vous pensez que le texte d'une question est ambigu, faites une hypothèse raisonable et écrivez la sur votre copie. Le barême, donné à titre indicatif, tiendra compte de la qualité de la rédaction.


\section {Définition inductive d'un ensemble de mots [4 points]}
On considère l'ensemble $M$ des mots sur l'alphabet $\{a,b,c \}$ tels que 
%% les suites (maximales) de $c$ consécutifs soient toujours de longueur paire.
toutes les suites (maximales) de $c$ consécutifs soient de longueur paire.
 Ainsi, le mot $abccccbaccaa$ est un mot de $M$ , mais le mot $aaccbbcccba$ n'est pas un mot de $M$.
On considère l'ensemble $E$ défini inductivement par :
\begin{itemize}
\item $\epsilon \in E$
\item Si $m \in E$, alors $am \in E$
\item Si $m \in E$, alors $bm \in E$
\item Si $m \in E$, alors $ccm \in E$
\end{itemize}
\begin{enumerate}
\item A-t-on $M$ inclus dans $E$?
\begin{copie}
  \lignes{7}
\end{copie}
\item A-t-on $E$ inclus dans $M$?
\begin{copie}
  \lignes{7}
\end{copie}
\item Le schéma définissant $E$ est-il libre?
\begin{copie}
  \lignes{7}
\end{copie}
\item Trouver et résoudre une relation de récurrence permettant de compter le nombre de mots de longueur $n$ appartenant à $E$.
\begin{copie}
  \lignes{10}
\end{copie}
\end{enumerate}

\section{Tours de Hanoï, avec trois piquets dont un piquet central [4 points]}
On considère une variante des tours de Hanoï avec trois piquets A,B,C et n disques.
\begin{itemize}
\item
	les n disques sont de tailles différentes
\item initialement les n disques sont rangés sur un des piquets X, du plus grand en bas, au plus petit en haut
\item on désire amener les n disques dans le même ordre sur un autre piquet Y
\item on ne peut déplacer qu'un seul disque à la fois
\item on ne peut pas poser un disque sur un disque de taille inférieure
\item tous les déplacements de disque doivent se faire via le piquet central (un déplacement direct entre les deux piquets extérieurs est interdit)
\end{itemize}

On rappelle que si X et Y sont les piquets extérieurs, le nombre minimum de déplacements pour transporter n disques entre X et Y est de $3^n -1$.

On suppose que moveExterieurToCentral(n,X) (que vous pourrez noter mE2C(n,X) pour abréger) déplace de manière optimale une tour de hauteur n d'un piquet extérieur X vers le piquet central.
De même, moveCentralToExterieur(n,X) (que vous pourrez noter mC2E(n,X) pour abréger) déplace de manière optimale une tour de hauteur n du piquet central vers un piquet extérieur X. 
\begin{enumerate}
\item
Déterminer, prouver et résoudre les équations de récurrence permettant de calculer la complexité de ces deux méthodes.
\begin{copie}
  \lignes{32}
\end{copie}
\item
En déduire que l'algorithme suivant est optimal
\begin{verbatim}
moveExterieurToExterieur(n, initial, final){
  if (n>0){  
        mE2C(n-1, initial);
        mC2E(n-1, final);
        moveDisque(initial, central);
       	mE2C(n-1, final);
        mC2E(n-1, initial);
        moveDisque(central, final);
        mE2C(n-1, initial);
        mC2E(n-1, final);
        }	
  }

\end{verbatim}
\begin{copie}
\lignes{18}
\end{copie}
\end{enumerate}


\section{Tours de Hanoï, avec quatre piquets [4 points]}
On suppose connue la méthode moveHanoi(n,initial, final, intermediaire) qui déplace de manière optimale  (c'est à dire avec $2^n -1$ mouvements de disques) une tour de Hanoi de hauteur n, d'un piquet initial vers un piquet final en utilisant un seul piquet intermédiare avec comme contraintes :
\begin{itemize}
\item les n disques sont de tailles différentes
\item initialement les n disques sont rangés sur un piquet initial, du plus grand en bas, au plus petit en haut
\item on désire amener les n disques dans le même ordre sur un piquet final
\item on ne peut déplacer qu'un seul disque à la fois
\item on ne peut pas poser un disque sur un disque de taille inférieure.
\end{itemize}

On suppose que l'on dispose d'un quatrième piquet. Pour chacune des stratégies suivantes, évaluer la compléxité en nombre de déplacements de disques, et déterminer la meilleure de ces stratégies.
\begin{itemize}
\item Stratégie 1 : Déplacer les n-2 plus petits disques vers l'un des piquets intermediaires, puis déplacer les 2 grands disques restant du piquet initial vers le piquet final (en utilisant le piquet intermediaire resté libre) , enfin déplacer les n-2 plus petits disques disques vers le piquet final.
\begin{copie}
  \lignes{15}
\end{copie}
\item Stratégie 2 : Déplacer les n-3 plus petits disques vers l'un des piquets intermediaires, puis déplacer les 3 grands disques vers le piquet final (en utilisant le piquet intermediaire resté libre) , enfin déplacer les n-3 disques vers le piquet final.
\begin{copie}
  \lignes{15}
\end{copie}
\item Stratégie 3 : Déplacer les n/2 plus petits disques vers l'un des piquets intermediaires, puis déplacer les n/2 grands disques vers le piquet final (en utilisant le piquet intermédiaire resté libre), enfin déplacer les n/2 petits disques vers le piquet final.
\begin{copie}
  \lignes{15}
\end{copie}
\item Meilleure stratégie parmi les trois? 
\begin{copie}
  \lignes{8}
\end{copie}
\end{itemize}
Question facultative : avez-vous une meilleure stratégie ?
\begin{copie}
  \lignes{20}
\end{copie}


\section{Listes d'entiers [4 points]}
On considère des listes d'entiers $L_E$, définies inductivement par : 
\begin{itemize}
\item  $liste\_vide \in L_E$
\item Si $l \in L_E$ et $ e \in E$, alors $cons(e,l) \in L_E$
\end{itemize}
%%
On rappelle que les fonctions $car(l)$ et $cdr(l)$ sont définies sur les listes non vides par :

Si $l=cons(e,l')$, $car(l) = e$ et $cdr(l) = l'$



 On dit qu'une liste $l$ est croissante, si elle est vide ou réduite à un seul élément ou sinon si $car(l)$ est inférieur ou égal à tous les éléments de $cdr(l)$, et $cdr(l)$ est elle même une liste croissante. 
%%
Si de plus il n'y a pas deux éléments consécutifs égaux de la liste $l$, $l$ est strictement croissante.
 
 Soit $LC_E$ le sous ensemble de $L_E$ constitué des listes croissantes, et $LSC_E$ le sous-ensemble de $LC_E$ constitué des listes strictement croissantes.
 
 Donner une définition {\it récursive} des fonctions suivantes et déterminer la complexité de chacune de ces fonctions, 
en supposant que $car$, $cdr$ et $cons$ 
%%
$estVide$ 
sont toutes en temps constant.

 \begin{enumerate}
 \item Croissante : $L_E \rightarrow \{vrai, faux \}$
 
 Cette fonction retourne vrai si et seulement si la liste considérée est croissante
 \begin{copie}
  \lignes{12}
\end{copie}
\item  Simplifiée : $LC_E  \rightarrow LSC_E$ 

Cette fonction retourne une liste où les répétitions ont été éliminées (donc une liste strictement croissante)
\begin{copie}
  \lignes{12}
\end{copie}
\item Fusion : $LC_E \times LC_E \rightarrow LC_E$

Cette fonction 
%% fusionne deux listes triées en une seule.
retourne une liste de $LC_E$ qui est la fusion des deux listes triées. 
\begin{copie}
  \lignes{12}
\end{copie}
\item Intersection : $LSC_E \times LSC_E \rightarrow LSC_E$

Cette fonction retourne une liste de $LSC_E$ contenant les éléments qui sont dans les deux listes.
\begin{copie}
  \lignes{12}
\end{copie}
\end{enumerate}


\section {\'Equations de récurrence [4 points]}
Donnez l'ordre de grandeur des solutions des équations de récurrence suivantes :
\begin{enumerate}
\item $u_n= 6 u_{n-1} -8u_{n-2} + 3^n$
\begin{copie}
  \lignes{12}
\end{copie}
\item  $v_n= 6 v_{n-1} -8v_{n-2}+4^n$
\begin{copie}
  \lignes{12}
\end{copie}
\item  $w_n= 6 w_{n-1} -8w_{n-2}+2^n $
\begin{copie}
  \lignes{12}
\end{copie}
\item  $x_n= 6 x_{n-1} -9x_{n-2}+3^n $
\begin{copie}
  \lignes{12}
\end{copie}
\end{enumerate}



\end{document}