DS 6 (MP2I 2022-2023) — Recherche trichotomique et médians¶

Devoir surveillé · MP2I · 2022-2023 · parties 2 et 4 du DS 6 (4 h au total)

Autres parties : 1. Arbres n-aires en C · 3. Table de hachage

2. Recherche trichotomique¶

On considère ici un tableau de valeurs entières triées dans l'ordre croissant. Pour rechercher si un élément \(x\) est dans un tel tableau de taille \(n \ge 2\), on propose de prendre les deux éléments d'indice \(k = \left\lfloor \frac{n}{3} \right\rfloor\) et \(p = \left\lfloor \frac{2n}{3} \right\rfloor\) :

Si \(x = t[k]\) on renvoie \(k\)
Si \(x = t[p]\) on renvoie \(p\)
Si \(x < t[k] \le t[p]\), on continue la recherche dans le tableau des indices \(0\) à \(k-1\)
Si \(t[k] < x < t[p]\), on continue la recherche dans le tableau des indices \(k+1\) à \(p-1\).
Si \(x > t[p]\), on continue la recherche dans le tableau des indices \(p+1\) à \(n-1\).

Quand le tableau a 0 ou 1 élément, on se contente de répondre faux ou de vérifier que le seul élément est \(x\).

Question 7

La manière dont on a rédigé cet algorithme considère qu'on va extraire des sous-tableaux pour faire des appels récursifs. Justifier brièvement pourquoi ce n'est pas une bonne idée ici.

Corrigé

Ici, on a un algorithme où la fusion est clairement en \(O(1)\). Or, les extractions de sous-tableaux induisent une fusion linéaire, ce qui est forcément plus coûteux que l'algorithme lui-même.

Question 8

Décrire, sans écrire de code mais avec précision, un algorithme récursif de recherche n'effectuant pas d'extraction de sous-tableaux.

Corrigé

Petite imprécision du sujet qui parle de renvoyer un indice dans les premiers cas puis change d'avis en demandant juste le booléen.

On considère une fonction récursive d'interface \(Rech(t,i,j,x)\) qui va chercher \(x\) dans \(t\) aux indices entre \(i\) et \(j\) (inclus).

Si \(j<i\) on renvoie faux.
Si \(j = i\), on teste si \(t[i] = x\).
Sinon, on note \(m = j - i + 1\) la taille de la zone de recherche et on pose \(k = i + \left\lfloor \frac{m}{3} \right\rfloor\) et \(p = i + \left\lfloor \frac{2m}{3} \right\rfloor\).
- Si \(x = t[k]\) ou \(x = t[p]\) on renvoie vrai.
- Si \(x < t[k] \le t[p]\), on continue avec \(Rech(t,i,k-1,x)\)
- Si \(t[k] < x < t[p]\), on continue avec \(Rech(t,k+1,p-1,x)\)
- Si \(x > t[p]\), on continue avec \(Rech(t,p+1,j,x)\)

On note \(T(n)\) le nombre d'opérations élémentaires effectuées pour un tableau de \(n\) valeurs.

Question 9

Montrer qu'on a, pour \(n \ge 2\),

\[ T(n) \le T\left( \left\lceil \frac{n}{3} \right\rceil \right) + O(1) \]

et \(T(0) = T(1) = 1\).

Corrigé

Pour les cas de base, le 1 est un peu grossier, on remarque juste qu'on effectue un \(O(1)\) opérations élémentaires.

Si \(n \ge 2\), on va couper en trois. Les fragments sont de taille \(\le \left\lceil \frac{n}{3} \right\rceil\), on continue dans un seul, et le coût du découpage est en \(O(1)\), on a donc la majoration de \(T(n)\) demandée.

Question 10

On pose \(u_n = T(3^n)\).

Exprimer \(u_n\) sans récursivité.

Corrigé

Imprécision encore, c'est une majoration qu'on exprime ici.

\(u_{0} = T(1) = 1\) et \(u_{n+1} = T(3^{n+1}) \le u_n + O(1)\).

Ainsi \(u_n \le n O(1) = O(n)\).

Question 11

En déduire la complexité de cette recherche sous la forme d'un \(O(\cdots)\).

Corrigé

Soit \(p\) tel que \(3^{p-1} < n \le 3^p\), donc \(p = \lceil \log_3 n \rceil\).

On a \(T(n) \le T(3^p) \le O(p) = O(\log_3 n)\).

Question 12

Cette recherche est-elle meilleure que la recherche dichotomique ?

Corrigé

On a \(O(\log_3 n) = O(\log_2 n)\) donc on obtient exactement la même complexité asymptotique.

La partie 4 (« Médians ») reprend le premier problème de l'épreuve d'informatique de Polytechnique 2004 (filière MP, option informatique).

4. Médians¶

