\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èsen raisonable et écrivez la sur votre copie.


\section {}
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. Ainsi, le mot $abccccbaaa$ est un mot de $M$ , mais le mot $aabbcccba$ 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 Trouvez et résoudre une relation de récurrence permettant de compter le nombres de mots de longueur $n$ appartenant à $E$
\begin{copie}
  \lignes{10}
\end{copie}
\end{enumerate}

\section{}
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 mouvements de disques doivent se faire via le piquet central (un déplacement direct dentre les deux piquets no centraux est interdit)
\end{itemize}

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

On suppose que Move\_non\_central\_to\_central(n,X) déplace de manière optimale une tour de hauteur n d'un piquet non central X vers le piquet central? et que Move\_non\_central\_to\_central(n,X) déplace de manière optimale une tour de hauteur n du piquet central vers un piquet non central 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{20}
\end{copie}
\item
En déduire que l'algorithme suivant est optimal
\begin{verbatim}
Move_non_central_to_non_central (n, initial, final){
  if (n>0){  Move_non_central_to_central(n-1, initial);
             Move_central_to_non_central(n-1,final);
             Move_disque(initial, central);
             Move_non_central_to_central(n-1, final);
             Move_central_to_non_central(n-1,initial);
             Move_disque(central, final);
             Move_non_central_to_central(n-1, initial);
             Move_central_to_non_central(n-1,final)
						 }
}
\end{verbatim}
\begin{copie}
\lignes{10}
\end{copie}
\end{enumerate}
\section{}
On suppose connue la méthode Move\_Hanoi(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 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 n/2 disques vers l'un des piquets intermediaires, puis déplacer les n/2 grands disques vers le piquet final (en utilisant le piquet intermediaire resté libre) , enfin déplacer les n/2 petits disques vers le piquet final.
\begin{copie}
  \lignes{15}
\end{copie}
\end{itemize}
Question facultative : avez vous une meilleure stratégie ?
\begin{copie}
  \lignes{20}
\end{copie}
\section{}
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 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.
 
 Soit $LC_E$ le sous ensemble de $L_E$ constitué des seules listes croissantes, et $LSC_E$ le sous-ensemble de $LC_E$ constitué des listes strictement croissantes.
 
 Donner une définition inductive des fonctions suivantes et déterminez la complexité de chacune de ses fonctions, en supposant que car, cdr et cons 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{6}
\end{copie}
\item  Simplifier : $LC_E  \rightarrow LSC_E$ 

Cette fonction retourne une liste où les doublons ont été éliminés (donc une liste strictement croissante)
\begin{copie}
  \lignes{6}
\end{copie}
\item Fusion: $LC_E \times LC_E \rightarrow LC_E$

Cette fonction fusionne deux listes triées en une seule. 
\begin{copie}
  \lignes{6}
\end{copie}
\item Extraire : $LSC_E \times LSC_E \rightarrow LSC_E$

Cette fonction extrait de la première liste  les éléments qui sont à la fois dans la première et dans  la seconde liste.
\begin{copie}
  \lignes{6}
\end{copie}
\end{enumerate}


\section {}
Donnez l'ordre de grandeur des solutions des équations de récurrences suivantes :
\begin{itemize}
\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}
\end{itemize}



\end{document}