\documentclass[documents]{monexamen}
%\documentclass[documents]{monexamen}
%\setlength{\parindent}{0pt}
\usepackage{a4wide,amssymb,frenchle}



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


\begin{document}

\entete{\'{E}cole Sup\'{e}rieure en Sciences
Informatiques}
{ }{03}{04}{Math\'{e}matiques Discr\`{e}tes \\ du 21 Novembre 2004}{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}
}
\\
\begin{copie}%
  \textsf{{\small Il vous est
      demand\'{e} de r\'{e}pondre sur la copie avec clart\'{e}, concision et
      rigueur.  Certaines r\'{e}ponses peuvent
      \^{e}tre beaucoup plus courtes que le nombre de lignes pourrait le
      laisser supposer. Le bar\^{e}me est donn\'{e} \`{a} titre indicatif.\\
   }}
\end{copie}


\section{acb, abcca, mais pas aacccb [4 points]}
Soit A = \{a,b,c\}. 
\begin{enumerate}

\item {\it Donner et prouver une d\'{e}finition inductive de  L, le sous ensemble de A*, form\'{e} des mots contenant autant de a que de c (le nombre de b est quelconque).}

  Une définition possible parmi d'autres:
  
  Soit $E$ l'ensemble défini inductivement par
  
  Base : $\epsilon$ et $b$ appartiennent à $E$
  
  Règles : 
  \begin{itemize}
  	\item $R1$ :Si $m$ est dans  $E$ alors $amc$  est dans $E$
  	\item $R2$ :Si $m$ est dans  $E $ alors  $mca$ est dans $E$
  	\item $R3$ :Si $m$ et $m'$ sont dans $E$, alors $mm'$ est dans $E$.
  \end{itemize}
  
  Montrons que $E=L$
 
  	{\bf Version courte}
  	\begin{itemize}
 			\item il est clair que $E$ est inclus dans $L$, car tous les éléments de la base de $E$ ont autant de a que de c et que ceci est conservé par chacune des trois règles.
 
 			\item $L$ inclus dans $E$
 
 Par récurrence sur la longueur des mots.  
$ HR(k)$ : Tout mot de $L$ de longueur inférieure ou égale à $k$ appartient à $E$.

Comme $\epsilon$ est $L$ et $E$, $ HR(0)$ est bien vérifiée.

Montrons $ HR(k+1)$ en supposant $ HR(k)$. Soit $m$, un mot quelconque de longueur $k+1$, on a alors deux cas et deux seulement (déjà fait en TD et se voit "clairement" en utilisant le compteur habituel, $m.nombreDe(a) - m.nombreDe(c)$)  :
			\begin{itemize}
			\item $m = ps$ avec $p$ et $s$ différents du mot vide, et $p$ et $s$ sont dans  $L$ : par hypothèse de récurrence et utilisation de $R3$, $m$ est dans $E$
			\item sinon : $m = am'c$ ou $m = cm'a$ avec $m'$ appartient à $L$, auquel cas par hypothèse de récurrence et utilisation de $R1$ ou $R2$, $m$ est dans $E$ 
			\end{itemize}
		\end{itemize} 
		
  	{\bf Version longue}
  
  \begin{itemize}
  	\item $E$ est inclus dans $L$ 
  
  Par induction structurelle :  Les élements de la base de $E$ contiennent autant de a que de c. Les règles $R1$ et $R2$ préservent la propriété "avoir autant de a que de c" puisqu'elles ajoutent un a et un c. La règle $R3$ aussi, le mot $mm'$ ayant un nombre de a (resp. de c) égal à la somme du nombre de a (resp. de c) de $m$ et de $m'$.
  
  	\item $L$ inclus dans $E$
  
  Par récurrence sur la longueur des mots. 
  
 		$ HR(k)$ : Tout mot de $L$ de longueur inférieure ou égale à $k$ appartient à $E$
  	
  	\item Base: $k=0$. Le seul mot de $L$ de longueur 0 est $\epsilon$, ce mot est bien dans $E$
 		\item Propagation: Supposons $HR(k)$ vrai. Soit $m$ un mot de $ L$ de longeur $k+1$.
  Un et un seul de ces trois cas est toujours vrai : $ m $ commence par un a, un b ou un c.
  				\begin{enumerate}
  				\item $m=bm$ Puisque $m$ est dans $L$, $m'$ est dans $L$. Par $HR(k)$, $m'$ est dans $E$, par $R3$ (b est dans $E$), $m $ est dans $E$
  				\item $m=am'$. Puisque $m$ est dans $L$, $m$ a au moins deux lettres, on peut donc considérer la dernière lettre de $m$.
  						\begin{itemize}
 	 							\item $m=am'c$. Puisque $m$ est dans $L$, $m'$ est dans $L$. Par $HR(k)$, $m'$ est dans $E$, par $R1$, $m$ est dans $E$.
  
  							\item  $m=am'a$. Introduisons le compteur habituel.... un a vaut 1, un b 0 et un c vaut -1. Ce compteur vaut 1 sous la premiere lettre de a, 0 à la fin de $m$, et -1 à l'avant dernière position. Il s'annule donc quelque part entre la premiere et l'avant dernière lettre.  Il existe donc un prefixe $p$ de $ m$  qui appartient à $L$. Soit $s$ tel que $m=ps$. Puis que $p$ et $m$ sont dans $L$, $s$ est dans $  L$. Par $HR(k)$, $p$ et $s$ sont dans $E$. Donc par $R3$, $m$ est dans $E$.
  							\item m=am'b. Puisque m est dans L, am' est dans L. Par HR(k), am' est dans E, par R3, m est dans E
  						\end{itemize}
  				\item m=cm' Se traite comme le cas précédent.
  				\end{enumerate}
  \end{itemize}
  
  
 
  	
  	
  

\item	{\it Le sch\'{e}ma que vous avez donn\'{e} \`{a} la question 1. est -il libre ?}

Non par exemple, le mot "b" qui est  dans la base, peut aussi être obtenu par la règle $R3$  
\end{enumerate}

\section{auto inverse [3 points]}
{\it On consid\`{e}re la fonction $s$ de $A*$ dans $A*$ d\'{e}finie inductivement par
		$$	s(\epsilon )= \epsilon$$
et pour tout m de A*
		$$	s(ma)=cs(m)$$
		$$	s(mb)=bs(m)$$
		$$	s(mc)=as(m).$$


Montrer que pour tout m de A*, s(s(m))=m}

\begin{itemize}
  \item On montre par induction que pour tout $m$ de $A*$
        $$    s(am)=s(m)c$$
        $$    s(bm)=s(m)b$$
        $$    s(cm)=s(m)a.$$
C'est vrai si $m$ est le mot vide. Montrons que si c'est vrai pour $m$, alors c'est vrai pour (par exemple) $mc$:
$s(amc) = as(am) = as(m)c = s(mc)c$
On nomtrerait de même que $    s(bmc)=s(mc)b$ et $    s(cmc)=s(mc)a$

		
		
  \item Montrons que pour tout $m$ de $A*$, $s(s(m))=m$, par induction structurelle
  \begin{itemize}
  \item Base $s(s(\epsilon))=\epsilon$
  \item Supposons que $s(s(m))=m$, alors
  $s(s(am))=s(s(m)c)=as(s(m))=am$, de même $s(s(bm))=bm$ et $s(s(cm))=cm$
  \end{itemize}
\end{itemize}

\section{N encore [5 points]}
\begin{enumerate}

\item	{\it En vous inspirant des d\'{e}finitions de N vues en TD, donner une d\'{e}finition inductive de N qui permette de d\'{e}finir facilement et inductivement  l'\'{e}criture d'un entier en base 3.}
 \begin{itemize}
  \item Base 0, 1 et 2 sont dans N
  \item Si $n$ est dans N et $n \neq 0$, alors 3n  , 3n+1 et 3n+2 sont dans N
\end{itemize}

Preuve : la même que pour l'exercice du TD. Note la condition $n \neq 0$ est indispensable pour assurer un schéma libre
\item	{\it Donner une d\'{e}finition inductive de l'\'{e}criture d'un entier en base 3}
 \begin{itemize}
  \item Base ecriture(0)=0, ecriture(1)=1, ecriture(2)=2,
  \item Induction : Si $n \neq 0$, ecriture(3n)=ecriture(n).0,
  ecriture(3n+1)=ecriture(n).1,
  ecriture(3n+2)=ecriture(n).2
\end{itemize}
\item	{\it Soit f la fonction qui associe \`{a} tout entier non nul la longueur de son \'{e}criture en base 3. Donner une d\'{e}finition inductive de f }
 \begin{itemize}
  \item Base f(0)=1, f(1)=1, f(2)=2,
  \item Induction : Si $n \neq 0$, f(3n)=f(n)+1,
  f(3n+1)=f(n)+1,
  f(3n+2)=f(n)+2
\end{itemize}
\end{enumerate}
 

\section{Soustraction [4 points]}
\begin{enumerate}
\item {\it Donner et prouver une d\'{e}finition inductive libre de l'ensemble 
		$$	E = \{(m,n) / (m,n) \in N^2 \ et\  m \geq n\}$$}
\begin{itemize}
 \item Base $(n,n) \in  E'$ pour tout $n$ de N
 \item $R$ Si $(m,n)$ appartient à $E'$, alors $(m+1,n)$ appartient à $E'$
\end{itemize}
Ce schéma est libre.
\item	
{\it	Donner une d\'{e}finition inductive de la fonction soustrait de E dans N, telle que soustrait((m,n))=m-n .}

\begin{itemize}
 \item Base $soustrait((n,n))=0$  \item  $soustrait((m+1,n)) = soustrait((m,n))+1$
\end{itemize}
\end{enumerate}

\section{ABD en long et en large cette fois [4 points]}
En reprenant la d\'{e}finition vue en TD des arbres binaires ABD, on appelle largeur d'un arbre binaire ABD, le nombre maximum de noeuds ($\epsilon$ ou "rond") situ\'{e}s sur une m\^{e}me ligne de la repr\'{e}sentation graphique de l'arbre.
\begin{enumerate}
\item
{\it Dessiner un arbre de hauteur 5 et de largeur 4.}
\begin{copie}
  \lignes{10}
\end{copie}
\item	{\it Donner une d\'{e}finition de la largeur d'un ABD utilisant l'induction}

On défini inductivement la fonction largeurligne de ABDxN dans N de la manière suivante

\begin{itemize}
\item largeurligne(T,1)=1
  \item Si $i> hauteur(T)+1$ alors largeurligne(T,i)=0
  \item $largeurligne(T,i)=largeurligne (filsgauche(T),i-1)+largeurligne(filsdroit(T),i-1))$
\end{itemize}

On a alors $largeur(T) = Max _{1\leq i\leq hauteur(T)+1 } largeur(T,i)$

 
\end{enumerate}

\end{document}
