%\magnification=1000
\input math 
\def\carreblanc{\cadre{2pt}{\raise 2pt\vbox{\null}}}
\nopage
\def\s{\sigma}
\centerline{\gsl
Sp\'e MATH-INFO \hskip1truecm \cadre{4pt}{Exercice d'algorithmique.}}
\vskip3truecm
Soit $V$ un tableau de $n$ ‚l‚ments distincts, des entiers par exemple. 
On appelle m‚diane de $V$ l'unique ‚l‚ment $\s$ de $V$ tel que le nombre des 
‚l‚ments de $V$ $< \s$ soit ‚gal ou inf‚rieur d'une unit‚ au nombre d'‚l‚ments 
de $V$ $>\s$~, soit:
$$Card\(\bigl\{x\in V\tq x<\s\bigr\}\)=\Bigl\lfloor{\Frac{n-1}{2}}\Bigr\rfloor
~~{\rm et}~~Card\(\bigl\{x\in V\tq x>\s\bigr\}\)=\Bigl\lceil{\Frac{n-1}{2}}
\Bigr\rceil~~.$$
Le problŠme est le suivant: le tableau $V$ contient $2n$ ‚l‚ments distincts 
et est d‚j… partiellement tri‚, en ce sens que les $n$ premiers ‚l‚ments de 
$V$ (d'indices de $0$ … $n-1$~)   
forment un sous-tableau $V_1$ tri‚, et les $n$ derniers ‚l‚ments de $V$ 
(d'indices de $n$ … $2n-1$~) 
forment un sous-tableau tri‚ $V_2$~. On veut trouver un algorithme 
``performant'' trouvant la m‚diane dans ces conditions.
\par
\question
Une premiŠre m‚thode consiste … parcourir les sous-tableaux $V_1$ et $V_2$ 
de gauche … droite, en commen‡ant aux indices respectifs $i_1=0$ et 
$i_2=n$~. A chaque pas, on test si $V.(i_1)<V.(i_2)$~: si oui, on fait 
progresser $i_1$ de $1$~, si non on fait progresser $i_2$ de $1$~. On 
s'arrˆte quand on a ainsi class‚ suffisamment des plus petits ‚l‚ments du 
tableau $V$~. 
\sousquestion
Compl‚ter le squelette de programme suivant r‚alisant cet algorithme, \cad 
remplacer $<test>$ par une condition appropri‚e, et 
remplacer $<valeur>$ par la valeur de retour de la fonction, … savoir 
l'‚l‚ment $\s$ m‚diane de $V$~: 
\medskip
{\sl \cleartabs
\+let mediane1 V $=$ \cr
\+\qquad &let &n $=$ (vect\_length V)/2 in\cr
\+\qquad &    &let i1 $=$ ref 0 and i2 $=$ ref n in \cr
\+\qquad &    &(while &~$<test>$~~ &do\cr 
\+\qquad &    &   &if V.(!i1) $<$  &V.(!i2) &then i1$:=$(!i1)+1\cr 
\+\qquad &    &   &              &        &else i2$:=$(!i2)+1\cr
\+\qquad &    &   &              &done;\cr
\+\qquad &    &$<valeur>$ );;\cr
}
\medskip
\sousquestion
L'unit‚ de co–t pour la complexit‚ temporelle est la comparaison entre 
deux ‚l‚ments de $V$~. Dire si la complexit‚ du programme ci-dessus est:
\par\qquad\carreblanc~~ $n-1$ 
\par\qquad\carreblanc~~ $n$
\par\qquad\carreblanc~~ $n+1$
\par\qquad\carreblanc~~ $2n-1$
\par\qquad\carreblanc~~ $2n$
\par\qquad\carreblanc~~ $2n+1$~.

\tournepage

\question
On pense pouvoir am‚liorer l'efficacit‚ de l'algorithme en proc‚dant par 
dichotomie: au d‚part, on compare l'‚l‚ment ``milieu'' de $V_1$~, $V.(m_1)$~,  
avec l'‚l‚ment ``milieu'' de $V_2$~, $V.(m_2)$~, et suivant le cas on 
recommence la recherche dans le sous-tableau … gauche ou … droite de cet 
‚l‚ment milieu. En effet, si $V.(m_1)<V.(m_2)$ par exemple, alors la m‚diane 
$\s$ se trouve dans l'intervalle $[V.(m_1),V.(m_2)]$ et donc on doit 
poursuivre la recherche dans $V_1$ entre les indices $m_1$ et $n-1$~, et 
dans $V_2$ entre les indices $n$ et $m_2$~. 
Le programme correspondant est la fonction $mediane2$ ci-aprŠs:
\par

{\sl \cleartabs
\+let mediane2 V =      \cr
\+\qquad(*~0~*)\quad    &let n = (vect\_length V)/2 in\cr
\+\qquad(*~1~*)    &let &rec med i1 j1 i2 j2 = \cr
\+\qquad(*~2~*)    &    &if i1 $<$ (j1-1)  \cr
\+\qquad(*~3~*)    &    &then &\cr
\+\qquad(*~4~*)    &    &     &let m1 $=$ (i1+j1)/2 and m2=(i2+j2+1)/2 in \cr
\+\qquad(*~5~*)    &    &     &if V.(m1)~&$<$~V.(m2) &then med m1 j1 i2 m2 \cr
\+\qquad(*~6~*)    &    &     &          &         &else med i1 m1 m2 j2\cr
\+\qquad(*~7~*)    &    &else &          &         &\cr
\+\qquad(*~8~*)    &    &~if  &i1$=$j1-1 &then max &V.(i1) V.(i2)\cr
\+\qquad(*~9~*)    &    &     &          &else min &V.(i1) V.(i2)\cr
\+\qquad(*~10~*)   &in  &     &          &         &\cr
\+\qquad(*~11~*)   &if  &V.(n-&1)$<$V.(n)&         & \cr
\+\qquad(*~12~*)   &    &then &V.(n-1)   &         &\cr
\+\qquad(*~13~*)   &    &else &if V.(2*n &-1)~$<$~V.(0)\cr 
\+\qquad(*~14~*)   &    &     &then V.(2 &*n-1)     \cr
\+\qquad(*~15~*)   &    &     &else med 0&~(n-1)~n~(&2*n-1);;\cr
}
\bigskip

\sousquestion
Justifier la correction de la fonction pr‚c‚dente lorsque les donn‚es 
satisfont … la condition (*~11~*) ou … la condition (*~13~*). 
\bigskip

\sousquestion
Il s'agit maintenant de justifier la correction du programme dans les 
autres cas, \cad lorsqu'il appelle la fonction r‚cursive $med$ 
d‚finie … partir de la ligne (*~1~*)~. \par
\smallbreak\item{\bf\char\sqno.1.~}
Pourquoi peut-on dire que les indices $m_1$ et $m_2$ cr‚‚s … la ligne 
(*~4~*) ‚voluent de maniŠre ``sym‚trique''?\par
Pourquoi les tests des lignes (*~2~*) et (*~8~*) ne portent-ils que sur les 
indices $i_1$ et $j_1$ et non pas aussi sur $i_2$ et $j_2$~?\par
\smallbreak\item{\bf\char\sqno.2.~} Justifier l'invariant d'appel suivant:
\par
\quad -~le nombre d'‚l‚ments de $V_1$ inf‚rieurs strictement … 
$V.(m_1)$ est ‚gal au nombre d'‚l‚ments de $V_2$ sup‚rieurs strictement 
… $V.(m_2)$~, et vice-versa.\par
En d‚duire une propri‚t‚ invariante reliant $V.(m_1)~,~\s~,~V.(m_2)$~.\par
\smallbreak\item{\bf\char\sqno.3.~}
Y-a-til des donn‚es pour lesquelles le retour de la fonction $med$ 
se fait … la ligne (*~9~*)~? \par
Prouver la correction de la fonction $mediane2$~. 
\bigskip

\sousquestion
Donner un majorant de la complexit‚ de la fonction $mediane2$ en fonction 
de l'entier $\l$ d‚fini par $2^{\l-1}< n \leq 2^{\l}$~. \par
Conclusion?
\vfill
\nopage
\troiset
\end
