\magnification=1000
\input math 
%\nopage
\def\s{\sigma}
\centerline{\gsl
Sp\'e MATH-INFO \hskip1truecm \cadre{4pt}{Exercice d'algorithmique. 
\'El‚ments de corrig‚.}}
\vskip 1truecm
\question
\sousquestion
Ici la m‚diane est l'‚l‚ment class‚ $n^{i\mag eme}$~. Il s'agit donc de 
d‚terminer les $n-1$ plus petits ‚l‚ments puis de choisir le suivant. 
Donc la boucle $while$ doit s'‚x‚cuter $n-1$ fois et ensuite on doit 
prendre le $min$ des deux ‚l‚ments candidats. D'o— le programme donn‚, 
avec $<test>=(!i1)+(!i2)<2*n-1$ et $<valeur>=min~V.(!i1)~V.(!i2)$~. 

\sousquestion
Chaque passage dans la boucle $while$ co–te une unit‚, et dans la fonction 
$min$ finale il y a une comparaison suppl‚mentaire, d'o— un co–t 
de $n-1+1=n$~. 

\question
\sousquestion
Si la condition $(*~11~*)$ est satisfaite, c'est que le tableau $V$ est 
totalement class‚, donc la m‚diane est le $n^{i\mag eme}$ ‚l‚ment, soit 
$V.(n-1)$ puisque les indices commencent … $0$~. \par
De mˆme, si la condition $(*~13~*)$ est satisfaite, c'est que le tableau 
$V$ est totalement class‚ lorsqu'on permute les sous-tableaux $V_1$ et $V_2$~,  
donc la m‚diane est le $n^{i\mag eme}$ ‚l‚ment de ce tableau permut‚, soit 
$V.(2*n-1)$~. 

\sousquestion
\smallbreak\item{\bf\char\sqno.1.~}
Montrons que les indices $i_1$ et $j_2$ d'une part, $j_1$ et $i_2$ 
d'autre part, sont sym‚triques par rapport au milieu du tableau, \cad 
$$(1)\qquad j_2=(2n-1)-i_1~~;~~  i_2=(2n-1)-j_1~~.$$
C'est vrai pour les valeurs initiales appel‚es … la ligne $(*~15~*)$~: 
$i_1=0~,~j_1=n-1~,~i_2=n~,~j_2=2n-1$~. Montrons alors que ces relations 
constituent un invariant d'appel de la fonction $med$~. Supposons qu'… 
l'appel de la ligne $(*~1~*)$ les relations $(1)$ soient satisfaites, 
et montrons qu'elles le restent lors de l'appel r‚cursif des lignes 
$(*~5~*)$ et $(*~6~*)$~. Cela revient … montrer, dans tous les cas, 
que $m_2=(2n-1)-m_1$~, avec $m_1$ et $m_2$ tels que d‚finis ligne 
$(*~4~*)$~. Or, 
$$\eqalign{
m_2 &=\Bigl\lfloor\Frac{i_2+j_2+1}{2}\Bigr\rfloor\cr
    &=\Bigl\lfloor\Frac{2n-1-i_1+2n-1-j_1+1}{2}\Bigr\rfloor\cr 
    &=2n-1+\Bigl\lfloor\Frac{-i_1-j_1+1}{2}\Bigr\rfloor~~.\cr
}$$
Or, si $i_1+i_2=2k$ est pair, on a $m_1=k$ et 
$\lfloor\Frac{-i_1-j_1+1}{2}\Bigr\rfloor=\lfloor\Frac{-2k+1}{2}\Bigr\rfloor
=-k=-m1$~, 
et si $i_1+i_2=2k+1$ est impair, on a $m_1=k$ et 
$\lfloor\Frac{-i_1-j_1+1}{2}\Bigr\rfloor=\lfloor\Frac{-2k}{2}\Bigr\rfloor
=-k=-m1$~, donc dans tous les cas $m_2=(2n-1)-m_1$ et les relations $(1)$ 
sont donc vraies … chaque appel. Mais on vient d'en d‚duire qu'alors 
$m_1$ et $m_2$ v‚rifient aussi la propri‚t‚ $(1)$ de sym‚trie par rapport 
au mileu du tableau, cqfd.
\par
A cause de cette sym‚trie, tout test semblable sur $i_2$ et $j_2$ donne le 
mˆme r‚sultat que sur $i_1$ et $j_1$~, donc il est inutile de les faire. 
\bigskip
\smallbreak\item{\bf\char\sqno.2.~}
Le nombre d'‚l‚ments de $V_1$ strictements inf‚rieurs … $V.(m_1)$ est 
exactement $m_1$~, puisque $V_1$ est tri‚ et que les indices commencent … 
$0$~. De mˆme, le nombre d'‚l‚ments de 
$V_2$ strictement sup‚rieurs … $V.(m_2)$ est $2n-1-m_2$~: ces deux nombres 
sont donc ‚gaux en vertu de la sym‚trie d‚montr‚e en {\bf b.2.}~.\par
Supposons $V.(m_1)<V.(m_2)$~. Alors, parmi les ‚l‚ments de $V$ 
strictement sup‚rieurs … $V.(m_1)$~, il y a d‚j… tous ceux de $V_1$ d'indices 
$>m_1$~, $V.(m_2)$~, et tous les ‚l‚ments de $V_2$ d'indices $>m_2$~. 
En vertu de la propri‚t‚ ci-dessus, il y en a donc au moins $(n-1)+1=n$~, 
donc $\s$ ne peut pas ˆtre $<V.(m_1)$~.
\par
De mˆme, parmi les ‚l‚ments de $V$ strictement inf‚rieurs … $V.(m_2)$~, 
il y a d‚j… tous ceux de $V_2$ d'indices 
$<m_2$~, $V.(m_1)$~, et tous les ‚l‚ments de $V_1$ d'indices $<m_1$~,  
il y en a donc au moins $(n-1)+1=n$~, et $\s$ ne peut pas ˆtre 
$\leq V.(m_2)$~. 
\par
On peut raisonner de mˆme dans le cas o— $V.(m_1)>V.(m_2)$~, et la 
propri‚t‚ invariante est donc
$$min~V.(m_1)~V.(m_2)\leq \s < max~V.(m_1)~V.(m_2)~~.$$
\bigskip
\smallbreak\item{\bf\char\sqno.3.~}
On ne peut avoir accŠs … la ligne $(*~9~*)$ que si $i_1=j_1$~, mais ceci 
ne peut pas se produire lors d'un appel r‚cursif … la fonction $med$~, 
car il faudrait pour cela que $m_1=i_1$ ou $m_1=j_1$~, or ces deux 
possibilit‚s sont exclues par le test ligne $(*~2~*)$ qui garantit dans ce 
cas qu'il y a au moins $3$ ‚l‚ments dans l'intervalle $[i_1,j_1]$~. 
Donc la seule 
donn‚e donnant un retour ligne $(*~9~*)$ est $n=1$~! Et dans ce cas, on 
v‚rifie facilement la correction de la fonction $mediane2$~!
\par
V‚rifions alors la correction de la fonction $mediane2$ dans le cas $n\geq 2$ 
et lorsque les tests des lignes $(*~11~*)$ et $(*~13~*)$ ont ‚chou‚s.\par 
A cause du test ligne $(*~2~*)$ et de la valeur de $m_1$~, on voit que la 
fonction $med$ est appel‚e sur des paramŠtres $i_1$ et $j_1$ tels que 
le nombre entier $j_1-i_1$ d‚croit strictement. Il arrive donc 
n‚cessairement un appel o— $j_1-i_1\leq 1$~, terminant la fonction $med$~. 
\par
De plus, pendant tout le processus des appels r‚cursifs, si la nouvelle 
valeur de $i_1$ est celle de $m_1$~, c'est qu'on est pass‚ … l'appel de la  
ligne $(*~5~*)$ et que $V.(m_1)<V.(m_2)$~, et donc, lors du nouvel appel 
r‚cursif, on a d'aprŠs {\bf b.2.}  que $V.(i_1)\leq \s$~; 
si au contraire c'est $j_1$ qui prend la valeur de $m_1$~, c'est qu'on est 
pass‚ … l'appel de la  ligne $(*~6~*)$ et que $V.(m_1)>V.(m_2)$~, et donc, 
lors du nouvel appel r‚cursif on a d'aprŠs {\bf b.2.}  que 
$\s < V.(j_1)$~. Il en va de mˆme pour les indices $i_2$ et $j_2$ du 
tableau $V_2$~: chaque fois que $i_2$ a ‚t‚ modifi‚, on a 
$V.(i_2)\leq \s$~, chaque fois que  $j_2$ a ‚t‚ modifi‚, on a 
$\s < V.(j_2)$~. Si donc au cours du processus des appels r‚cursifs 
$i_1$ {\it et} $j_1$ ont ‚t‚ modifi‚s au moins une fois, … la sortie en ligne 
$(*~8~*)$ on se retrouve avec les deux in‚galit‚s
$$V.(i_1)\leq \s<V.(i_1+1)~~et~~V.(i_2)\leq \s<V.(i_2+1)~~.$$ 
Or $\s$ est la valeur d'un ‚l‚ment de $V$~, ce ne peut donc qu'ˆtre 
$V.(i_1)$ ou $V.(i_2)$~, et en fait n‚cessairement le plus grand des deux 
vu que tous les ‚l‚ments de $V$ sont distincts. Donc la valeur rendue ligne 
$(*~8~*)$ est correcte dans ce cas. \par
Il reste … examiner le cas o— $2$ des $4$ indices restent constants, 
et supposons que cela soit $j_1=n-1$ et $i_2=n$~. Les appels r‚cursifs se 
sont donc tous produits avec la condition $V.(m_1)<V.(m_2)$ et … la sortie 
en ligne $(*~8~*)$ on a $V.(n-2)\leq \s <V.(n+1)$~. Comme le test 
$V.(n-1)<V.(n)$ de la ligne $(*~11~*)$ est suppos‚ faux, on a de plus 
$V.(n)=V.(i_2)<V.(n-1)$~. On voit facilement que si $V.(n-2)<V.(n)$~, c'est 
$\s=V.(n)$ qui est le $n^{i\mag eme}$ ‚l‚ment class‚, et si 
$V.(n)<V.(n-2)$~, c'est $\s=V.(n-2)$ qui est le $n^{i\mag eme}$ ‚l‚ment 
class‚, donc le r‚sultat $\s=max~V.(i_1)~V.(i_2)$ est correct. 
\par\medskip
\setbox20=\vtop{
\hsize=50truemm \leftskip=0mm\rightskip=0mm
\special{em\DP graph corimi24.pcx}
}
\hbox{Sch‚ma:\qquad \box20}
\vskip 4.2truecm
Il en va de mˆme si ce sont les indices $i_1=0$ et $j_2=2n-1$ qui restent 
fixes, … cause du test n‚gatif de la ligne $(*~13~*)$~, cqfd. 

\sousquestion
La complexit‚ est la pire lorsque les deux tests des lignes $(*~11~*)$ et 
$(*~13~*)$ ont ‚chou‚ et qu'il faut en passer par la fonction $med$~,  
la complexit‚ ‚tant alors $2$ plus le nombre d'appels de la fonction $med$~. 
Soit $n_1=n$ le nombre d'‚l‚ments de l'intervalle $[i_1,j_1]$ initial, 
\cad lors du premier appel de la fonction $med$~, et notons $n_k~,~k\geq 1$ 
le nombre d'‚l‚ments de ce mˆme intervalle lors du $k^{i\mag eme}$ appel de 
la fonction $med$~. Si $n_k$ est pair, le nombre d'‚l‚ments dans $[i_1,m_1]$ 
est $\Frac{n_k}{2}$~, celui dans $[m_1,j_1]$ est $\Frac{n_k}{2}+1$~, et si 
$n_k$ est impair, ces deux sous-intervalles ont exactement le mˆme nombre 
d'‚l‚ments, … savoir $\Frac{n_k+1}{2}$~. Dans tous les cas, on a donc la 
relation de r‚currence
$$\Bigl\lceil\Frac{n_k}{2}\Bigr\rceil\leq 
n_{k+1}\leq \Bigl\lceil\Frac{n_k+1}{2}\Bigr\rceil~~.$$
Compte tenu de la relation initiale $2^{\l -1}<n_1\leq 2^{\l}$~, on voit 
ainsi par r‚currence 
que si aucun des nombres $n_k$ ne passe par une puissance de $2$~, alors 
$$\qqsoit k\geq 1~~2^{\l -k}<n_k\leq 2^{\l -k+1}~~.$$
Reste le cas o— $n_k=2^p$ par exemple. Alors, $n_{k+1}\leq 2^{p-1}+1$ et 
$n_{k+2}\leq 2^{p-2}+1$~: on voit qu'… partir de $j=k+1$ tous les 
$n_j$ sont major‚s par $2^{p+k-j}+1$~. Finalement, on a dans tous les 
cas la majoration 
$$\qqsoit k\geq 1~~n_k\leq 2^{\l -k+1}+1~~.$$
On voit ainsi que le nombre d'appels de la fonction $med$ est au plus 
de $k=\l+1$~, ce qui conduit … une complexit‚ dans le pire cas pour 
$mediane2$ de $\l+3=\bigl\lceil\ln n\bigr\rceil+3$~. 
Cette complexit‚ est en $O(\ln n)$ donc est bien 
meilleure que celle de $mediane1$~. On peut mˆme montrer, au moyen de 
l'arbre de d‚cision associ‚, que cette complexit‚ est quasi-optimale pour le 
problŠme consid‚r‚. 

\vfill
\troiset
\end