Centrale Informatique MP 2012

MP
4 heures

Calculatrices autorisées

2012

Informatique

Les candidats indiqueront en tête de leur copie le langage de programmation 
choisi (Pascal ou Caml). Les
candidats ayant choisi Caml devront donner le type de chaque fonction écrite, 
lorsque celui-ci n'est pas imposé.
Les candidats travaillant en Pascal pourront écrire des fonctions ou des 
procédures.

Choix du pivot dans le tri rapide
L'objet de ce problème est le choix d'un pivot dans l'algorithme du tri rapide. 
On s'intéresse au tri en ordre
croissant d'un tableau d'entiers qui pourront toujours être supposés distincts.
En Pascal, on dispose du type tableau suivant :
const long_tab = 1000;
type tableau = array[0..long_tab-1] of integer;
La longueur t des tableaux avec lesquels on travaille devra donc être majorée 
par long_tab et les données sont
alors présentes dans la zone indexée par 0 6 i 6 t - 1. Cette longueur utile t 
devra donc être éventuellement
donnée en paramètre.
En Caml, on rappelle que la longueur d'un tableau est donnée par vect_length en 
Caml light et Array.length
en Ocaml.

I Tri rapide d'un tableau
I.A ­

Écrire une fonction/procédure echange réalisant l'échange de deux éléments d'un 
tableau.
echange : int -> int -> int vect -> unit = 
procedure echange(i, j : integer ; var t : tableau);

I.B ­
Décrire un algorithme simple de tri ; évaluer sa complexité dans le pire des 
cas en termes de comparaisons. Le programmer.
I.C ­
L'algorithme du tri rapide sur un tableau consiste en une première étape où on 
permute les éléments
du tableau de sorte que les éléments plus petits (respectivement plus grands) 
qu'un pivot p soient placés avant
(respectivement après) cet élément p dans le tableau. On exécute ensuite 
récursivement le tri rapide sur les deux
parties du tableau ainsi séparées par p.
Par exemple, le tableau [|19; 7; 17; 14; 22; 5; 26; 21; 2; 12|] devient après 
la première étape (si on choisit 19 comme
pivot) : [|2; 7; 17; 14; 12; 5; 19; 21; 26; 22|]. Notons que les éléments 
inférieurs (respectivement supérieurs) à 19
peuvent être permutés entre eux. Le point crucial est qu'ils soient situés 
avant (respectivement après) 19 dans
le tableau.
Un des intérêts importants de cet algorithme est qu'il peut être réalisé en 
place : le tableau ne sera jamais
recopié. Pour cela, les appels récursifs prendront comme arguments les indices 
délimitant la partie à trier.
I.C.1) Expliquer comment on peut réaliser en place la phase de séparation du 
tableau en temps O(n), avec
n la longueur (nombre d'éléments) du (sous-)tableau à traiter.
I.C.2) Écrire une fonction separation prenant en entrée un vecteur v et deux 
indices i1 et i2 (avec 0 6 i1 < i2 6 t - 1, condition que le programme n'aura pas à vérifier), ayant pour fonction de séparer le sous-tableau v[i1 + 1..i2 ] selon le pivot p = v(i1 ), et retournant l'indice du tableau correspondant à la position de p dans v après séparation. Dans l'exemple précédent, l'appel separation v0 0 9 (Caml) ou separation(v0,0,9) (Pascal) retourne l'indice 6 et le vecteur v0 a été modifié. separation: 'a vect -> int -> int -> int = 
function separation(var v: tableau ; i1, i2: integer): integer;
I.C.3) Écrire une fonction tri_rapide réalisant le tri d'un vecteur/tableau en 
appliquant l'algorithme décrit
plus haut.

II Étude de complexité
On s'intéresse maintenant à la complexité du tri rapide dans deux cas 
particuliers.
II.A ­ Donner un ordre de grandeur du nombre de comparaisons effectuées lorsque 
le tableau est déjà trié dans
l'ordre croissant (respectivement décroissant). Sans forcément donner un 
équivalent de ce nombre de comparaison
C(n), on donnera (en justifiant) une valeur simple v(n) telle que C(n) = 
O(v(n)) et v(n) = O(C(n)).

2 avril 2012 16:53

Page 1/3

