CCP Informatique PSI 2020

Thème de l'épreuve Détection d'obstacles par un sonar de sous-marin
Principaux outils utilisés programmation Python, listes, tableaux NumPy, récursivité
Mots clefs sonar, signal, Fourier, spectrogramme, arbre, décision, forêt, Gini

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                                           

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2020 PSISIN

GP

CONCOURS
COMMUN
INP

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE PSI

INFORMATIQUE

Mercrediémai:8h-1ilh

N.B. : le candidat attachera la plus grande importance à la clarté, à la 
précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur 
d'énoncé, il le signalera sur sa copie
et devra poursuivre sa composition en expliquant les raisons des initiatives 
qu'il a été amené à prendre.

RAPPEL DES CONSIGNES

«_ Utiliser uniquement un stylo noir ou bleu foncé non efjaçable pour la 
rédaction de votre composition ; d'autres
couleurs, excepté le vert, 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.

Les calculatrices sont interdites

Le sujet est composé de trois parties indépendantes.

L'épreuve est à traiter en langage Python. La syntaxe de Python est rappelée en 
Annexe, page 8 du
Document Réponse.

Les différents algorithmes doivent être rendus dans leur forme définitive sur 
le document réponse dans
l'espace réservé à cet effet en respectant les éléments de syntaxe du langage 
(les brouillons ne sont
pas acceptés).

La réponse ne doit pas se cantonner à la rédaction de l'algorithme sans 
explication, les programmes
doivent être expliqués et commentés.

Énoncé : page 1 à page 12
Document réponse et Annexe : page | à page 8

Seul le Document Réponse est à rendre.

1/12
Détection d'obstacles par un sonar de sous-marin

Partie I - Introduction

Pour détecter des obstacles sous l'eau, en l'absence de visuel direct, les 
sous-marins sont équipés
de sonars. L'onde ultrasonore émise par le sonar est réfléchie sur l'obstacle 
et le signal en retour est
détecté et analysé pour obtenir la distance de l'obstacle au sous-marin. Une 
des difficultés rencontrée
lors de l'analyse du signal de retour est de déterminer si l'obstacle est une 
roche ou un objet métallique
donc un danger potentiel.

Il existe des techniques d'aide à la décision faisant partie des algorithmes 
dits d'Intelligence Arti-
ficielle permettant d'analyser le signal de retour d'un sonar et de déterminer 
de quelle nature est
l'obstacle.

Objectif

L'objectif du travail proposé est de découvrir des algorithmes d'Intelligence 
Artificielle en s'ap-
puyant sur ce problème de détection d'obstacle. À partir d'une base de données 
comportant des
mesures de sonar réalisées sur des roches et sur du métal, il s'agira d'être 
capable de déterminer
à partir d'une mesure inconnue, si l'objet situé devant le sous marin est une 
roche ou un objet
métallique.

Le sujet abordera les points suivants :
- analyse et représentation des données,
- construction des arbres de décisions.
- prédiction par la méthode « random forest ».

Dans tout le sujet, 1l sera supposé que les modules python numpy, 
matplotlib.pyplot sont déjà
importés dans le programme (cf. Annexe), on utilisera donc les fonctions de ces 
modules sans préciser
l'origine de celles-ci. Lorsqu'il est demandé de définir des vecteurs ou des 
matrices, 1l est demandé
d'utiliser le type array du module numpy.

Partie II - Analyse des données

IL.1 - Présentation

Les données utilisées pour l'apprentissage de l'algorithme ont été obtenues 
suite à une campagne
d'essais réalisés dans l'océan à partir des mesures d'un sonar situé à environ 
10 mètres d'un cylindre
métallique ou d'un cylindre en pierre pour différentes incidences angulaires du 
signal émis par le
SONT.

Le signal émis par le sonar et le signal reçu sont numériques et représentés 
avec N valeurs sur une
durée totale T;. Les variables Tf et N sont définies dans le programme.

Q1. Écrire une instruction permettant de définir la variable temps, vecteur 
décrivant les instants de
0 à T ; uniformément répartis (exclu).

Le signal émis par le sonar (appelé CHIRP) est un signal modulé en fréquence 
linéairement en partant
d'une fréquence f, jusqu'à la fréquence f;, (figure 1), ceci permet d'atteindre 
de grandes portées et
une bonne réception du signal lors du retour de l'onde malgré les bruits de 
mesure.

2/12
L'expression du signal émis est la suivante :

e(f) = Eosin(2x f.(t)t) S0 > Dij 
Si; W(t, j;,n) df dt avec

i J
pi; poids (valeurs connues).

Q6. Écrire une fonction enveloppe(eta,S,p,dt,df) qui renvoie la valeur de 
l'intégrale numé-
rique en fonction de la valeur de eta = 7. On supposera connus les pas df et 
df. Le tableau
numpy S contient les valeurs de la fonction discrète S;; et le tableau numpy p 
contient les
valeurs des poids p;;.

