Corrigé X-ENS 2026 Informatique A MP — Partie III (III.1 à III.8) : Quantification de produit : k-moyennes et distances approchées

Sujet officiel du concours X-ENS, session 2026, épreuve Informatique A MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

La base db contient $n$ vecteurs $p_{0}, \dots, p_{n - 1}$ de $R^{d}$ ; dist2 p1 p2 calcule en $O (d)$ le carré de leur distance euclidienne. Pour les $k$ -moyennes, centroids est une matrice $k \times d$ de centroïdes et centroid_of.(i) est l'indice du centroïde le plus proche de db.(i).


type vector = float array        (* vecteur *)
type matrix = vector array       (* tableau de vecteurs *)
type square = float array array  (* matrice carrée n x n *)
val dist2 : vector -> vector -> float
(* fonctions fournies à partir de III.4 *)
val vector_sum : vector -> vector -> vector (* somme *)
val matrix_sum : square -> square -> square (* somme *)
val vector_div : vector -> float -> vector  (* division *)
(* fournie à partir de III.7 *)
val submatrix : matrix -> int -> matrix list

III.1. Écrire compute_all_dist2 : matrix -> square (matrice des $∥ p_{i} - p_{j} ∥^{2}$ ), avec Array.init_matrix.
III.2. Complexité de la recherche du plus proche voisin d'un vecteur query parmi les $n$ vecteurs (sans code).
III.3. Écrire pick : matrix -> matrix -> int array -> unit : pick db centroids centroid_of met à jour en place centroid_of.
III.4. Écrire update : int -> matrix -> int array -> matrix -> unit : update k db centroid_of centroids recalcule en place les $k$ centroïdes.
III.5. Votre code peut-il mettre à jour moins de $k$ centroïdes ?
III.6. Écrire kmeans : matrix -> int -> int -> int array * matrix : kmeans db k n_iter fait n_iter itérations et renvoie (centroid_of, centroids), les centroïdes étant initialisés aux $k$ premiers vecteurs.

Chaque vecteur est coupé en $m$ paquets consécutifs de taille $d / m$ ( $m$ divise $d$ ) ; les $k$ -moyennes sur le $ℓ$ -ième paquet de tous les vecteurs donnent $c_{ℓ} (p) \in [k]$ , indice du centroïde du $ℓ$ -ième paquet de $p$ . submatrix db m renvoie la liste des $m$ matrices $n \times (d / m)$ des paquets.

III.7. Écrire approx_dist : matrix -> int -> int -> int -> square : approx_dist db k n_iter m calcule la matrice des $D_{ij}^{'} = \sum_{ℓ = 1}^{m} d_{ℓ} (c_{ℓ} (p_{i}), c_{ℓ} (p_{j}))$ , où $d_{ℓ} (a, b)$ est le carré de la distance entre les centroïdes $a$ et $b$ du $ℓ$ -ième paquet.
III.8. On pré-calcule les $d_{ℓ} (a, b)$ dans un dictionnaire (les $c_{ℓ} (p_{i})$ et les centroïdes étant connus). (a) Complexité de ce pré-calcul en fonction de $k$ , $d$ , $m$ . (b) Borner le nombre de valeurs distinctes des $D_{ij}^{'}$ en fonction de $k$ et $m$ . (c) Complexité, après pré-calcul, de la recherche des plus proches voisins de db.(i) pour la distance approchée. (d) Même question pour un nouveau vecteur $p \in R^{d}$ .

Corrigé

Pour les tests, dist2, vector_sum, matrix_sum, vector_div et submatrix ont été écrites selon leur spécification (OCaml 5.4, qui fournit Array.init_matrix).

III.1. Le coefficient $(i, j)$ est dist2 db.(i) db.(j) :


let compute_all_dist2 (db : matrix) : square =
  let n = Array.length db in
  Array.init_matrix n n (fun i j -> dist2 db.(i) db.(j))

Array.init_matrix appelle la fonction une fois par case : $n^{2}$ appels à dist2 en $O (d)$ , soit $O (n^{2} d)$ . Sur $p_{0} = (0, 0)$ , $p_{1} = (3, 4)$ , $p_{2} = (1, 1)$ , on obtient les lignes $(0, 25, 2)$ , $(25, 0, 13)$ , $(2, 13, 0)$ . On pourrait n'en calculer que la moitié par symétrie, sans changer l'ordre de grandeur.

III.2. Il faut, dans le cas général, calculer la distance de query à chacun des $n$ vecteurs (un vecteur non examiné pourrait être le plus proche), chaque calcul coûtant $O (d)$ , en retenant le minimum courant en $O (1)$ par vecteur : la complexité est $O (n d)$ . On compare les carrés des distances, qui sont rangés dans le même ordre que les distances (la racine est croissante). Si query est l'un des db.(i) et que la matrice de III.1 est déjà calculée, il suffit de parcourir sa ligne $i$ (en excluant $j = i$ ) : $O (n)$ , mais après un pré-calcul en $O (n^{2} d)$ .

III.3. Pour chaque vecteur, on cherche le centroïde de carré de distance minimal (premier indice en cas d'égalité).


let pick (db : matrix) (centroids : matrix)
    (centroid_of : int array) : unit =
  let k = Array.length centroids in
  Array.iteri (fun i p ->
      let best = ref 0 and d_best = ref (dist2 p centroids.(0)) in
      for j = 1 to k - 1 do
        let dj = dist2 p centroids.(j) in
        if dj < !d_best then begin best := j; d_best := dj end
      done;
      centroid_of.(i) <- !best)
    db

Invariant de la boucle for : après le tour $j$ , !best est l'indice d'un centroïde le plus proche de $p$ parmi les centroïdes $0, \dots, j$ et !d_best son carré de distance. Complexité : $k$ appels à dist2 par vecteur, soit $O (nk d)$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →