%  Corrig\'e de l'\'epreuve d'Informatique pos\'ee aux ENSI en 1999
%  en langage Caml

% par Daniel GENOUD - Lyc\'ee La Martini\`ere-Monplaisir - LYON
% email : Daniel.Genoud@ac-lyon.fr

% LaTeX 2.09

\documentstyle[a4]{article}

% Num\'erotation ups
\input upsnum.sty

\parindent=0pt

\def\und#1{\underline{#1}}
\def\num#1{\medskip \hskip-8mm\und{{\bf #1}}~}
\def\bkp{\bigskip}
\def\skp{\smallskip}
\def\mbx{\makebox}

\begin{document}

\centerline{\fbox{{\bf 
CORRIG\'E DE L'\'EPREUVE D'INFORMATIQUE DES ENSI - 1999}}}

\bkp\bkp

\fbox{{\bf Partie I : Logique et calcul des propositions}}
\bkp

\def\ov#1{\overline{#1}}

Les r\'eponses aux deux questions sont :

\skp
\fbox{$Q_1=\left(\ov{P_1}\wedge \ov{P_2}\wedge\ov{P_3}\right)\vee
\big(P_1\wedge(P_2\vee P_3)\big)$ ~et~
$Q_2=\left(\ov{P_1}\wedge {P_2}\right)\vee
\left(P_1\wedge\ov{P_2}\right).$}
\skp

On cherche lorsque $Q_1\wedge Q_2$ est vrai.
\bkp