6/12

Pour chaque expérience (fonction de l'obstacle et de l'angle d'incidence de 
l'onde émise), on construit
cette enveloppe. En prenant m = 60, on obient 60 valeurs qui caractérisent une 
expérience. Ces valeurs
seront utilisées dans les algorithmes de prédiction décrits dans la suite pour 
classer une nouvelle
mesure.

De manière à pouvoir comparer les enveloppes, on normalise le vecteur P, en 
ramenant le maximum
à 1 et le minimum à 0 par une fonction affine.

Q7. Proposer une fonction normalisation(P) qui renvoie un vecteur de m valeurs 
comprises
entre 0 et 1. On pourra utiliser les fonctions min(x) et max(x) avec x un 
vecteur.

II.2 - Lecture des données

Les données à utiliser sont stockées dans un fichier texte où une ligne 
représente l'ensemble des
valeurs associées à une expérience. Une expérience est caractérisée par 60 
valeurs issues du traite-
ment de la mesure (chaque valeur est un nombre réel entre 0 et 1) et un 
caractère donnant le groupe
d'appartenance (un caractère M pour métal et R pour roche).

Premières lignes partielles du fichier, les points de suspension permettent de 
cacher les 56 données
intermédiaires pour chaque ligne :

0.0200 ,0.0371,...,0.0090 ,0.0032 ,R
0.0453,0.0523,...,0.0052,0.0044 M
0.0262,0.0582,...,0.0095 ,0.0078 ,R
0.0100,0.0171,...,0.0040 ,0.0117,M

On souhaite lire ce fichier de données pour créer un tableau de type liste 
contenant des listes. Pour
la dernière colonne, le caractère "R""', respectivement "M", sera converti en 
la valeur 0.0, respective-
ment 1.0. La fonction suivante permet de lire le fichier de données et renvoie 
les données au format
souhaité.

def lire donnees(nom fichier ):
donnees = {|
with open(nom_fichier, 'r') as fichier
for ligne in fichier:
a = ligne.split(",')
b = []
for 1 in range(len(a)-l):
b.append(float(al1il]l))
if af---1].strip() == "R'":
b.append(0.0)
else :
b.append(1.0)
donnees .append(b)
return donnees

QS. A partir de la fonction lire_donnees, préciser la valeur de la variable 
donnees en se limitant
aux deux premières lignes lues. Les fonctions usuelles sur les fichiers et 
chaînes de caractères
et leur documentation sont rappelées dans l' Annexe.

Le fichier de données comporte nr, = 208 enregistrements.

Q9. Donner la taille mémoire minimale nécessaire en octets pour stocker les 
données. On rappelle
que Python stocke les nombres réels en format double précision par défaut.

7/12
Partie III - Méthode des forêts aléatoires

La méthode des forêts aléatoires est une amélioration de la méthode des arbres 
de décision.
IIL.1 - Arbre de décision

Un arbre de décision est une représentation qui permet de séparer les données 
en deux groupes,
appelés noeuds de l'arbre, selon un critère objectif. Les sous-groupes (ou 
noeuds) sont ensuite séparés
en deux selon un autre critère, puis on sépare à nouveau jusqu'à obtenir un 
noeud terminal appelé
feuille.

Pour classer une nouvelle donnée, il suffit ensuite de suivre les différentes 
règles issues de la construc-
ton de l'arbre pour savoir dans quelle catégorie la placer.

Le principal problème rencontré est qu'un arbre de décision peut vite conduire 
à du surapprentissage
si l'on tente de décrire parfaitement le jeu de données initial avec une donnée 
unique par feuille. Dans
ce cas, 1l ne sera pas forcément possible de classer une nouvelle donnée. Il 
est donc souvent nécessaire
d'arrêter la construction à un nombre maximal de séparations, on parle 
d'élaguer l'arbre.

Ilustrons ces notions sur le jeu de données aléatoires suivant, la dernière 
colonne représentant le

groupe d'appartenance :
0.96, 0.95, 0.06, 0.08, 0.84, 0.74, 0.67, 0.31, 0.61, 0.61, I
0.16, 0.43, 0.39, 0.72, 0.99, 0.95, 0.54, 0.44, 0.27, 0.04, 0
0.46, 0.32, 0.38, 0.89, 0.53, 0.56, 0.24, 0.02, 0.33, 0.14, 1
1.00, 0.67, 0.18, 0.89, 0.80, 0.73, 0.91, 0.76, 0.79, 0.35, 1
0.96, 0.16, 0.75, 0.72, 0.46, 0.53, 0.49, 0.92, 0.50, 0.83, 0
0.88, 0.90, 0.46, 0.57, 0.92, 0.72, 0.49, 0.22, 0.32, 0.70, 0
0.91, 0.27, 0.91, 0.31, 0.96, 0.71, 0.50, 0.52, 0.65, 0.59, 0
0.21, 0.51, 0.93, 0.62, 0.08, 0.82, 0.73, 0.91, 0.19, 0.74, 0
0.65, 0.27, 0.23, 0.88, 0.11, 0.52, 0.85, 0.24, 0.21, 0.88, 1
0.72, 0.03, 0.36, 0.17, 0.67, 0.08, 0.95, 0.03, 0.73, 0.02, I

