\documentclass[documents]{examen}
%\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{Ecole Polytech' Nice Sophia }
{ }{05}{06}{Math\'{e}matiques  Discr\`{e}tes\\ du 30 Novembre 2005}{Durée : 1 heure}% \
%{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 &   \\\hline
6 &   \\

\end{tabular}
}
\\

Aucun document autorisé.

Toutes vos réponses doivent être justifiées par une démonstration ou un contre-exemple.
Si vous pensez que le texte d'une question est ambigu (voire erroné) faites une hypothèse raisonnable et écrivez la sur votre copie.



On supposera que si $m$ est un mot, on dispose de la méthode $m.vide()$ qui retourne vrai si et seulement si le mot est vide, et que si $m$ est un mot non vide , on dispose des méthodes $m.premiereLettre(),$ $m.derniereLettre(),$ $ m.debutMot(),$ $m.finMot()$, $m.longueur()$ qui retournent respectivement la premiere lettre de $m$, la dernière lettre de $m$, le mot $m$ privé de sa dernière lettre, le mot $m $ privé de sa première lettre, la longueur de m . Si vous le souhaitez vous pouvez racourcir l'écriture des noms de ces méthodes en $m.pL(),$ $m.dL(),$ $m.fM(), $ $m.dM()$, $m.l()$.On dispose aussi de la méthode $m.concat(m')$ qui retourne le mot $mm'$ et la methode l.toMot() qui retourne le mot composé de la seule lettre $l$.



\section {Définitions inductives \small[4 points]}

Soit $P$ le sous ensemble des mots binaires, composés des mots admettant un nombre pair de "1" et de "0".

Soit $E$ l'ensemble défini inductivement par 

Base : $\epsilon \in E$

Règles :

$m \in E \rightarrow 00m \in E$

$m \in E   \rightarrow m00 \in E$

$m \in E   \rightarrow m11 \in E$

$m \in E   \rightarrow 11m \in E$

$m \in E \rightarrow 1m1 \in E$

$m \in E \rightarrow 0m0 \in E$

$m \in E \rightarrow 01m01 \in E$

$m \in E \rightarrow 10m10 \in E$

Montrez que $P$ est inclus dans $E$.

\begin{solution}
\begin{itemize}
\item Montrons par récurrence sur k que tout mot de  $P$ de longueur inférieure ou égale à $k$ appartient à $ E$ 

Pour $k$ = 0 c'est vrai.
Supposons l'hypothèse vraie au rang $k$ et soit $m$ un mot de $P$ de longueur $k+1$.
Si $m$ commence par 0 alors 
\begin{itemize}
\item
s'il termine par 0, il s'écrit $0m'0$ et  $m'$  appartient à $P$. Par hypothèse de récurrence $m'$ est donc dans $E$ et par définition de $E$, on a donc $m$ dans $E$.
\item sinon il termine par 1 et s'écrit $0m'1$. m' ne peut pas être vide, sa première lettre est soit 0 soit 1.


\begin{itemize}
\item
si m' commence par 0, alors  $m= 00m"1$ et  $m"1$  appartient à $P$. Par hypothèse de récurrence $m"1$ est donc dans $E$ et donc par définition de $E$ on a  $m$ dans $E$.
\item sinon $m=01m"1$, m" ne peut pas être vide, sa dernière lettre est soit 0 soit 1.
\begin{itemize}
\item
si m" termine par 0, alors  $m= 01p01$ et  $p$  appartient à $P$. Par hypothèse de récurrence $p$ est donc dans $E$ et donc par définition de $E$ on a  $m$ dans $E$.
\item sinon $m=01p11$, et $01P$appartient à $P$. Par hypothèse de récurrence $p$ est donc dans $E$ et donc par définition de $E$ on a  $m$ dans $E$.
\end{itemize} 

\end{itemize} 


\end{itemize} 
Le cas où $m$ commence par 1 se traite de manière analogue
 \end{itemize}


\end{solution}
\begin{copie}
\lignes{33}
\end{copie}
\section {Désaccentuation  \small[3 points]}
Soit $A$ l'alphabet usuel a 26 lettres, soit $A_{acc} = A \cup \{$é,è,ê$\}$. Donner une définition inductive de la fonction  de $A_{acc}^*$ dans $A^*$ qui remplace toutes les  occurences d'un e accentué par un e.

Donner aussi un code récursif.

\begin{solution}

{\it
 \begin{itemize}
 \item $enleveAccent(\epsilon) = \epsilon $
 \item $enleveAccent(a.m) =a.enleveAccent(m) $, si $a \notin $ {é,è,ê}
 \item $enleveAccent(a.m) =e.enleveAccent(m) $, sinon

 \end{itemize}
 }
 \begin{verbatim}
 
 public mot enleveAccent (mot m){
 	if (m.vide()) {return m ;}
 	if m.pL()== 'é' ||m.pL()='è' ||m.pL='ê' {return 'e'.toMot().concat(m.fM())}
 	else return m.pL().toMot().concat(m.fM().enleveAccent()) ;
}
 \end{verbatim}							   


\end{solution}
\begin{copie}
\lignes{32}
\end{copie}

\section {Palindrome \small[3 points]}



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.


 
\begin{copie}
\lignes{30}
\end{copie}

\begin{solution}
{\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().toMot().concat(fairePalindrome(m.fM())).concat(m.pL().toMot()) ;
}
 \end{verbatim}							   
\end{solution}

\section { Prefixe \small[3 points]}
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.


\begin{copie}
\lignes{31}
\end{copie}



\begin{solution}
{\it
 \begin{itemize}
 \item $Prefixe(\epsilon , m') = vrai $
 \item Si $m \neq \epsilon, $ $Prefixe(m, \epsilon ) = faux $
  \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{solution}
\section { Facteur \small[4 points]}
Soit $A$ un alphabet, définir inductivement la fonction

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

telle que $Facteur (m,m')$ est vraie si et seulement si $m$ est un facteur  de $m'$, c'est à dire s'il existe un prefixe $p$ de $m'$ et un suffixe $s$ de $m'$ tels que $m'=pms$.
Vous pouvez utiliser toutes les fonctions définies aux questions précédentes. 


Donner aussi un code récursif.


\begin{copie}
\lignes{30}
\end{copie}



\begin{solution}
{\it
 \begin{itemize}
 \item $Facteur(\epsilon , m') = vrai $
 \item Si $m \neq \epsilon, $ $Facteur(m, \epsilon ) = faux $
  \item $Facteur(am,bm')=((a=b)$ et $Prefixe(m,m')) $ ou $Facteur(am,m')$
 \end{itemize}
 }
 \begin{verbatim}
public boolean facteur (mot m, mot m'){
	if (m.vide()) {return true ;}
	if (m'.vide()) {return false ;}
	return (m.pL()==m'.pL())&& prefixe(m.fM(),m'fM())||facteur(m,m'.fM());
}
\end{verbatim}
\end{solution}
 \section {SousMot \small[3 points]}
Soit $A$ un alphabet, définir inductivement la fonction

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

telle que $SousMot(m,m')$ est vraie si et seulement si $m$ peut être obtenu à partir de $m'$ en supprimant certaines lettres de $m'$ pas necessairement consécutives. Ainsi,SousMot(exemple, elxeerrrmddprsleee)=vrai alors que SousMot (exemple, ekxksmple)= faux


Donner aussi un code récursif.


\begin{copie}
\lignes{30}
\end{copie}



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

\end{document}