II.B ­ On suppose ici que lors d'une exécution du tri rapide, chaque séparation 
du tableau a coupé le tableau
en deux parts égales.
II.B.1) Montrer qu'un majorant raisonnable du nombre de comparaisons effectuées 
pour trier un tableau de
taille n vérifie une relation de la forme M (2n) = 2M (n) + n.
II.B.2) Donner (en fonction de n) la valeur de M (n) lorsque n est de la forme 
2k avec k  N.
II.B.3) On ne suppose plus, ici, que n est de la forme 2k . Montrer que, si on 
suppose que (M (n))nN est
croissante, alors M (n) = O(n ln n).

III Recherche d'une pseudo médiane
Ce qui précède suggère que le choix d'un pivot « proche de la médiane » permet 
d'améliorer les performances
du tri rapide. Il existe un algorithme permettant de trouver cette médiane en 
un temps linéaire en la taille du
tableau, mais cet algorithme difficile ne sera pas discuté ici. Une façon 
simple pour lutter contre le pire des cas
consiste à choisir le pivot de façon aléatoire, mais le gain obtenu est 
relativement subtil et le pire des cas reste
quadratique. Une méthode intermédiaire consiste à rechercher une « pseudo 
médiane ».
Lorsque   ]0, 1[, une -pseudo médiane d'un tableau est une valeur présente dans 
le tableau telle qu'au moins
K1 n (respectivement K2 n ) éléments du tableau lui sont inférieurs 
(respectivement supérieurs), avec K1 et
K2 deux constantes strictement positives.
Pour un tableau de taille n = 3k , on utilisera l'algorithme de recherche d'une 
pseudo médiane suivant :
- si k = 0, on retourne directement le seul élément considéré ;
- sinon, on regroupe les éléments du tableau par 3, on calcule les 3k-1 
médianes de ces groupes, puis on
applique récursivement l'algorithme à ces 3k-1 valeurs.
Dans les questions III.A et III.B, on admet que cet algorithme permet le calcul 
d'une pseudo médiane et on
propose de le mettre en oeuvre de deux manières différentes.
On rappelle que les différents éléments du tableau pourront être supposés 
distincts.
III.A ­ Dans un tableau, en place
III.A.1) Écrire une fonction prenant en entrée un tableau et trois indices 
distincts et retournant la position de
la médiane, parmi les trois éléments du tableau dont on a donné les indices.
III.A.2) Écrire une fonction calculant une pseudo médiane. Cette fonction 
travaillera obligatoirement dans le
tableau initial, sans en créer de nouveau, et en maintenant globalement 
invariant l'ensemble des valeurs présentes
dans le tableau.
On pourra supposer le tableau de taille 3k , placer dans une première étape les 
médianes de blocs de
trois en positions 3i, puis prendre les médianes de ces médianes et les placer 
en position 9i, etc.
III.B ­ À l'aide d'un arbre ternaire
On propose de construire un arbre ternaire : les feuilles sont étiquetées par 
les entrées du tableau et chaque
noeud interne est la médiane de ses fils. La figure 1 montre l'arbre construit 
sur le tableau [7; 1; 4; 9; 8; 5; 3; 2; 6].
4

4

7

1

8

4

9

8

3

5

3

2

6

Figure 1
En Caml :
type ternaire=F of int | N of int*ternaire*ternaire*ternaire;;
let racine=function F(x)->x | N(x,_,_,_)->x;;
En Pascal :
type
Arbre = ^Noeud;
Noeud = record
racine: integer;
fg, fm, fd: Arbre;
end;

2 avril 2012 16:53

Page 2/3