(a) Arbre de décision associé au jeu de données précédent (b) Exemple d'arbre 
de décision pour illustrer
la représentation en Python

Figure 5 - Différents arbres de décision

Un arbre est représenté sur la figure 5(a). Cet arbre est composé de noeuds 
représentés par des cercles,
des liens représentés par des flèches avec condition et des feuilles 
représentées par des rectangles
composés de Î ou de 0.

8/12

Un noeud contient l'indice d'une des colonnes du tableau de données (les 
colonnes sont numérotées
à partir de 0). Les liens permettent de parcourir l'arbre de décision. Pour une 
ligne du tableau de
données, on prend la valeur de la colonne d'indice indiqué par le noeud et on 
évalue la condition
du lien. Si la valeur est strictement plus petite que la valeur indiquée sur le 
lien, on descend vers la
gauche, sinon on va vers la droite. Lorsqu'on ne peut aller plus loin en 
descendant, on aboutit à une
feuille représentant le type d'obstacle détecté (0 pour roche, 1 pour métal).

En Python, on choisit de représenter un noeud par une liste de 4 éléments [ind, 
val, gauche,
droite]. Le premier élément est l'indice de la colonne du tableau de données, 
le deuxième élément
est la valeur permettant de faire le test pour descendre à droite ou à gauche. 
Le troisième élément est :
- soit le noeud de la branche de gauche (représentée elle-même par une 
structure de type noeud)
- soit la valeur terminale 0 ou 1 pour définir le groupe.
De même, le quatrième élément est soit le noeud de la branche de droite, soit 
la valeur terminale.

Par exemple, l'arbre de la figure 5(b) sera représenté en Python par la liste 
suivante :
[2, 0.39, [6, 0.19, 1, ©], 1].

Q10. Donner la représentation en Python de l'arbre défini sur la figure 5(a) .

Soit une donnée non classée a=[60.5,0.2,60.7,0.4,0.9,0.25,0.7,0.7,60.9,60.21].

Q11. Déterminer, en justifiant, dans quel groupe cette donnée sera classée en 
utilisant l'arbre de la
figure 5(a). Expliquer le chemin parcouru dans l'arbre.

IIL.2 - Construction d'un arbre

Pour construire l'arbre, la principale question à laquelle 1l faut répondre est 
de savoir comment séparer
les données à chaque 1tération. Il existe différentes méthodes, souvent 
statistiques, qui permettent de
réaliser cette séparation. Nous allons 1ic1 étudier l'algorithme CART (« 
classification and regression
trees »), qui se base sur une grandeur appelée indice de concentration de Gini 
qui sera définie par la
suite. Cet indicateur permettra de choisir la colonne et la valeur pour faire 
la séparation.

La fonction suivante permet de séparer les données en deux groupes en utilisant 
l'indice de concen-
tration de Gin1. Nous allons détailler dans la suite les fonctions intervenant 
dans cette fonction. Pour
rappel, la variable donnees est un tableau constitué de n, lignes et m+ 1 
colonnes, la dernière colonne
contient la classe à laquelle appartient la ligne (qui correspond à une 
expérience).

