CCINP Informatique Commune PC PSI 2026Sujet et rapport du jury

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH ÉPREUVE SPÉCIFIQUE - FILIÈRE PC

INFORMATIQUE

• -Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, bleu clair ou turquoise, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
• -Ne pas utiliser de correcteur.
• -Écrire le mot FIN à la fin de votre composition.

Autour de l'astro-informatique

Introduction

• -extraction des informations contenues dans une base de données astronomiques issue du SDSS (Sloan Digital Sky Survey);
• -classification des galaxies en différentes classes spectrales à l'aide de l'algorithme des k-moyennes;
• -classification des étoiles en différentes classes spectrales à l'aide de l'algorithme des k plus proches voisins;
• -reconnaissance de la structure à grande échelle de l'Univers à l'aide de la théorie des graphes.

ANNEXE

Rappels des syntaxes en Python

Partie I - Interrogation d'une base de données astronomiques

I. 1 - Observation du ciel et poids des données

• -les photographies du ciel dans une couleur donnée;
• -les spectres pris pour certains objets lumineux du ciel détectés sur les photographies précédentes.

I. 2 - Interrogation de la base en SQL

• -objID (int, clef primaire) : identifiant unique dans la base d'un objet au sens « zone lumineuse intéressante sur une photographie donnée ». Si un même objet astrophysique est observé sur deux photographies différentes, il aura deux objID uniques différents, un pour chaque observation;
• -ra (float) et dec (float) : respectivement l'ascension droite et la déclinaison qui sont un couple d'angles (similaires à θ et φ en coordonnées sphériques) permettant de définir la direction d'observation de l'objet dans le ciel;
• -z (float) : magnitude absolue M_z (soit la luminosité) dans la bande z (infrarouge).

• -Spec0bjId (int, clef primaire) : identifiant unique du spectre ;
• -bestObjId (int) : identifiant de l'observation la plus précise de la table PhotoObj qui correspond au spectre ;
• -target0bjId (int) : identifiant de l'observation de la table Photo0bj qui a déclenché la procédure permettant d'obtenir le spectre;
• -class (str) : classification (déduite du spectre) de l'objet astronomique associé, cela peut être une étoile ('STAR') ou une galaxie ('GALAXY');
• -z (float) : redshift (décalage vers le rouge) z de l'objet considéré (à ne surtout pas confondre avec PhotoObj.z qui est une luminosité), cela mesure l'éloignement de l'objet le long de la ligne de visée.

Partie II - Classification de spectres de galaxies

II. 1 - Justification de l'approche

• Q6.Rappeler en quelques phrases en quoi consiste l'algorithme des k-moyennes et en particulier ce que représente le paramètre k dans cet algorithme.

II. 2 - Distance entre deux spectres

• Q7.Écrire une fonction distance (S1, S2) qui, étant donné deux listes de flottants de même taille S1 et S2 représentatives de deux spectres, renvoie la distance entre les deux spectres comme définie ci-dessus.

• Q8.Écrire une fonction positions_a_rejeter(S1, S2) qui prend en entrée deux listes et renvoie la liste des indices i pour lesquels soit S1[i], soit S2[i] vaut None.
• Q9.Implémenter une fonction est_absent(element, L) qui renvoie True si element est absent de la liste L et False sinon. Donner la complexité temporelle dans le pire des cas de votre implémentation en fonction de r = len(L).

def distance2(S1, S2, a_rejeter):
    d = 0
    N = Ien(S1)
    m = N - len(a_rejeter)
    for i in range(N) :
        if est_absent(i, a_rejeter):
            d = d + (S1[i]-S2[i])**2
    return (d / m) ** 0.5

def distance3(S1, S2, a_rejeter):
    d = 0
    N = Ien(S1)
    m = N - len(a_rejeter)
    S1c = S1.copy()
    S2c = S2.copy()
    for i in a_rejeter:
        S1c[i] = 0
        S2c[i] = 0
    for i in range(N) :
        d = d + (S1c[i]-S2c[i])**2
    return (d / m) ** 0.5

• Q10.Énoncer une propriété invariante de boucle qui serait utile pour démontrer la correction de la fonction distance2 (on ne demande pas de démontration).
• Q11.Estimer les complexités temporelles de chacune des deux implémentations distance 2 et distance3 en fonction de N = len(S1) et de r = len(a_rejeter).

II. 3 - Implémentation des k-moyennes

