Corrigé CCINP 2026 Informatique PC-PSI — Partie II (Q6 à Q14) : Classification de spectres de galaxies par les k-moyennes

Sujet officiel du concours CCINP, session 2026, épreuve Informatique PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un spectre est une liste de $N$ flottants. La distance entre deux spectres est

$d (S_{1}, S_{2}) = \frac{1}{N} i = 0 \sum N - 1 (S_{1, i} - S_{2, i})^{2} .$

Les fonctions min, max, sum, .sort() sont interdites.

Q6. Principe de l'algorithme des $k$ -moyennes ; rôle de $k$ .
Q7. Écrire distance(S1, S2).
Certaines valeurs défectueuses sont remplacées par None.
Q8. Écrire positions_a_rejeter(S1, S2) : liste des indices $i$ où S1[i] ou S2[i] vaut None.
Q9. Écrire est_absent(element, L) ; complexité en fonction de $r =$ len(L).

Deux fonctions ignorent les positions de a_rejeter (longueur $r$ ) ; toutes deux posent m = N - len(a_rejeter) et renvoient (d/m)**0.5 :

distance2 : pour i dans range(N), si est_absent(i, a_rejeter), ajoute (S1[i]-S2[i])**2 à d ;
distance3 : copie S1 et S2 (.copy()), met à 0 dans les deux copies chaque position de a_rejeter, puis ajoute à d les carrés des différences des copies pour tout i de range(N).

Q10. Énoncer un invariant de boucle utile pour prouver distance2.
Q11. Complexités de distance2 et distance3 en fonction de $N$ et $r$ .

On suppose désormais les spectres sans défaut. spectres est une liste de $p$ spectres, centroides une liste de $k$ centroïdes (barycentres de groupes, listes de $N$ flottants), partitionnement une liste de $p$ entiers : partitionnement[i] est l'indice du centroïde le plus proche de spectres[i]. On dispose de calcule_centroides(partitionnement, spectres) (barycentres des groupes), initialise(k, spectres) ( $k$ spectres tirés au hasard) et trouve_centroide_le_plus_proche(S, centroides) (un indice).

Q12. Écrire produit_partition(spectres, centroides), qui renvoie le partitionnement (exemple : [1, 2, 1, 1, 0]).
Q13. Écrire k_moyennes(spectres, k), qui renvoie centroides et partitionnement ; on s'arrête quand le partitionnement ne change plus.

Nombre de groupes inconnu : (1) partir de $k = 10$ spectres ; (2) appliquer les $k$ -moyennes ; (3) retirer des spectres le groupe le plus peuplé ; (4) s'il reste plus de $100$ spectres, revenir en (1). On dispose de principal_et_reste(partitionnement, spectres), qui renvoie la liste des spectres du groupe majoritaire et la liste des autres.
Q14. Écrire groupes_de_spectres(spectres), qui renvoie la liste des groupes extraits (les spectres restants sont abandonnés).

Corrigé

Q6. Les $k$ -moyennes sont un algorithme de classification non supervisée (partitionnement, « clustering ») : on dispose de $p$ points (ici des spectres, vus comme des vecteurs de $R^{N}$ ) sans étiquette, et l'on cherche à les répartir en $k$ groupes de points proches les uns des autres. L'algorithme :

choisir $k$ centroïdes initiaux (par exemple $k$ points tirés au hasard) ;
affecter chaque point au groupe du centroïde le plus proche ;
remplacer chaque centroïde par le barycentre (la moyenne) des points de son groupe ;
recommencer en 2 jusqu'à ce que les affectations ne changent plus.

Chaque étape fait décroître (au sens large) l'inertie $\sum_{i} d (S_{i}, C_{groupe (i)})^{2}$ ; l'algorithme converge, mais vers un minimum local qui dépend de l'initialisation. Le paramètre $k$ est le nombre de groupes (de classes) recherchés, fixé à l'avance par l'utilisateur.

Ce que le correcteur attend : ne pas confondre avec les $k$ plus proches voisins (Q15) : ici $k$ n'est pas un nombre de voisins, et il n'y a pas de données de référence étiquetées.

Q7. Une boucle sur les indices, un accumulateur, puis la moyenne et la racine :


def distance(S1, S2):
    N = len(S1)
    somme = 0
    for i in range(N):
        somme = somme + (S1[i] - S2[i]) ** 2
    return (somme / N) ** 0.5

Coût $O (N)$ . Test : distance([0,0,0,0], [1,1,1,1]) renvoie 1.0.

Q8. Une seule condition composée par indice, pour ne pas ajouter deux fois un indice où les deux valeurs manquent :


def positions_a_rejeter(S1, S2):
    a_rejeter = []
    for i in range(len(S1)):
        if S1[i] is None or S2[i] is None:
            a_rejeter.append(i)
    return a_rejeter

Les indices sont ajoutés dans l'ordre croissant et sans doublon ; coût $O (N)$ .

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 →