def separe(donnees, p_var):
#Initialisation des parametres
b_ind ,b_val ,b_gini = inf, inf, inf
b_g, b d = [],f]
m = len(donnees[0])-I
#extractions d'indices aléatoires
ind_var = indices_aleatoires (m,p_var)
for ind in ind_var:
for ligne in donnees:
#Séparation des données en deux groupes
[gauche , droite]=test_ separation (ind ,ligne[ind],donnees)
gini = Gini_groupes ([ gauche , droite |)
if gini < b_gini: b_ind ,b_val ,b_gini = ind ,lignel[ind],gini b_g,b_d = gauche , droite return [b_ind, b_val, b_g, b_d] 9/12 La fonction renvoie l'indice de la colonne et la valeur retenus pour faire le test de séparation ainsi que les deux groupes gauche et droite (la structure identique à la valeur renvoyée par la fonction lire_donnees rappelée avant la question Q8). Q12. Écrire une fonction indices_aleatoires(m,p_var) qui prend en arguments le nombre m correspondant au nombre de colonnes disponibles et p_var un nombre permettant de tirer aléatoirement p,. nombres parmi la liste des numéros de colonnes (p_var < m) et qui renvoie une liste de taille p,,, contenant les numéros de colonnes tirés aléatoirement. Un numéro de colonne ne doit apparaître qu'une seule fois dans cette liste. On utilisera la fonction randrange (p) qui renvoie un entier aléatoirement entre 0 et p-- 1. Par exemple, si on choisit p_var = 4 avec m = 60, on pourrait obtenir la liste d'indices aléatoires suivante [10, 50, 3,24]. Q13. Écrire une fonction [gauche ,droite]=test_separation(ind, val, donnees) qui prend en argument ind un numéro de colonne, val une valeur permettant de séparer les don- nées et donnees le tableau contenant les données. Cette fonction renvoie une liste de deux éléments du même type que donnees : les lignes, dont la valeur de la colonne ind est 1in- férieure strictement à val, sont stockées dans le groupe gauche et les autres dans le groupe droite. Les groupes gauche ou droite peuvent être vides. L'indice de concentration de Gini pour un jeu de données d'un groupe gr (noté Gini,,) est calculé k-1 à l'aide de la formule suivante : Gini,, = > 1 -- P; où k est le nombre de 
classes possibles, 1c1 2
i=0
(0 ou 1), p; est la proportion des éléments du jeu de données appartenant à la 
classe 5. On rappelle que

la valeur de la classe est contenue dans la dernière colonne du tableau de 
données.

Pour obtenir l'indice de concentration de Gin1 total pour les deux groupes 
(gauche et droite), on réalise
une somme des deux indices de concentration Gini,, pondérée d'un coefficient de 
taille relative : taille
du jeu de données du groupe divisé par le nombre de données des deux groupes 
(nombre de données
totales).

Q14. Compléter les instructions notées 1 à 5 de la fonction Gini_groupes donnée 
sur le document
réponse qui prend en argument groupes la liste contenant les deux groupes à 
tester et qui
renvoie l'indice de concentration de Gin1.

Lors de la construction de l'arbre, on peut fixer plusieurs critères permettant 
d'arrêter la construction
en calculant une feuille :
- premier critère : quand le nombre de données à séparer est inférieur à une 
valeur que l'on notera
taille_min,
- deuxième critère : quand le nombre de séparations a atteint une valeur 
maximale notée sep_max.

On donne à la feuille associée au jeu de données restant en fin de séparation 
la valeur du groupe
majoritaire. Si la majorité des données est dans la classe 0 (roche) alors la 
feuille prendra la valeur 0,
sinon elle prendra la valeur 1 (métal).

Q15. Écrire une fonction feuille(data) qui prend en argument un jeu de données 
data et qui
renvoie la valeur de la classe majoritaire. La variable data est du même format 
que la variable
donnees.

La fonction permettant de lancer la construction de l'arbre est la suivante :

def construire _arbre(data_train , sep_ max, taille min , p_var):
arbre = separe(data_train , p_var)
construit(arbre , sep _ max, taille min , p_var, Î)
return arbre

10/12
avec :
- data_train des données dont on connaît déjà la classe ;
- Sep_max : le nombre de séparations maximales pouvant être effectuées avant de 
placer une
feuille ;
- taille _min : le nombre de données minimales sous lequel on impose de mettre 
une feuille
plutôt que de séparer les données en deux ;
- p_var : le nombre de valeurs à tirer aléatoirement pour le calcul de l'indice 
de concentration
de Gini.
La construction de l'arbre est réalisée récursivement avec la fonction 
construit(arbre, sep_max,
taille _ min, p_var, ind_rec) après avoir créé un arbre initial à deux branches 
avec la fonction
separe.
La fonction construit prend en argument entre autres :
- arbre : structure de type noeud constituée de 4 éléments [ind, val, gauche, 
droite];
- Sep_max;
- taille_min;
- p_var;
- ind_rec : l'indice de récursivité donnant le nombre de séparations déjà 
effectuées.
La fonction separe peut renvoyer un groupe gauche ou droite vide ([]), cela 
signifie qu'il n'y à
pas eu de critères permettant de séparer les données en deux groupes. Dans ce 
cas, 1l faut calculer la
feuille terminale associée au groupe non vide et imposer la valeur de cette 
feuille à droite et à gauche.
Les variables gauche et droite peuvent être des nombres 0 ou 1 (feuilles) ou 
des structures de type
noeud (cf. question Q10).
Dans la fonction récursive, la variable arbre de type noeud est modifiée au 
cours des appels succes-
SIfs.

Q16. Compléter les conditions numérotées 1 à 4 de la fonction récursive 
construit donnée sur le
document réponse.

IIL.3 - Test d'une prédiction sur un arbre simple

À partir des fonctions présentées précédemment, il est possible de construire 
un arbre de décision
classique en prenant en compte toutes les colonnes disponibles pour faire les 
séparations. Pour le cas
que l'on traite, on prendra ainsi p_var = 60.

Pour tester les performances de prédiction dans ce cas, on utilise un jeu de 
100 données connues pour
construire l'arbre. On réalise ensuite une prédiction sur un jeu de 50 données 
(non utilisées pour la
construction mais dont on connait la classe) : pour chaque donnée, on parcourt 
l'arbre jusqu'à arriver
sur une feuille qui donnera le groupe prédit. On compare cette prédiction à la 
classe connue. On
compte le nombre de succès pour en déduire un taux de réussite. On recommence 
cette analyse en
faisant une nouvelle construction d'arbre à partir des 100 données (ce qui 
correspond aux prédictions
notées 1, 2 et 3). On étudie également l'influence du nombre de données pour 
construire l'arbre en
effectuant la même démarche pour des jeux de 125 et 150 données.