Un médian d'un ensemble \(X = \{ e_1, e_2, \dots, e_n \}\) de \(n\) nombres entiers distincts est un nombre \(e\) dans \(X\) tel que les nombres d'éléments strictement plus petits et strictement plus grands que \(e\) dans \(X\) diffèrent d'au plus \(1\) (\(n > 0\)). Si \(n\) est impair, le médian est unique ; si \(n\) est pair, il y a deux médians possibles.

Le problème de la sélection consiste à trouver l'élément de rang \(k\) dans \(X\), c'est-à-dire l'élément se trouvant en \(k\)-ième position quand \(X\) est trié en ordre croissant \((1\le k \le n)\).

Nous supposerons l'ensemble \(X\) représenté par la liste de ses éléments, c'est-à-dire par le type ensemble défini par :

type ensemble = int list

On supposera que les ensemble sont sans répétitions mais pas nécessairement triés.

Question 19

Écrire une fonction card qui prend un ensemble et renvoie son nombre d'éléments.

val card : ensemble -> int

Quelle est la complexité de cette fonction par rapport à \(n\) ?

Corrigé

Vu la question, il fallait réécrire la fonction List.length.

let rec card e =
  match e with
  | [] -> 0
  | _::q -> 1 + card q

Elle est linéaire en \(n\) : un appel par élément.

Soit \(p\) un entier quelconque, on sera amené à partitionner l'ensemble \(X\) en éléments plus grands, égaux ou plus petits que \(p\).

Question 20

Écrire la fonction nPetits qui prend en arguments un entier \(p\) et l'ensemble \(X\) ; et qui renvoie le nombre d'éléments strictement inférieurs à \(p\) dans \(X\).

val nPetits : int -> ensemble -> int

Quelle est la complexité de cette fonction par rapport à \(n\) ?

Corrigé

let rec nPetits p x =
  match x with
  | [] -> 0
  | t::q -> (if t < p then 1 else 0) + nPetits p q

Cette fonction est linéaire en \(n\) car elle effectue un parcours de la liste.

Pour sélectionner le \(k\)-ième élément de \(X\), on prend un nombre \(p\) bien choisi dans \(X\), appelé pivot \((p \in X)\), et on effectue une partition de \(X\) par rapport à \(p\).

Question 21

Écrire la fonction partitionP qui prend en arguments un entier \(p\) et l'ensemble \(X\) ; et qui renvoie l'ensemble de tous les éléments de \(X\) strictement plus petits que \(p\).

val partitionP : int -> ensemble -> ensemble

Modifier cette fonction pour obtenir la fonction partitionG qui retourne l'ensemble de tous les éléments de \(X\) strictement plus grands que \(p\). Quelles sont les complexités en temps de ces fonctions par rapport à \(n\) ?

Corrigé

let rec partitionP p x =
  match x with
  | [] -> []
  | t::q -> let q' = partitionP p q in
    if t < p then t::q' else q'

let rec partitionG p x =
  match x with
  | [] -> []
  | t::q -> let q' = partitionG p q in
    if t > p then t::q' else q'

Exactement comme la question précédente : linéaire en \(n\).

Question 22

Écrire la fonction récursive elementDeRang qui prend en arguments un nombre \(k\) entier naturel et l'ensemble \(X\) ; et qui renvoie l'élément de rang \(k\) dans \(X\), en choisissant comme pivot le premier élément de la liste représentant \(X\).

val elementDeRang : int -> ensemble -> int

Corrigé

let rec elementDeRang k x =
  match x with
  | [] -> failwith "Vide"
  | p::q ->
    let petits, grands =
      partitionP p q, partitionG p q in
    let m = card petits in
    if k <= m
    then elementDeRang k petits
    else if k = m+1
    then p
    else elementDeRang (k-m-1) grands

Le nombre d'opérations pris par la fonction précédente varie en fonction du choix du pivot.

Question 23

Donner un ordre de grandeur, par rapport à \(n\), du nombre maximum \(M(n)\) d'opérations pris par la fonction précédente.

Corrigé

En pire cas, on effectue un appel récursif avec un seul élément de moins, comme les opérations sont linéaires dans la longueur des listes, on retrouve une complexité quadratique.

Plus précisément : \(M(n) \le M(n-1) + O(n)\) donc \(M(n) = O(n^2)\).

En supposant équiprobables tous les rangs possibles pour le pivot choisi dans \(X\), on peut démontrer que le temps moyen pris par elementDeRang est borné supérieurement par \(T(n)\) où \(T\) est une fonction croissante, vérifiant \(T(0) = 0\) et la formule de récurrence suivante :

\[ T(n) \le \ell n + \frac{1}{n} \sum_{i=1}^n \max\{T(i-1), T(n-i)\} \]

(\(\ell\) est une constante indépendante de \(n\) et \(k\)).

Question 24

