Mines Informatique Commune MP PC PSI 2018Sujet, corrigé et rapport du jury

Mesure de houle

Pas encore noté

Faisable en Sup

Représentation des données en mémoire
Lecture de fichiers texte en Python
Boucles, listes et utilisation de range
Intégration numérique : méthode des trapèzes
Algorithmes de tri : tri rapide, tri par insertion
Complexité des algorithmes
Bases de données : requêtes SQL, jointures, agrégation
Récursivité : diviser pour régner

Explorer les annales

BanqueMines Année2018 FilièreMP/PC/PSI MatièreInformatique

Annales Mines MP/PC/PSI Informatique Mines MP/PC/PSI 2018 MP/PC/PSI Informatique Informatique 2018

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Corrigé 2

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Mesures de houle : traitement en Python des relevés d'une bouée, tris, SQL et transformée de Fourier rapide

Le sujet exploite les mesures de niveau de la mer d'une bouée. Il aborde la taille des données et leur lecture dans un fichier texte, l'analyse « vague par vague » (moyenne, méthode des trapèzes, passages par le niveau moyen, hauteurs et périodes), le contrôle des données par tri rapide et tri par insertion, des requêtes SQL, puis l'algorithme récursif de transformée de Fourier rapide. L'épreuve dure 1 h 30.

1Partie I : stockage interne des donnéesTaille en octets d'un enregistrement, gain relatif de mémoire et lecture d'un fichier texte en liste de flottants.
2Partie II : analyse « vague par vague »Moyenne, intégrale par la méthode des trapèzes, recherche des passages par le niveau moyen en descente et découpage du signal en vagues.
3Partie III : contrôle des donnéesHauteur maximale, tri rapide combiné au tri par insertion, calcul de skewness et de kurtosis et complexité.
4Partie IV : base de données relationnelleRequêtes SQL sur les tables Bouee, Campagne et Tempete.
5Partie V : analyse « spectrale »Complexité et écriture récursive de la transformée de Fourier rapide de Cooley-Tukey.

Ce qu'a observé le jury

6 erreurs relevées

Ordres de grandeur et unités de mémoire · Lecture d'un fichier texte ignorée · Bornes de range et dépassement d'indice

Les copies sont en général bien présentées, mais le jury relève une maîtrise insuffisante de range, de la lecture de fichiers texte et de la syntaxe élémentaire. Il déplore les appels répétés à des fonctions coûteuses dans les boucles et les estimations de complexité fantaisistes. Les questions de fin de sujet (Q20, Q21) ont été peu réussies.

Les erreurs les plus sanctionnées

1
Ordres de grandeur et unités de mémoireQ1, Q2, Q3
Le calcul élémentaire du nombre d'octets est souvent faux, le préfixe giga est confondu avec méga et le gain relatif de 1/8 n'est pas vu.
« beaucoup de candidats ne maîtrisent pas le sens du préfixe giga, le confondant avec méga »
2
Lecture d'un fichier texte ignoréeQ4
Cette notion explicite du programme est rarement traitée et très rarement réussie, alors que la syntaxe nécessaire est légère.
3
Bornes de range et dépassement d'indiceQ7, Q8, Q9
Beaucoup parcourent range(len(L)) puis appellent L[i+1], ou se trompent de bornes en parcours décroissant. En Q8, un return -1 mal indenté arrête la fonction dès le premier test.
« avant de faire appel à L[i+1] dans la boucle sans paraître conscients du problème »
4
Division et moyenne mal calculéesQ6
Diviser par len(L)-1 ou utiliser la division entière // pour une moyenne est faux.
5
Tris du programme mal maîtrisésQ14, Q16
Le pivot du tri rapide doit porter sur l'élément de la sous-liste utilisé pour le tri ; le rôle de tmp dans le tri par insertion est mal compris.
6
SQL et complexités fantaisistesQ19, Q20
Écriture attribut.table au lieu de table.attribut, condition de jointure réduite à un nom d'attribut, jointures hors programme ; complexités en O(n!) ou O(ln n) pour la transformée de Fourier rapide.
« la condition de jointure après ON est bien une condition, et non seulement le nom d'un attribut »

