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


% \`a compiler en LaTeX 2.09 et \`a visualiser en Post Script
% l'\'enonc\'e commence \`a la ligne 102

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                          Enonc\'e 		                   %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{center}
{\Large \bf MINES-PONTS 2002{\,}: \'epreuve d'informatique}
{\Large \bf Fili\`ere MP}
\vskip 3mm
{\Large \bf (dur\'ee de l'\'epreuve{\,}: 3 heures)}
\end{center}
\thispagestyle{empty}
\vskip 2cm

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


\begin{center}
{\large\bf RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES}
\end{center}

\medskip
{\bf
\begin{itemize}
\item L'\'enonc\'e de cette \'epreuve, y compris cette page de garde, comporte 8 pages.
\item Si, au cours de l'\'epreuve, un candidat ou une candidate rep\`ere ce qui lui semble \^etre une
erreur d'\'enonc\'e, il ou elle la signale sur sa copie et poursuit sa composition en expliquant les
raisons des initiatives qu'il ou elle a d\'ecid\'e de prendre.
\item Tout r\'esultat fourni dans l'\'enonc\'e peut \^etre utilis\'e pour les questions ult\'erieures m\^eme s'il
n'a pas \'et\'e d\'emontr\'e.
\item Il ne faut pas h\'esit\'e \`a formuler les commentaires qui semblent pertinents m\^eme lorsque
l'\'enonc\'e ne les demande pas explicitement.
\item L'utilisation d'une calculatrice ou d'un ordinateur est interdite.
\end{itemize}}

\medskip
\begin{center}
{\large\bf COMPOSITION DE L'\'EPREUVE}
\end{center}

\medskip
L'\'epreuve comprend trois parties ind\'ependantes{\,}:
\begin{itemize}
\item un exercice de logique des propositions, \`a r\'esoudre en 30 mn environ{\,};
\item un probl\`eme d'algorithmique, \`a r\'esoudre en 120 mn environ{\,};
\item un exercice sur les automates, \`a r\'esoudre en 30 mn environ.
\end{itemize}

\vfill
\eject

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

\section*{1 \quad Exercice de logique des propositions -- 30 mn environ}
\begin{center}
{\bf D\'efinitions et notations}
\end{center}

\hskip 6mm On consid\`ere un ensemble fini de $n$ variables propositionnelles ${\cal V}=\{p_1,\dots ,p_n\}$, et
l'ensemble ${\cal F}_{\cal V}$ des formules construites \`a partir des variables propositionnelles de
${\cal V}$, des connecteurs usuels de conjonction (not\'e $\wedge$) et de disjonction (not\'e $\vee$),
et de la n\'egation ($\neg$). On consid\`ere que la formule sans aucune variable propositionnelle
(formule vide), not\'ee $T$, est un \'el\'ement de ${\cal F}_{\cal V}$. 

\hskip 6mm Toutes les formules consid\'er\'ees dans cet exercice sont des formules de ${\cal F}_{\cal V}$.

\hskip 6mm Pour toute formule $F$, ${\cal V}_{F }$ d\'esigne l'ensemble des variables propositionnelles qui
apparaissent dans $F$.

\hskip 6mm On appelle {\sl litt\'eral} une variable propositionnelle ou bien la n\'egation d'une variable
propositionnelle. Le litt\'eral est dit {\sl positif} dans le premier cas, et {\sl n\'egatif} dans le
second cas.

\hskip 6mm On appelle {\sl clause} toute formule de la forme $l_1\vee \dots \vee l_q$, o\`u $q\geq 1$ et
$l_1,\dots ,l_q$ sont des litt\'eraux deux \`a deux distincts.

\hskip 6mm On dit qu'une formule est sous {\sl forme normale conjonctive} si elle est de la forme $C_1\wedge
\dots \wedge C_m$, o\`u $m\geq 0$ et $C_1,\dots ,C_m$ sont des clauses (pour $m=0$, on obtient $T$).

\hskip 6mm Une {\sl formule de Horn} est une formule sous forme normale conjonctive telle que chacune de ses
clauses comporte au plus un litt\'eral positif.

\hskip 6mm Enfin, rappelons qu'une formule est satisfiable s'il existe une valuation \`a valeur dans
$\{vrai,faux\}$ de ses variables propositionnelles qui rende la formule vraie. La formule $T$ est
consid\'er\'ee comme satisfiable.

\begin{center}
{\bf \'Enonc\'e de l'exercice}
\end{center}



\hskip -6mm 1 -- Dans les exemples suivants, pr\'eciser si les formules sont satifiables ou non. Quand cela est
possible, donner un exemple de valuation des variables propositionnelles qui rende la formule vraie.

\begin{tabbing}
\=i)\ \ \  \=$(\neg p_1\vee p_2)\wedge (p_1\vee \neg p_2\vee \neg p_3)$\\
\\
\>ii) \>$(p_2)\wedge(\neg p_1\vee \neg p_3)\wedge (\neg p_2)\wedge (p_1\vee \neg p_3\vee \neg p_4)$\\
\\
\>iii) \>$(p_2)\wedge (\neg p_1\vee \neg p_2)\wedge (p_1\vee \neg p_2)\wedge (p_1\vee \neg p_2 \vee \neg p_3)$
\end{tabbing}

\medskip
\hskip -6mm 2 -- Soit $H$ une formule sous forme normale conjonctive telle que chacune de ses clauses contienne
au moins un litt\'eral n\'egatif. Montrer que $H$ est satisfiable en exhibant une valuation de ${\cal
V}$.

\medskip
\hskip -6mm 3 -- Soit $H$ une formule de Horn telle qu'une de ses clauses soit restreinte \`a un litt\'eral positif
$p_k$ (o\`u $k$ est dans $\{1,\dots ,n\}$), et qu'aucune autre de ses clauses ne soit restreinte \`a
$\neg p_k$. Montrer que l'on peut construire \`a partir de $H$ une formule de Horn $H'$ telle que{\,}:
\begin{itemize}
\item[--] ${\cal V}_{H'} \subset {\cal V}_{H'}\setminus \{p_k\}$,
\item[--] $H$ est satisfiable si et seulement si $H'$ est satisfiable.
\end{itemize}

\medskip
\hskip -6mm 4 -- D\'eduire des deux questions pr\'ec\'edentes un algorithme permettant de d\'eterminer si une formule de
Horn $H$ est satisfiable{\,}; la complexit\'e dans le pire des cas de cet algorithme doit \^etre 
major\'ee par un polyn\^ome en $n$ et $m$ (o\`u $n$ et $m$ d\'esignent respectivement le nombre de variables
propositionnelles et le nombre de clauses de $H$), propri\'et\'e que l'on justifiera. Cet algorithme
sera explicit\'e sans utiliser un langage de programmation.

\medskip
\hskip -6mm 5 -- Appliquer l'algorithme de la question 4 \`a l'exemple iii) de la question 1.

\medskip
\begin{center}
{\bf FIN DE L'EXERCICE DE LOGIQUE DES PROPOSITIONS}
\end{center}

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

\section*{2 \quad Probl\`eme d'algorithmique -- 120 mn environ}

{\bf Pr\'eliminaire.} Il faudra \'ecrire des programmes \`a l'aide d'un langage de programmation qui
pourra \^etre soir {\bf Pascal}, soit {\bf Caml}, tout autre langage \'etant exclu. {\bf Indiquer le
langage de programmation choisi.}

\medskip
{\bf Attention{\,}!} Il est interdit de modifier ce choix au cours de l'\'epreuve.

\medskip
\begin{center}
{\bf Le probl\`eme du sac \`a dos}
\end{center}
\medskip

\hskip 6mm On consid\`ere le probl\`eme suivant{\,}: Madame X doit partir en voyage{\,}; elle emporte un sac \`a dos
qui peut supporter au maximum un poids $Q$, poids qui est un entier strictement positif. Par
ailleurs, elle dispose de $n$ objets num\'erot\'es par 0, 1, \dots , $n-1$. Pour tout $i$ appartenant \`a 
0, 1, \dots , $n-1$, l'objet de num\'ero $i$ poss\`ede deux caract\'eristiques{\,}: son utilit\'e not\'ee $u_i$
et son poids not\'e $p_i$ qui sont des entiers strictement positifs. Madame X d\'esire emporter certains
de ces objets dans son sac \`a dos{\,}; le poids total des objets emport\'es ne doit pas d\'epasser
$Q${\,}; elle cherche \`a maximiser la somme des utilit\'es des objets qu'elle emporte parmi les
contenus possibles ne d\'epassant pas au total le poids $Q$.

\medskip
{\bf Attention{\,}:} pour la programmation que vous aurez \`a faire ult\'erieurement{\,}:

\begin{itemize}
\item[--] le nombre $n$ est m\'emoris\'e dans une variable enti\`ere nomm\'ee aussi $n${\,};
\item[--] les quantit\'es $u_i$ et $p_i$ sont m\'emoris\'ees dans des tableaux d'entiers nomm\'es
respectivement $u$ et $p$ et indic\'es de $0$ \`a $n-1${\,};
\item[--] la quantit\'e $Q$ est m\'emoris\'ee dans une variable enti\`ere nomm\'ee aussi $Q$.
\end{itemize}

\medskip
Quand on \'ecrira une fonction (ou une proc\'edure) dans le langage de programmation choisi, les
tableaux $u$ et $p$ ainsi que les variables $Q$ et $n$ seront suppos\'es d\'ej\`a d\'efinis comme variables
globales et initialis\'es avec les donn\'ees du probl\`eme. Apr\`es l'initialisation, \`a l'indice $i$ du
tableau $u$ (resp. $p$) se trouve la valeur $u_i$ (resp. $p_i$).

\medskip
{\bf Notation.} Si $x$ est un nombre r\'eel, $\lfloor x\rfloor$ d\'esigne la partie enti\`ere par d\'efaut
de $x$ (c'est-\`a-dire le plus grand entier inf\'erieur ou \'egal \`a $x$) tandis que $\lceil x\rceil$ d\'esigne sa
partie enti\`ere par exc\`es (c'est-\`a-dire le plus petit entier sup\'erieur ou \'egal \`a $x$).

\begin{center}
{\bf Premi\`ere partie}\\
{\bf Sac \`a dos fractionnaire}
\end{center}


Dans cette partie, les objets sont fractionnables. On note $x_i$ la quantit\'e de l'objet num\'ero $i$
emport\'ee par Madame X. Le probl\`eme s'\'ecrit{\,}:
$$\left\{\begin{array}{l}
         {\rm Maximiser}\ z=\d\sum_{i=0}^{n-1}u_ix_i\\
         \\
         {\rm avec\ les\ contraintes{\,}:}\\
         \\ 
         \qquad\d\sum_{i=0}^{n-1}p_ix_i\leq Q\\
         \\
         \qquad{\rm et\ pour}\ i\in \{0,1,\dots ,n-1\},\ x_i\in [0,1]
         \end{array}\right.$$


\hskip -6mm 1 -- On suppose que, pour tout $i$ appartenant \`a $\{1,\dots ,n-1\}${\,}:
$${u_{i-1}\over p_{i-1}} \geq {u_i\over p_i}.$$
On d\'efinit un entier $i^*$ compris entre 0 et $n$ par{\,}:
$$\left\{\begin{array}{l}
         {\rm si}\ \d\sum_{i=0}^{n-1}p_i<Q,\ {\rm alors}\ i^*=n\\
         \\
         {\rm si}\ p_0\geq Q,\ {\rm alors}\ i^*=0
         \\ 
         {\rm si}\ p_0<Q\ {\rm et}\ \d\sum_{i=0}^{n-1}p_i\geq Q,\ {\rm alors}\ i^*\ {\rm v\'erifie}\
         \d\sum_{i=0}^{i^*-1}p_i<Q\leq \sum_{i=0}^{i^*}p_i
         \end{array}\right.$$


\medskip
a -- Montrer qu'une solution maximale pour le probl\`eme est donn\'ee par{\,}:
$$\left\{\begin{array}{l}
         {\rm pour}\ i\ {\rm v\'erifiant}\ 0\leq i \leq i^*-1,\ x_i=1\\
         \\
         {\rm pour}\ i\ {\rm v\'erifiant}\ i^*+1\leq i \leq n-1,\ x_i=0\\
         \\ 
         {\rm si}\ i^*\not= n,\ x_{i^*}=\d{Q-\sum_{i=0}^{i^*-1}p_i\over p_{i^*}}
         \end{array}\right.$$


\medskip
b -- R\'esoudre le probl\`eme du sac \`a dos fractionnaire suivant{\,}:
$$\left\{\begin{array}{l}
         {\rm Maximiser}\ z=16x_0+21x_1+19x_2+15x_3+13x_4+7x_5\\
         \\
         {\rm avec\ les\ contraintes{\,}:}\\
         \\ 
         \qquad 15x_0+22x_1+20x_2+17x_3+15x_4+9x_5\leq 51\\
         \\
         \qquad{\rm et\ pour}\ i\in \{0,1,2,3,4,5\},\ x_i\in [0,1]
         \end{array}\right.$$

On donnera la valeur du maximum de la fonction $z$ et les valeurs $x_0$, $x_1$, $x_2$, $x_3$, $x_4$
et $x_5$ permettant d'atteindre ce maximum.

\medskip
c -- On revient au probl\`eme g\'en\'eral du sac \`a dos fractionnaire.


Dans le langage de programmation choisi, \'ecrire une fonction ou une proc\'edure qui examine si les
in\'egalit\'es{\,}:
$${u_{i-1}\over p_{i-1}} \geq {u_i\over p_i}$$
sont bien v\'erifi\'ees pour tout $i$ appartenant \`a $\{1,2,\dots ,n-1\}$.

\medskip
d -- En supposant que, pour tout $i$ appartenant \`a $\{1,2,\dots ,n-1\}$, les in\'egalit\'es 
$\d{u_{i-1}\over p_{i-1}} \geq {u_i\over p_i}$ sont v\'erifi\'ees, \'ecrire, dans le langage de
programmation choisi, une fonction qui calcule $i^*$.


\medskip
\hskip -6mm 2 -- {\sl Remarque{\,}:} le reste du probl\`eme ne d\'epend pas de cette question 2.

a -- On cherche \`a d\'eterminer la solution du probl\`eme du sac \`a dos fractionnaire {\bf sans faire
l'hypoth\`ese} que, pour tout $i$ appartenant \`a $\{1,2,\dots ,n-1\}${\,}:
$${u_{i-1}\over p_{i-1}} \geq {u_i\over p_i}.$$
En revanche, on suppose que l'on a $\sum_{i=0}^{n-1}p_i\geq Q$.



On cherche \`a d\'eterminer $i^*$ appartenant \`a $\{0,1,\dots ,n-1\}$ et une partition de l'ensemble 
$\{0,1,\dots ,n-1\}\setminus\{i^*\}$ en deux sous-ensembles $I'$ et $I''$ de fa\c{c}on \`a avoir
simultan\'ement{\,}:
$$\left\{\begin{array}{l}
         \hbox{pour tout}\ i\in I',\ \d{u_i\over p_i}\geq {u_{i^*}\over p_{i^*}}\\
         \\
         \hbox{pour tout}\ j\in I'',\ \d{u_{i^*}\over p_{i^*}}\geq {u_j\over p_j}\\
         \\ 
         \d\sum_{i\in I'}p_i<Q\\
         \\
         p_{i^*}+\d\sum_{i\in I'}p_i\geq Q\\
         \end{array}\right.$$
On dit qu'un algorithme est {\sl lin\'eaire} en une variable $v$ li\'ee aux donn\'ees trait\'ees s'il existe
une fonction lin\'eaire de $v$ majorant le nombre d'op\'erations \'el\'ementaires (op\'erations arithm\'etiques,
comparaisons, \dots) effectu\'ees par cet algorithme pour traiter ces donn\'ees.


On admet qu'on dispose d'un algorithme ${\cal A}$ qui, \'etant donn\'e un ensemble $E$ de $m$ \'el\'ements
ayant chacun une valeur, partitionne cet ensemble en deux sous-ensemble $E'$ et $E''$ de cardinaux
respectivement $\lfloor{m\over 2}\rfloor$ et $\lceil{m\over 2}\rceil$ de sorte que toutes les
valeurs des \'el\'ements de $E'$ soient sup\'erieures ou \'egales \`a toutes les valeurs des \'el\'ements de
$E''${\,}; on suppose de plus que ${\cal A}$ est lin\'eaire en $m$.


Expliciter, sans utiliser de langage de programmation, un algorithme r\'ecursif (qu'il ne sera pas la
peine de prouver) utilisant l'algorithme ${\cal A}$ qui d\'etermine $i^*$, $I'$ et $I''${\,}; cet
algorithme devra \^etre lin\'eaire en $n$.

\medskip
b -- Prouver la lin\'earit\'e en $n$ de l'algorithme propos\'e ci-dessus. Pour simplifier cette preuve, on
pourra se restreindre aux valeurs de $n$ qui sont des puissances de 2{\,}; on admettra que
l'algorithme est aussi lin\'eaire lorsque $n$ est quelconque.

\medskip
c -- D\'eduire des questions 1 - a, 2 - a et 2 - b qu'on peut r\'esoudre le probl\`eme du sac \`a dos
fractionnaire portant sur $n$ objets en un temps major\'e par une fonction lin\'eaire de $n$ m\^eme si les
objets ne sont pas au pr\'ealable class\'es pour que les rapports $\d{u_i\over p_i}$ ($i\in \{0,1,\dots
,n-1\}$) soient d\'ecroissants.


\begin{center}
{\bf Seconde partie}\\
{\bf Sac \`a dos en 0-1}
\end{center}


Dans cette partie, les objets ne sont plus fractionnables{\,}: chaque objet est pris ou laiss\'e. Le
probl\`eme s'\'ecrit{\,}:
$$\left\{\begin{array}{l}
         {\rm Maximiser}\ z=\d\sum_{i=0}^{n-1}u_ix_i\\
         \\
         {\rm avec\ les\ contraintes{\,}:}\\
         \\ 
         \qquad\d\sum_{i=0}^{n-1}p_ix_i\leq Q\\
         \\
         \qquad{\rm et\ pour}\ i\in \{0,1,\dots ,n-1\},\ x_i\in \{0,1\}
         \end{array}\right.$$



\hskip 6mm On dit que $\overline{x}=(\overline{x_0},\overline{x_1},\dots,\overline{x_{n-1}})\in \{0,1\}^n$ est
{\sl r\'ealisable} si on a $\sum_{i=0}^{n-1}p_i\overline{x_i}\leq Q$. On appelle {\sl valeur} d'une
telle solution la valeur correspondante de la fonction $z$ ou, autrement dit, la quantit\'e 
$\sum_{i=0}^{n-1}u_i\overline{x_i}$. Le probl\`eme consiste donc \`a d\'eterminer la meilleure solution
r\'ealisable, c'est-\`a-dire celle qui a la plus grande valeur.

\medskip
\hskip -6mm 3 -- Montrer que le maximum du probl\`eme du sac \`a dos en 0-1 est inf\'erieur ou \'egal au maximum du
probl\`eme du sac \`a dos fractionnaire ayant les m\^emes donn\'ees num\'eriques.

\medskip
\hskip -6mm 4 -- {\bf M\'ethode par s\'eparation}

\'Ecrire, dans le langage de programmation choisi, un algorithme fond\'e sur la strat\'egie {\sl
diviser pour r\'egner} qui exhibe tour \`a tour toutes les solutions r\'ealisables et m\'emorise la
meilleure.

Cet algorithme utilisera le principe esquiss\'e ci-apr\`es{\,}: la meilleure solution r\'ealisable peut
\^etre cherch\'ee successivement parmi les solutions r\'ealisables avec $x_0=1$ (s'il en existe) puis
parmi celles avec $x_0=0$. La meilleure solution r\'ealisable avec $x_0=1$ peut \^etre cherch\'ee
successivement parmi les solutions r\'ealisables avec $x_1=1$ (s'il en existe) puis parmi celles avec
$x_1=0$, etc.

Avant d'\'ecrire l'algorithme en langage de programmation{\,}:

\begin{itemize}
\item[--] on donnera la signification des diff\'erentes variables utilis\'ees (autre que celles
introduites par l'\'enonc\'e){\,};
\item[--] on pr\'ecisera le r\^ole des fonctions ou proc\'edures utilis\'ees.
\end{itemize}

\medskip
\hskip -6mm 5 -- Indiquer la complexit\'e dans le pire des cas de la m\'ethode par s\'eparation.

\medskip
\hskip -6mm 6 -- {\bf M\'ethode par s\'eparation et \'evaluation}


{\sl Remarque{\,}:} cette question peut \^etre trait\'ee sans avoir r\'esolu les deux questions
pr\'ec\'edentes.


La m\'ethode pas s\'eparation et \'evaluation am\'eliore la m\'ethode par s\'eparation en utilisant la
r\'esolution du sac \`a dos fractionnaire{\,}; elle se place dans l'hypoth\`ese o\`u, pour tout $i$ 
appartenant \`a $\{1,\dots ,n-1\}$, on a{\,}: $\d{u_{i-1}\over p_{i-1}} \geq {u_i\over p_i}$.


On ne fera qu'esquisser cette m\'ethode \`a travers un exemple.

\medskip
On associe au probl\`eme du sac \`a dos 0-1 un arbre binaire d\'ecrit ci-dessous.

La racine de l'arbre repr\'esente l'ensemble de toutes les solutions r\'ealisables.

{\`A} un sommet (n\oe ud ou feuille) quelconque de l'arbre correspondent un indice $i_0$ ($0\leq
i_0\leq n$) et un $i_0$-uplet $(\overline{x_0},\overline{x_1},\dots,\overline{x_{i_0-1}})\in
\{0,1\}^{i_0}${\,}; ce sommet repr\'esente l'ensemble, qui doit \^etre non vide, des solutions
r\'ealisables $(x_0,x_1,\dots,x_{n-1})$ pour lesquelles on a{\,}:
$x_0=\overline{x_0},x_1=\overline{x_1},\dots,x_{i_0-1}=\overline{x_{i_0-1}}${\,}; ces solutions
r\'ealisables seront dites {\sl contenues par ce sommet}. Si $i_0\not=n$, un tel sommet poss\`ede 1 ou 2
fils{\,}: un fils correspondant \`a l'indice $i_0+1$ et \`a
$(\overline{x_0},\overline{x_1},\dots,\overline{x_{i_0-1}},0)$ et, si
$p_{i_0}+\sum_{i=0}^{i_0-1}p_i\overline{x_i}\leq Q$, un second fils correspondant \`a l'indice $i_0+1$ et \`a
$(\overline{x_0},\overline{x_1},\dots,\overline{x_{i_0-1}},1)$.

On appelle {\sl \'evaluation d'un sommet} un majorant commun aux valeurs de toutes les solutions
r\'ealisables contenues par ce sommet.

\medskip
On consid\`ere dans toute la fin du probl\`eme l'exemple suivant, qui sera appel\'e le probl\`eme $({\cal
P})${\,}:
$$({\cal P})\qquad\left\{\begin{array}{l}
                  {\rm Maximiser}\ z=16x_0+21x_1+19x_2+15x_3+13x_4+7x_5\\
                  \\
                  {\rm avec\ les\ contraintes{\,}:}\\
                  \\ 
                  \qquad 15x_0+22x_1+20x_2+17x_3+15x_4+9x_5\leq 51\\
                  \\
                  \qquad{\rm et\ pour}\ i\in \{0,1,2,3,4,5\},\ x_i\in \{0,1\}
                  \end{array}\right.$$
Une partie de l'arbre associ\'e est dessin\'ee ci dessous{\,}:

$$\pspicture(-0.8,-0.96)(6.56,2.4)
\psset{unit=.8cm}
\cnodeput(0,0){A}{$A$}
\cnodeput(2.4,1.5){B}{$B$}
\cnodeput(4.8,2.5){C}{$C$}
\cnodeput(4.8,.8){D}{$D$}
\cnodeput(7.2,1.6){E}{$E$}
\cnodeput(7.2,0){F}{$F$}
\cnodeput(2.4,-0.7){G}{$G$}
\ncline{A}{B}
\Aput{$x_0=1$}
\ncline{B}{C}
\Aput{$x_1=1$}
\ncline{B}{D}
\Bput{$x_1=0$}
\ncline{D}{E}
\Aput{$x_2=1$}
\ncline{D}{F}
\Bput{$x_2=0$}
\ncline{A}{G}
\Bput{$x_0=0$}
\endpspicture$$

a -- D\'eterminer directement la meilleure solution r\'ealisable contenue par le sommet $C$ (obtenue en
fixant $x_0=x_1=1$).

\medskip
b -- D\'eterminer directement la meilleure solution r\'ealisable contenue par le sommet $E$ (obtenue en
fixant $x_0=1$, $x_1=0$ $x_2=1$).

\medskip
c -- R\'esoudre le probl\`eme du sac \`a dos fractionnaire ci-dessous{\,}:
$$\left\{\begin{array}{l}
         {\rm Maximiser}\ 15x_3+13x_4+7x_5\\
         \\
         {\rm avec\ les\ contraintes{\,}:}\\
         \\ 
         \qquad 17x_3+15x_4+9x_5\leq 36\\
         \\
         \qquad{\rm et\ pour}\ i\in \{3,4,5\},\ x_i\in [0,1]
         \end{array}\right.$$
En d\'eduire une \'evaluation du sommet $F$ (obtenu en fixant $x_0=1$, $x_1=x_2=0$). La solution
r\'ealisable optimale du probl\`eme $({\cal P})$ peut-elle \^etre contenue dans $F${\,}?

\medskip
d -- Montrer, en utilisant la m\^eme d\'emarche que dans la question pr\'ec\'edente, que la solution
r\'ealisable optimale du probl\`eme $({\cal P})$ n'est pas contenue dans le sommet $G$ (obtenu en fixant
$x_0=0$).

\medskip
e -- D\'eduire des questions pr\'ec\'edentes la solution r\'ealisable optimale du probl\`eme $({\cal P})$.

\medskip
\begin{center}
{\bf FIN DU PROBL\`EME D'ALGORITHMIQUE}
\end{center}

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

\section*{3 \quad Exercice sur les automates -- 30 mn environ}

\def\build#1_#2^#3{\mathrel{\mathop{\kern 0pt#1}\limits_{#2}^{#3}}}
\def\fl#1#2{\build\hbox to 8mm{\rightarrowfill}_{#2}^{#1}}

\begin{center}
{\bf Rappels pour fixer les notations}
\end{center}

\medskip
\hskip 6mm Un {\sl alphabet} $A$ est un ensemble fini d'\'el\'ements, appel\'es {\sl lettres}. L'ensemble
des suites finies de lettres de $A$, appel\'ees {\sl mots}, est not\'e $A^*$. Le mot vide est not\'e
$1_{A\*}$. Un {\sl langage} est une partie de $A\*$.

\medskip
\hskip 6mm Un automate fini ${\cal A}$ est un {\sl graphe orient\'e} et {\sl \'etiquet\'e}, not\'e par un
quintuplet $<Q,A,E,I,T>${\,}: $A$ est un alphabet{\,}; $Q$ est l'ensemble (fini) des {\sl \'etats} de ${\cal
A}${\,}: ce sont les sommets du graphe{\,}; $I$ et $T$, deux sous-ensembles de $Q$, sont
respectivement l'ensemble des {\sl \'etats initiaux} et des {\sl \'etats terminaux} de ${\cal A}$. Enfin,
$E$, sous-ensemble de $Q\times A\times Q$, est appel\'e ensemble des {\sl transitions} de ${\cal A}$.
Une transition $(p,a,q)$ est un arc du graphe, allant de l'\'etat $p$ \`a l'\'etat $q$ et \'etiquet\'e par
$a${\,}; on la note $p \fl a{} q$.

\medskip
\hskip 6mm
Un {\sl calcul} de ${\cal A}$ est un chemin $c$ dans le graphe{\,}: $c=p_0\fl {a_1}{} p_1 \fl{a_2}{}
\dots \fl{a_n}{}p_n$, o\`u, pour tout $i$, $0\leq i \leq n-1$, $p_i\fl {a_{i+1}}{} p_{i+1}$ appartient \`a
$E$. L'\'etat $p_0$ est l'{\sl origine} du calcul $c$, $p_n$ l'{\sl extr\'emit\'e} de $c$. La {\sl
longueur} du calcul est donn\'ee par le nombre $n$ d'arcs de $c$. L'{\sl \'etiquette} de $c$ est le mot
$f$ form\'e par la suite des \'etiquettes des transitions successives du calcul $c${\,}: $f=a_1a_2\dots
a_n$. Le calcul $c$ peut aussi \^etre not\'e $p_0\fl {f}{{\cal A}} p_n${\,}; il est {\sl r\'eussi} si $p_0$ est
initial et $p_n$ terminal.

\medskip
\hskip 6mm
Un mot de $A\*$ est {\sl reconnu} par l'automate ${\cal A}$ si c'est l'\'etiquette d'(au moins) un
calcul {\sl r\'eussi} de ${\cal A}$. Le {\sl langage reconnu} par ${\cal A}$, not\'e $L({\cal
A})$, est l'ensemble des mots reconnus par ${\cal A}$. Un langage est {\sl  reconnaissable} s'il est
reconnu par un automate fini.

\medskip
\hskip 6mm
On dira qu'un automate ${\cal A}=<Q,A,E,I,T>$ est {\sl normalis\'e} si{\,}:

i) $I$ est un singleton, $I=\{i\}$, qui n'est l'extr\'emit\'e d'aucune transition de ${\cal A}${\,};

ii) $T$ est un singleton, $T=\{t\}$, qui n'est l'origine d'aucune transition de ${\cal A}$.

\medskip
\hskip 6mm
Un automate normalis\'e est donc naturellement repr\'esent\'e par le sch\'ema ci-dessous (noter que
certaines transitions peuvent aussi aller de $i$ \`a $t$, m\^eme si elles n'apparaissent par sur le
sch\'ema).

$$\pspicture(0,-2)(6.4,2)
\psset{unit=.4cm}
\pnode(0,0){A}
\cnodeput(2,0){B}{$i$}
\pnode(6,1){C}
\pnode(6,-1){D}
\pnode(10,2){E}
\pnode(10,0){F}
\pnode(10,-2){G} 
\cnodeput(14,0){H}{$t$}
\pnode(16,0){I} 
\ncline{->}{A}{B}
\ncline{->}{B}{C}
\ncline{->}{B}{D}
\ncline{->}{E}{H}
\ncline{->}{F}{H}
\ncline{->}{G}{H}
\ncline{->}{H}{I}
\pscircle(8,0){3.5} 
\endpspicture$$

\begin{center}
{\bf \'Enonc\'e de l'exercice}
\end{center}

\medskip
Si un mot $f$ de $A^*$ se factorise en $f=uv$, avec $u,v$ dans $A^*$, le mot $g=vu$ est un {\sl
conjugu\'e} de $f$. 

Soit Conj{\,}: $A^*\longrightarrow {\cal P}(A^*)$ l'application qui \`a un mot $f$
fait correspondre l'ensemble de ses conjugu\'es{\,}:

$${\rm Conj}(f)=\{vu\, | \, (u,v)\in (A^*)^2 \ {\rm avec}\ uv=f \}.$$
En particulier, pour tout $f$, $f\in {\rm Conj}(f)$ puisque $f=1_{A^*}\,f=f\,1_{A^*}$ et pour tout
$f\in A\cup \{1_{A^*}\}$, ${\rm Conj}(f)=\{f\}$. L'application s'\'etend par additivit\'e{\,}: si $L$
est un langage, ${\rm Conj}(L)=\bigcup_{f\in L}{\rm Conj}(f)$.

\medskip
\hskip 6mm
Dans tout l'exercice, {\bf L est un langage reconnu par un automate fini}. L'objet de cet exercice
est de montrer que ${\rm Conj}(L)$ est reconnaissable.

\medskip
\hskip -6mm
1 -- Montrer que $L\setminus \{1_{A^*}\}$ est reconnu par un automate (fini) normalis\'e.

\medskip
\hskip -6mm
2 -- Soit ${\cal A}=<Q,A,E,\{i\},\{t\}>$ un automate normalis\'e qui reconna\^{\i}t le langage $L\setminus
\{1_{A^*}\}$ et $q$ un \'etat de ${\cal A}$ distinct de $i$ et de $t$. \`A chaque calcul r\'eussi de
${\cal A}$ qui passe par $q$ (et donc de longueur au moins \'egale \`a 2) d'\'etiquette $f=f_1f_2${\,}: $i
\fl{f_1}{{\cal A}} q \fl{f_2}{{\cal A}} t$, on associe le conjugu\'e $g=f_2f_1$ de $f$ et on note
$G_q$ l'ensemble des mots obtenus de cette fa\c{c}on{\,}:
$$G_q=\{g=f_2f_1\, |\, i \fl{f_1}{{\cal A}} q \fl{f_2}{{\cal A}} t \hbox{ est un calcul r\'eussi de
}{\cal A}\}.$$

Construire un automate qui reconna\^{\i}t le langage $G_q$.

\medskip
\hskip -6mm
3 -- Montrer que ${\rm Conj}(L)$ est reconnaissable.

\medskip
\begin{center}
{\bf FIN DE L'EXERCICE SUR LES AUTOMATES}
\end{center}

\medskip
\begin{center}
{\bf FIN DE L'\'EPREUVE}
\end{center}


\end{document}


