\documentclass[11pt]{article}
\usepackage[french]{babel}
\usepackage{amsfonts,amsmath,amssymb, epic, autograph}
\usepackage[all]{xy}
\pagestyle{empty}
\setlength{\oddsidemargin}{-5mm}
\setlength{\textwidth}{16 cm}
\setlength{\topmargin}{-10mm}
\setlength{\textheight}{24 cm}
\begin{document}

\parindent=0pt

%Num{\'e}rotation
\renewcommand{\thesection}{}
\renewcommand{\labelenumi}{\arabic{enumi})}
\renewcommand{\labelenumii}{\alph{enumii})}

%Macros
\renewcommand{\leq}{\,\leqslant\,}
\renewcommand{\geq}{\,\geqslant\,}
\newcommand{\set}[1]{\left \{ #1 \right \}}
\newcommand{\abs}[1]{\left | #1 \right |}
\newcommand{\systeme}[1]{\left \{ \begin{array}{l}  #1 \end{array} \right.}
\newcommand{\somme}[3]{\sum_{#1}^{#2}\limits{#3}}
\newcommand{\ceil}[1]{\left \lceil #1 \right \rceil}
\newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor}
\newcommand{\lxor}{\oplus}
\newcommand{\equivalent}[2]{\mathop{\sim}_{#1 \rightarrow #2} \limits}
%Portes logiques
\newcommand{\rectangle}[2]{\begin{picture}(#1,#2)
\put(0,0){\line(1,0){#1}}
\put(0,0){\line(0,1){#2}}
\put(#1,0){\line(0,1){#2}}
\put(0,#2){\line(1,0){#1}}
\end{picture}}

\newcommand{\Et}{\begin{picture}(10,7)
\put(2,0){\rectangle{6}{6}}
\put(0,2){\line(1,0){2}}
\put(0,4){\line(1,0){2}}
\put(8,3){\line(1,0){2}}
\put(3,2){ET}
\end{picture}}

\newcommand{\Ou}{\begin{picture}(10,7)
\put(2,0){\rectangle{7}{6}}
\put(0,2){\line(1,0){2}}
\put(0,4){\line(1,0){2}}
\put(9,3){\line(1,0){2}}
\put(3,2){OU}
\end{picture}}

\newcommand{\Xor}{\begin{picture}(10,7)
\put(2,0){\rectangle{9}{6}}
\put(0,2){\line(1,0){2}}
\put(0,4){\line(1,0){2}}
\put(11,3){\line(1,0){2}}
\put(3,2){XOR}
\end{picture}}

\newcommand{\Non}{\begin{picture}(10,7)
\put(0,3){\line(1,0){2}}
\put(6,3){\line(1,0){2}}
\put(4,3){\circle{4}}
\end{picture}}





\begin{center}{\Large Corrig{\'e}}\end{center}

\section{Exercice 1}

\begin{enumerate}
\item \begin{enumerate}
\item Pour un mot de longueur $1$ : $u = a \in \set{0, 1}$ :
\begin{itemize}
\item si $a = 0$, $a$ contient un nombre pair de $1$. Or l'automate s'arr{\^e}te sur 0 ;
\item si $a = 1$, $a$ contient un nombre impair de $1$. Or l'automate s'arr{\^e}te sur 1.
\end{itemize}

\textit{Hypoth{\`e}se de r{\'e}currence :} pour tout mot $u = a_{1}{\dots}a_{k}$ de longueur $k$, l'automate s'arr{\^e}te sur 0 (resp. sur 1) apr{\`e}s avoir lu $u$ lorsque celui-ci contient un nombre pair (resp. impair) de $1$.

Prenons un mot $u = a_{1}{\dots}a_{k+1}$ de longueur $k+1$. On peut appliquer l'hypoth{\`e}se de r{\'e}currence au mot $v = a_{1}{\dots}a_{k}$.

S'il y a un nombre pair de $1$ dans $v$, on est sur 0 apr{\`e}s l'avoir lu, et quand on lit $a_{k+1}$ :
\begin{itemize}
\item soit $a_{k+1} = 0$ : on reste sur 0 et il y a bien un nombre pair de $1$ dans $u$ ;
\item soit $a_{k+1} = 1$ : on passe sur 1 et il y a bien un nombre impair de $1$ dans $u$.
\end{itemize}

S'il y a un nombre impair de $1$ dans $v$, on est sur 1 apr{\`e}s l'avoir lu, et quand on lit $a_{k+1}$ :
\begin{itemize}
\item soit $a_{k+1} = 0$ : on reste sur 1 et il y a bien un nombre impair de $1$ dans $u$ ;
\item soit $a_{k+1} = 1$ : on revient sur 0 et il y a bien un nombre pair de $1$ dans $u$.
\end{itemize}

Dans tous les cas, l'hypoth{\`e}se de r{\'e}currence est v{\'e}rifi{\'e}e.

Ainsi, le mot $u$ est reconnu si et seulement si on s'arr{\^e}te sur 1, i.e. si et seulement si $u$ contient un nombre impair de $1$. \framebox{$\mathcal{A}$ reconna{\^i}t $L$}.

\item De la m{\^e}me fa{\c c}on, l'automate :
\begin{center}
\begin{picture}(50, 18)
\letstate A=(10,6) \drawinitialstate(A){0} \drawfinalstate[b](A){0}
\letstate B=(40,6) \drawstate(B){1}
\drawloop(A){$1$}
\drawloop(B){$1$}
\drawcurvededge(A,B){$0$}
\drawcurvededge(B,A){$0$}
\end{picture}
\end{center}
reconna{\^i}t le langage $L'$ constitu{\'e} des mots qui contiennent un nombre pair de $0$.
Alors \framebox{$M = L \cap L'$ est reconnaissable.}
\end{enumerate}


\item \begin{enumerate}
\item On a : $s = \lnot{a}$.
\begin{center}
\begin{picture}(15,5)
\put(0,3){$a$}
\put(3,1){\Non}
\put(12,3){$s$}
\end{picture}
\end{center}


\item Soit $u$ un mot de longueur $2^{n+1}$ que l'on coupe au milieu en deux mots de longueurs $2^{n}$ not{\'e}s $v$ et $w$ : $u = vw$.

On prend deux exemplaires du circuit $\mathcal{P}_{n}$ auxquels on envoie $v$ et $w$. Notons $s_{v}$ et $s_{w}$ leurs sorties respectives.

Alors si $s$ est la sortie de $\mathcal{P}_{n+1}$, on doit avoir :
$$s = {(s_{v} \lxor s_{w})}$$
o{\`u} $\lxor$ d{\'e}signe l'op{\'e}rateur \texttt{xor}.

\item Notons $p_{n}$ le nombre de portes utilis{\'e}es dans $\mathcal{P}_{n}$. On a alors :
$$p_{0} = 1 \hbox{ et } p_{n+1} = 2 p_{n} + 1$$
d'o{\`u} par une r{\'e}currence imm{\'e}diate \framebox{$p_{n} = \somme{k=0}{n}{2^{k}} = 2^{n+1}-1 \equivalent{n}{+{\infty}} 2^{n+1}$}.
\end{enumerate}

\item Supposons $N$ reconnaissable. D'apr{\`e}s le lemme de l'{\'e}toile,  il existe un entier $n {\geq} 1$ tel que, quel que soit le mot $w \in N$ de longueur sup{\'e}rieure ou {\'e}gale {\`a} $n$, $w$ admet une factorisation de la forme $w = u.x.v$ o{\`u} $u.x$ est de longueur au plus $n$, $x$ est non vide et $u.x^{*}.v$ est contenu dans $N$.

Prenons le mot $w = 1^{n}0^{2n}$. C'est bien un mot de $N$. Dans la factorisation pr{\'e}c{\'e}dente, $x$ doit {\^e}tre de la forme $1^{q}$ avec $q {\geq} 1$, donc $ux^{2}v = 1^{n+q}0^{2n}$ n'est plus un mot de $N$ : il y a contradiction.

Ainsi \framebox{$N$ n'est pas reconnaissable}.
\end{enumerate}



\section{Exercice 2}
\begin{enumerate}
\item \begin{itemize}
\item En Caml  : il faut {\'e}changer les termes d'indices $i+j$ et $n-1-j$ tant que $i+j < n-1-j$ donc pour $j$ variant de $0$ {\`a} $\floor{\dfrac{n-i-1}{2}}$. {\'E}crivons d'abord une fonction auxiliaire qui {\'e}change les termes d'indices $i$ et $j$ puis la fonction demand{\'e}e :
\begin{verbatim}
let echange d i j = let tampon=d.(i) in
  d.(i) <- d.(j) ;
  d.(j) <- tampon ;;

let retourne d i = for j=0 to (n-i-1)/2 do echange d (i+j) (n-1-j) done ;;
\end{verbatim}

\item En Pascal, le principe est le m{\^e}me :
\begin{verbatim}
PROCEDURE echange(VAR d : Pile ; i, j : INTEGER);
VAR tampon : INTEGER ;
    BEGIN
        tampon := d[i] ;
        d[i] := d[j] ;
        d[j] := tampon
    END;

PROCEDURE retourne(VAR d : Pile ; i : INTEGER);
VAR j : INTEGER ;
    BEGIN
         FOR i := 0 TO (n-i-1)/2 DO echange(d, i+j, n-1-j) ;
    END ;
\end{verbatim}
\end{itemize}
\item On fait deux affectations pour chaque appel {\`a} \texttt{echange}, et celle-ci est appel{\'e}e $\floor{\dfrac{n-i+1}{2}}$ fois, d'o{\`u} un co{\^u}t \framebox{$2 \floor{\dfrac{n-i+1}{2}}$}.

\item On trouve un indice $i_{0}$ tel que $d(i_{0})$ soit maximum (il peut y en avoir plusieurs). On retourne alors la partie de pile au-dessus de $i_{0}$, ce qui la met tout en haut du tas, puis on retourne {\`a} nouveau toute la pile.

\item On applique le principe pr{\'e}c{\'e}dent, mais en faisant comme si la place $i$ {\'e}tait le bas de la pile.
\begin{itemize}
\item En Caml, version sans r{\'e}f{\'e}rences : on {\'e}crit une fonction auxiliaire qui recherche $i_{0}$ :
\begin{verbatim}
let place d i =
   let rec maxi j i0 = if j = n then i0 else
        if d.(j) > d.(i0) then maxi (j+1) j else maxi (j+1) i0
   in retourne d (maxi (i+1) i) ;
   retourne d i;;
\end{verbatim}

En Caml, version avec r{\'e}f{\'e}rences :
\begin{verbatim}
let place d i = let i0=ref i in
  for j=(i+1) to (n-1) do if d.(j) > d.(!i0) then i0:=j done;
  retourne d !i0 ;
  retourne d i;;
\end{verbatim}

\item En Pascal :
\begin{verbatim}
PROCEDURE place(VAR d : Pile ; i : INTEGER);
VAR i0, j : INTEGER ;
    BEGIN
         i0:=i ;
         FOR j := i+1 TO n-1 DO
              IF d[j] > d[i0] THEN i0:=j ;
         retourne(d, i0) ;
         retourne(d, i)
    END ;
\end{verbatim}
\end{itemize}

\item Pour trier, il ne reste plus qu'{\`a} utiliser \texttt{place} pour $i$ variant de $0$ {\`a} $n-2$.
\begin{verbatim}
let tri d = for i=0 to n-2 do place d i done ;;

PROCEDURE tri(VAR d : Pile);
VAR i : INTEGER ;
    BEGIN
        FOR i := 0 TO n-2 DO place(d, i)
    END ;
\end{verbatim}

\item Chaque appel {\`a} \texttt{place} fait deux retournements, soit un co{\^u}t de $2(n-1)$ retournements.
\end{enumerate}

\end{document}
