\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
\usepackage{url}
\newcommand{\f}{\ensuremath{\uparrow}}

\begin{document}
\entete{\'{E}cole Sup\'{e}rieure en Sciences
Informatiques}
{ }{04}{05}{Math\'{e}matiques  Discr\`{e}tes\\ du 4 Novembre 2004}%{Dur\'{e}e : 55  minutes}% \
%{Probabilit\'{e}s}{02}{03}{du 1er Avril  2003 }
\\
\addtolength{\evensidemargin}{-1cm}
\addtolength{\oddsidemargin}{-1cm}
\\
\section {}
On veut définir de façon inductive une fonction inductive de $E$ dans $F$. Que doit on connaître sur $E$? 

{\it
 Il faut connaître un schéma inductif libre définissant $E$.
}

\section{}
Soit $EcrituresBin$ l'ensemble des ecritures en base $2$ (sans zéro inutile en tête).

Définir inductivement la fonction (sans faire appel à la fonction $val$)

$Suivant: EcrituresBin  \rightarrow EcrituresBin$

telle que $Suivant(m)$ soit l'écriture binaire de $val(m)+1$

Donner aussi un code récursif.
{\it
\begin{itemize}
  \item $Suivant(0)=1$
  \item $Suivant(1)=2$
  \item Pour $m \neq 0,$ $Suivant(m0)=m1$
  \item Pour $m \neq 0,$ $Suivant(m1)=Suivant(m)0$
\end{itemize}

Pour le code recursif voir \url{EcritureBinaire.java} 
}

\section {}


Définir inductivement la fonction (sans faire appel à la fonction val)

$Sup :\{0,1\}^* $ x $\{0,1\}^* \rightarrow \{vrai, faux\}$

telle que $Sup(m,m')$ est vraie si et seulement si $val(m) \geq val(m')$


Donner aussi un code récursif.
{\it
\begin{itemize}
	\item Sup(m,$\epsilon$)= vrai
  	\item Sup($\epsilon$,1m')= faux
  	\item Sup($\epsilon$,0m')= faux % Sup($\epsilon$,m')

  	\item Sup(0m,0m')=Sup(m,m')
   
  	\begin{itemize} 
  		\item Sup(0m,1m')= faux si longueur (m)$\leq$ longueur (m')
  		\item Sup(0m,1m')= Sup(m,1m) si longueur (m)> longueur (m')
  	\end{itemize}

  	\begin{itemize} 
  		\item Sup(1m,0m')= vrai si longueur (m)$\geq$longueur (m')
  		\item Sup(1m,0m')= Sup(1m,m') si longueur (m)<longueur (m')
  	\end{itemize}

	\begin{itemize} 
  		\item Sup(1m,1m')= faux si longueur (m)< longueur (m')
  		\item Sup(1m,1m')= vrai si longueur (m)> longueur (m')
  		\item Sup(1m,1m')= Sup(m,m') si longueur (m)= longueur (m')
  	\end{itemize}
  
\end{itemize}
Deuxième solution
\begin{itemize}
\item Sup(m0,m'0)=Sup(m,m')
\item Sup(m1,m'1)=Sup(m,m')
\item Sup(m0,m'1)=Sup(m,suivant(m'))
\item  Sup(m1,m'0)=Sup(m,m')
\item Sup (m,$\epsilon$)= vrai
\item Sup($\epsilon$,m1)=faux
\item Sup ($\epsilon$,m0)=Sup($\epsilon$,m)
\end{itemize}
Troisième solution valable sur l'ensemble $EcrituresBin \times EcrituresBin$ et non sur $ \{0,1\}^*  \times \{0,1\}^* $.
\begin{itemize}
	\item Sup(m,0)= vrai

	\begin{itemize} 
		\item Sup(m,suivant(n))= faux si m = n
		\item Sup(m,suivant(n))= Sup(m,n) sinon
	\end{itemize}
\end{itemize}
en utilisant le schéma suivant
\begin{itemize}
\item Base = \{(0,0)\}
\item (m,0) $\rightarrow $(suivant(m),0)
\item (m,n) $\rightarrow $(m,suivant(n))
\end{itemize}
\begin{verbatim}

		code laissé à l'imagination du lecteur....
\end{verbatim}

NB. Il est clair que cette question n'était pas très facile et il en a été tenu compte lors de la correction.
	
}

\section{}
Définir inductivement la fonction (sans faire appel à la fonction val)

$Mul: EcrituresBin$ x $EcrituresBin \rightarrow EcrituresBin$

telle que $mul(m,m')$ soit l'ecriture binaire de $val(m)*val(m')$


Donner aussi un code récursif.
\begin{copie}
  {\it
\begin{itemize}
  \item  $Mul(m,0)= 0$
  \item  $Mul(m,1)=m$
  \item Pour $m' \neq 0$, $Mul(m,m'0)=Mul(m,m')0$
  \item Pour $m' \neq 0$, $Mul(m,m'1)=\Sigma (Mul(m,m')0, m)$
\end{itemize}
Pour le code recursif voir \url{EcritureBinaire.java} 
}
\end{copie}



\section{}
Soit $A$ un alphabet, définir inductivement la fonction

$fairePalindrome : A^* \rightarrow A^*$

telle que $fairePalindrome(m)$ est le mot palindrome dont la moitié gauche est $m$. Par exemple, $fairePalindrome(abc)=abccba$


Donner aussi un code récursif.


 {\it
 \begin{itemize}
 \item $fairePalindrome(\epsilon) = \epsilon $
 \item $fairePalindrome(am) =amfairePalindrome(m)a$
 \end{itemize}
 }
 \begin{verbatim}
 
 public mot fairePalindrome (mot m){
 	if (m.vide()) {return m ;}
 	return m.pL().concat(fairePalindrome()).concat(m.pL()) ;
}
 \end{verbatim}							   


\section {}
Soit $A$ un alphabet, définir inductivement la fonction

$Prefixe : A^* x A^* \rightarrow \{faux, vrai\}$

telle que $Prefixe (m,m')$ est vraie si et seulement si $m$ est un prefixe de $m'$.


Donner aussi un code récursif.

{\it
 \begin{itemize}
 \item $Prefixe(\epsilon , m') = vrai $
 \item Si $m \neq \epsilon, $ $Prefixe(m, \epsilon ) = \epsilon $
  \item $Prefixe(am,bm')=((a=b)$ et $Prefixe(m,m')) $
 \end{itemize}
 }
 \begin{verbatim}
public boolean prefixe (mot m, mot m'){
	if (m.vide()) {return true ;}
	if (m'.vide()) {return false ;}
	return (m.pL()==m'.pL())&& prefixe(m.fM(),m'fM());
}

\end{verbatim}
\end{document}