Centrale Informatique commune MP 2015

Thème de l'épreuve Autour de la dynamique gravitationnelle
Principaux outils utilisés listes, boucles, schémas d'intégration, méthode d'Euler, bases de données

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


Q, % Informatique l-D
% . "'
_/ MP,PC,PSI,TSI @

EUNE[IHHS EENTHHLE-SUPËLEE 3 heures Calculatrices autorisées N

Autour de la dynamique gravitationnelle

Modéliser les interactions physiques entre un grand nombre de constituants mène 
à l'écriture de systèmes diffé--
rentiels pour lesquels, en dehors de quelques situations particulières, il 
n'existe aucune solution analytique. Les
problèmes de dynamique gravitationnelle et de dynamique moléculaire en sont 
deux exemples. Afin d'analyser le
comportement temporel de tels systèmes, l'informatique peut apporter une aide 
substantielle en permettant leur
simulation numérique. L'objet de ce sujet, composé de quatre parties, est 
l'étude de solutions algorithmiques
en vue de simuler une dynamique gravitationnelle afin, par exemple, de prédire 
une éclipse ou le passage d'une
comète.

Les programmes doivent être écrits en langage python et les requêtes de base de 
données en langage SQL.
Les candidats sont libres de définir et de programmer toute fonction auxiliaire 
dont ils estiment avoir besoin
pour répondre aux questions posées. Ils ueilleront dans ce cas à définir 
précisément, le rôle de chaque fonction
introduite, ses paramètres et son résultat. Ils peuvent également utiliser 
librement les fonctions de la bibliothèque
standard Python, en particulier celles du module math.

Lorsque le sujet demande l'écriture d'une fonction python, la réponse doit 
commencer par l'entête de la fonction
(instruction def). D'autre part, si le sujet précise que la fonction prend un 
paramètre d'un certain type ou qui
répond à une certaine condition, la fonction n'a pas à vérifier la conformité 
de l'argument reçu.

La lisibilité des codes produits, tant en python qu'en SQL, est un élément 
important d'appréciation.

I Quelques fonctions utilitaires

I .A -- Donner la valeur des expressions python suivantes :

I.A.1) [1, 2, s] + [4, 5, 6]

I.A.2) 2 * [1, 2, 3]

I .B -- Écrire une fonction python smul a deux paramètres, un nombre et une 
liste de nombres, qui multiple
chaque élément de la liste par le nombre et renvoie une nouvelle liste : smul 
(2, [1 , 2, 3]) --> [2, 4, 6].
LG -- Arithmétique de listes

I.C.1) Écrire une fonction python vsom qui prend en paramètre deux listes de 
nombres de même longueur et
qui renvoie une nouvelle liste constituée de la somme terme à terme de ces deux 
listes :
Vsom([1, 2, 3], i:4, 5, 6]) _) [5' 72 9]

I.C.2) Écrire une fonction python vdif qui prend en paramètre deux listes de 
nombres de même longueur et
qui renvoie une nouvelle liste constituée de la différence terme a terme de ces 
deux listes (la première moins la
deuxième) : Vdif([1, 2, 3] , [4, 5, 6]) --> [--3, --3, --3].

II Étude de schémas numériques

min et tmax deux réels tels que tmin < tmax.
On s'intéresse a une équation différentielle du second ordre de la forme :

Vt EUR I y"(t) = f (W)) (II-1)

où f est une fonction donnée, continue sur [R. De nombreux systèmes physiques 
peuvent être décrits par une
équation de ce type.

Soient y une fonction de classe C'2 sur [R et t On note I l'intervalle

[tmin7 tmaxi '

On suppose connues les valeurs y() : y(tmin) et z0 = y'(tmin). On suppose 
également que le système physique
étudié est conservatif. Ce qui entraîne l'existence d'une quantité indépendante 
du temps (énergie, quantité de

mouvement, .), notée E, qui vérifie l'équation (11.2) où g' = -- f .
1
w e 1 5y'2 +g [R définie par
Vt EUR I, z(t) : y'(t).

2015-03-09 14:08:31 Page 1/4 [_

II.A.1) Montrer que l'équation (11.1) peut se mettre sous la forme d'un système 
différentiel du premier ordre
en z(t) et y(t), noté (S).

t --t .
II.A.2) Soit n un entier strictement supérieur à 1 et Jn : l[0,n -- 1]]. On 
pose h = % et Vi E J...
t,-- : tmin + ih. Montrer que, pour tout entier i EUR |[0,n -- 2]],
ti+1 ti+1
y = z 2 étant
un entier positif donné. Le mouvement de ces points est étudié dans un 
référentiel galiléen muni d'une base