Arbre construit à partir
de 100 données

Arbre construit à partir
de 125 données

Arbre construit à partir
de 150 données

Test de prédiction 1 | 79 14 % 88 %
Test de prédiction 2 | 76 % 718 % 84 %
Test de prédiction 3 | 74 % 718 % TT %

Temps moyen 0,425 0,645 0,865

Tableau 1 - Pourcentages de réussite obtenus et temps de prédiction

11/12

Le tableau 1 liste une synthèse des pourcentages de réussite obtenus ainsi que 
le temps pour réaliser
une prédiction.

Q17. Au vu de ces quelques résultats d'analyse de la méthode des arbres de 
décision, indiquer de
quels problèmes semblent souffrir cette méthode.

IIL.4 - Algorithme des forêts aléatoires : « random forest »

Pour palier les problèmes observés précédemment, on utilise un algorithme des 
forêts aléatoires.
L'idée de l'algorithme des forêts aléatoires est de construire plusieurs arbres 
de décision (n_arbres)
basés sur une vision partielle du problème en se limitant à quelques variables 
(d'où l'introduction de
la fonction indice_aleatoire dans la partie précédente). En pratique, on 
utilise la racine carrée du
nombre de variables, soit 7 au lieu de 60 dans notre exemple.

Ensuite, on réalise une prédiction sur les différents arbres construits et on 
associe à la donnée à classer
la classe majoritaire issue des différentes prédictions élémentaires.

On suppose que l'on dispose des fonctions : construire_foret qui renvoie une 
liste d'arbres (non
détaillée 1c1) et prediction qui pour un arbre connu et une donnée renvoie la 
valeur de sa classe.

Q18. Compléter les 4 instructions manquantes de la fonction  récursive
prediction(arbre,donnee) donnée sur le document réponse qui prend en argument
un arbre de décision noté arbre de type noeud et une donnée à classer donnee. 
La fonction
isinstance(var,type) renvoie True si var est du type type.

On note :
- data_train, les données d'entraînement de l'algorithme qui vont servir à 
construire les arbres ;
- data_test, les données permettant de tester l'efficacité de l'algorithme en 
comparant le clas-
sement proposé par rapport à la valeur connue.

Q19. Écrire une fonction random_forest(data_train, data_test, sep_max,
taille min, n_arbres, p_var) qui renvoie une liste contenant la classe de chaque
donnée contenue dans la variable data_test.

Conclusion

On réalise des tests de prédiction comme cela a été présenté en sous-partie 
IIL.3.
Le tableau 2 liste une synthèse des pourcentages de réussite obtenus ainsi que 
le temps pour réaliser
une prédiction avec une forêt de 20 arbres.

Arbre construit à partir
de 100 données

Arbre construit à partir
de 125 données

Arbre construit à partir
de 150 données

Test de prédiction 1 | 88 % 84 % 91
Test de prédiction 2 | 91 % 86 % 91
Test de prédiction 3 | 86 % 83 % 88 %

Temps moyen 0,235 0,355 0,55

Tableau 2 - Pourcentages de réussite et temps de prédiction pour une forêt de 
20 arbres

Q20. Conclure sur l'intérêt de cet algorithme des forêts aléatoires.

FIN

12/12

IMPRIMERIE NATIONALE - 20 1166 - D'après documents fournis

| N
Numéro

d'inscription N
C Nom :
| N D Numéro
de table
CONCOURS >
COMMUN Prénom :
Née) le

Session: 2020

Épreuve de: Informatique

Emplacement
QR Code

+ Remplir soigneusement l'en-tête de chaque feuille avant de commencer à 
composer
+ Rédiger avec un stylo non effaçable bleu ou noir
Consignes ° Ne rien écrire dans les marges (gauche et droite)
+. Numéroter chaque page (cadre en bas à droite)
* Placer les feuilles A3 ouvertes, dans le même sens et dans l'ordre

