Spé MATH-INFO  Exercice d’algorithmique.

Soit V un tableau de n éléments distincts, des entiers par exemple. On appelle médiane de V l’unique élément σ de V tel que le nombre des éléments de V < σ soit égal ou inférieur d’une unité au nombre d’éléments de V > σ , soit :

Card(\{x ∈ V / x < σ\}) = ⌊\frac{n − 1}{2}⌋ et Card(\{x ∈ V / x > σ\}) = ⌈\frac{n − 1}{2}⌉ .

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.

1^{o}) 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 .

a) Compléter le squelette de programme suivant réalisant cet algorithme, c’est-à-dire remplacer < test > par une condition appropriée, et remplacer < valeur > par la valeur de retour de la fonction, à savoir l’élément σ médiane de V :

let mediane1 V =

let n = (vect length V)/2 in

let i1 = ref 0 and i2 = ref n in

(while < test > do
if V.( !i1) <V.( !i2) then i1:=( !i1)+1

else i2:=( !i2)+1 done ;

< valeur > ) ; ;

b) 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 :

n − 1

n
n + 1
2n − 1
2n
2n + 1 .

.../...

2^{o}) 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 σ 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 : let mediane2 V =

(* 0 *) let n = (vect length V)/2 in
(* 1 *) let rec med i1 j1 i2 j2 =
(* 2 *)  if i1 < (j1-1)
(* 3 *)  then
(* 4 *)  let m1 = (i1+j1)/2 and m2=(i2+j2+1)/2 in
(* 5 *)  if V.(m1) < V.(m2) then med m1 j1 i2 m2
(* 6 *)  else med i1 m1 m2 j2
(* 7 *)  else
(* 8 *)  if i1=j1-1 then max V.(i1) V.(i2)
(* 9 *)  else min V.(i1) V.(i2)
(* 10 *) in
(* 11 *) if V.(n-1)<V.(n)
(* 12 *) then V.(n-1)
(* 13 *) else if V.(2*n -1) < V.(0)
(* 14 *)  then V.(2 *n-1)
(* 15 *)  else med 0 (n-1) n ( 2*n-1) ; ;

a) Justifier la correction de la fonction précédente lorsque les données satisfont à la condition (* 11 *) ou à la condition (* 13 *).

b) Il s’agit maintenant de justifier la correction du programme dans les autres cas, c’est-à-dire lorsqu’il

appelle la fonction récursive med définie à partir de la ligne (* 1 *) . b.1. Pourquoi peut-on dire que les indices m_{1} et m_{2} créés à la ligne (* 4 *) évoluent de manière

“symétrique” ? 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} ?

b.2. Justifier l’invariant d’appel suivant :

- 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. En déduire une propriété invariante reliant V.(m_{1}) , σ , V.(m_{2}) .

b.3. Y-a-til des données pour lesquelles le retour de la fonction med se fait à la ligne (* 9 *) ? Prouver la correction de la fonction mediane2 .

c) Donner un majorant de la complexité de la fonction mediane2 en fonction de l’entier λ défini par 2^{λ−1} < n ≤ 2^{λ} . Conclusion ?

⋇
⋇ ⋇