Ce qui a été bien réussi

La question 5 (lecture des hauteurs et périodes sur la figure) est bien traitée en général.
La fonction moyenne (Q6) est bien traitée.
La recherche de maximum (Q13) est souvent bien traitée.
La question 17 sur l'appel inutile dans la boucle est en général bien réussie.

Conseils du jury

Soigner l'indentation, capitale pour juger un programme, en commençant bien à gauche de la copie.
Se limiter aux notions du programme plutôt qu'à une syntaxe Python hasardeuse.
Vérifier les bornes exactes de chaque range.
Sortir des boucles les appels à des fonctions coûteuses qu'un seul appel suffit à remplacer.
S'entraîner à lire un fichier texte et à écrire des jointures avec table1 JOIN table2 ON condition.
Réfléchir avant d'écrire un algorithme non trivial et réutiliser les fonctions déjà écrites.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International), Concours Mines-Télécom, Concours Commun TPE/EIVP.

CONCOURS 2018

ÉPREUVE D'INFORMATIQUE COMMUNE

Durée de l'épreuve : 1 heure 30 minutes

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve est commune aux candidats des filières MP, PC et PSI
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie :

INFORMATIQUE COMMUNE

L'énoncé de cette épreuve comporte 10 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

Mesures de houle

Le sujet comporte des questions de programmation. Le langage à utiliser est Python.
On s'intéresse à des mesures de niveau de la surface libre de la mer effectuées par une bouée (représentée sur la Figure 1)

^1

. Cette bouée contient un ensemble de capteurs incluant un accéléromètre vertical qui fournit, après un traitement approprié, des mesures à étudier

^2

Figure 1 : bouée de mesure de houle

Les mesures réalisées à bord de la bouée sont envoyées par liaison radio à une station à terre où elles sont enregistrées, contrôlées et diffusées pour servir à des études scientifiques. Pour plus de sûreté, les mesures sont aussi enregistrées sur une carte mémoire interne à la bouée.

Partie I. Stockage interne des données

Une campagne de mesures a été effectuée. Les caractéristiques de cette campagne sont les suivantes :

durée de la campagne : 15 jours;
durée d'enregistrement : 20 min toutes les demi-heures;
fréquence d'échantillonnage : 2 Hz .

Les relevés de la campagne de mesure sont écrits dans un fichier texte dont le contenu est défini comme suit.

Les informations relatives à la campagne sont rassemblées sur la première ligne du fichier, séparées par des points-virgules (";"). On y indique différentes informations importantes comme le numéro de la campagne, le nom du site, le type du capteur, la latitude et la longitude de la bouée, la date et l'heure de la séquence.

Cette étude utilise des résultats extraits de la base de données du Centre d'Archivage National des Données de Houle In Situ. Les acquisitions ont été effectuées par le Centre d'Etudes Techniques Maritimes Et Fluviales.
L'ensemble des paramètres des états de mer présent dans la base CANDHIS est calculé par les logiciels :

Houle5 (CETMEF) : analyse vague par vague (temporelle);
PADINES (EDF/LNHE) : analyse spectrale et directionnelle (fréquentielle).

Les lignes suivantes contiennent les mesures du déplacement vertical (m). Chaque ligne comporte 8 caractères dont le caractère de fin de ligne. Par exemple, on trouvera dans le fichier texte les 3 lignes suivantes :
+0.4256
+0.3174
-0.0825

Q1 - On suppose que chaque caractère est codé sur 8 bits. En ne tenant pas compte de la première ligne, déterminer le nombre d'octets correspondant à 20 minutes d'enregistrement à la fréquence d'échantillonnage de 2 Hz .

◻

Q2 - En déduire le nombre approximatif (un ordre de grandeur suffira) d'octets contenus dans le fichier correspondant à la campagne de mesures définie précédemment. Une carte mémoire de 1 Go est-elle suffisante?

Q3 - Si, dans un souci de réduction de la taille du fichier, on souhaitait ôter un chiffre significatif dans les mesures, quel gain relatif d'espace mémoire obtiendrait-on?

Q4 - Les données se trouvent dans le répertoire de travail sous forme d'un fichier donnees.txt. Proposer une suite d'instructions permettant de créer à partir de ce fichier une liste de flottants liste_niveaux contenant les valeurs du niveau de la mer. On prendra garde à ne pas insérer dans la liste la première ligne du fichier.

Deux analyses sont effectuées sur les mesures : l'une est appelée "vague par vague", l'autre est appelée "spectrale".

Partie II. Analyse "vague par vague"

On considère ici que la mesure de houle est représentée par un signal

η(t) \in ℝ, t \in [0, T]

, avec

η

une fonction

C^1

On appelle niveau moyen

m

la moyenne de

η(t)

sur

[0, T]

.
On définit

Z_1, Z_2, \dots, Z_n

l'ensemble (supposé fini) des Passages par le Niveau moyen en Descente (PND) (voir Figure 2). A chaque PND, le signal traverse la valeur

m

en descente.

On suppose

η(0) > m

, et

(dη)/(dt)(0) > 0

.
On en déduit que

η(t) - m \geq 0

sur

[0, Z_1]

.
Les hauteurs de vagues

H_i

sont définies par les différences :