orthonormée. L'interaction entre deux corps j et k est modélisée par la force 
gravitationnelle. L'action exercée
m m
_] k
3
rjk
corps j et k (rjk = ||Pijll) et G = 6,67 >< 10_11 N-m2-kg_2 la constante de 
gravitation universelle.

par le corps k sur le le corps j est décrite par la force Î . = G PP où 7". est 
la distance séparant les
k/J ] k Jk

A tout instant t,-- avec i E [[O,n]], chaque corps de masse mj est repéré par 
ses coordonnées cartésiennes

(as,--j, y,,, 2,1) et les composantes de son vecteur v1tesse (v...--j, vyij, 
UZ,--j) dans le referent1el de reference.

Trois listes sont utilisées pour représenter ce système en python

-- masse conserve les masses de chaque corps : masse [j] = mj ;

-- position contient les positions successives de chaque corps : position [i] 
[j] = [as,--j,y,--j, z,--j] ;

-- vitesse mémorise les vitesses successives de chaque corps : vitesse [i] [j] 
= [vmj,vyij,vz,--j].
L'objet de la suite du problème est de construire ces listes en mettant en 
oeuvre l'algorithme de Verlet.

III.A -- Position du problème
III.A.1) Exprimer la force Î'j exercée sur le corps Pj par l'ensemble des 
autres corps Pk, avec k % j.

III.A.2) Écrire une fonction python force2 (m1, pi, m2, p2) qui prend en 
paramètre les masses (m1 et m2
en kilogrammes) et les positions (pl et p2, sous forme de listes de trois 
coordonnées cartésiennes en mètres) de
deux corps 1 et 2 et qui renvoie la valeur de la force exercée par le corps 2 
sur le corps 1, sous la forme d'une
liste a trois éléments représentant les composantes de la force dans la base de 
référence, en newtons.

III.A.3) Écrire une fonction forceN( j , m, pos) qui prend en paramètre 
l'indice j d'un corps, la liste des

masses des N corps du système étudié ainsi que la liste de leurs positions et 
qui renvoie Fj, la force exercée par
tous les autres corps sur le corps j, sous la forme d'une liste de ses trois 
composantes cartésiennes.

III.B -- Approche numérique
III.B.1) Expliciter la structure et la signification de position [i] et vitesse 
[i].

III.B.2) Écrire une fonction pos_suiv (m, pos, vit, h) qui prend en paramètres 
la liste des masses des N
corps du système étudié (en kilogrammes), la liste de leurs positions (en 
mètres) à l'instant t,, la liste de leurs
vitesses (en mètres par seconde) au même instant et le pas d'intégration h (en 
secondes) et qui renvoie la liste
des positions des N corps à l'instant t,-- +1 calculées en utilisant le schéma 
de Verlet.

III.B.3) Écrire une fonction etat_suiv(m, pos, vit, h) qui prend les mêmes 
paramètres que la fonction
pos_suiv et qui renvoie la liste des positions (en mètres) et la liste des 
vitesses (en m/s) des N corps à l'instant
t,-- +1 calculées en utilisant le schéma de Verlet.

III.B.4) En notant TN la durée des calculs pour un ln(TN)
nombre N de corps, la mise en oeuvre de la fonction 8'
etat_suiv a donné le résultat graphique de la figure 2 + ++
où on a porté ln(N ) en abscisse et ln(TN) en ordonnée. 7 +++
a ) Quelle relation simple peut--on établir entre ln(TN) +++
et ln(N ) a partir de la figure 2 ? 6 + +
b) Quelle hypothèse peut-on émettre quant à la com-- + +
plexité de l'algorithme étudié ? 5 +
III.B.5) +

