CCP Informatique PSI 2016

Thème de l'épreuve La mission Cassini-Huygens
Principaux outils utilisés stockage de données, boucles, recherche de maximum, méthode d'Euler
Mots clefs Cassini-Huygens, compression de données, modélisation d'orbite

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 2016 PSIIN07 ! ! ! EPREUVE SPECIFIQUE - FILIERE PSI! !!!!!!!!!!!!!!!!!!!!" ! INFORMATIQUE Vendredi 6 mai : 8 h - 11 h! !!!!!!!!!!!!!!!!!!!!" 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.! ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" ! ! ! Les calculatrices sont interdites ! ! ! Le sujet comporte 12 pages dont : ! ­ 11 pages de texte de présentation et énoncé du sujet ; ! ­ 1 page d'annexe. ! Toute documentation autre que celle fournie est interdite. ! ! ! REMARQUES PRELIMINAIRES ! ! ! L'épreuve peut être traitée en langage Python ou langage Scilab. Il est demandé au candidat ! de bien préciser sur sa copie le choix du langage et de rédiger l'ensemble de ses réponses dans ! ce langage. Les syntaxes Python et Scilab sont rappelées en annexe, page 12. ! ! Les différents algorithmes doivent être rendus dans leur forme définitive sur la copie en respec! tant les éléments de syntaxe du langage choisi (les brouillons ne sont pas acceptés). ! ! Il est demandé au candidat de bien vouloir rédiger ses réponses en précisant bien le numéro ! de la question traitée et, si possible, dans l'ordre des questions. 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. ! ! ! 1/12 ! La mission Cassini-Huygens I Introduction La mission spatiale Cassini-Huygens a pour objectif l'exploration de Saturne et de ses nombreux satellites naturels (62 « lunes » identifiées en 2009). Cassini orbite depuis 2004 autour de Saturne et collecte grâce à ses différents instruments d'observation, de précieuses informations sur la planète géante, ses anneaux caractéristiques et ses différents satellites. Le sujet proposé aborde des problématiques associées à différentes phases de la mission : ­ l'acquisition d'images par l'imageur spectral VIMS (Visible and Infrared Mapping Spectrometer) dans le domaine du visible et de l'infrarouge embarqué à bord de la sonde Cassini et la compression des données avant transmission vers la Terre pour leur exploitation, ­ la mise en orbite autour de Saturne de la sonde, en utilisant le phénomène d'assistance gravitationnelle de Vénus, de la Terre, puis de Jupiter. II II.1 Figure 1 ­ La sonde Cassini-Huygens Acquisition d'images par l'imageur VIMS et compression des données Présentation La sonde Cassini embarque à son bord un ensemble de 12 instruments scientifiques destinés à l'étude de Saturne et son système, dont 4 instruments d'observation à distance permettant de couvrir une bande spectrale d'observation très large (figures 2 et 3). Figure 2 ­ Instruments d'observation à distance Figure 3 ­ Domaine de travail des différents instruments d'observation à distance L'un des principaux objectifs scientifiques associés à l'instrument VIMS est de cartographier la distribution spatiale des caractéristiques minéralogiques et chimiques de différentes cibles : anneaux de Saturne, surface de ses satellites, atmosphère de Saturne et Titan, etc. Pour cela, l'instrument VIMS mesure les radiations émises et réfléchies par les corps observés, sur une gamme de 0,35 à 5,1 µm (domaines visible et infrarouge) avec au total 352 longueurs d'onde différentes. 2/12 Les données acquises par l'instrument sont organisées sous la forme d'un cube (figure 4) constitué d'un ensemble de 352 « tranches » (associées aux différentes longueurs d'onde ) comportant 64 pixels dans les deux directions spatiales x et y. Il est ensuite possible d'en extraire une image à une longueur d'onde donnée (k ) ou un spectre associé à un pixel de coordonnées spatiales (xi ,yj ). y : 64 pixels x : 64 pixels : 352 longueurs d'onde Image à une longueur d'onde donnée (k ) Spectre associé à un pixel (xi , yi ) Figure 4 ­ Structure d'un cube de données hyperspectrales Les contraintes technologiques liées au transfert de l'ensemble des données recueillies par la sonde vers la Terre imposent une réduction de leur volume. Pour l'imageur VIMS, cela consiste en une compression des données prise en charge par une unité de traitement numérique embarquée à bord de la sonde. Cette compression doit toutefois s'effectuer sans perte d'information. Après compression, la taille maximale attendue pour un cube de données est de 1 Mo (mégaoctet). Objectif Cette partie s'intéresse à l'implémentation d'algorithmes spécifiques visant à améliorer les performances de la compression en vue d'une mise à jour des programmes de l'unité de traitement embarquée. A chaque pixel pijk du cube de données hyperspectrales (de coordonnées xi , yj et appartenant à une image de longueur d'onde k ) est associé un nombre moyen de photons reçus par les capteurs de l'instrument VIMS. Cette dernière information est codée sur 12 bits. Q1. Déterminer en octets la taille d'un cube de données hyperspectrales avant compression. Si T et Tc représentent respectivement la taille des données avant compression et après c compression, le taux de compression est défini comme : = T -T . T Q2. Déterminer alors le taux de compression à appliquer aux données afin de respecter le cahier des charges. II.2 Principe de la compression des données La compression des données est réalisée à l'issue de l'acquisition d'une ligne (soit 64 pixels pour la dimension spatiale et 352 longueurs d'onde pour la dimension spectrale) par l'imageur 3/12 VIMS. Les données sont traitées par blocs de 64 pixels × 32 longueurs d'onde. L'algorithme mis en oeuvre pour la compression est un algorithme dit entropique, qui réalise un codage des données exploitant la redondance de l'information. L'exemple proposé ci-après permet d'en illustrer le principe, avec le codage d'une suite de 10 entiers naturels. Soit la série Sn de 10 entiers naturels sk [0,8] : 4 - 5 - 7 - 0 - 7 - 8 - 4 - 1 - 7 - 4. Un codage en binaire naturel des entiers 0 à 8 nécessitant au minimum 4 bits, le choix d'un tel codage pour la série Sn conduirait à un code d'une longueur totale de 40 bits. La longueur du code associé à la série Sn peut être réduite en adoptant un codage exploitant les propriétés suivantes de la série : ­ seules 6 valeurs vi sont utilisées parmi les 9 possibles ; ­ certaines valeurs vi possèdent des probabilités pi d'apparition plus importantes que d'autres. Une solution consiste par exemple à adopter un codage à longueur variable, où les codes les plus courts sont associés aux valeurs qui possèdent la probabilité d'apparition la plus importante. Un tel codage est proposé dans le tableau 1 pour les entiers de la série Sn . La série Sn est alors codée de la manière suivante : 4 5 7 0 7 8 4 1 7 4 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 0 La longueur du code associé à la série est à présent de 24 bits (soit une longueur moyenne de 2,4 bits par caractère). Le décodage est unique, mais il nécessite la connaissance de la table de codage établissant la correspondance entre un code et la valeur associée. C'est cette stratégie qui est adoptée pour les opérations de compression. Pour la série Sn considérée, avec des valeurs initialement codées sur 4 bits en binaire naturel, le codage à longueur variable présenté permet d'obtenir un taux de compression = 40 %. II.3 valeur vi probabilité pi code 4 0,3 0 0 7 0,3 1 0 0 0,1 0 1 0 1 0,1 0 1 1 5 0,1 1 1 0 8 0,1 1 1 1 Tableau 1 ­ Table de codage Limite du taux de compression Les algorithmes de compression entropiques étant basés sur l'exploitation de la redondance dans les données à coder, leur efficacité est directement liée à la « quantité d'information » qu'elles contiennent : plus il y a répétitions de certaines valeurs dans les données à coder (l'entropie des données est alors faible), plus le taux de compression atteint est élevé. Une valeur limite du taux de compression que l'on peut espérer atteindre peut être approchée par le calcul de l'entropie de Shannon H, grandeur fournissant une mesure de la « quantité d'information » contenue dans les données, en bits par caractère. Pour une série de données Sn (considérée comme une variable aléatoire) l'entropie H est définie de la manière suivante : H(Sn ) = - i=N v pi log2 pi , avec (1) i=1 · Nv : nombre de valeurs vi différentes contenues dans la série ; · pi : probabilité d'apparition de la valeur vi (pi = nni avec ni nombre d'occurrences de la valeur vi et n nombre de termes de la série Sn ) ; où ln est la fonction · log2 : fonction logarithme binaire (base 2). Pour x R, log2 (x) = ln(x) ln(2) logarithme népérien. On suppose que la fonction log2(x) est définie dans le langage de programmation choisi. 4/12 Q3. Calculer l'entropie associeé à l'exemple précédent. En déduire le taux de compression limite de cet exemple et le comparer à la longueur moyenne de 2,4 bits par caractère. Dans le cadre d'une étude visant à améliorer les performances de la compression des données, les ingénieurs souhaitent caractériser l'entropie des images acquises par l'instrument VIMS. La fonction entropie(S) dont le code est partiellement présenté ci-après reçoit en argument d'entrée une série d'entiers naturels S sous forme de tableau à une dimension (liste en Python) et renvoie la valeur H de l'entropie de Shannon associée. Code Python de la fonction entropie(S) : Code Scilab de la fonction entropie(S) : def entropie (S) : # 1 .COMMENTAIRE1 à compl é t e r à l a q u e s t i o n Q4 v a l e u r s= l i s t ( s e t ( S ) ) # 2 .Dé t e r m i n a t i o n du nombre d ' o c c u r e n c e s ( nombre d ' a p p a r i t i o n s ) occ_i de chaque v a l e u r v_i e t c a l c u l de l a p r o b a b i l i t é proba [ i ] a s s o c i é e . # QUESTION Q5 : zone à compl é t e r # 3 . C a l c u l de l ' e n t r o p i e de Shannon H # QUESTION Q6 : zone à compl é t e r return H // DEFINITION DE LA FONCTION ENTROPIE f u n c t i o n H=e n t r o p i e ( S ) // 1 . COMMENTAIRE1 à compl é t e r à l a q u e s t i o n Q4 v a l e u r s=u n i q u e ( S ) // 2 .Dé t e r m i n a t i o n du nombre d ' o c c u r e n c e s ( nombre d ' a p p a r i t i o n s ) occ_i de chaque v a l e u r v_i e t c a l c u l de l a p r o b a b i l i t é proba [ i ] a s s o c i é e . // QUESTION Q5 : zone à compl é t e r // 3 . C a l c u l de l ' e n t r o p i e de Shannon H // QUESTION Q6 : zone à compl é t e r endfunction La fonction réalise différentes étapes. La première étape utilise la fonction set en Python ou unique en Scilab. Un exemple extrait de la documentation de la fonction set est donnée ci-dessous. En Python, il faut transformer le résultat en list pour itérer sur le résultat de set (le principe est similaire en Scilab avec la fonction unique). >>> b a s k e t = [ ' a p p l e ' , ' orange ' , ' a p p l e ' , ' pear ' , ' orange ' , ' banana ' ] >>> f r u i t = s e t ( b a s k e t ) # c r e a t e a s e t without d u p l i c a t e s >>> f r u i t s e t ( [ ' orange ' , ' pear ' , ' a p p l e ' , ' banana ' ] ) >>> ' orange ' i n f r u i t # f a s t membership t e s t i n g True >>> ' c r a b g r a s s ' i n f r u i t False Q4. Compléter le commentaire 1 de la fonction entropie(S) correspondant à la ligne de programme définissant la variable valeurs. Q5. Compléter la 2e étape de la fonction entropie(S) à partir du commentaire afin de calculer les probabilités pi . Q6. Compléter la 3e étape de la fonction entropie(S) afin de calculer l'entropie de Shannon H définie par l'équation (1). Suite à une acquisition d'image par l'instrument VIMS, l'utilisateur dispose de données brutes dont il souhaite évaluer l'entropie. Un bloc élémentaire de données se présente sous la forme d'un tableau à une dimension bloc_image constitué de valeurs entières (allant de 0 à 4 095 = 212 - 1). Q7. Ecrire la suite d'instructions permettant de calculer et d'afficher la valeur du taux de compression limite associé aux données contenues dans le tableau bloc_image. II.4 Prétraitement des données avant compression Les données brutes sont traitées par blocs correspondants à une acquisition de 64 pixels (dimension spatiale y) par 32 longueurs d'onde (dimension spectrale ). Ces données sont organisées sous forme d'une matrice donnees_brutes composée de 32 lignes et 64 colonnes. 5/12 Une stratégie efficace permettant d'améliorer la compression consiste à réaliser un prétraitement des données visant à réduire leur entropie. Il a été constaté pour les images acquises par l'instrument VIMS que les importantes variations de luminance (intensité lumineuse par unité de surface) constituent la contribution dominante dans l'entropie des données. Ainsi, le prétraitement consiste à estimer ces variations, puis à les soustraire aux données brutes à compresser afin de constituer un nouvel ensemble de données, d'entropie inférieure. La procédure de prétraitement consiste d'abord à construire une matrice modèle matrice_modele permettant d'estimer les variations de luminance associées au bloc de données brutes, suivant les étapes décrites ci-après : 1. construction d'une ligne luminance_moy représentative de la luminance moyenne, en effectuant la moyenne de 4 lignes de la matrice donnees_brutes régulièrement espacées et associées à différentes longueurs d'ondes i , i = 1, 11, 21, 31 ; 2. identification du pixel de luminance maximale (de valeur luminance_max) dans la ligne moyenne luminance_moy construite à l'étape précédente ; 3. extraction d'un vecteur colonne spectre_max contenant le spectre (32 composantes) associé au pixel de luminance maximale ; 4. normalisation du vecteur spectre_max en divisant (division réelle) chacune de ses composantes par la valeur luminance_max relevée à l'étape 2. Le résultat est une liste contenant des réels ; 5. construction de la matrice modèle matrice_modele de dimension (32 lignes, 64 colonnes) en effectuant le produit du vecteur colonne spectre_max par la ligne de luminance moyenne luminance_moy. Q8. A partir de la description des étapes 1 et 2, écrire une fonction pretraitement12(donnees_ brutes) recevant en argument d'entrée la matrice donnees_brutes et renvoyant le vecteur ligne luminance_moy, la valeur de luminance maximale luminance_max relevée pour cette ligne moyenne, ainsi que l'indice j (variable j_max) associé (sans utiliser la fonction max interne au langage). Q9. A partir de la description des étapes 3 et 4, écrire une fonction pretraitement34(donnees_ brutes, luminance_max,j_max) recevant en argument d'entrée la matrice donnees_brutes, la valeur de luminance maximale luminance_max ainsi que l'indice j_max et renvoyant le vecteur colonne spectre_max normalisé. Q10. A partir de la description de l'étape 5, écrire une fonction pretraitement5(luminance_ moy, spectre_max) recevant en argument d'entrée le vecteur ligne luminance_moy, le vecteur colonne spectre_max et renvoyant la matrice modèle matrice_modele. La matrice modèle matrice_modele obtenue constitue une estimation des variations de luminance associées au bloc de données brutes. Elle est alors soustraite à la matrice donnees_ brutes pour construire la matrice de données prétraitées matrice_pretraitee. Q11. Evaluer la complexité calculatoire (additions, soustractions, ...) associée à chacune des fonctions de prétraitement, en fonction des dimensions de la matrice modèle (n lignes, m colonnes). En déduire la complexité calculatoire de la phase de prétraitement. II.5 Compression des données Les données de la matrice matrice_pretraitee, d'entropie réduite, sont ensuite envoyées vers le compresseur qui prend en charge leur compression. Il en est de même pour les vecteurs 6/12 luminance_moy et spectre_max qui sont nécessaires à la reconstruction des données après réception. L'architecture fonctionnelle du compresseur qui prend en charge ces opérations est décrite sur la figure 5. Données d'entrée x Prédicteur Mappeur Données compressées y Encodeur entropique Compresseur Figure 5 ­ Architecture fonctionnelle du compresseur Le compresseur est composé : ­ d'un prédicteur, qui effectue une prédiction xk pour chaque échantillon xk des données d'entrée x. La prédiction xk est réalisée simplement ici, en prenant la valeur xk-1 de l'échantillon précédent. Le prédicteur retourne l'erreur k , différence entre la valeur de l'échantillon xk et la prédiction xk ; ­ d'un mappeur, qui réalise un mappage (correspondance) entre l'erreur de prédiction k et un entier non signé k représenté avec un nombre de bits équivalent à celui de l'échantillon xk ; ­ d'un encodeur entropique, qui réalise un codage sans perte des valeurs k en exploitant la redondance des données tel que présenté en partie II.2, page 3. II.5.1 Prédiction-mappage k xk xk k k k Le sous-ensemble prédicteur-mappeur a pour fonc1 2 025 -- -- -- -- tion d'associer aux échantillons d'entrée xk une série 2 2 027 2 025 2 2 025 4 d'entiers k . Cette association est réalisée de telle sorte 3 2 032 2 027 5 2 027 10 que les valeurs k les plus faibles (donc celles qui pourront être codées avec le moins de bits) sont celles qui 4 2 041 2 032 9 2 032 18 ont la probabilité d'apparition la plus élevée. 5 2 050 2 041 9 2 041 18 Pour l'application proposée ici, le compresseur reçoit 6 2 053 2 050 3 2 045 6 en entrée les données x constituées d'un paquet de 32 7 2 052 2 053 -1 2 042 1 échantillons xk . Les échantillons xk considérés étant des entiers naturels représentés sur 12 bits, les valeurs asso8 2 050 2 052 -2 2 043 3 ciées appartiennent à l'intervalle I = [0 , 4 095 = 212 -1]. .. .. .. .. .. .. . . . . . . Le tableau 2 illustre les opérations réalisées par le prédicteur et le mappeur permettant d'obtenir la série Tableau 2 ­ Illustration de la de valeur k : prédiction et du mappage de l'er­ le premier échantillon x1 = 2 025 est un échantillon reur associée de référence sur lequel se base la prédiction au rang suivant x2 ; ­ à partir du deuxième échantillon, l'erreur de prédiction k = xk - xk est calculée ; ­ un entier non signé k est associé à l'erreur de prédiction k par la fonction de mappage définie comme : si 0 k k 2k (2) k = 2|k | - 1 si - k k < 0 + | | sinon k k avec k = min(xk - xmin , xmax - xk ), soit ici : k = min(xk , 4 095 - xk ). 7/12 Q12. Ecrire une fonction prediction(x) recevant en argument d'entrée le tableau à une dimension x et renvoyant le tableau erreur contenant les valeurs k . Q13. A partir de la définition de la fonction de mappage, équation (2), écrire une fonction mappage(erreur,x) recevant en arguments d'entrée les tableaux à une dimension erreur et x et renvoyant le tableau delta contenant les valeurs k . II.5.2 Codage entropique - Algorithme de Rice L'ensemble de valeurs k est ensuite codé en utilisant un codage entropique spécifique : le codage de Rice. Celui-ci est particulièrement adapté à la compression de données dans lesquelles les valeurs les plus faibles sont celles qui ont la probabilité d'apparition la plus élevée, mais également lorsque la vitesse d'exécution de l'algorithme est un paramètre important. Le principe du codage d'un entier N avec l'algorithme de Rice de paramètre p est le suivant : ­ l'entier N à coder est divisé par 2p (division entière) ; ­ le quotient q de la division entière est codé avec un codage unaire (q occurences de 1 suivies d'un 0, voir tableau 3), ce qui constitue la première partie du code de Rice ; ­ le reste r de la division entière est codé en binaire sur p bits, ce qui constitue la seconde partie du code de Rice. Le tableau 4 illustre le codage des entiers 0 à 7 avec un codage de Rice de paramètre p = 2. Une procédure d'analyse de l'ensemble de valeurs k à coder permet de déterminer la valeur optimale popt du paramètre p. Le codage de chaque valeur k est ensuite réalisé par une fonction codage(delta_k,p_opt) recevant en argument d'entrée la valeur k et l'entier popt et renvoyant le code de Rice associé. Q14. Déterminer le code de Rice associé à la suite de valeurs k données dans le tableau 2, page 7 pour p = 3. Q15. Définir la suite d'instructions de la fonction codage(delta_k,p_opt) permettant d'obtenir un tableau à une ligne code1 associé à la première partie du code de Rice (codage unaire du quotient). Q16. Définir la suite d'instructions de la fonction codage(delta_k,p_opt) permettant d'obtenir un tableau à une ligne code2 associé à la seconde partie du code de Rice (codage binaire du reste) et réalisant ensuite l'assemblage des deux parties dans le tableau code. Les instructions bin de Python ou dec2bin de Scilab (voir annexe, page 12) pourront être utilisées (on supposera que ces fonctions retournent une chaîne de caractères associée au code binaire). Décimal Code unaire 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 7 11111110 Décimal Rice p = 2 0 0 00 1 0 01 2 0 10 3 0 11 4 10 00 5 10 01 6 10 10 7 10 11 Tableau 3 ­ Codage unaire des entiers 0 à 7 Tableau 4 ­ Codage de Rice de paramètre p = 2 des entiers 0 à 7 8/12 III III.1 Mise en orbite de la sonde autour de Saturne Présentation La sonde Cassini-Huygens a été lancée du site de Cap Canaveral (Floride - USA) le 15 Octobre 1997. Une fusée Titan IV-B/Centaur a été nécessaire pour assurer le lancement de cette sonde de 5,6 tonnes. Aucun lanceur n'étant alors capable de donner à une sonde spatiale de cette masse l'énergie suffisante pour rejoindre Saturne par une trajectoire directe, l'énergie manquante est obtenue en utilisant le phénomène d'assistance gravitationnelle de Vénus, de la Terre et enfin de Jupiter. L'assistance gravitationnelle consiste à utiliser le champ de gravitation d'une planète afin de fournir une accélération supplémentaire à la sonde. Le trajet de la sonde vers Saturne s'est donc effectué en plusieurs étapes comme indiqué sur la figure 6. Figure 6 ­ Trajet de la sonde depuis la Terre vers Saturne Objectif L'objectif de cette partie est de simuler le mouvement de la sonde lors de la phase d'assistance gravitationnelle de Vénus afin de déterminer sa trajectoire ainsi que le gain de vitesse obtenu. III.2 Modélisation du mouvement de la sonde lors de la phase d'assistance gravitationnelle Paramétrage ­ Le mouvement de la sonde est étudié dans le référentiel héliocentrique auquel est associé le repère (O, x, y ). ­ La sonde est repérée par la position de son centre d'inertie G auquel est associé le vecteur - r(t) = OG et l'angle (t). ­ La planète Vénus est repérée par la position de son centre d'inertie Gv auquel est associé -- le vecteur rv (t) = OGv et l'angle v (t). 9/12 Hypothèses ­ Seuls le Soleil et Vénus ont une influence gravitationnelle significative sur la trajectoire de la sonde. ­ Le propulseur de la sonde n'étant pas utilisé lors du survol de Vénus, sa poussée n'est pas prise en compte. ­ Les trajectoires de la sonde et de Vénus sont considérées comme coplanaires (plan O, x, y ). Aussi, les vecteurs position s'expriment en coordonnées cartésiennes : r(t) = x(t) x + y(t) y rv (t) = xv (t) x + yv (t) y ­ L'orbite de Vénus autour du Soleil, considérée comme quasiment circulaire, est décrite par les équations : xv (t) = rv cos(t + ) yv (t) = rv sin(t + ) y Orbite de la Terre Position de la Terre au 26 avril 1998 Orbite de Vénus Terre G r(t) Position de Vénus au 26 avril 1998 Gv Vénus v (t) rv (t) (t) x O Soleil Terre Trajectoire de la sonde Position de la Terre au lancement Figure 7 ­ Paramétrage du mouvement avec rv = 1,082 09 × 1011 m, = v (t) = 3,236 39 × 10-7 rad · s-1 et la position angulaire initiale de Vénus. Equations de mouvement Le mouvement de la sonde est défini par l'équation suivante : d2r(t) r(t) r(t) - rv (t) = - Gms - Gmv 2 3 dt ||r(t)|| ||r(t) - rv (t)||3 (3) avec G constante universelle de gravitation, ms masse du Soleil, mv masse de Vénus (GmS = 1,327 24 × 1020 N · m2 · kg-1 et GmV = 3,249 16 × 1014 N · m2 · kg-1 ). On note m la masse de la sonde. Q17. Indiquer comment a été obtenue cette équation en précisant le théorème utilisé et ce que représentent chacun des termes. L'équation précédente peut se mettre sous la forme : d2 x(t) = Sx (x(t),y(t),t) dt2 (4) d2 y(t) = Sy (x(t),y(t),t) dt2 (5) Q18. Donner les expressions des fonctions Sx et Sy . Ecrire une fonction eval_sm(x,y,t), qui prend en argument les coordonnées x et y et l'instant t et qui renvoie les valeurs Sx et Sy associées. 10/12 III.3 III.3.1 Résolution numérique Méthode numérique La résolution numérique des équations différentielles (4) et (5) repose sur leur discrétisation temporelle et conduit à déterminer à différents instants ti une approximation de la solution. On note ui et vi , les approximations des composantes du vecteur vitesse (vx (t),vy (t)) à dx(t) dy(t) l'instant ti avec vx (t) = et vy (t) = . On note t = ti+1 - ti . dt dt Q19. En appliquant la méthode d'Euler explicite, déterminer les deux relations de récurrence reliant ui+1 à ui , Sx et t ainsi que vi+1 à vi , Sy et t. On note xi et yi , les approximations des composantes du vecteur position (x(t),y(t)) à l'instant ti . Q20. En appliquant la méthode d'Euler explicite, déterminer les deux relations de récurrence reliant xi+1 à xi , ui et t ainsi que yi+1 à yi , vi et t. III.3.2 Le programme de résolution On supposera toutes les constantes du problème définies comme variables globales et donc utilisables directement dans votre programme. Les conditions initiales du problème seront supposées être : u0 = vx (t = 0), v0 = vy (t = 0), x0 = x(t = 0), y0 = y(t = 0). Le programme doit permettre de calculer les quatre vecteurs : x(t), y(t), u(t) et v(t), contenant les différentes valeurs pour les différents instant ti , qui seront stockés respectivement dans les variables x, y, u et v. Le programme est constitué de trois étapes : initialisation des variables, résolution et traitement. On définira également le vecteur temps contenant l'ensemble des instants de calcul ti de longueur n et qui sera stocké dans la variable t. Q21. Donner les lignes de programme permettant de définir et d'initialiser les quatre variables x, y, u et v ainsi que le vecteur t contenant l'ensemble des instants de calcul ti de longueur n sachant que la variable deltaT égale à t et la variable n sont déjà déclarées. Q22. Donner les lignes de programme permettant de calculer les vecteurs x, y, u et v en utilisant les relations de récurrence définies précédemment. Q23. Donner un ordre de grandeur de la quantité de mémoire nécessaire pour réaliser cette simulation numérique pour une durée de simulation de 30 jours et pour un pas de temps de 1 seconde sachant que les variables x, y, u et v contiennent des flottants codés sur 8 octets. Conclure sur la faisabilité de la simulation par cette méthode. III.4 Evolution de la vitesse Q24. Afin de quantifier le gain de vitesse obtenu par l'assistance gravitationnelle étudiée, écrire une fonction vitesse_sonde dont vous préciserez les arguments et les valeurs retournées, permettant d'afficher l'évolution de la norme de la vitesse v (t) de la sonde en fonction du temps t. Les vitesses seront exprimées en km · s-1 et les axes seront légendés. On pourra utiliser les informations données en annexe pour l'utilisation des commandes de tracés. 11/12 Annexe : rappels des syntaxes en Python et Scilab Remarque : sous Python, l'import du module numpy permet de réaliser des opérations pratiques sur les tableaux : from numpy import *. Les indices de ces tableaux commencent à 0. Remarque : sous Scilab, les indices des tableaux commencent à 1. accéder à un élément ajouter un élément tableau à deux dimensions (matrice) accéder à un élément extraire une portion de tableau (2 premières colonnes) tableau de 0 ( 2 lignes, 3 colonnes) dimension d'un tableau T de taille (i,j) séquence équirépartie quelconque de 0 à 10.1 (exclus) par pas de 0.1 définir une chaîne de caractères taille d'une chaîne extraire des caractères boucle For condition If définir une fonction qui possède un argument et renvoie 2 résultats conversion entier > binaire tracé d'une courbe de deux listes de points x et y ajout d'un titre sur les axes d'une figure ajout d'un titre principe sur une figure Scilab v=[1, 2, 3] ou [1 2 3] v(1) renvoie 1 v($+1) = 5 M=array(([1,2,3],[3,4,5])) M=[1,2,3;3,4,5] M[1,2] ou M[1][2] donne 5 M(2,3) donne 5 M[:,0:2] M(:,1:2) zeros((2,3)) zeros(2,3) T.shape donne [i,j] length(T) donne (i,j) arange(0,10.1,0.1) [0:0.1:10] mot="Python et Scilab" mot="Python et Scilab" len(mot) mot[2:7] length(mot) part(mot,[11:16]) for i in range (10) : print ( i ) for i =1:10 disp ( i ) ; end if (i >3) : print ( i ) else : print ( " hello " ) if (i >3) then disp ( i ) else disp ( " hello " ) end def f ( param ) : a = param b = param * param return a , b bin(entier) function [a , b ]= f ( param ) a = param b = param * param endfunction dec2bin(entier) plot(x,y) plot(x,y) xlabel(texte) ylabel(texte) xlabel(texte) ylabel(texte) title(texte) title(texte) FIN 12/12 I M P R I M E R I E N A T I O N A L E ­ 16 1226 ­ D'après documents fournis tableau à une dimension Python L=[1,2,3] (liste) v=array([1,2,3]) (vecteur) v[0] renvoie 1 L.append(5) uniquement sur les listes

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


 CCP Informatique PSI 2016 -- Corrigé Ce corrigé est proposé par Jean-Julien Fleck (Professeur en CPGE) ; il a été relu par Vincent Puyhaubert (Professeur en CPGE) et Benjamin Monmege (Enseignantchercheur à l'université). Ce sujet aborde divers aspects de la mission Cassini-Huygens à destination de Saturne, depuis le stockage et la compression des images jusqu'à l'idée de simulation de la trajectoire de la sonde lors de son passage aux environs de Vénus pour profiter de l'effet de fronde gravitationnelle. Les premières questions (1 à 7) portent sur le stockage des données (nombre de bits, etc.) et la détermination d'un stockage optimal à l'aide de la notion d'entropie de Shannon. Il s'agit juste de faire quelques boucles pour écrire les fonctions demandées. La suite (questions 8 à 11) demande déjà d'avoir une bonne compréhension du format des données et de ne pas s'y perdre, mais une fois cette représentation en tête, les calculs sont assez directs. Vient alors la partie sur la compression de données (questions 12 à 16), où les questions ne sont pas difficiles à condition d'avoir su extraire les quelques informations utiles de la page de texte explicatif, qui n'est pas toujours très clair. C'est certainement l'endroit qui a bloqué le plus de candidats. La fin du sujet (question 17 à 24), assez classique, demande d'implémenter la méthode d'Euler pour trouver la trajectoire de la sonde soumise à la double influence du Soleil et de Vénus. Ici, la difficulté est double : l'équation à intégrer est du deuxième ordre et les deux équations différentielles en x et en y sont couplées. Le sujet ne traite pas du tout des bases de données ni du programme de deuxième année, mais sa longueur le rend adapté au concours. Le facteur limitant est la capacité à absorber des informations tandis que les questions elles-mêmes ne sont pas intrinsèquement difficiles. C'est particulièrement criant dans les questions 12 à 16 où les réponses sont aisées une fois que l'on a bien compris comment cela marche. Indications Partie II 1 Normalement, 1 ko = 1 000 o alors que 1 024 o = 1 Kio. 8 Par commodité, on pourra définir une liste d'indices à sélectionner sous la forme selection = [1,11,21,31] 10 Les coefficients d'une matrice M produit d'une colonne C avec une ligne L sont tels que Mij = Ci × Lj . 11 Les complexités d'actions successives s'ajoutent. Seul compte finalement le terme prédominant. 12 Faire la liste des différences de deux termes consécutifs de la liste x. 13 Cette question ne sert qu'à vérifier que vous utilisez correctement les branchements conditionnels. 14 Convertir le quotient de la division euclidienne par 2p en code unaire et le reste en code binaire. 15 L'énoncé attend que code1 contienne des chaînes de caractères. Partie III 18 Définir une fonction auxiliaire position_venus(t) peut être une bonne idée. II. Acquisition d'images par l'imageur VIMS et compression de données 1 Il s'agit simplement de compter le nombre de pixels sur une image, multiplié par le nombre total d'images, et de multiplier par la taille occupée en mémoire par l'information contenue dans un pixel (soit 12 bits). Comme un octet correspond à 8 bits, on a une taille totale de nb total de pixels z }| { 64 × 64 × 352 ×12 = 17 301 504 bits = 2 162 688 octets = 2,16 Mo Si on considère que 1 ko = 1 024 octets (alors qu'en fait c'est un kibioctet noté Kio, voir la page Wikipédia sur l'octet), on trouverait 2,06 Mo, ce qui n'est pas très éloigné. La taille n'est pas très importante comparée à celle, usuelle, occupée par les photos numériques de nos jours malgré le grand nombre de longueurs d'ondes explorées. La différence vient en fait du nombre de pixels présent dans chaque image : 64 × 64 = 4 096, ce qui semble ridicule en comparaison des photos actuelles qui se mesurent en méga-pixels. Néanmoins, pour des images astronomiques dont les objets étudiés occupent en général un champ très réduit, c'est largement suffisant, l'étude multi-spectrale étant bien plus intéressante que le nombre effectif de pixels sur chaque image. 2 Comme on vise une taille de 1 Mo après compression, le taux de compression est d'environ 50 % ou plus exactement = 2,16 - 1 = 53,8 % 2,16 3 Prenons en compte le fait que plusieurs caractères apparaissent avec la même probabilité (2 avec une probabilité de 0,3 et 4 avec une probabilité de 0,1). Alors H = -2 × 0,3 log2 (0,3) - 4 × 0,1 log2 (0,1) = 2,37 Connaissant le nombre de bits pour un caractère (4 ici), le taux de compression vaut donc sur cet exemple = 4-H = 40,7 % 4 Le codage présenté (à 2,4 bits/caractère) se rapproche bien de l'estimation entropique. L'énoncé ne précise pas la provenance du codage utilisé dans le tableau 1. De manière évidente, il ne s'agit pas du codage utilisé dans la partie II.5.2, ce qui n'est pas très honnête. À première vue, il s'agit vraisemblablement d'un codage de Huffman. Comme l'indique l'énoncé, il s'agit d'associer à chaque entier un codage par une suite de bits. La contrainte principale est d'éviter l'ambiguïté. Supposons par exemple que l'on utilise le code suivant : 4 00 5 1 6 001 La séquence 001 peut alors aussi bien coder la chaîne 45 que la chaîne 6. Pour cela, une propriété essentielle du codage est qu'aucun symbole ne doit pouvoir être codé par une chaîne qui est préfixe d'une autre. On parle alors de codage préfixe. On associe généralement un arbre à un tel code. Voici celui de l'exemple de l'énoncé : 0 0 1 0 1 4 0 0 1 7 1 1 0 5 1 8 Le code d'un symbole est la suite des bits rencontrés lors du parcours de la racine de l'arbre jusqu'au symbole en question. Cela assure la propriété préfixe. L'arbre est construit suivant un procédé algorithmique qui permet d'avoir les symboles les plus fréquents les plus proches de la racine, et donc avec les codes les plus courts. On peut alors s'en servir pour décoder directement un texte en se déplaçant dans l'arbre en fonction des bits lus. À chaque fois que l'on arrive à un symbole, on imprime le symbole trouvé puis on repart de la racine. En particulier, 0010100111010110111 47717758 4, 5 et 6 Le code complet demandé peut être implémenté de la façon suivante. def entropie(S): # Question 4: On veut récupérer la liste des valeurs distinctes dans S valeurs = list(set(S)) # Question 5: Calcul des différentes probabilités. Il faut d'abord compter. # On initialise donc la liste des probas (liée à la liste 'valeurs') avant # d'incrémenter chaque compteur en fonction de la valeur trouvée. proba = [0]*len(valeurs) for data in S: for i in range(len(valeurs)): if data == valeurs[i]: proba[i] += 1 # On divise par le nombre de données pour avoir la proba de chaque valeur. proba = [c/len(S) for c in proba] # Question 6: reste à appliquer la formule pour trouver l'entropie H = 0 for p in proba: H = H - p * log2(p) return H L'application de ce code à la liste proposée donne bien le résultat calculé auparavant. >>> entropie([4,5,7,0,7,8,4,1,7,4]) 2.37095059445 Lorsqu'on trouve un « gagnant » dans le code précédent, on pourrait utiliser l'instruction break pour sortir de la boucle puisque, par unicité des valeurs de la liste valeurs, aucune autre ne pourra convenir. Néanmoins, il s'agit ici d'optimisation prématurée. En effet, on ne sait pas encore à ce stade si on risque de passer beaucoup de temps dans ces boucles et en pratique, on ne gagnera que des clopinettes (sans compter les risques de bug). Comme