Spé MATH-INFO  Exercice d’algorithmique. Éléments de corrigé.

1^{o})

a) Ici la médiane est l’élément classé n^{ième} . 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) .

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

2^{o})

a) Si la condition (∗ 11 ∗) est satisfaite, c’est que le tableau V est totalement classé, donc la médiane est le n^{ième} élément, soit V.(n − 1) puisque les indices commencent à 0 . 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ème} élément de ce tableau permuté, soit V.(2 ∗ n − 1) .

b) b.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,

c’est-à-dire

(1) 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,

m_{2} = ⌊\frac{i_{2} + j_{2} + 1}{2}⌋

= ⌊\frac{2n − 1 − i_{1} + 2n − 1 − j_{1} + 1}{2}⌋

= 2n − 1 + ⌊\frac{−i_{1} − j_{1} + 1}{2}⌋ .

Or, si i_{1} + i_{2} = 2k est pair, on a m_{1} = k et ⌊\frac{−i_{1} − j_{1} + 1}{2}⌋ = ⌊\frac{−2k + 1}{2}⌋ = −k = −m1 , et si i_{1} + i_{2} = 2k + 1 est

impair, on a m_{1} = k et ⌊\frac{−i_{1} − j_{1} + 1}{2}⌋ = ⌊\frac{−2k}{2} ⌋ = −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. 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.

b.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 b.2. . 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 σ ne peut pas être < V.(m_{1}) . 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 σ ne peut pas être ≤ V.(m_{2}) . 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}) ≤ σ < max V.(m_{1}) V.(m_{2}) .

b.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 ! Vérifions alors la correction de la fonction mediane2 dans le cas n ≥ 2 et lorsque les tests des lignes (∗ 11 ∗) et (∗ 13 ∗) ont échoués.

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} ≤ 1 , terminant la fonction med . 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 b.2. que V.(i_{1}) ≤ σ; 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 b.2. que σ < 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}) ≤ σ , chaque fois que j_{2} a été modifié, on a σ < V.(j_{2}) . Si donc au cours du processus des appels récursifs i_{1} 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}) ≤ σ < V.(i_{1} + 1) et V.(i_{2}) ≤ σ < V.(i_{2} + 1) .

Or σ 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. 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) ≤ σ < 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 σ = V.(n) qui est le n^{ième} élément classé, et si V.(n) < V.(n − 2) , c’est σ = V.(n − 2) qui est le n^{ième} élément classé, donc le résultat σ = max V.(i_{1}) V.(i_{2}) est correct.

Schéma :

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.

c) 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, c’est-à-dire lors du premier appel de la fonction med , et notons n_{k} , k ≥ 1 le nombre d’éléments de ce même intervalle lors du k^{ième} 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

⌈\frac{n_{k}}{2} ⌉ ≤ n_{k+1} ≤ ⌈\frac{n_{k} + 1}{2}⌉ .

Compte tenu de la relation initiale 2^{λ−1} < n_{1} ≤ 2^{λ} , on voit ainsi par récurrence que si aucun des nombres n_{k} ne passe par une puissance de 2 , alors

∀ k ≥ 1 2^{λ−k} < n_{k} ≤ 2^{λ−k+1} .

Reste le cas où n_{k} = 2^{p} par exemple. Alors, n_{k+1} ≤ 2^{p−1} + 1 et n_{k+2} ≤ 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

∀ k ≥ 1 n_{k} ≤ 2^{λ−k+1} + 1 .

On voit ainsi que le nombre d’appels de la fonction med est au plus de k = λ+1 , ce qui conduit à une complexité dans le pire cas pour mediane2 de λ + 3 = ⌈ln n⌉ + 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é.

⋇ ⋇ ⋇