\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\'{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}
\reversemarginpar{ 

\begin{tabular}{l|l}
1 &  \ \  \\\hline
2 &   \\\hline
3 &   \\\hline
4 &   \\\hline
5 &   \\\hline
6 &   \\

\end{tabular}
}
\\

Les solutions de ces exercices seront publiées sur la page web du cours de Mathématiques Discrètes, à partir de demain matin.


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'$.

On pourra utiliser la fonction $\Sigma$ vue en cours, telle que si m et m' sont deux ecritures binaires, $\Sigma(m,m')=m"$ si et seulement si $m"$ est l'ecriture binaire de $val(m)+val(m')$




\section {}
On veut définir de façon inductive une fonction inductive de $E$ dans $F$. Que doit on connaître sur $E$? 

\begin{copie}
\lignes{4}
\end{copie}
\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.

\begin{copie}
\lignes{16}
\end{copie}

\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.

\begin{copie}
\lignes{16}
\end{copie}

\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}
\lignes{16}
\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.


 
\begin{copie}
\lignes{16}
\end{copie}



\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.


\begin{copie}
\lignes{16}
\end{copie}



\end{document}