\hskip-5mm\und{Premi\`ere m\'ethode}

\skp
\hskip2cm
\begin{tabular}{|c|c|c|c|c||c|c|c|}
\hline
$P_1$ & $P_2$ & $P_3$ & $\ov{P_1}\wedge \ov{P_2}\wedge\ov{P_3}^{~\atop~}$ &
$P_1\wedge(P_2\vee P_3)$ & $Q_1$ &$Q_2$ & $Q_1\wedge Q_2$ \\
\hline
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \cr
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \cr
0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \cr
0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \cr
1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \cr
1 & 0 & 1 & 0 & 1 & 1 & 1 & {\bf 1} \cr
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \cr
1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \cr
\hline
\end{tabular}
\bkp

\und{Conclusion} :
~\fbox{Les processeurs n$^o1$ et n$^o3$ sont en panne et 
le n$^o2$ en \'etat normal.}
\bkp

\hskip-5mm\und{Deuxi\`eme m\'ethode}
\skp

On utilise la formule suivante :
$~\big(\ov A\wedge B\big)\vee\big(A\wedge \ov B\big)=
A\oplus B=\big(A\vee B)\wedge \big(\ov A\vee \ov B\big)$.
\skp

Ainsi $~Q_1=P_1\oplus\ov{P_2\vee P_3}=\big(P_1\vee\ov{P_2\vee P_3}\big)
\wedge\big(\ov{P_1}\vee(P_2\vee P_3)\big)$
~et~ $Q_2=(P_1\vee P_2)\wedge\big(\ov{P_1}\vee\ov{P_2}\big)$.
\skp

Donc $~Q_1\wedge Q_2=\left[P_1\vee\big(P_2\wedge\ov{P_2\vee P_3}\,\right]
\wedge\left[\,\ov{P_1}\vee\big(\ov{P_2}\wedge(P_2\vee P_3)\right]
=P_1\wedge\big(\ov{P_1}\vee(\ov{P_2}\wedge P_3)\big)$.
\skp

\und{Conclusion} ~\fbox{$Q_1\wedge Q_2=P_1\wedge \ov{P_2}\wedge P_3$.}

\bkp
\hrule

\newpage

\fbox{{\bf Partie II : Algorithmique et programmation en CaML}}

\input emlines.sty

\def\cnx#1#2{\langle#1,#2\rangle}
\def\ch#1{\langle\!\langle\,#1\,\rangle\!\rangle}
\def\cpt{complexit\'e }
\bkp

La notation $|X|$ d\'esignera le cardinal de l'ensemble $X$.

\und{Remarque} : $\cnx p q =\cnx q p$.
\skp

\num{Q II.1} 
Donnons tous les r\'eseaux connexes et sans cycles ayant un nombre minimum
de connexions ``extraits" du r\'eseau propos\'e : ils ont tous
exactement $5-1=4$ connexions.

On doit donc enlever deux connexions bien choisies \`a l'exception de $\cnx D E$.

\hskip-3mm* Si on enl\`eve la connexion $\cnx A B$, on doit garder
$\cnx A C$, mais il reste un cycle $\ch{B,C,D,B}$
dans lequel on peut supprimer n'importe laquelle des trois connexions.

\hskip-3mm* Si on enl\`eve la connexion $\cnx A C$, c'est analogue.

\hskip-3mm* Si on enl\`eve la connexion $\cnx B C$, alors dans le cycle
 $\ch{A,B,D,C,A}$, on peut supprimer $\cnx B D$ ou $\cnx C D$
(les autres possibilit\'es ayant d\'ej\`a \'et\'e examin\'ees).

\hskip-3mm* Si on enl\`eve la connexion $\cnx B D$ ou $\cnx C D$, 
dans le cycle $\ch{A,B,C,A}$, 
toutes les  possibilit\'es de suppression ont d\'ej\`a \'et\'e examin\'ees.

Il y a donc \und{8 solutions}.
\bkp

\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{28.00}{10.00}{3}{37.00}{10.00}{4}  % C,D
\put(32.50,8.00){\mbx(0,0)[cc]{1}}
\emline{12.00}{23.00}{9}{22.00}{12.00}{10} % A,C
\put(14.00,18.00){\mbx(0,0)[cc]{1}}
\emline{28.00}{23.00}{11}{38.00}{12.00}{12}% B,D
\put(35.00,18.00){\mbx(0,0)[cc]{1}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{12.00}{23.00}{9}{22.00}{12.00}{10} % A,C
\put(14.00,18.00){\mbx(0,0)[cc]{1}}
\emline{25.00}{22.00}{7}{25.00}{13.00}{8}  % B,C
\put(27.00,18.00){\mbx(0,0)[cc]{2}}
\emline{28.00}{23.00}{11}{38.00}{12.00}{12}% B,D
\put(35.00,18.00){\mbx(0,0)[cc]{1}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}

\bkp
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{28.00}{10.00}{3}{37.00}{10.00}{4}  % C,D
\put(32.50,8.00){\mbx(0,0)[cc]{1}}
\emline{12.00}{23.00}{9}{22.00}{12.00}{10} % A,C
\put(14.00,18.00){\mbx(0,0)[cc]{1}}
\emline{25.00}{22.00}{7}{25.00}{13.00}{8}  % B,C
\put(27.00,18.00){\mbx(0,0)[cc]{2}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{13.00}{25.00}{1}{22.00}{25.00}{2}  % A,B
\put(17.00,27.00){\mbx(0,0)[cc]{1}}
\emline{28.00}{10.00}{3}{37.00}{10.00}{4}  % C,D
\put(32.50,8.00){\mbx(0,0)[cc]{1}}
\emline{28.00}{23.00}{11}{38.00}{12.00}{12}% B,D
\put(35.00,18.00){\mbx(0,0)[cc]{1}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}

\bkp
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{13.00}{25.00}{1}{22.00}{25.00}{2}  % A,B
\put(17.00,27.00){\mbx(0,0)[cc]{1}}
\emline{25.00}{22.00}{7}{25.00}{13.00}{8}  % B,C
\put(27.00,18.00){\mbx(0,0)[cc]{2}}
\emline{28.00}{23.00}{11}{38.00}{12.00}{12}% B,D
\put(35.00,18.00){\mbx(0,0)[cc]{1}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{13.00}{25.00}{1}{22.00}{25.00}{2}  % A,B
\put(17.00,27.00){\mbx(0,0)[cc]{1}}
\emline{28.00}{10.00}{3}{37.00}{10.00}{4}  % C,D
\put(32.50,8.00){\mbx(0,0)[cc]{1}}
\emline{25.00}{22.00}{7}{25.00}{13.00}{8}  % B,C
\put(27.00,18.00){\mbx(0,0)[cc]{2}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}

\bkp
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{13.00}{25.00}{1}{22.00}{25.00}{2}  % A,B
\put(17.00,27.00){\mbx(0,0)[cc]{1}}
\emline{28.00}{10.00}{3}{37.00}{10.00}{4}  % C,D
\put(32.50,8.00){\mbx(0,0)[cc]{1}}
\emline{12.00}{23.00}{9}{22.00}{12.00}{10} % A,C
\put(14.00,18.00){\mbx(0,0)[cc]{1}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}
\qquad
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(58.00,28.00)
\put(10.00,25.00){\circle{6.00}}
\put(25.00,25.00){\circle{6.00}}
\put(25.00,10.00){\circle{6.00}}
\put(40.00,10.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(10.00,25.00){\mbx(0,0)[cc]{$A$}}
\put(25.00,25.00){\mbx(0,0)[cc]{$B$}}
\put(25.00,10.00){\mbx(0,0)[cc]{$C$}}
\put(40.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(55.00,10.00){\mbx(0,0)[cc]{$E$}}
\emline{13.00}{25.00}{1}{22.00}{25.00}{2}  % A,B
\put(17.00,27.00){\mbx(0,0)[cc]{1}}
\emline{12.00}{23.00}{9}{22.00}{12.00}{10} % A,C
\put(14.00,18.00){\mbx(0,0)[cc]{1}}
\emline{28.00}{23.00}{11}{38.00}{12.00}{12}% B,D
\put(35.00,18.00){\mbx(0,0)[cc]{1}}
\emline{43.00}{10.00}{5}{52.00}{10.00}{6}  % D,E
\put(47.00,8.00){\mbx(0,0)[cc]{2}}
\end{picture}
\skp

\num{Q II.2} 
Il y a 4 r\'eseaux de co\^ut minimum \'egal \`a 5 :

\qquad ce sont tous ceux qui ne contiennent pas la connexion $\cnx B C$.

\num{Q II.3} 
Si $(P_i,C_i)$ est un r\'eseau tel que $p\in P_i$, $q\in P_i$
et $\cnx  p q\notin C_i$, alors il existe un chemin
$\ch{p,\ldots,q}$ de longueur $\ge 2$ compos\'e de connexions de $C_i$
joignant $p$ \`a $q$. 

On remarque alors que $\ch{p,\ldots,q,p}$
est un cycle dans $\big(P_i,C_i\cup\{\cnx p q\}\big)$.

\num{Q II.4} 
Si $(P_i,C_i)$ est un r\'eseau et si $p\notin P_i$, $q\notin P_i$,
alors $\big(P_i\cup\{p,q\},C_i\cup\{\cnx p q\}\big)$ n'est pas un r\'eseau car il n'est pas connexe.
En effet $p$ ne peut \^etre reli\'e qu'\`a $q$ puisqu'aucune connexion de $C_i$
n'a pour extr\'emit\'e $p$ ou $q$.

\num{Q II.5} 
On suppose que  $(P_i,C_i)$ est un r\'eseau et que $p\in P_i$, 
$q\notin P_i$. ~Ainsi $\cnx p q \notin C_i$.

On pose $\,P_{i+1}=P_1\cup \{q\}\,$
et $C_{i+1}=C_i\cup\{\cnx p q\})$.

Pour v\'erifier que $(P_{i+1},C_{i+1})$ est un r\'eseau, il suffit de s'assurer que :

\hskip-3mm $*$ les extr\'emit\'es des connections de $C_{i+1}$
sont dans $P_{i+1}$ : \'evident.

\hskip-3mm $*$ $q$ est reli\'e \`a tout \'el\'ement $r$ de $P_i$ par des connexions de $C_{i+1}$,
ce qui est vrai car il existe un chemin $\ch{r,\ldots,p}$
compos\'e de connexions de $C_i$ (puisque $(P_i,C_i)$
est un r\'eseau), donc $\ch{r,\ldots,p,q}$ est un chemin joignant $r$ \`a $q$
constitu\'e de connexions de $C_{i+1}$.

\hskip-3mm $*$ $(P_{i+1},C_{i+1})$ est acyclique car c'est le cas de $(P_i,C_i)$ et qu'il
n'existe pas de cycle dans $(P_{i+1},C_{i+1})$  passant par $q$
puisque $q$ n'est connect\'e qu'\`a un seul point qui est $p$.

\num{Q II.6} 
{\it L'\'enonc\'e  est incorrect : il faut s'arr\'eter \`a  
$\und{k=p-1}$ avec $p=|P|$.}

\skp
Utilisons d\`es maintenant la notion de cocycle d\'efinie dans la question suivante
et \'etablissons le lemme suivant utile pour la suite:

\qquad{\sl\und{Si $Q$ est une partie non vide stricte de $P$,
 alors le cocycle $\omega(Q)$ n'est pas vide}.}

\skp
En effet, soit $r\in P\setminus Q$ et $p_0\in Q$.

Le r\'eseau $(P,C)$ \'etant connexe, $r$ est reli\'e \`a $p_0$.
Il existe donc un chemin $\ch{s_0,s_1,\ldots, s_j}$ compos\'e de 
connexions de $C$ tel que $s_0=p_0$ et $s_j=r$.

L'ensemble $\,\big\{l\in[\![0;j]\!]~/~s_l\notin Q\big\}\,$ est une 
partie de ${\bf N}$ non vide (car contient $j$) :
 elle admet donc un plus petit
\'el\'ement not\'e $m$  tel que $m\ge 1$ car $s_0\in Q$.

Ainsi $q=s_m\notin Q$, ~$p=s_{m-1}\in Q$ ~et~ $\cnx p q \in C$,
donc $\,\cnx p q\in \omega(Q)$.

\bkp
Revenons maintenant \`a l'algorithme propos\'e par l'\'enonc\'e.
\skp

A l'initialisation, on choisit $p_0$ quelconque dans $P$ et on pose
$P_0=\{p_0\}$ et $C_0=\emptyset$.

 Ainsi $(P_0,C_0)$ est un \und{r\'eseau} \und{partiel} de $(P,C)$.
\skp

Supposons avoir construit  $(P_i,C_i)$ o\`u $i\le k-1$ tel que 
$|P_i|=i+1$ et $|C_i|=i$ de sorte que $(P_i,C_i)$ soit un 
\und{r\'eseau partiel} de $(P,C)$.

Ainsi $|P_i|=i+1\le k=p-1<|P|$; d'apr\`es le lemme, le cocycle $\omega(P_i)$
n'est pas vide. Choisissons une connexion \und{quelconque}
$c_{i+1}=\cnx{p_i}{q_i}$ dans $\omega(P_i)$ avec $p_i\in P_i$  et $q_i\notin P_i$
et posons $\,P_{i+1}=P_i\cup \{q_i\}\,$ et $\,C_{i+1}=C_i\cup\{c_{i+1}\}$
~($c_{i+1}\notin C_i$).
On a bien $|P_{i+1}|=(i+1)+1$ et $|C_{i+1}|=i+1$ (premier invariant de boucle).
De plus, d'apr\`es la question pr\'ec\'edente, $(P_{i+1},C_{i+1})$
est un \und{r\'eseau} (connexe et acyclique) 
 et comme $C_{i+1}\subset C$, il s'agit bien
d'un r\'eseau \und{partiel} de $(P,C)$ ~(deuxi\`eme invariant de boucle). 

\skp
L'algorithme s'arr\^ete pour $i=k=p-1$ car alors $P_k=P$ :
il construit donc en $k$ \'etapes un r\'eseau 
qui r\'epond au probl\`eme $(P,C)$.

\skp
\und{Remarque} : en contraposant le lemme, si  $\omega(P_i)=\emptyset$,
alors $P_i=P$.\par
On peut donc aussi utiliser pour test d'arr\^et la condition :
\und{$\omega(P_i)=\emptyset$}.

\newpage

\num{Q II.7} {\bf Construction d'un cocycle}

\begin{verbatim}
let rec cocycle q c = match c with
       |         []  -> [] 
       | (x,y,ct)::r -> 
            if ((appartient x q) && (not appartient y q))
            or ((appartient y q) && (not appartient x q)) 
                       then (x,y,ct)::(cocycle q r)
                       else cocycle q r
;;
\end{verbatim}
\und{Remarque} : l'ordre des connexions de la liste obtenue
est le m\^eme que dans la liste $C$.

\num{Q II.8}
 On parcourt enti\`erement la liste $C$. Les appels r\'ecursifs
s'effectuent sur la queue de la liste, on termine donc toujours avec la liste vide.

\num{Q II.9}
Il y a exactement \und{$c=|C|$ appels r\'ecursifs}. ~Sachant que la \cpt  de la fonction
{\tt appartient} est major\'ee par la longueur de la liste {\tt q}, on peut donc 
estimer la \cpt  de la fonction {\tt cocycle} comme \'etant
en $\und{O\big(c\,|Q|\big)}$.

\num{Q II.10}
On prendra chaque fois l'\'el\'ement de t\^ete du cocycle et 
on ne tient pas compte des co\^uts.

- Initialisons avec par exemple $p_0=A$.

- $\omega(P_0)=\{\cnx A B,\cnx A C\}$, 
~d'o\`u $P_1=\{B,A\}$ ~et~ $C_1=\{\cnx A B\}$.

- $\omega(P_1)=\{\{\cnx A C,\cnx B C,\cnx B D\}$, 
d'o\`u $P_2=\{C,B,A\}$ ~et~ $C_2=\{\cnx A C,\cnx A B\}$.

- $\omega(P_2)=\{\cnx B D,\cnx C D\}$, 
~d'o\`u $P_3=\{D,C,B,A\}$ ~et~ $C_3=\{\cnx B D\cnx A C,\cnx A B\}$.

- $\omega(P_3)=\{\{\cnx D E\}$, 
~d'o\`u $P_4=\{E,D,C,B,A\}$ ~et~ $C_4=\{\cnx D E\cnx B D\cnx A C,\cnx A B\}$.

Il s'agit du dernier r\'eseau repr\'esent\'e \`a la question {\bf II.1}.


\num{Q II.11} {\bf Construction du r\'eseau}

Donnons successivement une version it\'erative de la fonction {\tt construire}
utilisant des r\'ef\'erences et la fonction {\tt taille},
puis une version r\'ecursive demand\'ee par l'\'enonc\'e.

\begin{verbatim}
 let construire p c =         (* iterative *}        
    let  k = taille p - 1 in           
    let pi = ref [hd p] and ci = ref [] in
    for i = 1 to k do
      let (x,y,t) = hd (cocycle !pi c) in 
          if appartient x !pi then pi := y :: !pi
                              else pi := x :: !pi;
          ci := (x,y,t) :: !ci ;
    done;
    (!pi, !ci) 
 ;;
\end{verbatim}

\newpage
\begin{verbatim}
 let construire p c =                 
    let  rec constr_aux pi ci =   (* fonction recursive locale *)
        let omega = cocycle pi c in
           if omega = [] then (pi, ci)  (* i = k *)
           else let (x,y,t) = hd(omega) in 
                   if appartient x pi 
                           then constr_aux (y::pi) ((x,y,t)::ci)
                           else constr_aux (x::pi) ((x,y,t)::ci)
    in constr_aux [hd p] []
 ;;
\end{verbatim}

\und{Remarque} : cette fonction appelle la fonction {\tt cocycle}
qui calcule le cocycle en entier alors qu'il suffirait ici d'obtenir
un seul de ses \'el\'ements.

\num{Q II.12}
 Il y a exactement \und{$k=p-1$ appels r\'ecursifs} de la
fonction {\tt constr\_aux} avec $p=|P|$.

\num{Q II.13}
 Pour passer de $(P_{i-1},C_{i-1})$ \`a $(P_i,C_i)$
 pour $i=1\ldots k$, la fonction
r\'ecursive {\tt constr\_aux} appelle :

\qquad . {\tt cocycle} qui a une \cpt  major\'ee par $i\,|C|$
~(car $|P_{i-1}|=i$)

\qquad . {\tt appartient} qui a une \cpt  major\'ee par $i$.

Sachant que 
$\displaystyle\sum_{i=1}^{p-1}i={ p\,(p-1)\over2}$,
la \cpt  totale de {\tt construire} est donc en
$\und{O(c\,p^2)}$ avec $p=|P|$ et $c=|C|$.

\num{Q II.14} 
On se place dans le cas o\`u $c'=\cnx{p_0}{p_n}\in\omega(X)$, 
mais $c'\notin Z$.

Comme $c'\in\omega(X)$, on peut supposer que par exemple $p_0\in X$ et $p_n\notin X$.

En consid\'erant de m\^eme qu'au {\bf II.6} le plus petit \'el\'ement $m$
de l'ensemble

 $\,\big\{l\in[\![0;n]\!]~/~p_l\notin X\big\}\,$,
on trouve que $c=\cnx {p_{m-1}}{p_m}\in\omega(X)$.

\num{Q II.15}
Il est clair que dans un r\'eseau (connexe et acyclique), il existe un et un seul
chemin reliant deux points distincts.

On remarque que $(P,Z\cup \{c'\})$ contient le cycle 
$\ch{p_0,p_1, \ldots, p_{m-1},p_m,\ldots,p_{n-1},p_n,p_0}$ 
(du fait de l'ajout de $c'$) et 
c'est le \und{seul} cycle du fait de l'unicit\'e de chemin joignant
$p_0$ \`a $p_n$ dans le r\'eseau $(P,Z)$.

Il est clair que la suppression de $c$ fait disparaitre ce cycle
dans $H'=(P,Z')$ avec $Z'=(Z\setminus \{c\})\cup\{c'\}$, donc 
\und{$H'$ est acyclique}.

\skp
D'autre part, la suppression de la connexion $c$ n'alt\`ere pas la
\und{connexit\'e} car dans  tout chemin $\ell$ qui joint deux points distincts de $P$
dans $H=(P,Z)$ et  qui contient $c=\cnx{p_{m-1}}{p_m}$,
 on peut remplacer ce chemin par un chemin $\ell'$
en substituant \`a $c$ dans $\ell$ le chemin 
$\gamma=\ch{p_{m-1},\ldots,p_0,\ldots,p_n,p_0,\ldots,p_m} $.
~Il se peut que dans $\ell'$,
 certaines connexions figurent deux fois 
(une fois dans $\ell$ et une fois dans $\gamma$).
Une telle situation correspond \`a des suites de connexions cons\'ecutives
de la forme $\cnx{q_1}{q_2},\ldots\cnx{q_{m-1}}{q_m},
\cnx{q_m}{q_{m-1}},\ldots\cnx{q_2}{q_1}$ repr\'esentant \`a des ``aller-retours" qui peuvent
\^etre supprim\'ees dans $\ell'$ pour donner un chemin final
 compos\'e uniquement de connexions \und{distinctes}.

\num{Q II.16}
 On notant $t$ la fonction co\^ut, on a :
~\und{$t(H')=t(H)+t(c')-t(c)$}.

\num{Q II.17}
Puisque $c'$ est une connection de co\^ut minimal 
dans $\omega(X)$ et que $c\in\omega(X)$,
alors $t(c')\le t(c)$, d'o\`u $~t(H')\le t(H)$.\par
Mais d'autre part, $H$ \'etant de co\^ut minimal, $~t(H)\le t(H')$,
donc $~t(H)=t(H')$, ce qui montre que $H'$ est lui-m\^eme un r\'eseau de co\^ut minimal.

\num{Q II.18} 
On reprend l'algorithme d\'ecrit au {\bf II.6} en choisissant $c_{i+1}$
de co\^ut minimum dans $\omega(P_i)$.

Montrons que la propri\'et\'e ${\cal P}(i) : "(P_i,C_i)$ {\sl  est un r\'eseau partiel
de $(P,C)$ et $C_i\subset Z_i$ o\`u 
$H_i=(P,Z_i)$ est un r\'eseau de co\^ut minimal"} ~est vraie pour 
tout $i\in[\![0;k]\!]$.

\hskip-3mm$*$
${\cal P}(0)$ est vrai car tout r\'eseau $H_0$ de co\^ut minimal (il en existe) convient.

\hskip-3mm$*$
Supposons $C_i\subset Z_i$ avec $H_i=(P,Z_i)$ de co\^ut minimal.

Consid\'erons $c_{i+1}\in \omega(P_i)$ de co\^ut minimal.

. Si $c_{i+1}\in Z_i$, alors $C_{i+1}=C_i\cup\{c_{i+1}\} \subset Z_{i}=Z_{i+1}$.

. Sinon, si $c_{i+1}\notin Z_i$, enlevons de $Z_i$
la connection $c$ du {\bf II.15} : comme cette connection $c$
est dans $\omega(P_i)$, elle n'est pas pr\'esente dans $C_i$.

Ainsi
$C_{i+1}=C_i\cup\{c_{i+1}\}\subset (Z_i\setminus\{c\})\cup \{c_{i+1}\}=Z_{i+1}$.

\skp
Finalement, \`a la derni\`ere \'etape de l'algorithme, on obtient $(P_k,C_k)$
avec $P_k=P$, $C_k\subset Z_k$ et $H_k=(P,Z_k)$ r\'eseau de co\^ut minimum, 
d'o\`u n\'ecessairement $C_k=Z_k$, 
donc \und{$(P_k,C_k)$ est un r\'eseau partiel de $(P,C)$ de co\^ut minimum}.

\num{Q II.19} {\bf Optimisation de la fonction} {\tt cocycle}
\begin{verbatim}
let rec cocycle q c = match c with
     |        []  -> [] 
     | (x,y,t)::r -> 
        if ((appartient x q) && (not appartient y q)) 
        or ((appartient y q) && (not appartient x q)) 
                   then inserer (x,y,t) (cocycle q r)
                   else cocycle q r
;;
\end{verbatim}

\und{Remarque} : cette fois, il faut bien calculer enti\`erement
 chaque cocycle pour pouvoir en extraire une des connexions de co\^ut minimum.

\num{Q II.20}
Cette fois, en plus de la \cpt  de la fonction {\tt appartient}
qui s'effectue toujours sur la liste $Q$, il faut en plus tenir compte de
 celle de la fonction {\tt inserer} qui op\`ere sur des listes successives de longueur croissante
d'au plus une unit\'e \`a chaque appel. Comme il y a $|C|$ appels r\'ecursifs de {\tt cocycle},
on obtient une \cpt  en $O\big(c\,|Q|+c^2\big)$.

\num{Q II.21}
La \cpt  de {\tt cocycle} \`a la $i^e$ \'etape est cette fois de
major\'ee par $c\,i+c^2$.

On obtient donc une \cpt  totale en $O\big(p^2\,c+p\,c^2\big)$ et comme
en g\'en\'eral $p\le c$, on arrive \`a \und{$O\big(p\,c^2\big)$}.

\bkp
\hrule

\newpage
\fbox{{\bf Partie III : Automates et langages}}
\bkp

\def\Equ{\Longleftrightarrow}

\und{Rappel} : {\bf lemme de Arden}.

{\sl Si $M$ et $L$ sont deux langages et si $\Lambda\notin L$,
alors l'\'equation en langages : $X=L.X+M$~
admet une unique solution \'egale \`a $L^*.M$.}

\skp
On notera $L_P$ le langage reconnu par l'automate lorsque
l'on prend $P$ comme \'etat initial et $E_P$ une expression rationnelle
de ce langage.

\skp
\num{Q III.1}
On note $E_1$ une expression rationnelle du langage $L({\cal E}_1)$.

On remarque que les \'etats $B$ et $C$ ont un r“le identique,
donc \und{$L_B=L_C$}.

\und{Premi\`ere m\'ethode}
\skp

On a : ~$E_1=E_A=(a+b)\,E_B$, ~$E_B=\Lambda+a\,E_B+c\,E_D$
~et~ $E_D=(a+c)^*$.

On en d\'eduit que $~E_B=a^*\,\big(\Lambda+c\,(a+c)^*\big)$~
et ~\fbox{$E_1=(a+b)\,a^*+(a+b)\,a^*\,c\,(a+c)^*$.}

\skp
\und{Deuxi\`eme m\'ethode}

\skp
On remarque que l'automate ${\cal E}_1$ est \'equivalent \`a l'automate suivant (minimal) :\par

\hskip1cm
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(83.50,23.00)
\put(20.00,10.00){\circle{6.00}}
\put(20.00,10.00){\mbx(0,0)[cc]{$A$}}
\put(50.00,10.00){\circle{6.00}}
\put(50.00,10.00){\circle{7.00}}
\put(50.00,10.00){\mbx(0,0)[cc]{$B$}}
\put(80.00,10.00){\circle{6.00}}
\put(80.00,10.00){\circle{7.00}}
\put(80.00,10.00){\mbx(0,0)[cc]{$D$}}
\put(23.00,10.00){\vector(1,0){23.00}}
\put(54.00,10.00){\vector(1,0){22.00}}
\put(50.00,13.50){\oval(4.00,9.00)[t]}
\put(48.00,14.00){\vector(0,-1){1.00}}
\put(35.00,12.00){\mbx(0,0)[cc]{$a,b$}}
\put(65.00,12.00){\mbx(0,0)[cc]{$c$}}
\put(80.00,20.00){\mbx(0,0)[cc]{$a,c$}}
\put(80.00,13.50){\oval(4.00,9.00)[t]}
\put(78.00,14.00){\vector(0,-1){1.00}}
\put(50.00,20.00){\mbx(0,0)[cc]{$a$}}
\end{picture}

On ``voit" directement que 
$E_1=(a+b)\,a^*+(a+b)\,a^*\,c\,(a+c)^*$.

\skp
\num{Q III.2}
On note $E_2$ une expression rationnelle du langage $L({\cal E}_2)$.

\skp
\und{Premi\`ere m\'ethode}
\skp

On a : $~E_2=a\,E_F+c\,E_G$, ~$E_G=\Lambda+b\,E_H+c\,E_F$,
~$E_F=\Lambda+b\,E_H+c\,E_F$ ~et~ $E_H=c\,E_F$.\par
\skp

On remarque que $E_F=E_G$ et on en d\'eduit successivement que :

$E_2=(a+c)\,E_F$, $~E_F=(c+bc)\,E_F+\Lambda$, ~donc $~E_F=(c+bc)^*$,
d'o\`u \fbox{$E_2=(a+c)\,(c+bc)^*.$}

\skp
\und{Deuxi\`eme m\'ethode}
\skp

Puisque les deux \'etats $F$ et $G$ sont ``\'equivalents",
 l'automate ${\cal E}_2$ est \'equivalent \`a l'automate suivant  :\par

\hskip1cm
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(83.50,23.00)
\put(20.00,10.00){\circle{6.00}}
\put(20.00,10.00){\mbx(0,0)[cc]{$E$}}
\put(50.00,10.00){\circle{6.00}}
\put(50.00,10.00){\circle{7.00}}
\put(50.00,10.00){\mbx(0,0)[cc]{$F$}}
\put(80.00,10.00){\mbx(0,0)[cc]{$H$}}
\put(23.00,10.00){\vector(1,0){23.00}}
\put(54.00,11.00){\vector(1,0){23.00}}
\put(77.00,9.00){\vector(-1,0){23.00}}
\put(50.00,13.50){\oval(4.00,9.00)[t]}
\put(48.00,14.00){\vector(0,-1){1.00}}
\put(35.00,12.00){\mbx(0,0)[cc]{$a,c$}}
\put(65.00,13.00){\mbx(0,0)[cc]{$b$}}
\put(65.00,7.00){\mbx(0,0)[cc]{$c$}}
\put(50.00,20.00){\mbx(0,0)[cc]{$c$}}
\end{picture}

On ``voit" directement que $E_2=(a+c)\,(b+bc)^*$.

\skp
\num{Q III.3}
Plut“t que de repr\'esenter l'automate ${\cal E}_1\times{\cal E}_2$
\`a l'aide d'un graphe comportant 16 sommets,
il est pr\'ef\'erable de donner la table de transition de $\delta_{1\times 2}$.\par
Pour construire celle-ci, on commence d'abord par mettre des signes $-$
dans les nombreuses cases o\`u elle n'est pas d\'efinie
(parce que $\delta_1$ ou $\delta_2$ ne l'est pas).

\skp
\qquad
\begin{tabular}{|c||c|c|c|}
\hline
 & $a$ & $b$ & $c$ \\
\hline
(A,E) & (B,F) & - & - \\
(A,F) & - & (C,H) & -  \\
(A,G) & - & (C,H) & -  \\
(A,H) & - & - & -  \\
(B,E) & (C,F) & - & (D,G) \\
(B,F) & - & - & (D,F)  \\
(B,G) & - & - & (D,F)  \\
(B,H) & - & - & (D,F)  \\
\hline
\end{tabular}
\qquad
\begin{tabular}{|c||c|c|c|}
\hline
 & $a$ & ~~$b$~~ & $c$ \\
\hline

(C,E) & (B,F) & - & (D,G) \\
(C,F) & - & - & (D,F)  \\
(C,G) & - & - & (D,F)  \\
(C,H) & - & - & (D,F)  \\
(D,E) & (D,F) & - & (D,G) \\
(D,F) & - & - & (D,F)  \\
(D,G) & - & - & (D,F)  \\
(D,H) & - & - & (D,F)  \\
\hline
\end{tabular}

\skp
On constate que la plupart des \'etats ne sont pas accessibles
depuis l'\'etat initiel $(A,E)$.\par

Un automate accessible \'equivalent \`a ${\cal E}_1\times{\cal E}_2$
se r\'eduit \`a :

\hskip1cm
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(83.50,23.00)
\put(20.00,10.00){\circle{9.00}}
\put(20.00,10.00){\mbx(0,0)[cc]{$A,E$}}
\put(50.00,10.00){\circle{9.00}}
\put(50.00,10.00){\circle{10.00}}
\put(50.00,10.00){\mbx(0,0)[cc]{$B,F$}}
\put(80.00,10.00){\circle{9.00}}
\put(80.00,10.00){\circle{10.00}}
\put(80.00,10.00){\mbx(0,0)[cc]{$D,F$}}
\put(24.50,10.00){\vector(1,0){20.00}}
\put(55.00,10.00){\vector(1,0){20.00}}
\put(80.00,15.00){\oval(4.00,9.00)[t]}
\put(78.00,15.50){\vector(0,-1){1.00}}
\put(35.00,12.00){\mbx(0,0)[cc]{$a$}}
\put(65.00,12.00){\mbx(0,0)[cc]{$c$}}
\put(80.00,21.00){\mbx(0,0)[cc]{$c$}}
\end{picture}

On constate que le langage reconnu par ${\cal E}_1\times{\cal E}_2$
est d\'ecrit par l'expression rationnelle \fbox{$a\,c^*$.}
\skp

On remarque ce $L({\cal E}_1\times{\cal E}_2)$ est \und{inclus} dans 
$L({\cal E}_1)$ et dans $L({\cal E}_2)$.

\num{Q III.5}
Montrons par \und{induction structurelle} la propri\'et\'e :
\skp

\qquad \und{${\cal P}(m) : \delta_{1\times 2}^*\big(m,(q_1,q_2)\big)=
\big(\delta_1^*(m,q_1),\delta_2^*(m,q_2)\big)$}
\qquad ({\sl lorsque ces quantit\'es existent}).
\skp

{\it Il reviendrait au m\^eme de raisonner par r\'ecurrence sur la longueur de $m$.}

\skp
. \und{${\cal P}(\Lambda)$} est vraie car
$~\delta_{1\times 2}^*\big(\Lambda,(q_1,q_2)\big)=(q_1,q_2)=
\big(\delta_1^*(\Lambda,q_1),\delta_2^*(\Lambda,q_2)\big)$.
\skp

. \und{Supposons ${\cal P}(m)$ vraie} et montrons alors
que $\forall\, x\in X,~{\cal P}(m.x)$ est vraie.
~En effet :

 $~ \und{\delta_{1\times 2}^*\big(m.x,(q_1,q_2)\big)}=
\delta_{1\times2}\Big(x, \delta_{1\times 2}^*\big(m,(q_1,q_2)\big)\Big)
=\delta_{1\times2}\Big(x, \big(\delta_1^*(m,q_1),\delta_2^*(m,q_2)\big)\Big)$

\hskip3cm
$=\Big(\delta_1\big(x,\delta_1^*(m,q_1)\big),\delta_2\big(x,\delta_2^*(m,q_2)\big)\Big)
=\und{\big(\delta_1^*(m.x,q_1),\delta_2^*(m.x,q_2)\big)}.$

\num{Q III.6}
$\und{m\in L(A_1\times A_2)}
\Equ \delta_{1\times 2}^*\big(m,(q_1,q_2)\big)\in T_1\times T_2
\Equ\big(\delta_1^*(m,q_1),\delta_2^*(m,q_2)\big)\in T_1\times T_2$
\skp

\hskip3.3cm
$\Equ\delta_1^*(m,q_1)\in T_1~\wedge~
\delta_2^*(m,q_2)\in T_2
\Equ \und{m\in L(A_1) ~\wedge~ m\in L(A_2)}.$

\skp

\num{Q III.7} 
On en d\'eduit que :  ~\fbox{$L(A_1\times A_2)=L(A_1)\,\cap\, L(A_2)$.}

\bkp
$$*+*+*+*+*+*+*+*+*+*$$
\end{document} 



          