{H_1 = maxη(t) − min_(t ∈ [0, Z_1])η(t); H_i = maxη(t) − min_(t ∈ [Z_2])η(t); t ∈ [Z_(i − 1), Z_i] pour 2 ≤ i < n

On définit les périodes de vagues par

T_i = Z_(i + 1) - Z_i

◻

Q5 - Pour le signal représenté sur la Figure 2, que valent approximativement

H_1, H_2

H_3

? Que valent approximativement

T_1

T_2

On adopte désormais une représentation en temps discret du signal. On appelle horodate, un ensemble (fini) des mesures réalisées sur une période de 20 minutes à une fréquence d'échantillonnage de 2 Hz . Les informations de niveau de surface libre d'un horodate sont stockées dans une

Figure 2 : Passages par le Niveau moyen en Descente (PND). Ici la moyenne

m

vaut 2

liste de flottants liste_niveaux. On suppose qu'aucun des éléments de cette liste n'est égal à la moyenne.

◻

Q6 - Proposer une fonction moyenne prenant en argument une liste non vide liste_niveaux, et retournant sa valeur moyenne.

Q7 - Proposer une fonction integrale_precise prenant en argument une liste non vide liste_niveaux, et retournant la valeur approchée de l'intégrale de

η

sur une période de 20 minutes. On demande d'utiliser la méthode des trapèzes. En déduire une fonction moyenne_precise prenant en argument une liste non vide liste_niveaux et retournant une estimation de la moyenne de

η

sur une période de 20 minutes.

◻

Q8 - Proposer une fonction ind_premier_pzd(liste_niveaux) retournant, s'il existe, l'indice du premier élément de la liste tel que cet élément soit supérieur à la moyenne et l'élément suivant soit inférieur à la moyenne. Cette fonction devra retourner -1 si aucun élément vérifiant cette condition n'existe.

Q9 - Proposer une fonction retournant l'indice

i

du dernier élément de la liste tel que cet élément soit supérieur à la moyenne et l'élément suivant soit inférieur à la moyenne. Cette fonction devra retourner -2 si aucun élément vérifiant cette condition n'existe. On cherchera à proposer une fonction de complexité

O(1)

dans le meilleur des cas.

On souhaite stocker dans une liste successeurs, les indices des points succédant (strictement) aux PND (voir Figure 3).

◻

Q10 - On propose la fonction construction_successeurs en annexe (algorithme 1). Elle retourne la liste successeurs. Compléter (sur la copie) les lignes 6 et 7.

◻

Q11 - Proposer une fonction decompose_vagues(liste_niveaux) qui permet de décomposer une liste de niveaux en liste de vagues. On omettra les données précédant le premier PND et celles

Figure 3 : propriétés d'une vague

succédant au dernier PND. Ainsi decompose_vagues (

[1, - 1, - 2, 2, - 2, - 1, 6, 4, - 2, - 5]

) (noter que cette liste est de moyenne nulle) retournera

[[ - 1, - 2, 2], [ - 2, - 1, 6, 4]]

On désire maintenant caractériser les vagues.
Ainsi, on cherche à concevoir une fonction proprietes (liste_niveaux) retournant une liste de listes à deux éléments [Hi, Ti] permettant de caractériser chacune des vagues i par ses attributs :

Hi, sa hauteur en mètres (m) (voir Figure 3),
Ti, sa période en secondes ( $s$ ).
$◻$ Q12 - Proposer une fonction proprietes(liste_niveaux) réalisant cet objectif. On pourra utiliser les fonctions de Python $max(L)$ et $min(L)$ qui retournent le maximum et le minimum d'une liste L , respectivement.

Partie III. Contrôle des données

Plusieurs indicateurs sont couramment considérés pour définir l'état de la mer. Parmi eux, on note :

$H_(max)$ : la hauteur de la plus grande vague observée sur l'intervalle d'enregistrement $[0, T]$ ;
$H_(1/3)$ : la valeur moyenne des hauteurs du tiers supérieur des plus grandes vagues observées sur $[0, T]$ ;
$T_(H1/3)$ : la valeur moyenne des périodes du tiers supérieur des plus grandes vagues observées sur $[0, T]$ .
$◻$ Q13 - Proposer une fonction prenant en argument la liste liste_niveaux de la question 12 et retournant $H_(max)$ .

Afin de déterminer

H_(1/3)

T_(H1/3)

, il est nécessaire de trier la liste des propriétés des vagues. La méthode utilisée ici est un tri rapide (quick sort). On donne en annexe un algorithme possible pour la fonction triRapide (algorithme 2). Trois arguments sont nécessaires : une liste liste, et deux indices g et d .

Q14 - Préciser les valeurs que doivent prendre les arguments g et d au premier appel de la fonction triRapide. Compléter (sur la copie) la ligne 2.

Lorsque le tri rapide est utilisé et que le nombre de données à traiter devient petit dans les sous-listes (de l'ordre de 15), il peut être avantageux d'utiliser un "tri par insertion". On appelle triInsertion la fonction qui permet d'effectuer un tri par insertion. Elle admet en argument une liste liste, et deux indices

g

d

. Ces deux indices permettent de caractériser la sous-partie de la liste à trier (indices de début et de fin inclus).

Q15 - Donner les modifications à apporter à la fonction triRapide pour que, lorsque le nombre de données dans une sous-liste devient inférieur ou égal à 15 , la fonction triInsertion soit appelée pour terminer le tri.

Le code incomplet de la fonction triInsertion est donné en annexe : algorithme 3.

Q16 - La fonction triInsertion admet trois arguments : une liste de données liste, et deux indices g et d. Elle trie dans l'ordre croissant la partie de la liste comprise entre les indices g et d inclus. Compléter cette fonction (avec sur la copie le nombre de lignes de votre choix).

La distribution des hauteurs de vague (voir Figure 4) lors de l'analyse vague par vague est réputée être gaussienne. On peut contrôler ceci par des tests de skewness (variable désignée par

S

) et de kurtosis (variable désignée par

K

) définis ci-après. Ces deux tests permettent de quantifier respectivement l'asymétrie et l'aplatissement de la distribution.

Figure 4 : histogramme des hauteurs de vague

On appelle

H¯

σ^2

les estimateurs non biaisés de l'espérance et de la variance,

n

le nombre d'éléments

H_1, H_2, \dots, H_n

On définit alors

S = n/((n - 1)(n - 2)) \times (1/(σ^3)) \times \sum_(i = 1)^n(H_i - H¯)^3; K = n/((n - 1)(n - 2)(n - 3)) \times (1/(σ^4)) \times \sum_(i = 1)^n(H_i - H¯)^4 - (3(n - 1)^2)/((n - 2)(n - 3))

Le test suivant est appliqué :

si la valeur absolue de $S$ est supérieure à 0,3 alors l'horodate est déclaré non valide;
si la valeur de $K$ est supérieure à 5 alors l'horodate est déclaré non valide.

On utilise la fonction moyenne pour estimer la valeur de

H¯

, et on suppose disposer de la fonction ecartType qui permet de retourner la valeur de l'écart type non biaisé

σ

◻

Q17 - Un codage de la fonction skewness pour une liste ayant au moins 3 éléments est donné en annexe (algorithme 4). Le temps d'exécution est anormalement long. Proposer une modification simple de la fonction pour diminuer le temps d'exécution (sans remettre en cause le codage des fonctions ecartType et moyenne).
Q18 - Doit-on s'attendre à une différence de type de la complexité entre une fonction évaluant

S

et une fonction évaluant

K

Partie IV. Base de données relationnelle

On dispose d'une base de données relationnelle Vagues.
La première table est Bouee. On se limite aux attributs suivants : le numéro d'identification idBouee, le nom du site nomSite, le nom de la mer ou de l'océan localisation, le type du capteur typeCapteur et la fréquence d'échantillonnage frequence.

	idBouee	nomSite	localisation	typeCapteur	frequence
Bouee	831	Porquerolles	Mediterranee	Datawell non directionnelle	2.00
	291	Les pierres noires	Mer d'iroise	Datawell directionnelle	1.28
	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

La seconde table est Campagne.
On se limite aux attributs suivants : le numéro d'identification idCampagne, le numéro d'identification de la bouée idBouee, la date de début debutCampagne et la date de fin finCampagne.

	idCampagne	idBouee	debutCampagne	finCampagne
Campagne	08301	831	$01/01/201000 h00$	$15/01/201000 h00$
	02911	291	$15/10/200518 h30$	$18/10/200508 h00$
	$\dots$	$\dots$	$\dots$	$\dots$

La troisième table est Tempete. Les informations fournies relatives à un événement "tempête" sont les suivantes :

date de début et fin de tempête,
évolution des paramètres $H_(1/3)$ et $H_(max)$ en fonction du temps,
le détail de certains paramètres non définis ici, obtenus au pic de tempête.

On se limite aux attributs suivants : le numéro d'identification de la tempête idTempete, le numéro d'identification de la bouée idBouee, la date de début debutTempete, la date de fin finTempete, la valeur maximale de hauteur de vague Hmax.

	idTempete	idBouee	debutTempete	finTempete	Hmax
Tempete	083010	831	$07/01/201020 h00$	$09/01/201015 h30$	5.3
	029012	291	$16/10/200508 h30$	$18/10/200509 h00$	8.5
	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

Le schéma de la base de données est donc : Vagues

= {

Bouee, Campagne, Tempete

}

◻

Q19 - Formuler les requêtes SQL permettant de répondre aux questions suivantes :

"Quels sont le numéro d'identification et le nom de site des bouées localisées en Méditerranée?"
"Quel est le numéro d'identification des bouées où il n'y a pas eu de tempêtes?"
"Pour chaque site, quelle est la hauteur maximale enregistrée lors d'une tempête?"

Partie V. Analyse "spectrale"

L'analyse spectrale (fréquentielle) du niveau, permet elle aussi de caractériser l'état de la mer, qui peut, en première approximation, être modélisé par une superposition linéaire d'ondes sinusoïdales indépendantes.

Figure 5 : analyses temporelle et spectrale

Des coefficients estimateurs de l'état de la mer issus de l'analyse spectrale ont donc été définis. Parmi eux, on note par exemple

H_(m0)

la hauteur significative spectrale des vagues ou

T_P

la période de pic barycentrique.

Pour leur calcul, il est nécessaire d'introduire la Transformation de Fourier Discrète (TFD).
Sa définition pour un signal numérique

x

N

échantillons, est la suivante :

X_k = \sum_(i = 0)^(N - 1)x_i \times e^(- 2πjki/N), 0 \leq k < N et j^2 = - 1

Il existe plusieurs méthodes dites de "transformée de Fourier rapide". On étudie dans la suite l'algorithme de Cooley - Tukey adapté de celui de Gauss. On propose ici une réécriture de (1) appelée entrelacement temporel (DIT decimation-in-time).

Dans toute la suite, on suppose que

N

est une puissance de 2.
On note

w = e^(- (2πj)/N)

(qui est une racine

N

-ième de l'unité).
On pose

P_k, = \sum_(i = 0)^(N/2 - 1)x_(2i) \times e^(- (2πj)/(N/2)ik); I_k, = \sum_(i = 0)^(N/2 - 1)x_(2i + 1) \times e^(- (2πj)/(N/2)ik)

P_k

: TFD des indices pairs,

I_k

: TFD des indices impairs

On montre alors que pour

0 \leq k < N/2, | X_k = P_k + w^k I_k; X_(k + N/2) = P_k - w^k I_k

L'algorithme est de type "diviser pour régner" : le calcul d'une TFD pour

N

éléments se fait à l'aide de deux TFD de

N/2

éléments.

◻

Q20 - Quelle est la complexité en temps de cet algorithme en fonction de

N

? Justifier en une ou deux lignes.

◻

Q21 - Écrire une fonction récursive prenant en argument la liste de données x et retournant la liste X obtenue par transformée de Fourier discrète rapide. La longueur de x est une puissance de 2.

Annexe

Algorithme 1

def construction__successeurs(liste__niveaux):
    n=len(liste__niveaux)
    successeurs=[]
    m=moyenne(liste__niveaux)
    for i in range(n-1):
            if # A completer
                # A completer
    return successeurs

Algorithme 2

def triRapide(liste,g,d):
    pivot= # A completer
    i=g
    j=d
    while True:
        while i <=d and liste [i][0]<pivot:
            i=i+1
        while j>=g and liste[j][0]>pivot:
            j=j -1
        if i>j:
            break
        if i<j:
            liste[i],liste[j]=liste[j],liste[i]
        i=i+1
        j=j -1
    if g<j:
        triRapide(liste,g,j)
    if i<d:
        triRapide(liste,i,d)

Algorithme 3

def triInsertion (liste,g,d):
    for i in range(g+1,d+1):
        j=i-1
        tmp = liste[i]
        while # A completer
liste[j+1]=tmp

Algorithme 4

def skewness(liste_hauteurs):
    n=len(liste__hauteurs)
    et 3=(ecartType(liste__hauteurs))**3
    S=0
    for i in range(n):
        S+=(liste_hauteurs[i]_moyenne(liste_hauteurs))**3
    S=n/(n-1)/(n-2)*S/et3
    return S

Fin de l'épreuve.

Questions fréquentes

4 questions

Sur quoi porte le sujet d'informatique commune Mines 2018 MP PC PSI ?

Sur l'analyse de mesures de houle d'une bouée : lecture d'un fichier, analyse vague par vague, tri rapide et tri par insertion, requêtes SQL et transformée de Fourier rapide.

Quelles erreurs le jury a-t-il relevées en informatique Mines-Ponts 2018 ?

Des bornes de range fausses et des accès L[i+1] hors de la liste, la confusion entre giga et méga, la lecture de fichier texte non maîtrisée, des erreurs de jointure SQL et des complexités fantaisistes.

Le sujet d'informatique Mines 2018 contenait-il une erreur ?

Oui, en Q9 : le calcul de la moyenne étant forcément linéaire, il fallait comprendre que seule la recherche du dernier passage par le niveau moyen devait être en O(1) dans le meilleur des cas.

Quelle syntaxe SQL de jointure utiliser au concours Mines informatique commune 2018 ?

Le jury rappelle que la seule syntaxe exigible est table1 JOIN table2 ON condition, et déconseille NATURAL JOIN ou FULL JOIN mal maîtrisés.

Pas de description pour le moment

Commentaires• Mines Informatique Commune MP PC PSI 2018

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...