En déduire une constante \(c\), qu'on déterminera en fonction de \(\ell\), telle que pour tout \(n\) entier naturel, on a \(T(n) \le cn\).

Corrigé

Un peu pénible vu la manière dont l'énoncé le présente. On peut couper en deux la somme pour résoudre le maximum par croissance de \(T\) :

Si \(n = 2p+\epsilon\) avec \(\epsilon \in \{0,1\}\), on a

\[ \sum_{i=1}^n \max(T(i-1), T(n-i)) = \sum_{i=1}^p T(n-i) + \epsilon T(p) + \sum_{i=p+1+\epsilon}^n T(i-1) = \epsilon T(p) + 2 \sum_{i=p+1+\epsilon}^n T(i-1) \]

On montre par récurrence forte sur \(n\) que \(T(n) \le cn\) avec \(c = 4\ell\). C'est vrai pour \(n = 0\). Soit \(n \ge 1\), on suppose que \(T(m) \le cm\) pour tout \(m < n\).

Dans le cas où \(n = 2p\) :

\[ \begin{array}{rcl} T(n) & \le & \ell 2p + \frac{2}{2p} c \sum_{i=p+1}^{2p} (i-1) \\ & = & \ell 2p + \frac{c}{p} \left( \frac{2p(2p-1)}{2} - \frac{(p-1)p}{2} \right) \\ & = & \ell 2p + \frac{c}{2} (2(2p-1) - (p-1)) \\ & = & \ell 2p + \frac{c}{2} (3p - 1) \\ & \le & n (\ell + \frac{3c}{4}) \end{array} \]

Dans le cas où \(n = 2p+1\) :

\[ \begin{array}{rcl} T(n) & \le & \ell (2p+1) + c \frac{p}{2p+1} + \frac{2c}{2p+1} \sum_{i=p+2}^{2p+1} (i-1) \\ & = & \ell (2p+1) + \frac{c}{2p+1} (p + 2p(2p+1) - p(p+1) )\\ & = & \ell (2p+1) + \frac{c}{2p+1} p (3p+2) \\ & \le & n (\ell + \frac{3c}{4}) \end{array} \]

la dernière inégalité venant de \(4p(3p+2) \le 3(2p+1)^2\).

Et on a dans les deux cas, \(T(n) \le n(\ell + \frac{3c}{4}) = cn\) pour \(c = 4 \ell\).

On s'intéresse à présent à optimiser le coût dans le pire cas \(M(n)\). Considérons d'abord les sous-ensembles

\[ X_i = \{ e_{5i+1}, e_{5i+2}, e_{5i+3}, e_{5i+4}, e_{5i+5} \} \]

de 5 éléments consécutifs dans \(X\) pour \(0 \le 5i + 5 \le n\).

Soit \(Y\) l'ensemble des médians des \(X_i\).

Question 25

Écrire une fonction medians qui prend en arguments l'ensemble \(X\) ; et qui renvoie l'ensemble \(Y\).

val medians : ensemble -> ensemble

Quelle est la complexité en temps pris par cette fonction par rapport à \(n\) ?

Corrigé

Les éléments d'un dernier paquet incomplet (moins de 5 éléments) ne sont pas pris en compte, puisque seuls les \(X_i\) avec \(5i+5 \le n\) sont considérés.

let rec medians x =
  match x with
  | x1::x2::x3::x4::x5::q ->
    elementDeRang 3 [x1;x2;x3;x4;x5] :: medians q
  | _ -> []

Comme chaque calcul d'une médiane de 5 peut être supposé en temps constant, on a une complexité linéaire en \(n\).

Pour améliorer la vitesse de la fonction de sélection, on prend à présent comme pivot le médian de l'ensemble \(Y\).

Question 26

Écrire la fonction elementDeRangBis qui prend en entrée un entier naturel \(k\) et l'ensemble \(X\) ; et qui renvoie l'élément de rang \(k\) dans \(X\), en prenant comme pivot le médian de l'ensemble \(Y\).

val elementDeRangBis : int -> ensemble -> int

Question 27

Montrer que son temps maximum \(M'(n)\) vérifie la formule

\[ M'(n) \le \ell' n + M'\left(\left\lfloor \frac{n}{5} \right\rfloor\right) + M'\left(7 \left\lfloor \frac{n}{10} \right\rfloor + 4\right) \]

où \(\lfloor x \rfloor\) est la partie entière de \(x\), et \(\ell'\) est une constante que l'on ne cherchera pas à expliciter. En déduire que pour \(n\) suffisamment grand, on a \(M'(n) \le c' n\) où \(c'\) est une constante à déterminer en fonction de \(\ell'\).

Question 28

Expliquer pourquoi l'ordre de grandeur du nombre maximal d'opérations pris par la fonction de sélection serait différent si on avait regroupé les éléments de \(X\) par groupes de \(3\), plutôt que par groupes de \(5\).