PSISIN

DOCUMENT RÉPONSE

Q1 - Instruction pour la création de la variable temps

Q2 - Fonction chirp(temps,f0,Deltafe,T,E0@)

Q3 - Instructions pour stocker f, t, S. Taille de f, t, S en fonction de net N

1/8

Q4 - Intérêt du

- Fonction w(t,f,eta)

- Fonction envelo

e(eta,sS,

,dt,df)

218

Q7 - Fonction normalisation(P)

Q8 - Valeur de la variable donnees (deux premières lignes lues seulement)

Q9 - Taille mémoire minimale pour stocker les données

Q10 - Représention en Python de l'arbre de la figure 5(a)

Q11 - Classification de la donnée. Justification

318

12 - Fonction indices_aleatoires(m,p_var)

13 - Fonction [gauche, droite

test_separation(ind,val,donnees)

418

| N
Numéro

d'inscription N
C Nom :

| N D Numéro

de table
CONCOURS >
COMMUN Prénom :

Née) le

Filière: PSI Session: 2020

Épreuve de: Informatique

Emplacement
QR Code

+ Remplir soigneusement l'en-tête de chaque feuille avant de commencer à 
composer
+ Rédiger avec un stylo non effaçable bleu ou noir
Consignes ° Ne rien écrire dans les marges (gauche et droite)
+. Numéroter chaque page (cadre en bas à droite)
* Placer les feuilles A3 ouvertes, dans le même sens et dans l'ordre

PSISIN
Q14 - Compléter les instructions notées 1 à 5

def Gini_groupes (groupes ):
#nombre de données total

n_ donnees -- #Hinstructionl

gini = 0.0 #somme pondérée des indices Gini de chaque groupe
for donnees in groupes:

taille = len(donnees) #taille d'un groupe

if taille != 0:

gini_gr = 0.0
for val in [0,1]:
p=0
for ligne in donnees
if ligne[-1] == val:
#instruction2

#H#instruction3

gini_gr += #instructiond4

#ajout de gini_gr avec Île poids relatif

gini += #instructions

return gini

(C) | 518

NE RIEN ÉCRIRE DANS CE CADRE

Q15 - Fonction feuille(data)

Q16 - Compléter les conditions numérotées 1 à 4 de la fonction récursive 
construit

def construit(arbre , sep _ max, taille min , p_var, ind_rec ):

gauche, droite = arbre[2], arbre[3]

#conditionli

#condition2

#condition3

ind_rec+1l)

#condition4

