%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                                                                  %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                      Corrig\'e de l'\'epreuve d'info                 %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                          Mines-Ponts 2002                        %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                                                                  %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% \`a compiler en LaTeX 2.09 et \`a visualiser en Post Script
% d\'ebut du corrig\'e ligne 104

\documentstyle[pstricks,pst-node]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%        %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% MACROS %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%        %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\pagestyle{plain}
\input upsnum.sty
\textheight=230mm
\textwidth=165mm
\topmargin  -10mm
\footskip 14mm
\headheight  6mm
\headsep 7.5mm
\oddsidemargin -5mm
\evensidemargin -5mm
\voffset 0mm
\hoffset 4mm
\def\longtetep{165mm}
\def\longtetei{165mm}


\parskip 3pt
\renewcommand{\footnoterule}{\vskip 3pt \hbox to 2.35cm{\hrulefill} \vskip 3pt}

\font\twelvesym=msbm10 at 12pt
\font\tensym=msbm10
\font\sevensym=msbm7
\font\fivesym=msbm5

\font\twelvegoth=eufb10 at 12pt
\font\tengoth=eufb10
\font\sevengoth=eufb7
\font\fivegoth=eufb5

\newfam\symfam
\textfont\symfam=\tensym
\scriptfont\symfam=\sevensym
\scriptscriptfont\symfam=\fivesym
\def\sym{\fam\symfam\tensym}

\newfam\gothfam
\textfont\gothfam=\tengoth
\scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}

\def\bb{\sym}
\def\A{{\sym A}}
\def\C{{\sym C}}
\def\E{{\sym E}}
\def\F{{\sym F}}
\def\H{{\sym H}}
\def\K{{\sym K}}
\def\L{{\sym L}}
\def\N{{\sym N}}
\def\Q{{\sym Q}}
\def\R{{\sym R}}
\def\U{{\sym U}}
\def\Z{{\sym Z}}


\def\SG{{\goth S}}


%%%%%%%%%%%%%%%%%%%%%

\frenchspacing
\parindent=0pt
\def\ques#1{\vskip .5cm \hskip -1.6cm \hbox to 1.58cm{\bf #1 \hfill}}
\def\d{\displaystyle}
\def\build#1_#2^#3{\mathrel{\mathop{\kern 0pt#1}\limits_{#2}^{#3}}}
\def\fl#1#2{\build\hbox to 8mm{\rightarrowfill}_{#2}^{#1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%                %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% fin des MACROS %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%                %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                          Corrig\'e 		                   %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{center}
{\Large \bf Mines-Ponts 2002}\\
\vskip 3mm
{\Large \bf Corrig\'e de l'\'epreuve d'informatique}
\vskip 3mm
{\Large \bf (dur\'ee de l'\'epreuve{\,}: 3 heures)}
\end{center}
\thispagestyle{empty}
\vskip 1cm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\parindent=0pt

\section*{1 \quad Exercice de logique des propositions}

\ques{1 --}Notons $F_1$, $F_2$ et $F_3$ les trois formules \'etudi\'ees. Alors{\,}:
\begin{itemize}
\item[--] $F_1$ est satisfiable, en choisissant par exemple la valuation qui associe $vrai$ aux
trois variables $p_i$. 
\item[--] $F_2$ n'est pas satisfiable par pour que la formule soit vraie, il faudrait que $p_2$ et
$\neg p_2$ soient simultan\'ement v\'erifi\'ees.
\item[--] $F_3$ n'est \'egalement pas satisfiable. En effet, $(\neg p_1\vee \neg p_2)\wedge (p_1\vee
\neg p_2)$ est logiquement \'equivalente \`a $\neg p_2$, et donc $F_3$ est logiquement \'equivalente \`a 
$p_2\wedge (\neg p_2) \wedge (p_1\vee \neg p_2 \vee \neg p_3)$ qui n'est clairement pas satisfiable.
\end{itemize}

\ques{2 --}Soit $H$ une formule de Horn et consid\'erons la valuation $v$ associant la valeur $faux$ \`a 
toutes les variables $p_i$. Nous pouvons \'ecrire $H=C_1\wedge \dots \wedge C_m$ o\`u $m\geq 0$ et o\`u les $C_i$ sont des
clauses comportant au moins un litt\'eral n\'egatif. Pour tout $i$, nous avons donc $v(C_i)=vrai$, puis
$v(H)=vrai$ (en remarquant que cela marche, par convention, m\^eme si $m=0$). $H$ est donc
satisfiable.

\ques{3 --}Soit $H$ une formule de Horn de la forme $H=p_k\wedge C_2\dots \wedge C_m$, avec $C_i\not=
\neg p_k$ pour tout $i$ compris entre 2 et $m$. Pour chacun de ces $i$, soit $C'_i$
d\'efinie de la fa\c{c}on suivante{\,}: 
\begin{itemize}
\item si $p_k$ est un litt\'eral de $C_i$, alors $C'_i=T${\,};
\item sinon, $C'_i$ est la clause obtenue en supprimant de $C_i$ les \'eventuels litt\'eraux
de la forme $\neg p_k$.
\end{itemize}
Soit enfin $H'$ la formule de Horn conjonction des $C'_i$ distincts de $T${\,}: $\d H'=\bigwedge_{i,\ C'_i\not= T}
C'_i$. Par construction, nous avons bien ${\cal V}_{H'}\subset {\cal V}_H$. Montrons que $H$ et $H'$
sont simultan\'ement satisfiable.

\begin{itemize}
\item si $H$ est satisfiable, soit $v$ une valuation telle que $v(H)=vrai$. Nous avons alors
$v(p_k)=vrai$, et $v(C_i)=vrai$ pour tout $i$. Si $i$ est tel que $C'_i\not= T$, $C_i$ est \'egal (\`a
l'ordre pr\`es des litt\'eraux) ou \`a $C'_i\wedge (\neg p_k)$, ou \`a $C'_i$. Comme $v(\neg p_k)=faux$,
nous avons dans les deux cas $v(C'_i)=c(C_i)=vrai$, puis $v(H')=vrai${\,}: $H'$ est satisfiable.

\item si $H'$ est satisfiable, soit $v$ une valuation telle que $v(H')=vrai$. Comme $p_k$ n'est pas
une variable de $H'$, nous pouvons (quitte \`a changer $v(p_k)$) supposer que $v(p_k)=vrai$. Pour $i$
compris entre 2 et $m$, deux cas se pr\'esentent{\,}:
\begin{itemize}
\item ou bien $C_i$ contient le litt\'eral $p_k$, et alors $v(C_i)=vrai${\,};
\item ou bien $C_i$ ne contient pas le litt\'eral $p_k$, et alors $C_i$ est de la forme $C'_i\wedge (\neg
p_k)$ ou $C'_i$, puis $v(C_i)=v(C'_i)=vrai$.
\end{itemize}
Nous obtenons donc $v(H)=vrai$ et $H$ est satisfiable.
\end{itemize}

\ques{4 --}Soit $H=C_1\wedge \dots \wedge C_m$ une formule de Horn. Pour d\'eterminer la
satisfiabilit\'e de $H$, on utilise l'algorithme r\'ecursif suivant{\,}:
\begin{itemize}
\item si $H=T$, alors $H$ est satisfiable{\,};
\item sinon, on cherche $i$ tel que la clause $C_i$ ne contienne pas de litt\'eraux n\'egatifs. Si un
tel $i$ n'existe pas, $H$ est satifiable d'apr\`es la question (2). Sinon, la clause $C_i$ est de la
forme $p_{k}$ o\`u $1\leq k \leq n$, puisque les clauses d'une formule de Horn contiennent au plus un
litt\'eral positif. Si l'une des autres clauses de $H$ est r\'eduite \`a $(\neg p_k)$, la formule $H$ n'est
pas satisfiable. Sinon, on applique r\'ecursivement l'algorithme \`a la formule de Horn $H'$ construite
en appliquant la question (3) (on sait que $H$ est satisfiable si et seulement si $H'$ l'est). 
\end{itemize}

\medskip
Cet algorithme se termine car, en cas d'appel r\'ecursif, l'ensemble ${\cal V}_{H'}$ est strictement
contenu dans ${\cal V}_{H}$. Dans le pire des cas, au bout de $n$ appel r\'ecursif, on appliquera
l'algorithme \`a la formule $T$. 

\medskip
Il est difficile de majorer le temps de calcul sans pr\'eciser le type de donn\'ee utilis\'e pour 
stocker les formules. Nous supposerons dans cette question qu'un litt\'eral est un couple
$(i,b)$ o\`u $i$ est un entier et $b$ un bool\'een, $(i,vrai)$ et $(i,faux)$ repr\'esentant respectivement $p_i$
et $\neg p_i$. Une clause sera alors une liste de litt\'eraux, et une formule sous forme normale
conjonctive sera une liste de clauses. Pour traiter le probl\`eme, on commence \`a tester
si l'une des clauses est de la forme $p_k$, ce qui demande un nombre d'op\'erations de l'orde de $m$
(on teste si une des $m$ listes est de taille 1, et associ\'ee \`a un litt\'eral de la forme $(k,vrai)$).
Si la recherche \'echoue, le calcul est termin\'e. Sinon, il faut encore de l'ordre de $m$ op\'erations
pour v\'erifier si l'une des autres clauses est de la forme $\neg p_k$. Si c'est le cas, le calcul est
termin\'e en un temps $\Theta(m)$. Sinon, il faut d\'efinir la formule $H'$, ce qui demande au plus de
l'ordre de $nm$ op\'erations (on parcourt les $m$ clauses, qui sont des listes de longueurs au plus
$2n$). Comme $n(H')\leq n(H)-1$, nous obtenons en notant $T(n,m)$ le temps de
calcul dans les pire des cas pour traiter une formule de Horn contenant $n$ variables et $m$
clauses{\,}:
$$T(n,m)\leq Knm+T(n-1,m)\footnotemark$$
\footnotetext{\ On pourrait aussi remplacer $T(n-1,m)$ par $T(n-1,m-1)$ puisque
$H'$ contient au moins une clause de moins que $H$, mais cela complique le calcul.}Ainsi, nous avons{\,}:
$$T(n,m)\leq Knm+T(n-1,m)\leq Km\bigl(n+n-1\bigr)+T(n-2,m)\leq \dots \leq Km\bigl(n+n-1+n-2+\cdots
+1\bigr)+T(0,m)$$
puis $T(n,m)=O(mn^2)$ puisque $T(0,m)=constante$ (c'est le temps de v\'erifier que la formule est associ\'ee \`a la liste vide).


\ques{5 --}On remarque que la clause $C_1$ est r\'eduite \`a $p_2$ et que ni $C_2$, ni $C_3$ ne sont
r\'eduites \`a $(\neg p_2)$. On pose donc $H'=(\neg p_1)\wedge (p_1)\wedge(p_1\vee \neg p_3)=C'_1\wedge
C'_2\wedge C'_3$. Comme $C'_2=p_1$ et $C'_1=(\neg p_1)$, $H'$ n'est pas satisfiable et $H$ n'est
\'egalement pas satisfiable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{2 \quad Probl\`eme d'algorithmique}
\ques{1 -- a}Le probl\`eme commence par une question tr\`es d\'elicate, en tout cas si l'on veut donner
une preuve pr\'ecise. La situation est plus facile \`a visualiser quand elle est propos\'ee sous la forme
\'equivalente suivante{\,}:
un voleur s'est introduit dans l'arri\`ere boutique d'un joaillier. Il est en pr\'esence de certaines quantit\'es de m\'etaux
pr\'ecieux{\,}: $p_0$ grammes du m\'etal $O_0$, $p_1$ grammes du m\'etal $O_1$, \dots, $p_{n-1}$ grammes du m\'etal $O_{n-1}$.
On suppose ici que les m\'etaux sont class\'es par valeurs d\'ecroissantes, la valeur \'etant le prix du gramme de m\'etal.
Il ne peut (malheureusement{\,}?) d\'erober qu'une masse maximale $Q$, et il cherche donc un remplissage optimal de
son sac \`a dos. Sous cette forme, le commun des mortel est convaincu que le gain maximal s'obtient en utilisant un
algorithme {\sl glouton}{\,}: on prend en priorit\'e le m\'etal $O_1$ (dans sa totalit\'e si $p_1\leq Q$), puis le m\'etal $O_2$
(dans sa totalit\'e si $p_1+p_2\leq Q$) et ainsi de suite, en s'arr\^etant quand le sac \`a dos sera plein 
(dans le cas o\`u $i^* <n$), ou bien quand tous les m\'etaux auront \'et\'e pris dans leur totalit\'e (dans le cas o\`u $i^*=n$).
Est-ce que cette fa\c{c}on de traduire le probl\`eme (m\^eme si elle est peu civique) suffira \`a convaincre le correcteur{\,}?
J'aurais plut\^ot tendance \`a croire que non, mais c'est peut-\^etre une d\'eformation de math\'ematicien. Nous
allons donc donner une preuve ``pr\'ecise'' de ce r\'esultat. 

\medskip
{\bf Premi\`ere m\'ethode}

L'id\'ee naturelle consiste \`a d\'emontrer que si $(y_0,\dots ,y_{n-1})$ est une solution non nulle du probl\`eme, il existe
une autre solution $(z_0,\dots ,z_{n-1})$ v\'erifiant{\,}:
\begin{itemize}
\item il existe $j^*\in \{0,\dots ,n\}$ tel que $z_i=1$ pour $i<j^*$, $z_i=0$ pour $i>j^*$ et
$z_{j^*}\not= 0${\,};
\item $\d\sum_{i=0}^{n-1}u_iz_i\geq \sum_{i=0}^{n-1}u_iy_i$.
\end{itemize}
Une fois cette propri\'et\'e d\'emontr\'ee, nous aurons{\,}:
\begin{itemize}
\item $\sum_{i=0}^{j^*-1}p_i=\sum_{i=0}^{j^*-1}p_iz_i< \sum_{i=0}^{j^*}p_iz_i\leq Q$ donc $j^* \leq
i^*${\,};
\item si $j^*<i^*$, $\sum_{i=0}^{n-1}u_iz_i=\sum_{i=0}^{j^*}u_iz_i\leq \sum_{i=0}^{j^*}u_i \leq 
\sum_{i=0}^{i^*-1}u_i\leq \sum_{i=0}^{n-1}u_ix_i${\,};
\item si $j^*=i^*$, $\sum_{i=0}^{n-1}p_iz_i=\sum_{i=0}^{i^*-1}p_i+p_{i^*}z_{i^*}\leq Q$, donc 
$z_{i^*}\leq \d{Q-\sum_{i=0}^{i^*-1}p_i\over p_{i^*}}=x_{i^*}$. On en d\'eduit{\,}:
$$\sum_{i=0}^{n-1}u_iz_i=\sum_{i=0}^{i^*-1}u_i+u_{i^*}z_{i^*}\leq 
\sum_{i=0}^{i^*-1}u_i+u_{i^*}x_{i^*}=\sum_{i=0}^{n-1}u_ix_i.$$
\end{itemize}
Ainsi, nous aurons $\sum_{i=0}^{n-1}u_iy_i\leq \sum_{i=0}^{n-1}u_iz_i\leq \sum_{i=0}^{n-1}u_ix_i$, ce qui
ach\`evera de d\'emontrer que l'algorithme fournit une solution optimale au probl\`eme du sac \`a dos fractionnaire.

\medskip
La construction de cette solution $(z_i)$ se fait r\'ecursivement. Supposons en effet que $(y_i)$ ne
soit pas de la forme $(1,\dots ,1,y_{j^*},0,\dots ,0)$. C'est donc qu'il existe deux indices $i_0$
et $i_1$ tels que{\,}:
\begin{itemize}
\item $0\leq i_0< j_0\leq n-1${\,};
\item $y=(1,\dots,1,y_{i_0},0,\dots ,0,y_{i_1},\dots,y_{n-1})${\,};
\item $y_{i_0}<1$ et $y_{i_1}>0$.
\end{itemize} 


Nous allons alors ``\'echanger'' une partie de l'objet $i_1$ contre une partie de l'objet $i_0$, de sorte
\`a remplacer ou bien $y_{i_0}$ par 1, ou bien $y_{i_1}$ par 0. Pour cela, posons
$\widetilde{y}_i=y_i$ pour tout $i$ \'el\'ement de $\{0,1,\dots ,n-1\}\setminus
\{i_0,i_1\}$, $\widetilde{y}_{i_0}=y_{i_0}+\varepsilon_0$ et $\widetilde{y}_{i_1}=y_{i_1}-\varepsilon_1$, o\`u $\varepsilon_0$ et
$\varepsilon_1$ sont deux r\'eels v\'erifiant les contraintes{\,}:

\begin{itemize}
\item $0\leq \varepsilon_0\leq 1-y_{i_0}${\,};
\item $0\leq \varepsilon_1\leq y_{i_1}${\,};
\item $p_{i_0}\varepsilon_0=p_{i_1}\varepsilon_1$.
\end{itemize}

Les deux premi\`eres contraintes assurent que l'on a bien $0\leq \widetilde{y}_i\leq 1$ pour tout $i$. La troisi\`eme
permet de conserver l'\'egalit\'e des poids{\,}: $\sum_{i=0}^{n-1}p_i\widetilde{y}_i=\sum_{i=0}^{n-1}p_iy_i$.
Ainsi, il faut choisir $\varepsilon_0$ et $\varepsilon_1$ v\'erifiant{\,}:

\begin{itemize}
\item $0\leq \varepsilon_0\leq 1-y_{i_0}${\,};
\item $0\leq \varepsilon_0\leq \d{p_{i_1}\over p_{i_0}}\,y_{i_1}${\,};
\item $\varepsilon_1=\d{p_{i_0}\over p_{i_1}}\,\varepsilon_1$.
\end{itemize}

En choisissant $\varepsilon_0=\min \left(1-y_{i_0},\d{p_{i_1}\over p_{i_0}}\,y_{i_1}\right)$ puis
$\varepsilon_1=\d{p_{i_0}\over p_{i_1}}\,\varepsilon_0$, nous aurons ainsi construit une solution $(\widetilde{y}_i)$
r\'epondant \`a la question pos\'ee. En effet, selon la valeur du minimum d\'efinissant $\varepsilon_0$, on
a bien
$\widetilde{y}_{i_1}=1$ ou $\widetilde{y}_{i_1}=0$. D'autre part, $(\widetilde{y}_i)$ est plus efficace que $(y_i)${\,}:
\begin{eqnarray*}
\sum_{i=0}^{n-1}u_i\widetilde{y}_i&=&\sum_{i=0}^{n-1}u_iy_i+u_{i_0}\varepsilon_0-u_{i_1}\varepsilon_1\\
&=&\sum_{i=0}^{n-1}u_iy_i+u_{i_0}\varepsilon_0-u_{i_1}{p_{i_0}\over p_{i_1}}\,\varepsilon_0\\
&=&\sum_{i=0}^{n-1}u_iy_i+p_{i_0}\varepsilon_0
\underbrace{\left({u_{i_0}\over p_{i_0}}-{u_{i_1}\over p_{i_1}}\right)}_{\geq 0}\\
&\geq& \sum_{i=0}^{n-1}u_iy_i
\end{eqnarray*}

\medskip
Nous pouvons ainsi r\'ep\'eter cette construction jusqu'\`a ce que l'on obtienne une suite
$(z_i)$ de la forme $(1,\dots ,1,z_{j^*},0,\dots ,0)$. En effet, l'algorithme se termine 
car \`a chaque application de la construction, l'un (au moins) des entiers $i_0$ ou $j_0$ augmente
strictement.

\medskip
{\bf Remarque{\,}:} la preuve peut sembler compliqu\'ee, et on peut penser au premier abord qu'il
serait plus simple de d\'emontrer directement que si une solution $(y_i)$ n'est pas de la forme
$(1,\dots ,1, y_{j^*},0,\dots ,0)$, elle n'est pas optimale (en construisant une solution $(z_i)$
v\'erifiant $\sum_{i=0}^{n-1}u_iz_i >\sum_{i=0}^{n-1}u_iy_i$). On pourrait alors conclure, un argument
de compacit\'e assurant l'existence d'une solution optimale. Malheureusement, 
cela ne fonctionne que si l'on suppose la suite $u_i/p_i$ strictement
d\'ecroissante. Il est bien s\^ur possible de se ramener \`a ce cas, en ``regroupant'' les objets de m\^eme
rapport utilit\'e/poids, mais l\`a encore, il est d\'elicat de donner des arguments pr\'ecis. Le plus
raisonnable serait de ne demander une preuve rigoureuse que dans le cas o\`u la suite $(u_i/p_i)$ est
strictement d\'ecroissante.

\medskip
{\bf Seconde preuve{\,}:}  consid\'erons une solution $(y_i)$. Nous allons imaginer que nous remplissons
le sac \`a dos ``en continu'', la variable $t$ mesurant le poids du sac. Nous obtenons ainsi un graphe
repr\'esentant l'\'evolution de $z$ en fonction de $t$, de la forme{\,}:

$$\pspicture(-2,-2)(6,5.5)
\psline(0,0)(1,2)(3,4)
\psline[linestyle=dashed](3,4)(5,4.5)
\psline(1,0)(1,2)
\psline(0,2)(1,2)
\psline(3,0)(3,4)
\psline(0,4)(3,4)
\psline{->}(-.5,0)(5.5,0)
\psline{->}(0,-.5)(0,5)
\rput{0}(1,-0.5){$p_0y_0$}
\rput{0}(3,-0.5){$p_0y_0+p_1y_1$}
\rput[r]{0}(-0.2,2){$u_0y_0$}
\rput[r]{0}(-0.2,4){$u_0y_0+u_1y_1$}
\rput{0}(5.8,0){$t$}
\rput{0}(0,5.3){$z(t)$}
\endpspicture$$
Si nous notons $f_y$ la fonction $t\mapsto z(t)$, il est clair que $f_y$ est une fonction affine par
morceaux, d\'efinie sur l'intervalle $[0,P_y]$ avec $P_y=\sum_{i=0}^{n-1}p_iy_i$, et dont les points
anguleux sont les points $(t_i,z_i)$ d\'efinis pour $0\leq i\leq n$ par{\,}:
$$t_i=\sum_{j=0}^{i-1} p_jy_j\qquad z_i=\sum_{j=0}^{i-1} u_jy_j,$$
certains points pouvant \^etre confondus si certains $y_i$ sont nuls. L'int\'er\^et de cette fonction est qu'elle
fait appara\^{\i}tre naturellement les quotients $u_i/p_i$, qui sont les pentes des segments formant le graphe de
$f_y${\,}: la d\'ecroissance de ces pentes montre que $f_y$ est une fonction concave.

\medskip
Notons maintenant $f_x$ la fonction associ\'ee \`a la solution $(x_i)$ fournie par l'algorithme glouton.
Pour tout $i$ compris entre $0$ et $n$, nous noterons $(t'_i,z'i)$ le point d\'efini par{\,}:
$$t'_i=\sum_{j=0}^{i-1} p_jx_j\qquad z'_i=\sum_{j=0}^{i-1} u_jx_j.$$
Pour montrer que la solution $(x_i)$ est optimale, il suffit de d\'emontrer que $f_x(P_x)$ est sup\'erieur ou \'egal
\`a $f_y(P_y)$. Pour cela, il suffit de remarquer les deux propri\'et\'es{\,}:

\begin{itemize}
\item $P_x\geq P_y${\,}; en effet, nous sommes dans l'un des deux cas suivants{\,}:
\begin{itemize}
\item $P_x=Q$ et $P_y\leq Q= P_x${\,};
\item $P_x<Q$ et $x$ est la suite constante \'egale \`a 1. On
a encore $\d P_y=\sum_{i=0}^{n-1}p_iy_i\leq \sum_{i=0}^{n-1}p_i=P_x$.
\end{itemize}
\item $f_y(t)\leq f_x(t)$ pour tout $t\in [0,P_y]${\,}; en effet, les fonctions $f_y$ et $f_x$ sont
d\'erivables, sauf peut-\^etre en les points $(t_0,\dots ,t_n,t'_0,\dots ,t'_n)$, et si $t$ est un
r\'eel compris entre 0 et $P_y$ et distinct des $t_i$ et des $t'_i$, nous avons
$f'_y(t)=\d{u_i\over p_i}$ et $f'_x(t)=\d{u_j\over p_j}$ o\`u $i$ et $j$ sont caract\'eris\'es par{\,}:
$$t_{i}<t<t_{i+1}\quad{\rm et}\quad t'_{j}<t<t'_{j+1}.$$
Or $t'_{j}=\d\sum_{k=0}^{j-1} p_kx_k=\d\sum_{k=0}^{j-1} p_i$ (car $x_j\not= 0$), donc 
$t'_{j}\geq \d\sum_{k=0}^{j-1} p_iy_i=t_j$. On en d\'eduit donc que $t>t_j$, i.e. que $i\leq j$, ce qui
donne $\d f_y'(t)={u_i\over p_i}\geq {u_j\over p_j}=f'_x(t)$.

Comme $f_x(0)=0=f_y(0)$, on a bien $f_y(t)\leq f_x(t)$ pour tout $t\in [0,P_y]$.

\end{itemize}
Nous obtenons enfin $f_y(P_y)\leq f_x(P_y)\leq f_x(P_x)$ puisque $f_x$ est croissante.

\ques{1 -- b}Remarquons tout d'abord que  $\d{16\over 15}>{21\over 22}>{19\over 20}>{15\over 17}>{13\over 15}>{7\over
9}$. Nous avons ensuite{\,}:
$$p_0+p_1= 37 < 51 \leq  57 = p_0+p_1+p_2$$ 
donc $i^*=2$ et la solution optimale est obtenue pour{\,}:
$$x_0=x_1=1,\ x_2={51-37\over 20}={7\over 10},\ x_3=x_4=x_5=0.$$
Le maximum obtenu est $\d z_{{\rm max}}=16+21+19\times {7\over 10}={503\over 10}.$

\ques{1 -- c}On utilise simplement une variable bool\'eenne {\tt b} qui garde la valeur {\tt true}
tant que l'on a $u_{i-1}p_i\geq u_ip_{i-1}$. On obtient facilement la fonction {\tt test}
suivante{\,}:

\eject
\tt test := function(): boolean{\,};

var

\hskip .5cm i{\,}: integer{\,};

\hskip .5cm b{\,}: boolean{\,};

begin

\hskip .5cm b := true{\,};

\hskip .5cm i := 1{\,};

\hskip .5cm while b and (i<n) do

\hskip 1cm begin

\hskip 1.5cm b := u[i-1]*p[i] >= u[i]*p[i-1]{\,};

\hskip 1.5cm i := i+1{\,};

\hskip 1cm end{\,};

\hskip .5cm test := b{\,};

end{\,};

\medskip
\rm La terminaison de cet algorithme est assur\'ee puisque la variable {\tt i} est
incr\'ement\'ee d'une unit\'e \`a chaque passage dans la boucle et ne peut pas d\'epasser $n$. Enfin, 
la propri\'et\'e{\,}:

\begin{center}
{\tt b} est \'equivalent \`a $\d\forall j\in \{1,\dots ,i-1\},\ {u_{j-1}\over p_{j-1}}\geq {u_{j}\over
p_{j}}$
\end{center}

est un invariant de boucle, ce qui prouve la correction de l'algorithme.


\ques{1 -- d}Pour calculer $i^*$, il suffit de calculer la somme $S=\sum_{j=0}^{i-1}p_i$ jusqu'\`a ce
que l'on ait $i=n$ ou $S\geq Q$. Nous commen\c{c}ons donc pas initialiser la variable $i$ \`a la
valeur 1 et la variable $S$ \`a la valeur $p_0$. Ensuite, nous ajoutons $p_i$ \`a $S$ et nous 
incr\'ementons $i$ tant que $S<Q$ et $i<n$. {\`A} la sortie de la boucle, ou bien $S<Q$ et
$i=n=i^*$, ou bien $S\geq Q$ et $i^*=i-1$. Il ne reste donc qu'\`a \'ecrire la fonction{\,}:

\medskip
{\tt i\verb|_|star := function(): integer{\,};

var

\hskip .5cm i,S{\,}: integer{\,};

begin

\hskip .5cm i := 1{\,};

\hskip .5cm S := p[0]{\,};

\hskip .5cm while (S<Q) and (i<n) do

\hskip 1cm begin

\hskip 1.5cm S := S+p[i]{\,};

\hskip 1.5cm i := i+1{\,};

\hskip 1cm end{\,};

\hskip .5cm if S<Q then

\hskip 1cm i\verb|_|star := i

\hskip .5cm else

\hskip 1cm i\verb|_|star := i-1{\,};

end{\,};}

\ques{2 -- a}La recherche de $i^*$ se fait de la fa\c{c}on suivante{\,}: on partitionne $\{0,1,\dots
,n-1\}$ en deux sous-ensembles $E'$ et $E''$ gr\^ace \`a ${\cal A}$ de telle sorte que{\,}:
$$\forall i\in E',\ \forall j \in E'',\ {u_i\over p_i}\geq {u_j\over p_j}.$$
On calcule ensuite $S=\d\sum_{i\in E'}p_i$, puis on distingue deux cas{\,}:

\begin{itemize}
\item $1^{\rm er}$ cas{\,}: $S\geq Q$. On applique r\'ecursivement l'algorithme en rempla\c{c}ant $\{0,1,\dots
,n-1\}$ par $E'${\,}; on obtient ainsi $i^*$, $J'$ et $J''$ tels que{\,}:
\begin{itemize}
\item $\{i^*\}$, $J'$ et $J''$ partitionnent $E'${\,};
\item $\forall i\in J',\ \forall j\in J'',\ \d{u_i\over p_i}\geq {u_{i^*}\over p_{i^*}}\geq {u_j\over
p_j}${\,};
\item $\d\sum_{i\in J'}p_i< Q \leq \sum_{i\in J'}p_i +p_{i^*}$.
\end{itemize}
On pose alors $I'=J'$, $I''=J''\cup E''$ et $(i^*,I',I'')$ est une solution au probl\`eme pos\'e.

\item $2^{\rm \acute{e}me}$ cas{\,}: $S<Q$. On applique r\'ecursivement l'algorithme en rempla\c{c}ant $\{0,1,\dots
,n-1\}$ par $E''$ et $Q$ par $Q-S${\,}; on obtient $i^*$, $J'$ et $J''$ tels que{\,}:
\begin{itemize}
\item $\{i^*\}$, $J'$ et $J''$ partitionnent $E''${\,};
\item $\forall i\in J',\ \forall j\in J'',\ \d{u_i\over p_i}\geq {u_{i^*}\over p_{i^*}}\geq {u_j\over
p_j}${\,};
\item $\d\sum_{i\in J'}p_i< Q-S \leq \sum_{i\in J'}p_i +p_{i^*}$.
\end{itemize}
On pose alors $I'=J'\cup E'$, $I''=J''$ et $(i^*,I',I'')$ est une solution au probl\`eme pos\'e.
\end{itemize}

\medskip
Remarque{\,}: l'algorithme se termine correctement car la somme des $p_i$ est sup\'erieure ou \'egale \`a
$Q$.

\ques{2 -- b}Nous sommes dans le cas classique d'un algorithme dichotomique{\,}: en notant $T(n)$ le
temps de calcul dans le pire des cas pour traiter un probl\`eme de taille $n$, nous avons{\,}:
$$\forall m\geq 1,\ T(2^m)\leq K2^m+T(2^{m-1}),$$
le terme $K2^m$ repr\'esentant une majoration du temps de calcul de $E'$, $E''$ et $S$ ($K$ est une constante). Nous en
d\'eduisons par une r\'ecurrence \'el\'ementaire{\,}:
$$\forall m\geq 1,\ T(2^m)\leq T(1)+K\sum_{i=1}^m 2^i \leq T(1)+2K(2^m-1),$$
ce qui prouve que l'algorithme est lin\'eaire (en g\'en\'eralisant, comme propos\'e par l'\'enonc\'e, aux entiers
$n$ quelconques).

\ques{2 -- c}Il n'y a presque rien \`a dire{\,}: on calcule en un temps lin\'eaire le triplet $(i^*,
I',I'')$ comme dans la question (a). Il reste \`a poser pour tout $i$ dans $\{0,1,\dots ,n-1\}${\,}:
$$x_i=\cases{\hfil 1\hfil &si $i\in I'$,\cr
             \noalign{\vskip 2mm}
             \hfil 0\hfil &si $i\in I''$,\cr  
             \noalign{\vskip 2mm}
             \d{Q-\sum_{j\in I'}p_j\over p_{i^*}}&si $i=i^*$,\cr}$$
pour obtenir une solution optimale, par application de la question (1a). 

\medskip
Remarque{\,}: si l'on commence par trier les quantit\'es $u_i/p_i$, le probl\`eme du sac \`a dos
fractionnaire est r\'esolu en un temps quasi-lin\'eaire. Gr\^ace \`a ce nouvel algorithme, nous obtenons la
solution du probl\`eme en temps lin\'eaire. 


\ques{3 --}Une solution du probl\`eme du sac \`a dos 0-1 est \'egalement une solution du probl\`eme du sac \`a
dos fractionnaire{\,}: la solution optimale du sac \`a dos 0-1 est donc moins bonne que la solution
optipale du sac \`a dos fractionnaire.

\ques{4 --}{\bf Remarque{\,}:} la strat\'egie propos\'ee n'est pas, comme l'\'enonc\'e le dit, une strat\'egie
de type {\sl diviser pour r\'egner}, mais simplement une \'etude de toutes les solutions r\'ealisables en
vue de calculer la solution optimale. C'est en fait un algorithme {\sl na\"{\i}f}, dont le temps de calcul dans
le pire des cas est exponentiel.

\medskip
Pour pouvoir \'ecrire une fonction r\'ecursive, nous allons un peu g\'en\'eraliser le probl\`eme{\,}: 
la fonction {\tt sacados\verb|_|aux} va prendre trois variables ({\tt k,S,x}) en arguments,
avec {\tt k,S} de type {\tt integer} et {\tt x} de type {\tt array[0..n-1] of integer}, et renvoyer
un entier. L'appel {\tt sacados\verb|_|aux(k,S,x)} r\'esout le probl\`eme
du sac \`a dos 0-1 restreint aux inconnues $(x_{k},\dots ,x_{n-1})$  pour le poids total {\tt S}, et
assigne aux entr\'ees d'indice $k$, \dots ,$n-1$ de {\tt x} les valeurs donnant une solution optimale,
puis renvoie la valeur de $z$ maximale. Autrement-dit, l'instruction {\tt sacados\verb|_|aux(k,x,S)},
stocke dans la table {\tt x} entre l'indice $k$ et l'indice $n-1$ une solution du probl\`eme{\,}:
$$\left\{\begin{array}{l}
         {\rm Maximiser}\ z=\d\sum_{i=k}^{n-1}u_ix_i\\
         \\
         {\rm avec\ les\ contraintes{\,}:}\\
         \\ 
         \qquad\d\sum_{i=k}^{n-1}p_ix_i\leq S\\
         \\
         \qquad{\rm et\ pour}\ i\in \{k,k+1,\dots ,n-1\},\ x_i\in \{0,1\}
         \end{array}\right.$$
et renvoie l'entier $\d\sum_{i=k}^{n-1}u_ix_i$.

La proc\'edure principale {\tt sacados} s'\'ecrira alors{\,}:


\medskip
{\tt sacados := procedure(var x:array[0..n-1] of integer){\,};

begin

\hskip .5cm sacados\verb|_|aux(0,Q,x){\,};

end{\,};}

\medskip
L'algorithme utilis\'e pour la fonction auxilliaire est \'el\'ementaire{\,}: 
\begin{itemize}
\item si $k=n-1$, on teste si $p_{n-1}$ est inf\'erieur ou \'egal \`a $S$. Si c'est le cas, on assigne \`a
$x[n-1]$ la valeur 1 et on renvoie la valeur $u_{n-1}$. Sinon, on assigne \`a
$x[n-1]$ la valeur 0 et on renvoie la valeur $0$.
\item si $0\leq k<n-1$, on teste si $p_k$ est inf\'erieur ou \'egal \`a $S$. 
\begin{itemize}
\item Si c'est le cas, on applique r\'ecursivement la proc\'edure aux triplets $(k+1,S,y0)$ et
$(k+1,S-p_k,y1)$, qui correspondent respectivement aux choix $x_k=0$ et $x_k=1$. Ces deux appels 
fournissent deux valeurs $z_0$ et $z_1${\,}: si $z_0>z_1+u_k$, on recopie dans {\tt x} les valeurs
contenues dans $y0$ pour les indices $k+1$, \dots ,$n-1$, on assigne \`a $x[k]$ la valeur 0 et
on renvoie la valeur $z_0$. Sinon, on recopie dans $x$ les valeurs contenues dans $y1$ pour 
les indices $k+1$, \dots ,$n-1$, on assigne \`a $x[k]$ la valeur 1 et on renvoie la valeur
$z_1+u_k$.

\item Sinon, on assigne \`a $x[k]$ la valeur 0 (on ne peut pas choisir $x_k=1$), puis on applique la proc\'edure
au triplet $(k+1,S,x)$, dont le r\'esultat donne \'egalement la valeur que nous devons renvoyer.
\end{itemize}
\end{itemize}

\eject

\medskip
{\tt sacados\verb|_|aux := function(k,S:integer; var x:array[0..n-1] of integer): integer{\,};

var

\hskip .5cm y0,y1{\,}: array[0..n-1] of integer{\,};

\hskip .5cm i,z0,z1{\,}: integer{\,};

begin

\hskip .5cm if k=n-1 then

\hskip 1cm if p[n-1]<=S then

\hskip 1.5cm begin

\hskip 1.5cm x[n-1] := 1{\,};

\hskip 1.5cm sacados\verb|_|aux := u[n-1]{\,};

\hskip 1.5cm end

\hskip 1cm else

\hskip 1.5cm begin

\hskip 1.5cm x[n-1] := 0{\,};

\hskip 1.5cm sacados\verb|_|aux := 0{\,};

\hskip 1.5cm end{\,};

\hskip .5cm else

\hskip 1cm if p[k]<=S then

\hskip 1.5cm begin

\hskip 1.5cm z0 := sacados\verb|_|aux(k+1,S,y0){\,};

\hskip 1.5cm z1 := sacados\verb|_|aux(k+1,S,y1){\,};

\hskip 1.5cm if z0>z1+u[k] then

\hskip 2cm begin

\hskip 2cm x[k] := 0; 

\hskip 2cm for i:=k+1 to n-1 do x[i]:=y0[i] ;

\hskip 2cm sacados\verb|_|aux:=z0{\,};

\hskip 2cm end

\hskip 1.5cm else

\hskip 2cm begin

\hskip 2cm x[k] := 1; 

\hskip 2cm for i:=k+1 to n-1 do x[i]:=y1[i] ;

\hskip 2cm sacados\verb|_|aux:=z1+u[k]{\,};

\hskip 2cm end

\hskip 1.5cm end

\hskip 1cm else

\hskip 1.5cm begin

\hskip 1.5cm x[k] := 0{\,};

\hskip 1.5cm sacados\verb|_|aux := sacados\verb|_|aux(k+1,S,x){\,};

\hskip 1.5cm end{\,};

end{\,};}

\ques{5 --}Si $T(n)$ d\'esigne le temps de calcul dans le pire des cas pour des donn\'ees de taille $n$,
nous avons 
$$T(n)=2T(n-1)+K_1n+K_2$$ 
o\`u $K_1$ et $K_2$ sont des constantes{\,}: $K_1n+K_2$ repr\'esente le temps de recopie des $n$
entr\'ees de {\tt x} auquel s'ajoute le temps (constant) pris pour effectuer les diff\'erents tests. En
posant $\alpha_n=\d{T(n)\over 2^n}$, nous obtenons{\,}:
$$\alpha_n={T(n)\over 2^n}=\alpha_{n-1}+ {K_1n+K_2\over 2^n}=\dots =T(0)+\sum_{k=1}^n {K_1k+K_2\over 2^k}.$$
Comme la s\'erie de terme g\'en\'eral $\d{K_1k+K_2\over 2^k}$ converge, la suite $\alpha_n$ a une limite
non nulle $L$. On en d\'eduit que $T(n)$ est \'equivalent \`a $L\,2^n$ quand $n$ tend vers l'infini{\,}:
le temps de calcul est exponentiel (c'\'etait \'evident puisque dans le pire des cas, il y a $2^n$ suites
r\'ealisables, qui doivent toutes \^etre \'etudi\'ees).

\ques{6 -- a}On a $p_0+p_1=37<51$. Comme $51-37=14$ est strictement inf\'erieur \`a $p_2$, $p_3$, $p_4$
et $p_5$, la seule solution r\'ealisable contenu dans le sommet $C$ est $(1,1,0,0,0,0)${\,}: c'est
donc la meilleure solution r\'ealisable contenue dans $C$. Sa valeur est \'egale \`a $u_0+u_1=37$.

\ques{6 -- b}$p_0+p_2=35<51$. Comme $p_3=17>51-35$, on est oblig\'e de choisir $x_3=0$. Par contre,
$p_4=15\leq 51-35$. On peut donc choisir $x_4=1$ ou $x_4=0$. En traitant de la m\^eme fa\c{c}on la
variable $x_5$, on obtient trois solutions r\'ealisables contenues dans $E${\,}:
$(1,0,1,0,1,0)$, $(1,0,1,0,0,1)$ et $(1,0,1,0,0,0)$, de valeurs respectivement $u_0+u_2+u_4=48$,
$u_0+u_2+u_5=42$ et $u_0+u_2=35$. La meilleure solution r\'ealisable contenue dans $E$ est donc 
$(1,0,1,0,1,0)$, de valeur \'egale \`a 48.

\ques{6 -- c}On applique la question (1a), en remarquant que $15/17\geq 13/15\geq \d\frac 79${\,}:
$x_3=x_4=1$ et $x_5=\d\frac 49$ donne la solution fractionnaire optimale, avec $15x_3+13x_4+7x_5=31+\d\frac
19$. On en d\'eduit que $\d M=u_0+31+\frac 19=47+\frac 19$ est une \'evaluation du sommet $F$. 
On en d\'eduit que les solutions r\'ealisables contenues dans $F$ sont strictement moins bonnes que la
solution r\'ealisable $(1,0,1,0,1,0)${\,}: la solution optimale du probl\`eme $({\cal P})$ n'est donc
pas contenue dans $F$.

\ques{6 -- d}La m\'ethode est la m\^eme que pr\'ec\'edemment{\,}: la solution maximale du probl\`eme
fractionnaire d\'efini pour le sommet $G$ est $(x_1,x_2,x_3,x_4,x_5)=(1,1,\d\frac 9{17},0,0)$. La
quantit\'e $M=u_1+u_2+\d{9\over 17}\,u_3=47+\d{16\over 17}$ est donc une \'evaluation du sommet $G$. Cette
valeur \'etant \'egalement strictement inf\'erieure \`a 48, le sommet $G$ ne contient pas de solution
r\'ealisable optimale.

\ques{6 -- e}Les calculs pr\'ec\'edents prouvent que le probl\`eme ${\cal P}$ a pour solution optimale la
suite $x=(1,0,1,0,1,0)$, avec $\d\sum_{i=0}^5 u_ix_i=48$ et $\d\sum_{i=0}^5 p_ix_i=48\leq 51$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{3 \quad Exercice sur les automates finis}
\ques{1 --}Soit ${\cal A}=<Q,A,E,I,T>$ un automate reconnaissant $L$. Soit alors
${\cal A}_{\rm n}=<Q_{\rm n},A,E_{\rm n},I_{\rm n},T_{\rm n}>$ d\'efini de
la fa\c{c}on suivante{\,}:
\begin{itemize}
\item[a)] $Q_{\rm n}=Q\cup \{i,t\}$ o\`u $i$ et $t$ sont deux \'el\'ements distincts n'appartenant pas \`a $Q${\,};
\item[b)] $I_{\rm n}=\{i\}$ et $T_{\rm n}=\{t\}${\,};
\item[c)] $E_{\rm n}=E\cup\{(i,a,q),\ \exists\,i_0\in  I,\ (i_0,a,q)\in E\} \cup\{(q,a,t),\ \exists\,t_0\in T,\ (q,a,t_0)\in
E\}$
\item[] \hskip 3cm $\cup\{(i,a,t),\ \exists\,i_0\in I,\ \exists\,t_0\in T,\ (i_0,a,t_0)\in E\}$
\end{itemize}

Autrement dit, pour chaque transition $(q_0,a,q_1)$ de ${\cal A}$, on d\'efinit dans l'automate ${\cal
A}_{\rm n}${\,}:
\begin{itemize}
\item une transition si $q_0\not\in I$ et $q_1\not\in T${\,}: la transition $(q_0,a,q_1)${\,};
\item deux transitions si $q_0\in I$ et $q_1\not\in T${\,}: les transitions $(q_0,a,q_1)$ et $(i,a,q_1)${\,};
\item deux transitions si $q_0\not\in I$ et $q_1\in T${\,}: les transitions $(q_0,a,q_1)$ et $(q_0,a,t)${\,}
\item quatre transitions si $q_0\in I$ et $q_1\in T${\,}: les transitions $(q_0,a,q_1)$,
$(i,a,q_1)$, $(q_0,a,t)$ et $(i,a,t)$.
\end{itemize}
Par construction, l'automate ${\cal A}_{\rm n}$ est normalis\'e. Il reste donc \`a montrer qu'il
reconna\^{\i}t le langage $L\setminus \{1_{A^*}\}${\,}:
\begin{itemize}
\item soit $u\in L({\cal A})$ diff\'erent du mot vide, et soit $i_0\fl {a_1}{{\cal A}} q_1\fl {a_2}{{\cal A}} q_2\dots 
\fl {a_{n-1}}{{\cal A}} q_{n-1}\fl {a_n}{{\cal A}} t_0$ un calcul r\'eussi d'\'etiquette $u$. Alors 
$i\fl {a_1}{{\cal A}_{\rm n}} q_1\fl {a_2}{{\cal A}_{\rm n}} q_2\dots \fl 
{a_{n-1}}{{\cal A}_{\rm n}} q_{n-1}\fl {a_n}{{\cal A}_{\rm n}}t$ est un calcul r\'eussi de
${\cal A}_{\rm n}$ d'\'etiquette $u$ et $u\in L({\cal A}_{{\rm n}})$.
\item soit $u\in L({\cal A}_{{\rm n}})$ et soit $i\fl {a_1}{{\cal A}_{\rm n}} q_1\fl {a_2}{{\cal A}_{\rm n}} q_2\dots \fl 
{a_{n-1}}{{\cal A}_{\rm n}} q_{n-1}\fl {a_n}{{\cal A}_{\rm n}}t$ est un calcul r\'eussi d'\'etiquette
$u$. On peut remarquer que les \'etats $q_1,\dots ,q_{n-1}$ sont des \'el\'ements de $E$, puisqu'ils sont
\`a la fois origine et extr\'emit\'e de transitions de l'automate normalis\'e ${\cal A}_{\rm n}$.
D'autre part, $n\geq 1$ et $u\not= 1_{A^*}$ car $i\not= t$. On montre ensuite que $u\in L$ en distinguant deux cas{\,}:
\begin{itemize}

\item si $n=1$, $u=a_1\in A$ et $i\fl  {a_1}{{\cal A}_{\rm n}} t${\,}; il existe donc $i_0\in I$ et $t_0\in T$
tels que $i_0\fl  {a_1}{{\cal A}} t_0${\,}: $u\in L${\,};

\item si $n\geq 2$, il existe $i_0\in I$ et $t_0\in T$ tels que $i_0\fl  {a_1}{{\cal A}}q_1$
et $q_{n-1}\fl  {a_n}{{\cal A}}t_0$. On en d\'eduit donc que $i_0\fl {a_1}{{\cal A}} q_1\fl {a_2}{{\cal A}} q_2\dots 
\fl {a_{n-1}}{{\cal A}} q_{n-1}\fl {a_n}{{\cal A}} t_0$ est un calcul r\'eussi de ${\cal A}$ d'\'etiquette
$u${\,}: $u\in L$.
\end{itemize}
\end{itemize}

\ques{2 --}Consid\'erons une copie ${\cal A}'=<Q',A,E',I',T'>$ de l'automate ${\cal A}${\,}; autrement
dit, les ensembles $Q$ et $Q'$ sont disjoints et il existe une bijection $\varphi$ de $Q$ sur $Q'$
telle que $\varphi(I)=I'$, $\varphi(T)=T'$ et $E'=\{(\varphi(p),a,\varphi(q)),\ p,q\in Q,\ a\in A,\
(p,a,q)\in E\}$. Soit alors ${\cal A}_q=<Q_q,A,E_q,E_q,I_q,T_q>$ l'automate d\'efini comme suit{\,}:
\begin{itemize}
\item $Q_q$ est la r\'eunion de $Q$ et de $Q'$, dans laquelle les \'etats $t$ et $\varphi(i)$ ont \'et\'e identifi\'es{\,};
\item $I_q=\{q\}${\,};
\item $T_q=\{\varphi(q)\}${\,};
\item $E_q=E\cup E'$ (avec un abus d'\'ecriture d\^u \`a l'identification de $t$ et de $\varphi(i)$).
\end{itemize}
En reprenant le sch\'ema propos\'e par l'\'enonc\'e, l'automate ${\cal A}_q$ admet la repr\'esentation
suivante ($\varphi$ n'appara\^{\i}t pas pour ne pas alourdir le sch\'ema){\,}:

$$\pspicture(0,-2.5)(12,2.5)
\psset{unit=.5cm}

\pnode(3.8,-2.2){P}
\cnodeput(5.5,-2.2){Q}{$q$}
\ncline{->}{P}{Q}

\cnodeput(0,0){B}{$i$}
\pnode(4,1){C}
\pnode(4,-1){D}
\pnode(8,2){E}
\pnode(8,0){F}
\pnode(8,-2){G} 
\cnodeput(12,0){H}{$t,i$}
\ncline{->}{B}{C}
\ncline{->}{B}{D}
\ncline{->}{E}{H}
\ncline{->}{F}{H}
\ncline{->}{G}{H}
\pscircle(6,0){3.5} 

\pnode(19.3,-2.2){PP}
\cnodeput(17.5,-2.2){QQ}{$q$}
\ncline{->}{QQ}{PP}

\pnode(16,1){CC}
\pnode(16,-1){DD}
\pnode(20,2){EE}
\pnode(20,0){FF}
\pnode(20,-2){GG} 
\cnodeput(24,0){HH}{$t$}
\ncline{->}{H}{CC}
\ncline{->}{H}{DD}
\ncline{->}{EE}{HH}
\ncline{->}{FF}{HH}
\ncline{->}{GG}{HH}
\pscircle(18,0){3.5} 


\endpspicture$$
On peut \'egalement remarquer que les \'etats $i$ et $\varphi(t)$ peuvent \^etre supprim\'es ($i$ n'est pas accessible et
$\varphi(t)$ n'est pas co-accessible). ${\cal A}_q$ est alors un automate (non normalis\'e) qui reconna\^{\i}t le langage $G_q$. En effet, un
calcul r\'eussi dans cet automate passera une et une seule fois par l'\'etat $\{t,\varphi(i)\}$, et sera
donc de la forme{\,}:
$$q\fl v{{\cal A}_q}\{t,\varphi(i)\}\fl u{{\cal A}_q}\varphi(q).$$
On a alors par d\'efinition de $E_q$ un calcul $q\fl v{{\cal A}}t$ et un calcul $i\fl u{{\cal A}}q$.
On en d\'eduit qu'il existe un calcul r\'eussi de ${\cal A}${\,}: $i\fl u{{\cal A}}q \fl v{{\cal A}}t$,
et donc $vu\in G_q$. 

\medskip
R\'eciproquement, si un mot $g$ est \'el\'ement de $G_q$, il existe une factorisation $g=vu$ et un calcul
r\'eussi de ${\cal A}$ de la forme $i\fl u{{\cal A}}q \fl v{{\cal A}}t$. On en d\'eduit que
$q\fl v{{\cal A}_q}\{t,\varphi(i)\}\fl u{{\cal A}_q}\varphi(q)$ est un calcul r\'eussi de ${\cal
A}_q$, i.e. que $g$ est \'el\'ement de $L({\cal A}_q)$.

\ques{3 --}Si $L$ contient le mot vide, ${\rm Conj}(L)=\{1_{A^*}\}\d\bigcup \left(\d\bigcup_{q\in L\atop q\not=i,\
q\not= t}G_q\right)$. Sinon, ${\rm Conj}(L)=\d\bigcup_{q\in L\atop a\not=i,\ q\not= t}G_q$. Dans tous
les cas,  ${\rm Conj}(L)$ est une r\'eunion finie de langages reconnaissables{\,}: il est donc
reconnaissable puisque ${\rm Rec}(A)$ est stable par union finie.


\end{document}