III.B.1) Écrire une fonction calculant la médiane de trois entiers distincts.
mediane3 : int * int * int -> int = 
function mediane3(i1, i2, i3 : integer) : integer;
III.B.2) Écrire une fonction prenant en entrée trois arbres ternaires et 
retournant l'arbre ternaire dont la racine
est étiquetée par la médiane des trois racines des arbres donnés en entrée et a 
pour fils ces trois arbres.
III.B.3) Écrire une fonction récursive construisant l'arbre ternaire associé à 
un sous-tableau de taille 3k . En
Caml, construire t i j retourne l'arbre du sous-tableau t[i..j]. Même chose en 
Pascal avec construire(t,i,j)
construire : int vect -> int -> int -> ternaire = 
function construire(t: tableau ; i, j: integer): Arbre;
III.B.4) Écrire une fonction calculant, à l'aide d'un arbre ternaire, une 
pseudo médiane d'un tableau (dont la
longueur pourra être supposée de la forme 3k ).
III.C ­ Étude théorique de l'algorithme
III.C.1) Donner un ordre de grandeur du temps d'exécution de l'algorithme de 
calcul d'une pseudo médiane.
III.C.2) Si k = 1, la valeur retournée est exactement la médiane du tableau. 
Montrer que pour k > 2, il existe
au moins 2k éléments du tableau qui sont majorés (au sens large) par la valeur 
retournée.
III.C.3) Montrer que pour tout k > 2, il existe un tableau pour lequel il y a 
exactement 2k éléments du tableau
qui sont majorés (au sens large) par la valeur retournée.
III.C.4) Prouver que cet algorithme permet de calculer une -pseudo médiane, 
avec  = ln 2/ ln 3.
III.C.5) Expliquer comment adapter l'implémentation de l'algorithme si le 
tableau a une longueur qui n'est
pas une puissance de 3 ?
III.D ­ Extensions du principe de l'algorithme
III.D.1) Si on modifie l'algorithme en considérant des blocs de 5 éléments 
plutôt que 3, que dire (en supposant
que la longueur du tableau est une puissance de 5) du résultat retourné et du 
temps de calcul de ce nouvel
algorithme ?
III.D.2) Montrer que pour tout  > 0, il existe un algorithme s'exécutant en un 
coût linéaire et permettant de
calculer une (1 - )-pseudo médiane d'un tableau.

IV Gain apporté par la pseudo médiane
On s'intéresse enfin au gain qu'apporte l'utilisation de pseudo médianes dans 
le tri rapide. On suppose ici (sauf
à la dernière question) que le tri rapide est exécuté en utilisant à chaque 
étape une 1/2-pseudo médiane. Ici
encore, une analyse précise et rigoureuse de la complexité est délicate, mais 
on souhaite obtenir une évaluation
de façon raisonnablement convaincante.
On note C(n) le temps de calcul dans le pire des cas pour appliquer le tri 
rapide avec une 1/2-pseudo médiane.
Dans cette évaluation en première approximation, on s'autorise à écrire C(x) 
même lorsque x n'est pas entier :
ce sera un raccourci pour C(x), avec x la « partie entière supérieure de x ».
IV.A ­ Justifier qualitativement le fait que C vérifie une inégalité de la forme

C(n) 6 C(n - n) + Kn

IV.B ­ Montrer que C(n) = C(n/2) + O(n3/2 ).

On pourra étudier la suite définie par 0 ð
= n et k+1 = k - k si k > 1 (et k+1 = 0 sinon) :
établir par exemple que k 6 n/2 si k > n/2.
IV.C ­ Conclure.
IV.D ­ Que peut-on raisonnablement espérer comme complexité dans le pire des 
cas, pour un tri rapide
effectué en calculant une ln 2/ ln 3-pseudo médiane avec l'algorithme de la 
partie III ?
· · · FIN · · ·

2 avril 2012 16:53

Page 3/3

Centrale Informatique MP 2012 -- Corrigé
Ce corrigé est proposé par Guillaume Batog (Professeur agrégé) ; il a été relu 
par
Gautier Marti (ENS Lyon) et Benjamin Monmege (ENS Cachan).