4 +
a) Estimer la complexité temporelle de la fonction
etat_suiv sous la forme O(N°'). 3 +
b) Comparer avec le résultat obtenu àla question III.B/l.

2

+

Figure 2

2015-03-09 14:08:31 Page 3/4 [_

IV Exploitation d'une base de données

À partir de mesures régulièrement effectuées par différents observatoires, une 
base de données des caractéristiques
et des états des corps célestes de notre Système solaire est maintenue à jour. 
L'objectif de cette partie est
d'extraire de cette base de données les informations nécessaires à la mise en 
oeuvre des fonctions développées
dans les parties précédentes, puis de les utiliser pour prévoir les positions 
futures des différentes planètes. Les
données à extraire sont les masses des corps étudiés et leurs états (position 
et vitesse) a l'instant tmin du début
de la simulation.

Une version simplifiée, réduite à deux tables, de la base de données du Système 
solaire est donnée figure 3. Les
masses sont exprimées en kilogrammes, les distances en unités astronomiques (1 
au : 1,5 >< 1011 m) et les vitesses
en kilomètres par seconde. Le référentiel utilisé pour exprimer les composantes 
des positions et des vitesses est
galiléen, orthonormé et son centre est situé a proximité du Soleil.

CORPS ETAT

id_corps-- masse id_corps ...

Figure 3 Schéma de la base de données

La table CORPS répertorie les corps étudiés, elle contient les colonnes

-- id_corps (clé primaire) entier identifiant chaque corps ;

-- nom, chaine de caractères, désigne le nom usuel du corps ;

-- masse de type flottant, contient la masse du corps.

La table ETAT rassemble l'historique des états successifs (positions et 
vitesses) des corps étudiés. Elle est consti-

tuée de huit colonnes :

-- id_corps de type entier, identifie le corps concerné ;

-- datem est la date de la mesure, sous forme d'un entier donnant le nombre de 
secondes écoulées depuis un
instant d'origine ;

-- trois colonnes de type flottant pour les composantes de la position x, y, z ;

-- trois colonnes de type flottant pour les composantes de la vitesse vx, vy, 
vz.

I V.A -- Écrire une requête SQL qui renvoie la liste des masses de tous les 
corps étudiés.

I V.B -- Les états des différents corps ne sont pas forcément tous déterminés 
exactement au même instant.
Nous allons assimiler l'état initial (à la date tmin) de chaque corps à son 
dernier état connu antérieur à tmin.
Dans toute la suite, on supposera que la valeur de tmin7 sous le format utilisé 
dans la table ETAT, est accessible

à toute requête SQL via l'expression tmin().
IV.B.1) On souhaite d'abord vérifier que tous les corps étudiés disposent d'un 
état connu antérieur à tmin().

Le nombre de corps présents dans la base est obtenu grâce à la requête SELECT 
count(*) FROM corps. Écrire
une requête SQL qui renvoie le nombre de corps qui ont au moins un état connu 
antérieur à tmin().

IV.B.2) Écrire une requête SQL qui renvoie, pour chaque corps, son identifiant 
et la date de son dernier état
antérieur à tmin().

IV.B.3) Le résultat de la requête précédente est stocké dans une nouvelle table 
date_mesure a deux colonnes :
-- id_corps de type entier, contient l'identifiant du corps considéré;

-- date_der de type entier, correspond à la date du dernier état connu du corps 
considéré, antérieur à tmin().
Pour simplifier la simulation, on décide de négliger l'influence des corps 
ayant une masse strictement inférieure
à une valeur fixée masse_min() et de ne s'intéresser qu'aux corps situés dans 
un cube, centré sur l'origine du
référentiel de référence et d'arête arete() donnée. Les faces de ce cube sont 
parallèles aux plans formés par les
axes du référentiel de référence.

Ecrire une requête SQL qui renvoie la masse et l'état initial (sous la forme 
masse, x, y, z, vx, vy, vz) de
chaque corps retenu pour participer à la simulation. Classez les corps dans 
l'ordre croissant par rapport a leur
distance a l'origine du référentiel.