if
valeur = feuille (gauche + droite)
arbre[2] = valeur
arbre[3] = valeur
return
if
arbre[2], arbref[3] = feuille(gauche), feuille (droite)
if
arbre[2] = feuille (gauche)
else :
arbre[2] = separe(gauche, p_var)
construit(arbre[2], sep_ max, taille min , p_var,
if
arbre[3] = feuille(droite)
else :
arbre[3|] = separe(droite , p_var)

construit(arbre[3], sep_ max, taille min , p_var,

ind_rec+1l)

6/8

Q17 - Problèmes de la méthode

Q18 - Compléter les 4 instructions manquantes

def prediction(arbre , donnee ):
[ind , val , gauche , droite ]=arbre
if donneel[ind] < val: if isinstance(gauche, list ): else : else : if isinstance(droite , list ): else : #H#instructionli #Hinstruction2 #H#instruction3 #H#instructiond4 Q19 - Fonction random_forest(data_train, data_test, sep_ max, taille _ min, n_arbres, p_var) (espace libre page suivante) 118 Q20 - Conclusion sur l'intérêt de l'algorithme des forêts aléatoires ANNEXE Rappels des syntaxes en Python Remarque : sous Python, l'import du module numpy permet de réaliser des opérations pratiques sur les ta- bleaux : from numpy import *. Les indices de ces tableaux commencent à 0. Python L=[1,2,3] (liste) v=array([1,2,3]) (vecteur) accéder à un élément V[0] renvoie 1 (L[O] également) ayouter un élément L.append(5) uniquement sur les listes séquence équirépartie quelconque de 0 à I0.I (exclus) par pas de 0.1 tableau à une dimension arange(®6,160.1,6.1) définir une chaîne de caractères mot="Python' taille d'une chaîne len(mot) extraire des caractères mot[2:7] éliminer le \n en fin d'une ligne ligne.str1ip() découper une chaîne de caractères selon un ca- ractère passé en argument. On obtient une liste | mot.split(",") qui contient les caractères séparés with open("'nom_fichier",'r'}) as file: ouverture d'un fichier en lecture | | | instructions avec file 8/8

Extrait du corrigé obtenu par reconnaissance optique des caractères



CCINP Informatique PSI 2020 -- Corrigé
Ce corrigé est proposé par William Aufort (professeur en CPGE) ; il a été relu
par Benjamin Monmege (enseignant-chercheur à l'université) et Jean-Julien Fleck
(professeur en CPGE).

Ce sujet met en oeuvre des méthodes de traitement du signal et d'intelligence
artificielle pour résoudre un problème de détection d'obstacles par un sonar de 
sousmarin. Un sonar émet des ondes qui sont réfléchies par les obstacles ; il 
détecte cette
réflexion et l'interprète pour déterminer la dangerosité de l'obstacle.
· La première partie présente le problème et ne comporte aucune question.
· La deuxième est consacrée au traitement des signaux émis et reçus par le 
sonar.
Elle détaille l'algorithme de transformée de Fourier discrète utilisé pour 
isoler
les composantes fréquentielles principales du signal réfléchi par l'obstacle. La
plupart des questions demandent de la programmation nécessitant la manipulation 
de listes et de tableaux NumPy.
· Enfin, la troisième partie propose deux algorithmes d'apprentissage pour 
classer
des données en deux groupes correspondant à deux types d'obstacles. La première 
méthode utilise un arbre de décision construit à partir d'une base de
données d'entraînement où le type d'obstacle est connu. La notion d'arbre n'est
pas au programme de l'informatique commune, mais elle est relativement bien
expliquée dans l'énoncé. La seconde méthode, dite des forêts aléatoires, 
utilise plusieurs arbres de décision de taille moins importante afin 
d'améliorer les
performances de la classification.
Comme en 2019, le sujet aborde un algorithme d'intelligence artificielle 
appliqué
à un problème original. Il comporte beaucoup de questions de programmation et de
compréhension de code ou de documentation. Quelques questions font appel à la 
récursivité. Les autres grandes parties du programme (ingénierie numérique, 
requêtes
SQL, tris) ne sont pas abordées. L'énoncé contient beaucoup d'informations, et 
la longueur de certaines questions (notamment la question 3) peut s'avérer 
déstabilisante.
Néanmoins, ce sujet est d'une difficulté tout à fait raisonnable.

Indications
Partie II
1 Utiliser la fonction arange ou la fonction array, toutes deux rappelées en 
annexe.
3 Identifier pour chaque argument optionnel de la fonction scipy.signal.stft si
la valeur par défaut correspond aux exigences de l'énoncé.
4 Observer l'intervalle de temps correspondant à la portion représentée sur les 
spectrogrammes et comparer avec la représentation du signal de la figure 3.
7 La fonction ci-dessous normalise les données contenues dans le vecteur P :
x 7-

x - min (P)
max (P) - min (P)

8 Les méthodes split et strip sont expliquées en annexe. La fonction float 
permet de convertir un objet Python en flottant.
9 Un flottant en double précision est codé sur 64 bits.
Partie III
12 Générer un à un des nombres aléatoires ; ne les ajouter à la liste à 
renvoyer que
s'ils y sont absents.
14 L'entier n_donnees est égal à la somme des longueurs des groupes. Utiliser la
variable p comme un compteur.
15 Compter le nombre de données correspondant à chaque valeur.
16 Identifier les différents cas de figure où l'on arrête de construire 
récursivement
l'arbre, puis choisir à l'aide des instructions de la fonction construit où 
placer
le test correspondant à chacun.
18 Identifier les instructions à l'arrivée sur une feuille dans le parcours de 
l'arbre.
Pour les autres, poursuivre récursivement le parcours.
19 Commencer par construire une liste contenant la forêt aléatoire, puis 
identifier
pour chaque donnée de data_test la classe majoritaire issue des différentes 
prédictions, à l'aide d'un code ressemblant à celui de la question 15.

II. Analyse des données
1 La fonction arange de NumPy rappelée dans l'annexe permet de construire des
séquences de valeurs uniformément réparties. Cette fonction prend en arguments
la première valeur, la dernière valeur (exclue), ainsi que le pas entre deux 
valeurs
consécutives. Dans notre situation, ces valeurs sont respectivement 0, Tf et Tf 
/N.
On obtient donc l'instruction suivante :
temps = arange(0, Tf, Tf/N)
Comme le pas Tf/N est un flottant, il est possible que des erreurs d'arrondi 
perturbent le résultat de la fonction arange, en particulier à proximité
de la valeur exclue. Par exemple, l'appel arange(0.2, 0.8, 0.1) renvoie
un tableau contenant la valeur 0.8 (plutôt une valeur flottante légèrement
supérieure, mais affichée 0.8) qui devrait être exclue.
Une autre possibilité serait de construire une liste Python contenant les
valeurs demandées, par exemple en compréhension, puis de convertir cette
liste en tableau NumPy à l'aide de la fonction array rappelée dans l'annexe.
Attention à ne pas oublier cette étape car l'énoncé attendait bien un tableau
NumPy. En suivant cette idée, on pourrait obtenir l'instruction
temps = array([i*Tf/N for i in range(N)])
Cette méthode assure que le tableau renvoyé aura la bonne longueur.
2 Pour plus de lisibilité, on définit à l'intérieur de la fonction chirp une 
fonction e
calculant e(t). Cette fonction prend comme unique argument la valeur de t, les 
autres
paramètres intervenant dans l'expression de e(t) étant tous des arguments de la
fonction chirp. Une fois cette fonction définie, on construit le vecteur 
correspondant
au signal émis à l'aide d'une liste en compréhension et de la fonction array.
def chirp(temps, f0, Deltafe, T, E0):
def e(t):
if t <= T: fe = f0 + t*Deltafe/T return E0 * sin(2*pi*fe*t) else: return 0 return array([e(t) for t in temps]) Certaines opérations peuvent être appliquées directement sur les tableaux NumPy sans passer par des boucles for ; on parle d'opérations vectorialisées. Ces opérations sont en général plus rapides que leurs homologues utilisant des boucles Python. Par exemple, on peut dans certains cas appliquer une fonction f directement sur un tableau NumPy T avec la syntaxe f(T). Ce n'est hélas pas possible avec l'implémentation proposée à cause de l'instruction conditionnelle présente dans la définition de e(t). On pourrait contourner ce problème en multipliant le résultat à renvoyer par le booléen (t <= T), interprété comme valant 0 (échec du test) ou 1 (succès) dans le produit. 3 D'après la description fournie dans l'énoncé, la fonction scipy.signal.stft prend pour argument obligatoire le signal temporel à traiter contenu dans s, ainsi que quatre arguments optionnels : · la fréquence d'échantillonage fs utilisée dans le calcul des transformées de Fourier locales. On l'obtient à partir de la période d'échantillonage te = Tf /N donnée dans l'énoncé par la formule fs = 1/te ; · le nom window de la fenêtre à utiliser, ici une fenêtre de type Hamming ; · la longueur nperseg de chaque fenêtre, fixée dans l'énoncé à n valeurs (n//2 avant la valeur  choisie et n//2 après) ; · noverlap, le nombre de valeurs qui chevauchent deux fenêtres consécutives. Il est fixé par défaut à n//2, correspondant à un chevauchement de 50 %, en accord avec les contraintes de l'énoncé. En conclusion, les seuls paramètres à expliciter dans l'appel de la fonction stft sont s, fs, window et nperseg. Les trois derniers étant des arguments optionnels, on les fournit ici avec leurs noms respectifs. On obtient finalement l'instruction suivante : f, t, S = scipy.signal.stft(s, fs=N/Tf, window='hamming', nperseg=n) Si les arguments optionnels sont fournis avec leurs noms, l'ordre dans lequel ils apparaissent dans la fonction n'a aucune importance. Dans le cas contraire, l'ordre d'apparition est décisif. Cela donnerait : f, t, S = scipy.signal.stft(s, N/Tf, 'hamming', n) En reprenant la notation nf = N//(n//2) de l'énoncé, la description de l'algorithme de transformée de Fourier locale nous indique que Les tableaux f et t sont de taille nf , et S est un tableau à deux dimensions de taille nf ×nf . L'énoncé comporte une erreur. En testant la fonction stft, on peut remarquer que la taille du tableau f vaut en réalité n//2 + 1. Cette différence est due au fait que la fonction calcule par défaut une transformée de Fourier « one-sided », c'est-à-dire dans laquelle seules les fréquences positives sont conservées (les fréquences négatives étant surtout utiles pour des signaux à valeurs complexes). Pour obtenir un tableau f de taille n, il faudrait forcer la fonction à calculer une transformée de Fourier « two-sided » en rajoutant l'argument optionnel return_onesided=False. De plus, pour des contraintes techniques (notamment la gestion des arrondis) les tailles des tableaux t et S sont proches de celles annoncées par l'énoncé, mais pas égales. 4 Le spectrogramme d'un signal est une représentation en niveaux de gris de la matrice S renvoyée par la fonction stft. Les pixels blancs correspondent à 0 et les noirs aux valeurs des spectres de Fourier calculés de module maximal. Tout d'abord, remarquons que les deux spectrogrammes présentés, associés respectivement à un signal non bruité et au même signal bruité, sont très similaires. Le spectrogramme semble donc peu sensible au bruit. Plus précisément, les seules fréquences associées à un module non négligeable sont toutes dans l'intervalle de temps [ 0,19 ; 0,32 ], qui correspond au « pic » de la figure 3 représentant le signal d'origine. Autrement dit, seules les composantes fréquentielles importantes du signal