Le problème porte sur l'algorithme de tri rapide d'un tableau. Il est composé de
quatre parties.
· La première partie, constituée uniquement de questions de cours, débute par
la programmation d'un algorithme de tri simple, au choix, après évaluation de
sa complexité. Puis les mêmes questions sont posées pour l'algorithme de tri
rapide. Un petit effort de rédaction est demandé pour décrire les algorithmes.
· La deuxième partie étudie la complexité du tri rapide dans deux cas extrêmes :
le pire, où le tableau est déjà trié, et le meilleur, où le pivot est l'élément 
médian
du sous-tableau traité à chaque étape. Bien que les relations de récurrence
obtenues soient classiques, les questions ne sont pas simples car leur 
formulation
approximative nécessite une petite prise d'initiative mathématique pour rendre
les choses parfaitement rigoureuses.
· La troisième partie, indépendante des précédentes, porte sur un algorithme de
recherche d'une -pseudo médiane dans un tableau de taille n (  ] 0 ; 1 [
à déterminer en fin de partie) : au moins n éléments sont inférieurs 
(respectivement supérieurs) à une -pseudo médiane. Deux implémentations sont
proposées : l'une en effectuant des manipulations sur le tableau en entrée (la 
plus
délicate du sujet), l'autre en utilisant une structure d'arbre (sans 
difficulté).
Il s'ensuit une étude théorique de l'algorithme et de ses extensions.
· La quatrième partie propose de montrer que la complexité du tri rapide est
sous-quadratique (o(n2 )) dans le pire des cas lorsqu'une pseudo médiane est
choisie comme pivot. De longueur modeste, cette partie nécessite de posséder
une petite expérience sur les questions de complexité. En effet, l'énoncé 
demande de justifier qualitativement des résultats tout en restant extrêmement
rigoureux dans certains calculs. La dernière question est même ouverte.
La progression du problème est limpide, de nombreuses questions sont classiques
ou faciles. Il est possible de traiter rapidement les trois premières parties, 
à moins
d'être freiné par certaines approximations mathématiques de l'énoncé. Attention,
les points de la dernière partie (sûrement nombreux) sont difficiles à 
décrocher,
c'est pourquoi il ne faut pas se brûler les ailes en traitant précipitamment le 
début
de l'épreuve.

Indications
Partie I
I.B Le tri à bulles est rapide à décrire et son analyse en complexité est assez
simple. C'est le choix adopté dans ce corrigé.
I.C.1 Décrire le principe consistant, pour un tableau v de pivot p, à déplacer 
un
indice g vers la droite, à déplacer un indice d vers la gauche et à échanger
v(g) et v(d) à chaque fois que v(g) > p > v(d).
Partie II
II.B.1 Supposer si besoin en première approximation que la séparation d'un 
tableau
de taille 2n le coupe en deux sous-tableaux de taille n.
II.B.2 Pour tout k  N , utiliser uk = M(2k )/2k pour trouver le terme général de
la suite (M(2k ))k>1 .
Partie III
III.A.2 Introduire pour structurer les idées une référence pas contenant la 
distance
entre deux éléments consécutifs d'un paquet de 3 dont on veut calculer la
médiane : 3 pas contient alors la distance entre deux paquets de 3 consécutifs.
À chaque parcours du tableau, pas est multiplié par 3.
III.C.1 L'algorithme calcule la médiane de n/3 paquets de 3, puis de n/9 paquets
de 3 etc.
III.C.2 Établir le résultat par récurrence sur k en s'appuyant sur la version 
récursive
de l'algorithme utilisée dans la question III.B.4.
III.C.3 Pour k = 2, le tableau suivant convient :
1

2

3

4

