\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 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).
\begin{copie}
  \lignes{15}
\end{copie}
\item	Le sch\'{e}ma que vous avez donn\'{e} \`{a} la question 1. est -il libre ?

\begin{copie}
  \lignes{8}
\end{copie}
\end{enumerate}

\section{auto inverse [3 points]}
On consid\`{e}re la fonction s de A* dans A* d\'{e}fini 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{copie}
  \lignes{15}
\end{copie}

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

\item	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{copie}
  \lignes{12}
\end{copie}
\item	Donner une d\'{e}finition inductive de l'\'{e}criture d'un entier en base 3
 \begin{copie}
  \lignes{12}
\end{copie}
\item	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{copie}
  \lignes{12}
\end{copie}
\end{enumerate}
 

\section{Soustraction [4 points]}
\begin{enumerate}
\item 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{copie}
  \lignes{12}
\end{copie}
\item	
	Donner une d\'{e}finition inductive de la fonction soustrait de E dans N, telle que soustrait((m,n))=m-n .

\begin{copie}
  \lignes{12}
\end{copie}
 
\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
Dessiner un arbre de hauteur 5 et de largeur 4.
\begin{copie}
  \lignes{10}
\end{copie}
\item	Donner une d\'{e}finition de la largeur d'un ABD utilisant l'induction
\begin{copie}
  \lignes{20}
\end{copie}
 
\end{enumerate}

\end{document}