• -S correspond à un spectre, représenté informatiquement par une liste de N flottants.
• -spectres est une liste de p éléments contenant l'ensemble des spectres S à classifier.
• -C correspond au barycentre d'un ensemble de spectres S, lui même liste de N flottants. On appellera un tel barycentre un centroïde.
• -centroides est une liste de k éléments contenant l'ensemble des centroïdes.
• -partitionnement est une liste de p éléments (autant que de spectres à classifier) telle que si on pose j = partitionnement[i], alors C = centroides[j] est le centroïde dont S = spectres [i] est le plus proche.

• -calcule_centroides(partitionnement, spectres) qui renvoie la liste des barycentres de chaque groupe dans la partition représentée par la liste partitionnement;
• -initialise(k, spectres) qui renvoie une liste de k spectres pris aléatoirement parmi la liste spectres;
• -trouve_centroide_le_plus_proche(S, centroides) qui renvoie l'indice du centroïde le plus proche du spectre S dans la liste centroides.
• Q12.
  Écrire une fonction produit_partition(spectres, centroides) qui renvoie une liste de p éléments et qui contient pour chaque spectre de spectres l'indice du centroïde auquel il est associé dans la liste centroides. Il faut utiliser au moins une des fonctions introduites précédemment.
  On donne l'exemple suivant dans lequel on suppose disposer de 5 spectres (dans les variables S1 à S5) à répartir autour de 3 centroïdes (dans les variables C1 à C3). Les spectres S1, S3 et S4 ont C2 pour centroïde le plus proche alors que S2 est plus proche de C3 et S5 de C1. On aurait alors :

  >>> spectres = [S1, S2, S3, S4, S5]
  >>> centroides = [C1, C2, C3]
  >>> produit_partition(spectres, centroides)
  [1, 2, 1, 1, 0]
  

• Q13.En utilisant des fonctions parmi celles introduites plus haut ainsi que celle de la question précédente, écrire une fonction k_moyennes(spectres, k) qui, étant donné une liste spectres de spectres et un entier k renvoie deux listes :
  • -une liste centroides de k éléments qui contient les centroïdes de chaque groupe trouvé;
  • -une liste partitionnement de p éléments qui contient pour chaque spectre de spectres l'indice du centroïde auquel il est associé dans la liste centroides précédente après convergence de l'algorithme.

II. 4 - Détermination automatique du nombre de groupes

>>> spectres = [S1, S2, S3, S4, S5]
>>> partitionnement = [ 1, 2, 1, 1, 0]
>>> principal_et_reste(partitionnement, spectres)
[S1, S3, S4], [S2, S5]

Partie III - Classification de spectres stellaires

references = lit_spectres_de_reference()
types_spectraux = ["O", "B", "A", "F", "G", "K", "M"]
R = len(references) // len(types_spectraux)
def mystere(S, k):
    L = []
    for Sref in references:
        d = distance(S, Sref)
        L.append(d)
    copie_L = copie_ordonnee(L)
    seuil = copie_L[k]
    resultats = [0] * len(type_spectraux)
    for i in range(len(references)):
        if L[i] < seuil:
            j = i // R
            resultats[j] = resultats[j] + 1
    M = max(resultats)
    for i in range(len(resultats)):
        if resultats[i] == M:
            return types_spectraux[i]
classification = []
for S in spectres_a_classifier:
    type_spectral = mystere(S, 8)
    classification.append(type_spectral)

• Q17.Quelle valeur de k a été choisie pour cette implémentation de l'algorithme des k plus proches voisins? Sur quel numéro de ligne le voit-on?
• Q18.Expliquer en une ligne (et sans paraphraser le code) ce que font les lignes 1 à 5, 8 à 11, 12 à 18, 19 à 22 et 24 à 27.
• Q19.Écrire la signature de la fonction mystere. On attend en particulier de spécifier les données attendues en entrée et ce que renvoit la fonction.
• Q20.Détailler deux défauts potentiels du script précédent en précisant les lignes de code incriminées.
• Q21.Proposer une modification de la fonction mystere qui permette de rajouter une notion de « niveau de confiance » dans le résultat renvoyé.
• Q22.Définir la notion de matrice de confusion. Proposer un algorithme en langage naturel qui permette de la calculer pour les spectres de référence.

Partie IV - Reconnaissance des filaments galactiques

Figure 1 - Placement original des galaxies en coordonnées ascension droite, déclinaison et redshift (a) et détection finale des filaments (b)

• 1. T est acyclique et connexe;
• 2. T est connexe et |A| = |S| − 1;
• 3. T est acyclique et |A| = |S| − 1.

IV. 1 - Exemple pour comprendre le concept