I V.C -- On dispose des variables python tO, p0, VO et masse initialisées a 
partir du résultat de la requête
précédente. 130 est un entier qui donne la date des conditions initiales : il 
correspond à tmin et à tmin(). p0 est
une liste de longueur N, chaque élément de 130 est une liste a 3 éléments de la 
forme [x, y, 2] représentant
la position initiale d'un corps, en unité astronomique. VO a une structure 
identique mais indique les vitesses
initiales des corps considérés, en km/s. masse est décrite en partie III.

Écrire la fonction python simulation_verlet (deltat, 11) qui prend en paramètre 
un incrément de temps en
secondes (deltat > O) et un nombre d'itérations (n > O) et qui renvoie la liste 
des positions des corps considérés
pour chaque instant t0, t0 + deltat, ..., 130 + n*deltat (cf variable position 
définie en partie III). Les calculs
seront menés en utilisant le schéma d'intégration de Verlet, le résultat sera 
fourni en unité astronomique.

oooFlNooo

2015-03-09 14:08:31 Page 4/4 [_

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



Centrale Informatique commune MP 2015 --
Corrigé
Ce corrigé est proposé par Jean-Julien Fleck (Professeur en CPGE) ; il a été 
relu
par Julien Dumont (Professeur en CPGE) et Guillaume Batog (Professeur en CPGE).
Ce sujet s'intéresse à une application en astronomie (effectivement utilisée 
par les
astronomes) d'un algorithme d'intégration numérique, appelé schéma d'intégration
de Verlet.
La première partie part du constat qu'en Python les listes ne sont pas 
directement
adaptées pour faire du calcul vectoriel puisque leur addition à l'aide du 
symbole +
conduit à la concaténation des deux listes (qui du coup peuvent être de tailles 
quelconques) plutôt qu'à l'addition terme à terme comme on pourrait s'y 
attendre si
l'on représente des vecteurs par des listes. On construit donc quelques 
fonctions qui
permettent de pallier cet inconvénient, comme l'addition ou la soustraction 
terme à
terme ou encore la multiplication par un scalaire. Ces questions servent 
essentiellement à vérifier que le candidat maîtrise les boucles sur les listes.
La deuxième partie est une étude plutôt théorique des avantages comparés des
schémas d'intégration d'Euler et de Verlet pour résoudre numériquement une 
équation différentielle1 . L'accent est mis sur l'aspect mathématique, mais on 
fait aussi des
liens avec le cours de mécanique sur les oscillateurs à un degré de liberté 
puisque l'on
étudie principalement l'effet du schéma d'intégration sur un oscillateur 
harmonique
et sa représentation graphique en terme de portrait de phase. Les 
implémentations
du schéma d'Euler (prolongement naturel et direct du cours) et du schéma de 
Verlet
(variation sur le thème d'Euler) constituent les applications informatiques de 
cette
partie.
La troisième partie se concentre sur l'implémentation du schéma de Verlet dans 
le
cadre classique du problème gravitationnel à N corps. Il s'agit dans un premier 
temps
de coder le calcul de la force gravitationnelle d'un objet sur un autre, puis 
de tous
les autres objets sur l'objet d'étude pour finalement intégrer les équations du 
mouvement à l'aide du schéma de Verlet. On termine sur une estimation 
expérimentale
et théorique de la complexité de l'algorithme proposé.
La quatrième partie aborde des questions sur les bases de données dans l'idée de
collecter une série de corps issus du système solaire pour démarrer une 
simulation à
grande échelle. Cela commence par des requêtes SQL très simples, puis la 
difficulté
augmente progressivement. Le problème se termine par l'écriture de la fonction 
simulant le système solaire, en partant des conditions initiales collectées via 
la base de
données. Elle utilise les fonctions de la partie III.
L'épreuve est progressive, même si elle démarre avec des questions légèrement
hors programme. Elle construit presque complètement un intégrateur à N corps qui
pourra servir de base, par exemple, à de futurs TIPE sur ce thème. La longueur
est raisonnable et le sujet semble parfaitement correspondre à ce qu'on est en 
droit
d'attendre sur le programme d'informatique commune.

1 Sans

surprise, c'est Verlet qui va gagner.

Indications
Partie I
I.A.1 Attention, les listes Python ne se comportent pas naturellement comme
des vecteurs en mathématiques. Dans le doute, tester le code dans une
session interactive de Python.
Partie II
II.A.1 Par définition, on a y = z, il reste donc à trouver à quoi relier z  .
Z ti+1
II.A.2 Il suffit de partir de la constatation que
y  (t) dt = y(ti+1 ) - y(ti ).

ti

II.B.2 Utiliser la fonction f définissant l'équation différentielle, les 
conditions
initiales y0 et z0 ainsi que le pas de temps h et le nombre n de points.
II.B.3.a Penser au cours de physique : multiplier par la vitesse y  pour faire
apparaître des dérivées de fonctions composées connues.
II.B.3.b Ne pas oublier qu'on se restreint ici au cas de l'oscillateur 
harmonique.
II.B.3.c Un schéma satisfait la conservation de l'énergie si... l'énergie se 
conserve.
II.B.3.d et e Là encore, il faut s'inspirer du portrait de phase de 
l'oscillateur harmonique vu dans le cours de physique.
II.C.2.a C'est la question la plus calculatoire du problème. Commencer par 
exprimer yi+1 et zi+1 en fonction uniquement de yi et zi sans oublier qu'on
s'intéresse toujours uniquement à l'oscillateur harmonique. Par la suite,
utiliser l'identité remarquable a2 - b2 = (a - b)(a + b) et faire un 
développement en O(h3 ) pour ne pas s'encombrer de termes inutiles.
Partie III
III.A.2 Définir une fonction auxiliaire norme(vecteur) pour simplifier 
l'implémentation.
III.B.2 Utiliser la méthode de Verlet pour chaque coordonnée en position de
chaque corps après avoir fait apparaître l'équation différentielle par
application de la relation fondamentale de la dynamique. Attention,
la fonction f dépend de la position de tous les corps et pas seulement
de la coordonnée considérée.
III.B.3 Il reste les vitesses à faire évoluer. Utiliser à nouveau la méthode de
Verlet sur chaque composante de chaque vitesse à l'aide des positions
présentes et à venir. Noter qu'il n'est pas nécessaire de calculer les 
positions suivantes pour chaque étape de la boucle sur j. Un seul calcul
en dehors de la boucle est suffisant.
III.B.5.a Il est possible de trouver une complexité cubique dans le cas où vous
n'avez pas tenu compte de l'indication précédente.
Partie IV
IV.B.1 Le mot-clé DISTINCT utilisé en conjonction avec COUNT permet d'éviter
les doublons.
IV.B.2 Pour un corps donné, la date du dernier état antérieur à tmin() est le
MAX de toutes les dates des états antérieurs à tmin().
IV.B.3 Il y a des informations à prendre sur trois tables donc deux jointures à
effectuer. La distance attendue pour l'ordonnancement est euclidienne.

I. Quelques fonctions utilitaires
I.A.1 Le + appliqué sur deux listes a pour action de les concaténer l'une à 
l'autre
en créant une troisième liste. Il ne faut donc pas confondre avec l'addition 
terme à
terme comme on peut l'imaginer lors de la sommation de deux vecteurs.
>>> [1,2,3] + [4,5,6]
[1, 2, 3, 4, 5, 6]
L'idée de cette partie est de montrer que les listes Python ne se comportent 
pas naturellement comme des vecteurs mathématiques, c'est-à-dire
que la « somme » de deux listes ne donne pas une somme composante par
composante des deux listes (ici on attendrait [5, 7, 9]) mais les concatène.
Il existe bien sûr des objets Python qui permettent de faire exactement cela,
ce sont les numpy.array qui se comportent « comme attendu » vis-à-vis de
l'addition :
>>> import numpy
>>> a = numpy.array([1,2,3])
>>> b = numpy.array([4,5,6])
>>> a+b
array([5, 7, 9])
Attention, il ne faut jamais utiliser la concaténation pour construire
une liste élément par élément car celle-ci, en Python, renvoie une copie des
deux listes. Par conséquent, la construction suivante d'une liste contenant les
n premiers entiers pairs est de complexité quadratique en n.
L= []
for i in range(n):
L= L + [2*i] # Ne JAMAIS faire cela, préférer L.append(2*i)
En effet, chaque concaténation est linéaire en i, le nombre d'éléments de la
liste L à l'étape i, de sorte que le nombre total d'opérations est de l'ordre de
N
P
N2
i
. Alors certes, cela ne sera pas trop handicapant quand on fabrique
2
i=1
une liste d'une dizaine d'éléments, mais déjà pour mille, cela se sentira et ce
sera encore bien pire pour un million !
I.A.2 Pour les entiers naturels, n × x vaut x + · · · + x où x apparaît n fois. 
Suivant
la même sémantique, la multiplication d'un entier avec une liste revient à 
concaténer
la liste avec elle-même autant de fois que demandé.
>>> 2*[1,2,3]
[1, 2, 3, 1, 2, 3]
Le résultat « naturel » attendu (soit [2, 4, 6]) serait donné par l'usage
d'un tableau Numpy (essayez 2*numpy.array([1,2,3])).
Ni la concaténation de deux listes, ni la multiplication d'une liste par
un entier ne sont à proprement parler au programme d'informatique pour
tous, mais il est probable que vous croisiez cette syntaxe pour définir une
liste initialisée à zéro sous la forme L = [0]*n.

Attention, il ne faut pas utiliser cette construction pour initialiser une
matrice de zéros car Python ne fait pas une « copie profonde » des objets
concernés. Observez plutôt :
>>> a = [[0]*3]*2
# Création de la "matrice"
>>> a[0][1] = 1
# Modification de la première ligne
>>> a
# Hein ?!?
[[0, 1, 0], [0, 1, 0]]
I.B Présentons trois versions possibles, l'une en créant une liste remplie de 
zéros,
l'autre en itérant sur les éléments et en construisant la liste au fur et à 
mesure par
ajouts successifs, la dernière en utilisant la Pythonnerie de construction de 
liste en
compréhension.
def smul(nombre,liste):
""" Multiplication terme à terme d'une liste par un nombre."""
L = [0]*len(liste)
# Initialisation à une liste de 0
for i in range(len(liste)): # Autant de fois que d'éléments
L[i] = nombre * liste[i] # On remplit avec la valeur idoine
return L
# On n'oublie pas de renvoyer L
def smul(nombre,liste):
L = []
for element in liste:
L.append(nombre*element)
return L

#
#
#
#

Initialisation à une liste vide
On itère sur les éléments
On rajoute la valeur idoine
On n'oublie pas de renvoyer L

def smul(nombre,liste):
return [nombre*element for element in liste] # One-liner !
Bien sûr, le jour du concours, une seule version est nécessaire (et suffisante 
!),
mais il est intéressant de comparer les diverses manières permettant d'arriver
au résultat. La version la plus proche de ce que tout le monde doit pouvoir
faire au vu du programme officiel est la seconde. Néanmoins, les correcteurs
comprendront les différents dialectes. Le rapport de concours précise même
que « De nombreux candidats résolvent cette partie à l'aide de liste en 
compréhension, qui produisent du code concis et lisible. »
I.C.1 L'addition terme à terme sur les listes se définit par
def vsom(L1,L2):
""" Fait l'addition vectorielle L1+L2 de deux listes.
Les deux listes doivent avoir la même taille. """
L = [0] * len(L1)
# Inialisation à une liste de 0
for i in range(len(L1)): # On regarde toutes les positions
L[i] = L1[i] + L2[i] # Addition à la position i
return L
# Renvoi du résultat
À noter qu'ici on ne peut pas itérer sur les éléments car on a besoin de ceux de
chaque liste, ce qui impose de passer par les indices des positions, communes
aux deux listes.
I.C.2 On définit de même la différence.