où  désigne une valeur suffisamment grande (qu'il est inutile d'expliciter).
Utiliser ce modèle pour construire récursivement les tableaux souhaités.
III.C.4 Justifier que l'on obtient une ln 2/ ln 3-pseudo médiane d'un tableau t 
de
taille n en appliquant l'algorithme uniquement au sous-tableau t[0..3k - 1]
où 3k est la plus grande puissance de 3 inférieure à n.
Partie IV
IV.A Les résultats de la partie II suggèrent (qualitativement) que C(n1 ) + 
C(n2 )
est d'autant plus grand que |n1 - n2 | l'est. Supposer que K1 = K2 = 1 pour
ne pas rester bloqué par les imprécisions de l'énoncé.
p
IV.B p
Penser télescopage pour établir que k < n/2 si k > n/2. Développer
n/2 fois la relation de récurrence de la question IV.A (ne pas se soucier du
problème posé par des indices non entiers).
IV.D Reprendre tous les raisonnements de cette partie dans le cas général d'une
-pseudo médiane avec   ] 0 ; 1 [. Faire l'hypothèse que la complexité est
majorée par O(n ) avec  6 1 pour ne pas rester bloqué par les imprécisions
de l'énoncé.

I. Tri rapide d'un tableau
I.A Une variable tmp est utilisée pour ne pas perdre la valeur de t(j) au moment
de déplacer t(i) à la place j du tableau t.
let echange i j t =
let tmp = t.(j) in
t.(j) <- t.(i); t.(i) <- tmp;; Lorsque des nombres sont manipulés, il est possible d'échanger le contenu de deux références sans utiliser de variable intermédiaire : a := !a + !b; b := !a - !b; a := !a - !b; I.B Décrivons l'algorithme de tri à bulles pour un tableau t de taille n, indicé de 0 à n - 1. Il s'agit d'échanger deux valeurs consécutives dans t qui ne sont pas rangées dans l'ordre croissant. Ces échanges s'opèrent de gauche à droite en partant du premier élément (boucle for interne dans le programme). Un tel parcours du tableau de gauche à droite est effectué n - 1 fois (boucle for externe) : à la fin du k-ième parcours, le k-ième plus grand élément du tableau t est placé en position n-k. C'est pourquoi il suffit d'arrêter le k-ième parcours à la position n - k. Finalement, le tableau est trié à la fin de l'exécution de l'algorithme. Une implémentation de cet algorithme est donnée par la fonction tribulle suivante, de type tribulle : int vect -> unit = 
let tribulle t =
let n = vect_length t in
for k = 1 to n-1 do
for j = 1 to n-k do
if t.(j) < t.(j-1) then echange j (j-1) t; done; done;; Évaluons la complexité de l'algorithme de tri à bulles. Quel que soit le tableau en entrée, le nombre de comparaisons effectuées est inchangé : n - k au cours du k-ième parcours pour k allant de 1 à n - 1, donc au total n-1 n-1 P P n(n - 1) n-k = j= 2 j=1 k=1 L'algorithme de tri à bulles est de complexité quadratique en termes de comparaisons. D'autres algorithmes peuvent convenir, en gardant à l'esprit que l'énoncé incite fortement à trier un tableau, et non une liste. Pour cela, les algorithmes « simples » (disons de complexité quadratique) les plus adaptés sont le tri à bulles et le tri par sélection, tous deux « en place », c'est-à-dire en modifiant le tableau lui-même, sans utiliser d'espace supplémentaire. Le tri par insertion quant à lui ne peut pas être réalisé en place et il nécessite de translater des morceaux de tableau. I.C.1 Dans l'algorithme suivant, le pivot p est le premier élément du (sous-)tableau t de taille n. Si ce n'est pas le cas, il suffit préalablement d'échanger le pivot avec le premier élément du tableau. Notons g (gauche) la 2e position du tableau t et d (droite) la dernière. L'idée consiste · à déplacer la position g vers la droite tant que t(g) est inférieur au pivot p ; · puis à déplacer la position d vers la gauche tant que t(d) est strictement supérieur au pivot p ; · enfin à échanger t(g) et t(d) (si g < d) car t(d) 6 p < t(g). Ces trois étapes sont répétées tant que la position gauche g est à gauche de la position droite d. À l'issue de ces opérations, tous les éléments à gauche de la position d (incluse) sont inférieurs au pivot et tous ceux à droite lui sont supérieurs. De ce fait, il reste à échanger le pivot avec t(d) pour obtenir la séparation attendue. Le nombre de comparaisons de valeurs du tableau est égal au nombre de positions possibles de g et d, à savoir entre n - 1 et n + 1. La phase de séparation est linéaire en la taille du tableau. I.C.2 La fonction separation ci-dessous programme l'algorithme décrit dans la question précédente (pour un tableau de taille n > 2).
let separation v i1 i2 =
let pivot = v.(i1)
and g = ref (i1+1)
and d = ref i2 in
while !g <= !d do while !g <= i2 && v.(!g) <= pivot do incr g (* montee de g *) done; while v.(!d) > pivot do
decr d
(* descente de d *)
done;
if !g < !d (* aucun echange si g et d se croisent *) then ( echange !g !d v; incr g; decr d ) done; echange i1 !d v; !d;; Une autre méthode, que l'on retrouve traditionnellement dans un cours de taupe, consiste à déplacer le pivot vers la droite en utilisant deux références : · !g désigne la position de fin d'un préfixe de t constitué de valeurs inférieures ou égales au pivot (ce dernier se trouvant à la position !g) ; · !d +1 désigne la position de début d'un suffixe de t constitué de valeurs strictement supérieures au pivot (initialement, ce suffixe est vide). Lorsque !g =!d, le tableau vérifie la propriété de partition pour le pivot se trouvant à la position !g.