• -on choisit un sommet de départ que l'on place dans l'arbre ;
• -tant qu'il reste des sommets non encore inclus dans l'arbre :
  • -on sélectionne, parmi les arêtes liant un sommet de l'arbre aux sommets non encore inclus, celle qui est de pondération minimale,
  • -on ajoute à l'arbre le sommet externe associé à cette arête (c'est le sommet qui est le plus proche de l'arbre construit jusqu'à présent en considérant la pondération comme une distance) en gardant en mémoire l'arête utilisée ;
• -à la fin, on a obtenu les N − 1 arêtes qui constituent l'arbre cherché.

Figure 2 - Graphe-jouet (a) permettant d'illustrer l'algorithme utilisé pour déterminer un « arbre couvrant de poids minimal » constitué de N − 1 arêtes de somme des pondérations minimale et gardant un graphe connexe (b)

Figure 3 - Modèle jouet où chaque point représente une galaxie dans un espace bidimensionnel : on y a mis deux amas circulaires connectés par un filament de galaxies ainsi qu'un amas isolé. Le but de cette partie est de comprendre comment passer à l'aide de la théorie des graphes de la représentation brute de gauche à celle à droite où l'on visualise plus facilement le filament et l'amas isolé

IV. 2 - Application à la distribution de galaxies : initialisation du graphe

• Q25.Étant donné une liste coords qui contient les coordonnées des différentes galaxies (sous forme de triplets (x, y, z) ) ainsi que les identifiants i et j de deux galaxies dans cette liste, écrire une fonction poids(coords, i, j) qui calcule et renvoie le poids p_(ij) de l'arête associée à ces deux galaxies. Exemple d'utilisation :

gal0 = ( 0, 1, 5)
gal1 = (-1, 2,-4)
gal2 = ( 3, 2, 5)
coords = [gal0, gal1, gal2]
poids(coords, 0, 2) # Doit renvoyer 10 = (0-3)**2 + (1-2)**2 + (5-5)**2

Figure 4 - Modèle jouet où chaque point représente une galaxie dans un espace bidimensionnel : on y a mis deux amas circulaires connectés par un filament de galaxies. La figure de droite indique l'arbre couvrant de poids minimal qui a été trouvé en partant de la configuration initiale de gauche

• Q26.Définir une fonction matrice_adjacence(coords) qui, à partir de la donnée de la liste des coordonnées, renvoie, sous forme de liste de listes, la matrice d'adjacence pour le graphe pondéré associé aux données galactiques : chaque galaxie est un sommet numéroté par sa position dans la liste des coordonnées et les coefficients m_(ij) de la matrice d'adjacence sont donnés par la fonction préparée à la question précédente.

IV. 3 - Algorithme de construction de l'arbre

• -un dictionnaire dist (pour distance) ayant pour clefs toutes les galaxies qui ne sont pas encore dans l'arbre et pour valeur la distance actuelle de la galaxie à l'arbre (c'est-à-dire le minimum des distances de la galaxie à toutes celles déjà présentes dans l'arbre). C'est le dictionnaire dist qui va permettre de choisir la galaxie à ajouter dans l'arbre (celle qui a la distance minimale). L'algorithme de Prim consiste à réactualiser ce dictionnaire après chaque ajout en regardant parmi les galaxies encore non ajoutées si leur distance à l'arbre a diminué ;
• -un dictionnaire pred (pour prédécesseur) ayant pour clefs toutes les galaxies (sauf le point de départ) et pour valeur la galaxie de l'arbre qui est la plus proche de la galaxie servant de clef.
  Lorsque le dictionnaire dist aura été vidé, le dictionnaire pred servira de description complète à l'arbre couvrant minimal obtenu en donnant pour chaque galaxie sa prédécesseure dans l'arbre.

def arbre_couvrant_minimal(G, depart):
    dist = initialisation_distance(G, depart)
    pred = {}
    while len(dist) != 0:
        x = recherche_distance_minimale(dist)
        mise_a_jour(dist, pred, x, G)
    return pred

• Q27.Définir la fonction initialisation_distance( G , depart) qui prend en argument une matrice d'adjacence G représentative du graphe à traiter et une galaxie depart. Elle doit renvoyer un dictionnaire dont les clefs sont les numéros associés à chaque galaxie dans G (compris entre 0 et len (G)-1 inclus) avec pour valeur float ('inf') ^3 sauf pour la clef depart qui doit avoir une valeur nulle.
• Q28.Compléter sur le DR la fonction recherche_distance_minimale(dist) qui prend en argument le dictionnaire contenant les distances associées à chaque galaxie. Noter que la fonction modifie le dictionnaire dist sans pour autant le renvoyer, mais, avec un dictionnaire en Python, la modification sera « visible » depuis la fonction principale. La fonction doit renvoyer la galaxie encore présente dans le dictionnaire dont la distance à l'arbre est la plus faible.
• Q29.Prouver que la fonction arbre_couvrant_minimal introduite par l'énoncé termine en exhibant un variant adéquat (et en justifiant rapidement que ce soit un variant).

def mise_a_jour(dist, pred, x, G):
    for y in range(len(G)) :
        if y in dist:
            if dist[y] > G[x][y]:
                dist[y] = G[x][y]
                pred[y] = x

• Q30.Estimer (en la justifiant) la complexité temporelle globale dans le pire des cas de la fonction arbre_couvrant_minimal introduite par l'énoncé en fonction du nombre N de galaxies présentes dans le graphe G. On détaillera brièvement chaque point du raisonnement, notamment les complexités pour chacune des fonctions initialisation_distance, recherche_distance_minimale et mise_a_jour.

IV. 4 - Élagage de l'arbre couvrant de poids minimal

Figure 5 - Application de l'algorithme de Prim menant à l'arbre couvrant de poids minimal (figure (a)) du modèle jouet de la figure 4 . La figure (b) indique le même arbre après élagage des branches non nécessaires

• Q31.Écrire une fonction dico_galaxies_avec_successeurs (arbre) qui renvoie un dictionnaire dont les clefs sont les galaxies x qui ont au moins un successeur dans l'arbre et dont la valeur est le nombre de successeurs, c'est-à-dire le nombre de galaxies y telles que x == arbre [y]. Si une galaxie n'a aucun successeur, elle ne doit pas être entrée comme clef du dictionnaire renvoyé. On privilégiera dans la mesure du possible une fonction en O(n) plutôt qu'en O(n^2) avec n = len (arbre). Notez que x peut être un prédécesseur de y et ne pas faire partie des clefs du dictionnaire arbre (cas de la racine, la galaxie depart de la question Q27).

def elagage(arbre, nb_etapes):
    for i in range(nb_etapes):
        nb_succ = dico_galaxies_avec_successeurs(arbre)
        arbre_elague = {}
        for gal in arbre:
            if gal in nb_succ:
                arbre_elague[gal] = arbre[gal]
        arbre = arbre_elague
    return arbre

IV. 5 - Séparation des groupes sans filament

• -le site du SDSS : https://www.sdss.org/
• -les publications basées sur le SDSS :

• -une page pour tester les requêtes SQL :
  https://skyserver.sdss.org/dr19/SearchTools/sql
• -la galerie d'images des instruments et des résultats dont les dernières figures ont été tirées: https://www.sdss.org/science/image-gallery/
• -l'article ayant servi de base d'inspiration à la partie IV : Bonnaire, Tony, et al. "T-ReX : a graph-based filament detection method." Astronomy & Astrophysics 637 (2020) : A18.

Figure 6 - À gauche : télescope du Sloan Digital Sky Survey à l'observatoire d'Apache point au Nouveau Mexique (crédits photo SDSS). À droite : fibres optiques servant à récolter les spectres dans le spectrographe APOGEE du temps où le placement des fibres se faisait encore à la main (crédits photo SDSS)

Figure 7 - À gauche : image prise par le SDSS de la galaxie M51 dite « galaxie du Tourbillon », d'un diamètre d'environ 75000 années lumière, en interaction avec sa voisine plus petite sur la gauche de l'image. Elle occupe environ 3 millionième de la surface totale imagée par le SDSS et fait partie des près de 100 millions de galaxies photographiées par le projet souvent bien plus petites et bien moins brillantes. On en voit quelques unes sous formes de taches diffuses sur la photo. Crédits photo SDSS et Robert Lupton. À droite : un empilement de plus de 46000 spectres de quasar (un par ligne) répartis selon leur redshift (décalage vers le rouge) issus de la DR3 du SDSS. Les bandes claires correspondent aux raies d'émission spécifiques de l'hydrogène, du carbone, de l'oxygène, du magnésium et du fer. Le décalage progressif vers le rouge (longueurs d'ondes plus grandes) est ce qui permet de mesurer le redshift z. Crédits photo X. Fan et le SDSS

Figure 8 - Distribution des galaxies du SDSS dans la tranche équatoriale (déclinaison δ comprise entre -2 et +2°) où l'on voit une coupe dans la structure filamentaire étudiée dans ce problème. Les zones blanches correspondent aux « angles morts » de l'ascension droite non observables via les télescopes du SDSS. Credits photo M. Blanton et SDSS